我們一起聊聊 Aho-Corasick 字符串匹配算法的實現
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
/**
* @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);第一次搜索輸出：
Array
(
[0] => Array
(
[0] => 0
[1] => 開源技術小棧
)
[1] => Array
(
[0] => 39
[1] => Tinywan
)
[2] => Array
(
[0] => 76
[1] => 程序猿
)
)第二次搜索輸出：
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是要搜索的字符串列表，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。
