## Aho-Corasick算法 AhoCorasick是Aho-Corasick字符串搜索算法的PHP实现，这是一种有效的方法，可以在文本中搜索多个搜索关键字。 > **维基百科：** Aho-Corasick算法（英语：Aho-Corasick algorithm）是由Alfred V. Aho和Margaret J. Corasick于1975年发明的字符串搜索算法。它是一种字典匹配算法，在输入文本中定位有限字符串集（“字典”）的元素。它同时匹配所有字符串。该算法的复杂度与字符串的长度加上搜索文本的长度加上输出匹配的数量成线性关系。请注意，因为所有匹配都被找到，所以如果每个子串都匹配，则可以有二次方个匹配（例如，字典= a，aa，并且输入字符串是）。  非正式地，该算法构造了一个有限状态机，类似于一个trie，在各个内部节点之间有额外的链接。这些额外的内部链接允许在失败的字符串匹配（例如，在不包含cart但包含art的trie中搜索cart，因此将在前缀为car的节点处失败）到共享公共后缀的trie的其他分支（例如，在前一种情况下，属性的分支可能是最好的横向过渡）。这允许自动机在字符串匹配之间转换，而不需要回溯。 当预先知道字符串字典（例如计算机病毒数据库）时，自动机的构造可以离线执行一次，编译后的自动机存储起来供以后使用。在这种情况下，它的运行时间与输入的长度加上匹配条目的数量成线性关系。 ## 特征 该算法的工作原理是从搜索关键字集合中构造一个有限状态机。构造有限状态机所花费的时间与搜索关键字的长度之和成比例。一旦构造完成，机器就可以在一次遍历中定位任何文本中所有搜索关键字的所有位置，对每个输入字符进行一次状态转换。 ## 安装 ``` composer require wikimedia/aho-corasick ``` ## 使用 ```php <?php /** * @desc AhoCorasick 阿霍·科拉西克 * @author Tinywan(ShaoBo Wan) * @date 2024/6/25 20:12 */ declare(strict_types=1); use AhoCorasick\MultiStringMatcher; require_once __DIR__ . '/../vendor/autoload.php'; $keywords = new MultiStringMatcher(['Tinywan', 'ShaoBoWan', '阿克苏', '开源技术小栈', '程序猿', 'Docker']); $res1 = $keywords->searchIn('开源技术小栈公众号的作者是Tinywan，他是一个热爱开源的程序猿，同时也是一个热爱生活的人。'); print_r($res1); $res2 = $keywords->searchIn('Docker 是一个开源的应用容器引擎。开源技术小栈dnmp'); print_r($res2); ``` 第一次搜索输出 ```php Array ( [0] => Array ( [0] => 0 [1] => 开源技术小栈 ) [1] => Array ( [0] => 39 [1] => Tinywan ) [2] => Array ( [0] => 76 [1] => 程序猿 ) ) ``` 第二次搜索输出 ```php Array ( [0] => Array ( [0] => 0 [1] => Docker ) [1] => Array ( [0] => 46 [1] => 开源技术小栈 ) ) ``` ## Unix命令fgrep > Aho-Corasick字符串匹配算法构成了原始Unix命令fgrep的基础。 Linux `fgrep` 命令是一个在文件中搜索固定字符串的过滤器。这个命令在你需要搜索包含大量正则表达式元字符（如“^”、“$”等）的字符串时非常有用。 基本语法如下 ``` fgrep [options] [ -e pattern_list] [pattern] [file] ``` 这里`options`是命令选项，`-e pattern_list`是要搜索的[字符串列表](https://so.csdn.net/so/search?q=%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%88%97%E8%A1%A8&spm=1001.2101.3001.7020)，`pattern`是要搜索的字符串，`file`是要搜索的文件。如果没有指定文件，`fgrep`命令将从标准输入读取数据。 > 使用`-h`选项可以显示匹配的行 ``` fgrep -h "tinywan" composer.json ``` 输出 ``` "tinywan/exception-handler": "^1.5", "tinywan/jwt": "^1.9", "tinywan/validate": "^0.0.6", "tinywan/util": "^1.1", ``` 这表示在文件`composer.json`中，这行包含字符串`tinywan`。