Aho-Corasick算法

AhoCorasick是Aho-Corasick字符串搜索算法的PHP實(shí)現(xiàn)，這是一種有效的方法，可以在文本中搜索多個(gè)搜索關(guān)鍵字。

維基百科： Aho-Corasick算法（英語：Aho-Corasick algorithm）是由Alfred V. Aho和Margaret J. Corasick于1975年發(fā)明的字符串搜索算法。它是一種字典匹配算法，在輸入文本中定位有限字符串集（“字典”）的元素。它同時(shí)匹配所有字符串。該算法的復(fù)雜度與字符串的長(zhǎng)度加上搜索文本的長(zhǎng)度加上輸出匹配的數(shù)量成線性關(guān)系。請(qǐng)注意，因?yàn)樗衅ヅ涠急徽业?，所以如果每個(gè)子串都匹配，則可以有二次方個(gè)匹配（例如，字典= a，aa，并且輸入字符串是）。

圖片

非正式地，該算法構(gòu)造了一個(gè)有限狀態(tài)機(jī)，類似于一個(gè)trie，在各個(gè)內(nèi)部節(jié)點(diǎn)之間有額外的鏈接。這些額外的內(nèi)部鏈接允許在失敗的字符串匹配（例如，在不包含cart但包含art的trie中搜索cart，因此將在前綴為car的節(jié)點(diǎn)處失?。┑焦蚕砉埠缶Y的trie的其他分支（例如，在前一種情況下，屬性的分支可能是最好的橫向過渡）。這允許自動(dòng)機(jī)在字符串匹配之間轉(zhuǎn)換，而不需要回溯。

當(dāng)預(yù)先知道字符串字典（例如計(jì)算機(jī)病毒數(shù)據(jù)庫(kù)）時(shí)，自動(dòng)機(jī)的構(gòu)造可以離線執(zhí)行一次，編譯后的自動(dòng)機(jī)存儲(chǔ)起來供以后使用。在這種情況下，它的運(yùn)行時(shí)間與輸入的長(zhǎng)度加上匹配條目的數(shù)量成線性關(guān)系。

特征

該算法的工作原理是從搜索關(guān)鍵字集合中構(gòu)造一個(gè)有限狀態(tài)機(jī)。構(gòu)造有限狀態(tài)機(jī)所花費(fèi)的時(shí)間與搜索關(guān)鍵字的長(zhǎng)度之和成比例。一旦構(gòu)造完成，機(jī)器就可以在一次遍歷中定位任何文本中所有搜索關(guān)鍵字的所有位置，對(duì)每個(gè)輸入字符進(jìn)行一次狀態(tài)轉(zhuǎn)換。

安裝

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', '阿克蘇', '開源技術(shù)小棧', '程序猿', 'Docker']);

$res1 = $keywords->searchIn('開源技術(shù)小棧公眾號(hào)的作者是Tinywan，他是一個(gè)熱愛開源的程序猿，同時(shí)也是一個(gè)熱愛生活的人。');
print_r($res1);

$res2 = $keywords->searchIn('Docker 是一個(gè)開源的應(yīng)用容器引擎。開源技術(shù)小棧dnmp');
print_r($res2);

第一次搜索輸出：

Array
(
    [0] => Array
        (
            [0] => 0
            [1] => 開源技術(shù)小棧
        )

    [1] => Array
        (
            [0] => 39
            [1] => Tinywan
        )

    [2] => Array
        (
            [0] => 76
            [1] => 程序猿
        )

)

第二次搜索輸出：

Array
(
    [0] => Array
        (
            [0] => 0
            [1] => Docker
        )

    [1] => Array
        (
            [0] => 46
            [1] => 開源技術(shù)小棧
        )

)

Unix命令fgrep

Aho-Corasick字符串匹配算法構(gòu)成了原始Unix命令fgrep的基礎(chǔ)。

Linux fgrep 命令是一個(gè)在文件中搜索固定字符串的過濾器。這個(gè)命令在你需要搜索包含大量正則表達(dá)式元字符（如“^”、“$”等）的字符串時(shí)非常有用。

基本語法如下

fgrep [options] [ -e pattern_list] [pattern] [file]

這里options是命令選項(xiàng)，-e pattern_list是要搜索的字符串列表，pattern是要搜索的字符串，file是要搜索的文件。如果沒有指定文件，fgrep命令將從標(biāo)準(zhǔn)輸入讀取數(shù)據(jù)。

使用-h選項(xiàng)可以顯示匹配的行

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。