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);
useAhoCorasick\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
。
