現(xiàn)O(n)多模式字符串匹配的核心原理)
Aho-Corasick算法從零講起ahoCorasick4cj實(shí)現(xiàn)O(n)多模式字符串匹配的核心原理【免費(fèi)下載鏈接】ahocorasick4cj一個(gè)ahoCorasick字符串匹配算法庫(kù)項(xiàng)目地址: https://gitcode.com/Cangjie-TPC/ahocorasick4cjahoCorasick4cj是一個(gè)基于 Aho-Corasick 算法的開源多模式字符串匹配庫(kù)Cangjie 語言實(shí)現(xiàn)。它把多個(gè)關(guān)鍵詞構(gòu)建成一棵 Trie 樹配合失敗指針failure link只需掃描一遍文本就能找出所有匹配位置匹配復(fù)雜度 O(n)。本文用通俗的方式從零講透它的核心原理。為什么需要 Aho-Corasick 算法想象一個(gè)場(chǎng)景你要在一篇文章里同時(shí)找出he、she、his、hers這 4 個(gè)詞出現(xiàn)在哪里。最樸素的做法是暴力法對(duì)每個(gè)關(guān)鍵詞從頭到尾掃一遍文本。假設(shè)文本長(zhǎng)n、關(guān)鍵詞總長(zhǎng)m最壞情況下要干n × m次比較——關(guān)鍵詞越多、文本越長(zhǎng)慢得越明顯。Aho-Corasick 算法的天才之處在于把多個(gè)關(guān)鍵詞合并成一棵狀態(tài)機(jī)文本只需從左到右走一遍每讀一個(gè)字符就切換一次狀態(tài)一次遍歷同時(shí)完成所有關(guān)鍵詞的匹配。這就是它做到 O(n) 的秘密。一圖看懂 ahoCorasick4cj 的整體流程下面是該庫(kù)的完整工作流程先逐個(gè)把關(guān)鍵詞加入 Trie 樹并構(gòu)建 success 表再檢查并創(chuàng)建 failure 表最后輸入文本、輸出所有被命中的模式。這張流程圖對(duì)應(yīng)的源碼入口是 src/payload_trie.cj構(gòu)建 success 表addKeyword 把關(guān)鍵詞逐字符掛到狀態(tài)樹上構(gòu)建 failure 表constructFailureStates 用廣度優(yōu)先遍歷為每個(gè)節(jié)點(diǎn)計(jì)算失敗指針輸出匹配結(jié)果parseText 單次掃描文本并輸出Emit起始位置、結(jié)束位置、關(guān)鍵詞。核心原理一用 Trie 樹把所有關(guān)鍵詞拼成一棵樹Trie字典樹的規(guī)矩很簡(jiǎn)單樹根到葉子的一條路徑就代表一個(gè)關(guān)鍵詞兩個(gè)關(guān)鍵詞有公共前綴就共享節(jié)點(diǎn)。比如關(guān)鍵詞he、she、hish、e這段路徑被he獨(dú)占s→h是she的入口而his和he共享h之后的分支起點(diǎn)。在源碼中每個(gè)節(jié)點(diǎn)就是一個(gè)狀態(tài)類 src/state.cj成員含義successsuccess 表論文里的 goto 結(jié)構(gòu)當(dāng)前狀態(tài)下讀到某字符該跳到哪個(gè)狀態(tài)failure失敗指針匹配不上時(shí)退而不敗地跳到哪個(gè)狀態(tài)emits到達(dá)該狀態(tài)時(shí)應(yīng)該輸出的關(guān)鍵詞列表構(gòu)建過程對(duì)應(yīng) addState沿關(guān)鍵詞逐字符走遇到?jīng)]有的子狀態(tài)就新建一個(gè)最后在該節(jié)點(diǎn)addEmit登記這個(gè)關(guān)鍵詞。 關(guān)鍵詞只建一次之后可以反復(fù)匹配任意長(zhǎng)度的文本——這是它適合關(guān)鍵詞庫(kù)場(chǎng)景的關(guān)鍵。核心原理二failure 指針讓匹配退而不斷只靠 success 表有一個(gè)致命問題匹配中途失配時(shí)樸素 Trie 只能退回樹根重來這會(huì)破壞 O(n) 的復(fù)雜度。Aho-Corasick 的解法是給每個(gè)節(jié)點(diǎn)預(yù)計(jì)算一個(gè)failure 指針指向當(dāng)前狀態(tài)所代表的字符串的、最長(zhǎng)的真后綴對(duì)應(yīng)的節(jié)點(diǎn)。拿經(jīng)典例子說明當(dāng)前已匹配到she的s→h狀態(tài)下一個(gè)字符卻不是e比如是s。此時(shí)不需要回退到根failure 指針會(huì)把你送到h狀態(tài)因?yàn)閟h的最長(zhǎng)真后綴h恰好是另一個(gè)關(guān)鍵詞的開頭匹配繼續(xù)。源碼中這一步在 constructFailureStates 里完成思路是教科書式的 BFS深度為 1 的節(jié)點(diǎn)failure 統(tǒng)一指向根節(jié)點(diǎn)第 126-129 行更深的節(jié)點(diǎn)沿著父節(jié)點(diǎn)的 failure 鏈向上探測(cè)找到第一個(gè)能沿當(dāng)前字符轉(zhuǎn)移的狀態(tài)作為自己的 failure第 131-144 行順帶把 failure 節(jié)點(diǎn)上的 emits合并過來第 143 行targetState.addEmit(newFailureState.emit())——這保證了像he和she這種嵌套匹配不會(huì)漏報(bào)。構(gòu)建失敗指針是一次性的預(yù)處理開銷與文本長(zhǎng)度無關(guān)。核心原理三單次掃描文本實(shí)現(xiàn) O(n) 匹配有了 success 表和 failure 表匹配階段的 parseText 就極其簡(jiǎn)單從根狀態(tài)出發(fā)for 每個(gè)字符 c 當(dāng)前狀態(tài) 沿 success 表轉(zhuǎn)移若走不通就沿 failure 鏈回退再轉(zhuǎn)移 輸出當(dāng)前狀態(tài)登記的所有關(guān)鍵詞位置 當(dāng)前下標(biāo) - 詞長(zhǎng) 1 起關(guān)鍵函數(shù)是 getState當(dāng)nextState為 None 時(shí)沿著failures()鏈逐級(jí)回退直到找到能接受該字符的狀態(tài)。為什么總復(fù)雜度是 O(n)因?yàn)槲谋镜拿總€(gè)字符只做常數(shù)次狀態(tài)轉(zhuǎn)移回退走的 failure 鏈總長(zhǎng)度被前進(jìn)抵消掉——這是 Aho-Corasick 算法的經(jīng)典結(jié)論。匹配結(jié)果封裝為 Emit包含start、end、keyword三個(gè)字段打印出來形如2:3he即第 2 位到第 3 位匹配到了 he。如果配置了ignoreOverlaps()還會(huì)經(jīng)過 src/interval_tree.cj 的區(qū)間樹剔除重疊區(qū)間避免相鄰匹配互相干擾。三大開箱即用的匹配模式ahoCorasick4cj 對(duì)外提供三種使用姿勢(shì)對(duì)應(yīng)它的三個(gè)核心特性 模式一多字符搜索parseText構(gòu)建 Trie 后調(diào)用parseText(text)返回所有匹配的Emit列表src/trie.cj。模式二關(guān)鍵詞庫(kù)模式tokenizetokenize(text)把文本切成一系列 Token命中關(guān)鍵詞的片段是MatchToken普通片段是FragmentToken見 src/match_token.cj 和 src/fragment_token.cj。適合做敏感詞高亮、文本分詞替換等邊遍歷邊處理的場(chǎng)景配合firstMatch還能只取第一個(gè)命中src/trie.cj#L70-L78。模式三自定義載荷輸出PayloadTriePayloadTrieWord允許給每個(gè)關(guān)鍵詞綁一份自定義數(shù)據(jù)比如詞性、權(quán)重、性別標(biāo)記等匹配命中時(shí)PayloadEmit會(huì)同時(shí)帶回這份數(shù)據(jù)src/payload_emit.cj。這是詞庫(kù)引擎、規(guī)則引擎里非常實(shí)用的設(shè)計(jì)。架構(gòu)與常用配置速覽庫(kù)的核心是一個(gè)core模塊所有公開類型都集中在 src/package.cj 所在包里統(tǒng)一導(dǎo)出源碼組織清晰。配置開關(guān)都收斂在 TrieConfig構(gòu)建時(shí)通過 TrieBuilder 的鏈?zhǔn)椒椒ㄩ_啟構(gòu)建器方法作用適用場(chǎng)景ignoreCase()忽略大小寫英文關(guān)鍵詞匹配ignoreOverlaps()忽略重疊匹配只要不重疊的結(jié)果onlyWholeWords()只匹配完整單詞避免單詞內(nèi)部的誤匹配stopOnHit()命中第一個(gè)即停止只做有沒有的判斷性能最優(yōu)典型用法一行搞定Trie.builder().addKeyword(she).addKeyword(he).build()然后parseText或tokenize?？偨Y(jié)Aho-Corasick 的三個(gè)關(guān)鍵思想Trie 合并關(guān)鍵詞公共前綴共享路徑一次建庫(kù)反復(fù)使用failure 指針失配時(shí)不退回根而是跳到最長(zhǎng)真后綴狀態(tài)匹配永不斷線單次掃描文本每個(gè)字符只轉(zhuǎn)移常數(shù)次狀態(tài)總復(fù)雜度 O(n)與關(guān)鍵詞數(shù)量基本無關(guān)。ahoCorasick4cj 用簡(jiǎn)潔的 Cangjie 代碼核心約 30 個(gè).cj文件完整實(shí)現(xiàn)了這套機(jī)制并貼心地提供了多字符搜索、關(guān)鍵詞庫(kù)、自定義載荷三種模式是學(xué)習(xí) Aho-Corasick 算法原理與工程落地的好素材。想動(dòng)手驗(yàn)證可以參考 test/ 目錄下的 DOC、FUZZ、HLT、LLT 多層測(cè)試用例尤其推薦從 test/LLT/char_search_test01.cj 開始讀起。【免費(fèi)下載鏈接】ahocorasick4cj一個(gè)ahoCorasick字符串匹配算法庫(kù)項(xiàng)目地址: https://gitcode.com/Cangjie-TPC/ahocorasick4cj創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 Aho-Corasick算法從零講起：ahoCorasick4cj實(shí)現(xiàn)O(n)多模式字符串匹配的核心原理
Aho-Corasick算法從零講起ahoCorasick4cj實(shí)現(xiàn)O(n)多模式字符串匹配的核心原理【免費(fèi)下載鏈接】ahocorasick4cj一個(gè)ahoCorasick字符串匹配算法庫(kù)項(xiàng)目地址: https://gitcode.com/Cangjie-TPC/ahocorasick4cjahoCorasick4cj是一個(gè)基于 Aho-Corasick 算法的開源多模式字符串匹配庫(kù)Cangjie 語言實(shí)現(xiàn)。它把多個(gè)關(guān)鍵詞構(gòu)建成一棵 Trie 樹配合失敗指針failure link只需掃描一遍文本就能找出所有匹配位置匹配復(fù)雜度 O(n)。本文用通俗的方式從零講透它的核心原理。為什么需要 Aho-Corasick 算法想象一個(gè)場(chǎng)景你要在一篇文章里同時(shí)找出he、she、his、hers這 4 個(gè)詞出現(xiàn)在哪里。最樸素的做法是暴力法對(duì)每個(gè)關(guān)鍵詞從頭到尾掃一遍文本。假設(shè)文本長(zhǎng)n、關(guān)鍵詞總長(zhǎng)m最壞情況下要干n × m次比較——關(guān)鍵詞越多、文本越長(zhǎng)慢得越明顯。Aho-Corasick 算法的天才之處在于把多個(gè)關(guān)鍵詞合并成一棵狀態(tài)機(jī)文本只需從左到右走一遍每讀一個(gè)字符就切換一次狀態(tài)一次遍歷同時(shí)完成所有關(guān)鍵詞的匹配。這就是它做到 O(n) 的秘密。一圖看懂 ahoCorasick4cj 的整體流程下面是該庫(kù)的完整工作流程先逐個(gè)把關(guān)鍵詞加入 Trie 樹并構(gòu)建 success 表再檢查并創(chuàng)建 failure 表最后輸入文本、輸出所有被命中的模式。這張流程圖對(duì)應(yīng)的源碼入口是 src/payload_trie.cj構(gòu)建 success 表addKeyword 把關(guān)鍵詞逐字符掛到狀態(tài)樹上構(gòu)建 failure 表constructFailureStates 用廣度優(yōu)先遍歷為每個(gè)節(jié)點(diǎn)計(jì)算失敗指針輸出匹配結(jié)果parseText 單次掃描文本并輸出Emit起始位置、結(jié)束位置、關(guān)鍵詞。核心原理一用 Trie 樹把所有關(guān)鍵詞拼成一棵樹Trie字典樹的規(guī)矩很簡(jiǎn)單樹根到葉子的一條路徑就代表一個(gè)關(guān)鍵詞兩個(gè)關(guān)鍵詞有公共前綴就共享節(jié)點(diǎn)。比如關(guān)鍵詞he、she、hish、e這段路徑被he獨(dú)占s→h是she的入口而his和he共享h之后的分支起點(diǎn)。在源碼中每個(gè)節(jié)點(diǎn)就是一個(gè)狀態(tài)類 src/state.cj成員含義successsuccess 表論文里的 goto 結(jié)構(gòu)當(dāng)前狀態(tài)下讀到某字符該跳到哪個(gè)狀態(tài)failure失敗指針匹配不上時(shí)退而不敗地跳到哪個(gè)狀態(tài)emits到達(dá)該狀態(tài)時(shí)應(yīng)該輸出的關(guān)鍵詞列表構(gòu)建過程對(duì)應(yīng) addState沿關(guān)鍵詞逐字符走遇到?jīng)]有的子狀態(tài)就新建一個(gè)最后在該節(jié)點(diǎn)addEmit登記這個(gè)關(guān)鍵詞。 關(guān)鍵詞只建一次之后可以反復(fù)匹配任意長(zhǎng)度的文本——這是它適合關(guān)鍵詞庫(kù)場(chǎng)景的關(guān)鍵。核心原理二failure 指針讓匹配退而不斷只靠 success 表有一個(gè)致命問題匹配中途失配時(shí)樸素 Trie 只能退回樹根重來這會(huì)破壞 O(n) 的復(fù)雜度。Aho-Corasick 的解法是給每個(gè)節(jié)點(diǎn)預(yù)計(jì)算一個(gè)failure 指針指向當(dāng)前狀態(tài)所代表的字符串的、最長(zhǎng)的真后綴對(duì)應(yīng)的節(jié)點(diǎn)。拿經(jīng)典例子說明當(dāng)前已匹配到she的s→h狀態(tài)下一個(gè)字符卻不是e比如是s。此時(shí)不需要回退到根failure 指針會(huì)把你送到h狀態(tài)因?yàn)閟h的最長(zhǎng)真后綴h恰好是另一個(gè)關(guān)鍵詞的開頭匹配繼續(xù)。源碼中這一步在 constructFailureStates 里完成思路是教科書式的 BFS深度為 1 的節(jié)點(diǎn)failure 統(tǒng)一指向根節(jié)點(diǎn)第 126-129 行更深的節(jié)點(diǎn)沿著父節(jié)點(diǎn)的 failure 鏈向上探測(cè)找到第一個(gè)能沿當(dāng)前字符轉(zhuǎn)移的狀態(tài)作為自己的 failure第 131-144 行順帶把 failure 節(jié)點(diǎn)上的 emits合并過來第 143 行targetState.addEmit(newFailureState.emit())——這保證了像he和she這種嵌套匹配不會(huì)漏報(bào)。構(gòu)建失敗指針是一次性的預(yù)處理開銷與文本長(zhǎng)度無關(guān)。核心原理三單次掃描文本實(shí)現(xiàn) O(n) 匹配有了 success 表和 failure 表匹配階段的 parseText 就極其簡(jiǎn)單從根狀態(tài)出發(fā)for 每個(gè)字符 c 當(dāng)前狀態(tài) 沿 success 表轉(zhuǎn)移若走不通就沿 failure 鏈回退再轉(zhuǎn)移 輸出當(dāng)前狀態(tài)登記的所有關(guān)鍵詞位置 當(dāng)前下標(biāo) - 詞長(zhǎng) 1 起關(guān)鍵函數(shù)是 getState當(dāng)nextState為 None 時(shí)沿著failures()鏈逐級(jí)回退直到找到能接受該字符的狀態(tài)。為什么總復(fù)雜度是 O(n)因?yàn)槲谋镜拿總€(gè)字符只做常數(shù)次狀態(tài)轉(zhuǎn)移回退走的 failure 鏈總長(zhǎng)度被前進(jìn)抵消掉——這是 Aho-Corasick 算法的經(jīng)典結(jié)論。匹配結(jié)果封裝為 Emit包含start、end、keyword三個(gè)字段打印出來形如2:3he即第 2 位到第 3 位匹配到了 he。如果配置了ignoreOverlaps()還會(huì)經(jīng)過 src/interval_tree.cj 的區(qū)間樹剔除重疊區(qū)間避免相鄰匹配互相干擾。三大開箱即用的匹配模式ahoCorasick4cj 對(duì)外提供三種使用姿勢(shì)對(duì)應(yīng)它的三個(gè)核心特性 模式一多字符搜索parseText構(gòu)建 Trie 后調(diào)用parseText(text)返回所有匹配的Emit列表src/trie.cj。模式二關(guān)鍵詞庫(kù)模式tokenizetokenize(text)把文本切成一系列 Token命中關(guān)鍵詞的片段是MatchToken普通片段是FragmentToken見 src/match_token.cj 和 src/fragment_token.cj。適合做敏感詞高亮、文本分詞替換等邊遍歷邊處理的場(chǎng)景配合firstMatch還能只取第一個(gè)命中src/trie.cj#L70-L78。模式三自定義載荷輸出PayloadTriePayloadTrieWord允許給每個(gè)關(guān)鍵詞綁一份自定義數(shù)據(jù)比如詞性、權(quán)重、性別標(biāo)記等匹配命中時(shí)PayloadEmit會(huì)同時(shí)帶回這份數(shù)據(jù)src/payload_emit.cj。這是詞庫(kù)引擎、規(guī)則引擎里非常實(shí)用的設(shè)計(jì)。架構(gòu)與常用配置速覽庫(kù)的核心是一個(gè)core模塊所有公開類型都集中在 src/package.cj 所在包里統(tǒng)一導(dǎo)出源碼組織清晰。配置開關(guān)都收斂在 TrieConfig構(gòu)建時(shí)通過 TrieBuilder 的鏈?zhǔn)椒椒ㄩ_啟構(gòu)建器方法作用適用場(chǎng)景ignoreCase()忽略大小寫英文關(guān)鍵詞匹配ignoreOverlaps()忽略重疊匹配只要不重疊的結(jié)果onlyWholeWords()只匹配完整單詞避免單詞內(nèi)部的誤匹配stopOnHit()命中第一個(gè)即停止只做有沒有的判斷性能最優(yōu)典型用法一行搞定Trie.builder().addKeyword(she).addKeyword(he).build()然后parseText或tokenize?？偨Y(jié)Aho-Corasick 的三個(gè)關(guān)鍵思想Trie 合并關(guān)鍵詞公共前綴共享路徑一次建庫(kù)反復(fù)使用failure 指針失配時(shí)不退回根而是跳到最長(zhǎng)真后綴狀態(tài)匹配永不斷線單次掃描文本每個(gè)字符只轉(zhuǎn)移常數(shù)次狀態(tài)總復(fù)雜度 O(n)與關(guān)鍵詞數(shù)量基本無關(guān)。ahoCorasick4cj 用簡(jiǎn)潔的 Cangjie 代碼核心約 30 個(gè).cj文件完整實(shí)現(xiàn)了這套機(jī)制并貼心地提供了多字符搜索、關(guān)鍵詞庫(kù)、自定義載荷三種模式是學(xué)習(xí) Aho-Corasick 算法原理與工程落地的好素材。想動(dòng)手驗(yàn)證可以參考 test/ 目錄下的 DOC、FUZZ、HLT、LLT 多層測(cè)試用例尤其推薦從 test/LLT/char_search_test01.cj 開始讀起。【免費(fèi)下載鏈接】ahocorasick4cj一個(gè)ahoCorasick字符串匹配算法庫(kù)項(xiàng)目地址: https://gitcode.com/Cangjie-TPC/ahocorasick4cj創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考