探索AC自動(dòng)機(jī)：多關(guān)鍵詞搜索的原理與應(yīng)用案例

引言

目前，大多數(shù)自由文本搜索技術(shù)采用類似于Lucene的策略，通過解析搜索文本為各個(gè)組成部分來(lái)定位關(guān)鍵詞。這種方法在處理少量關(guān)鍵詞時(shí)表現(xiàn)良好。但當(dāng)搜索的關(guān)鍵詞數(shù)量達(dá)到10萬(wàn)個(gè)或更多時(shí)，這種方法的效率會(huì)顯著下降，尤其是在需要與詞典進(jìn)行詳盡對(duì)比的場(chǎng)景中。本文將介紹的Aho-Corasick（AC）自動(dòng)機(jī)作為多模式匹配中的經(jīng)典算法，不僅能夠處理大規(guī)模文本數(shù)據(jù)，還能確保搜索過程的實(shí)時(shí)性和準(zhǔn)確性。

AC自動(dòng)機(jī)：文本搜索的革命性工具

AC自動(dòng)機(jī)可以被形象地比喻為一個(gè)超級(jí)找詞機(jī)器。想象你手頭有一本內(nèi)容繁多的書籍和一份包含多個(gè)詞語(yǔ)的列表，你的任務(wù)是快速找出所有這些詞語(yǔ)在書中出現(xiàn)的位置。如果采用傳統(tǒng)方法，即逐個(gè)詞進(jìn)行查找，工作量將會(huì)非常巨大。而AC自動(dòng)機(jī)通過構(gòu)建一種特殊的樹狀結(jié)構(gòu)——前綴樹或Trie，來(lái)極大地提升搜索效率。

AC自動(dòng)機(jī)構(gòu)建與搜索機(jī)制

構(gòu)建前綴樹（Trie）

AC自動(dòng)機(jī)首先會(huì)根據(jù)所有關(guān)鍵詞構(gòu)建一個(gè)前綴樹。這種樹狀結(jié)構(gòu)的每個(gè)節(jié)點(diǎn)代表一個(gè)字母，并且每個(gè)字母都指向下一個(gè)可能的字母，從而形成一個(gè)連續(xù)的路徑，表示一個(gè)或多個(gè)關(guān)鍵詞的前綴

圖片來(lái)源網(wǎng)絡(luò)

失配指針（Fail指針）

在搜索過程中，如果當(dāng)前路徑上無(wú)法找到匹配的關(guān)鍵詞，AC自動(dòng)機(jī)會(huì)利用失配指針進(jìn)行快速回溯。這些指針預(yù)先設(shè)置在樹的每個(gè)節(jié)點(diǎn)上，指向其他可能的匹配路徑，從而避免了從頭開始搜索的低效性

圖片來(lái)源網(wǎng)絡(luò)

實(shí)時(shí)搜索與高效報(bào)告

AC自動(dòng)機(jī)在讀取文本的同時(shí)，能夠快速地遍歷前綴樹結(jié)構(gòu)。一旦發(fā)現(xiàn)關(guān)鍵詞出現(xiàn)在文本中，它能夠立即報(bào)告這個(gè)詞及其出現(xiàn)的位置。這種能力使得AC自動(dòng)機(jī)能夠一次性高效完成大量關(guān)鍵詞的搜索任務(wù)

圖片來(lái)源網(wǎng)絡(luò)

算法核心組件與復(fù)雜度

核心組件：

?goto（轉(zhuǎn)跳）：每個(gè)遇到的字符都會(huì)被提交給goto結(jié)構(gòu)中的狀態(tài)對(duì)象，以確定新的當(dāng)前狀態(tài)

?fail（失敗轉(zhuǎn)移）：如果沒有找到匹配狀態(tài)，算法會(huì)觸發(fā)fail并回溯至深度更淺的狀態(tài)，從那里繼續(xù)搜索

?output（輸出）：每當(dāng)達(dá)到與整個(gè)關(guān)鍵詞相匹配的狀態(tài)時(shí)，該狀態(tài)會(huì)被發(fā)送到輸出集合中，完成掃描后即可讀取這些匹配項(xiàng)

時(shí)間復(fù)雜度：

Aho-Corasick算法的時(shí)間復(fù)雜度為O(n)，其中n是文本的長(zhǎng)度。這意味著無(wú)論提供多少關(guān)鍵詞，搜索的性能都將呈線性下降，與關(guān)鍵詞的數(shù)量無(wú)關(guān)。

AC自動(dòng)機(jī)的應(yīng)用

AC自動(dòng)機(jī)在多種場(chǎng)景下都能發(fā)揮重要作用，包括：

?在文本中查找并鏈接或突出顯示關(guān)鍵詞，提高信息的可檢索性

?為純文本添加語(yǔ)義，使文本內(nèi)容更加豐富和有層次

?檢查文本中的語(yǔ)法錯(cuò)誤，通過與詞典的對(duì)比來(lái)識(shí)別和糾正錯(cuò)誤

應(yīng)用案例：使用Aho-Corasick算法來(lái)識(shí)別和高亮HTML文本中的關(guān)鍵詞

本Java程序?qū)⒀菔救绾问褂肁ho-Corasick自動(dòng)機(jī)庫(kù)來(lái)搜索和高亮HTML文本中的關(guān)鍵詞。程序首先構(gòu)建一個(gè)自動(dòng)狀態(tài)機(jī)，該狀態(tài)機(jī)被訓(xùn)練識(shí)別一系列中文關(guān)鍵詞。然后，程序?qū)⑻幚鞨TML文檔，查找這些關(guān)鍵詞的出現(xiàn)，并用標(biāo)簽將它們包裹起來(lái)，以實(shí)現(xiàn)加粗顯示的效果。

第一步：Maven依賴配置，引入Aho-Corasick自動(dòng)機(jī)庫(kù)

    org.ahocorasick
    ahocorasick
    0.6.3

第二步：代碼實(shí)現(xiàn)

public class HighlightKeywordsInHtml {

   public static void main(String[] args) {
        // 定義HTML內(nèi)容的字符串，包含了南京大學(xué)的介紹
        String htmlContent = createHtmlContentForNanjingUniversity();
        // 創(chuàng)建Aho-Corasick Trie的構(gòu)建器實(shí)例
        Trie trie = buildAhoCorasickTrie();
        // 使用Trie實(shí)例處理HTML文本，獲取匹配的Token集合
        Collection tokens = trie.tokenize(htmlContent);
        // 使用StringBuilder構(gòu)建最終的HTML字符串，用于輸出高亮的關(guān)鍵詞
        StringBuilder html = new StringBuilder();
        html.append("

第三步：運(yùn)行程序，符合預(yù)期

本文對(duì)Aho-Corasick（AC）自動(dòng)機(jī)算法進(jìn)行了拋磚引玉，揭示了其在處理大規(guī)模文本數(shù)據(jù)方面的卓越性能和應(yīng)用潛力。若你渴望深入挖掘AC算法的精髓，進(jìn)一步探索其高級(jí)應(yīng)用和實(shí)現(xiàn)細(xì)節(jié)，建議參考以下的參考資料進(jìn)行進(jìn)一步的學(xué)習(xí)與挖掘。

參考資料

1. http://cr.yp.to/bib/1975/aho.pdf?

2. https://github.com/robert-bor/aho-corasick

審核編輯 黃宇