背景
某天，我們的產(chǎn)品經(jīng)理突然找到我拧额，說(shuō)我們的廣告業(yè)務(wù)上線后效果不錯(cuò)，但是需要做敏感詞過(guò)濾處理玉凯，需要接入一個(gè)模糊詞詞典和一個(gè)精確詞詞典势腮。然后我拿到了這兩份詞典，兩份違禁詞加起來(lái)總量近100w條漫仆。
這個(gè)需求簡(jiǎn)單來(lái)說(shuō)就是如果用戶的查詢?cè)~中命中了違禁詞的話是不能出廣告的捎拯。如：用戶query=怎么去故宮博物院，因?yàn)槊辛斯蕦m博物院，所以不能出廣告署照。 最終我合并了這兩份詞表祸泪，并寫(xiě)了一個(gè)高效的實(shí)現(xiàn)。
今天打算就其中的模糊匹配部分單獨(dú)抽出來(lái)討論一下其實(shí)現(xiàn)方案建芙，并開(kāi)源了一個(gè)我自己用go寫(xiě)的開(kāi)箱即用的高性能匹配方案倉(cāng)庫(kù)地址没隘。
理論基礎(chǔ)
如果想要開(kāi)箱即用的實(shí)現(xiàn)，可以跳過(guò)理論拉到最下面禁荸。
對(duì)于一個(gè)web應(yīng)用來(lái)說(shuō)右蒲，這種大量的字符串，一個(gè)一個(gè)匹配肯定是不行的赶熟。 肯定是需要高性能的匹配方案瑰妄。
使用字典樹(shù)（trie樹(shù)）進(jìn)行匹配是一個(gè)方案， 但是達(dá)不到高性能映砖。
因?yàn)閷?duì)于模糊匹配來(lái)說(shuō)间坐，使用字典樹(shù)需要不斷回退。
如：我們的字典里有下面這兩個(gè)詞：
怎么去天安門(mén)
故宮博物院
query=怎么去故宮博物院邑退。
字典樹(shù)匹配過(guò)程如下：
第一次匹配：q=怎么去故宮博物院
怎->么->去->故(fail)
到 故 這個(gè)詞失敗后進(jìn)行回退竹宋，回退到第二個(gè)詞進(jìn)行匹配
第二次匹配：q=么去故宮博物院
么（fail）
回退到第三個(gè)詞
第三次匹配：q=去故宮博物院
去(fail)
回退到第四個(gè)詞
第四次匹配：q=故宮博物院
故->宮->博->物->院(success)
匹配完成。
可以看到如果對(duì)于查詢?cè)~比較多的情況下地技，不斷回退導(dǎo)致了性能下降蜈七。如果剛好又遇到跟字典中命中了大量前綴，更是一個(gè)災(zāi)難莫矗。
那如何做到高性能呢宪潮？這時(shí)需要用到Aho–Corasick算法
該算法在1975年產(chǎn)生于貝爾實(shí)驗(yàn)室，是著名的多模匹配算法趣苏。其本質(zhì)是一個(gè)自動(dòng)機(jī)狡相，下面我們稱為AC自動(dòng)機(jī)。
我們先看下其特點(diǎn)食磕。
AC自動(dòng)機(jī)：
1.高速完成多模式匹配而不用回溯尽棕，與模式串的數(shù)量和長(zhǎng)度無(wú)關(guān)，只與查詢文本長(zhǎng)度有關(guān)彬伦，時(shí)間復(fù)雜度O(n)滔悉。
2.基礎(chǔ)結(jié)構(gòu)為trie樹(shù)。
3.KMP的思想：為trie樹(shù)所有節(jié)點(diǎn)建立fail指針单绑。與KMP不同的是：AC的fail指針是指向最長(zhǎng)后綴回官。
基本構(gòu)造：
goto表：成功轉(zhuǎn)移到另一個(gè)狀態(tài)
failure表：不可成功轉(zhuǎn)移時(shí)，則使用該表轉(zhuǎn)移到下一個(gè)狀態(tài)
output表：命中的模式串
查詢：
在goto表里查找搂橙，如果不能成功轉(zhuǎn)移到下個(gè)狀態(tài)歉提，就通過(guò)failure表轉(zhuǎn)移，在每步轉(zhuǎn)移的同時(shí)，判斷output是否可輸出
構(gòu)建方法：
goto表：trie樹(shù)
output表：trie樹(shù)葉子節(jié)點(diǎn)+在fail表構(gòu)建時(shí)的可輸出節(jié)點(diǎn)
failure表：逐層構(gòu)建
? ? 1）根節(jié)點(diǎn)的fail為0苔巨，深度為1的節(jié)點(diǎn)所有的fail=0
? ? 2）深度>=2的節(jié)點(diǎn)N版扩，從其父節(jié)點(diǎn)Pn轉(zhuǎn)移到N需要接收字符C，則測(cè)試goto(fail(Pn),C)侄泽，如果成功礁芦，則fail(N)=goto(fail(Pn),C)
? ? 3）如果失敗，則測(cè)試goto(fail(fail(Pn)),C)悼尾，如此反復(fù)柿扣，肯定可以找到一個(gè)有效狀態(tài)（最終往上到根節(jié)點(diǎn)時(shí)，如果轉(zhuǎn)移失敗闺魏，則fail(N)=0）窄刘。
以經(jīng)典的ushers為例，模式串是he/ she/ his /hers舷胜。構(gòu)建的自動(dòng)機(jī)如圖：
AC自動(dòng)機(jī)的基礎(chǔ)是trie樹(shù)，trie樹(shù)的實(shí)現(xiàn)決定了AC自動(dòng)機(jī)的效率高低, 我們看下常用的兩種實(shí)現(xiàn)活翩。 Hash trie樹(shù) VS Double Array Trie樹(shù)
Hash trie
實(shí)現(xiàn)起來(lái)相對(duì)簡(jiǎn)單
理想狀態(tài)下取詞復(fù)雜度O(1)
hash空間占用量大烹骨，hash函數(shù)也有性能消耗，數(shù)據(jù)量很大的情況下很難保證O(1)
另外含有大量指針材泄，對(duì)于有g(shù)c的語(yǔ)言來(lái)說(shuō)沮焕，不利于gc
用go來(lái)定義就是：
type node struct {
? ? val? ? ? rune
? ? term? ? bool
? ? depth? ? int
? ? children map[rune]*node
}
Double Array trie
實(shí)現(xiàn)起來(lái)較復(fù)雜
取詞復(fù)雜度O(1)
完全壓縮到兩個(gè)數(shù)組里，去掉了指針拉宗，結(jié)構(gòu)比較簡(jiǎn)單峦树，兼顧了查詢效率和空間存儲(chǔ)
用go來(lái)定義就是：
type doubleArrayTrie struct {
? ? base? []int
? ? check []int
}
我們著重說(shuō)下雙數(shù)組trie樹(shù)。
Double Array Trie
核心：
Base數(shù)組：維持鏈路關(guān)系旦事，存儲(chǔ)轉(zhuǎn)義基數(shù)(即子節(jié)點(diǎn)的索引)魁巩。
Check數(shù)組：和base數(shù)組等長(zhǎng)，用來(lái)確認(rèn)轉(zhuǎn)移的正確性姐浮。存儲(chǔ)上一個(gè)狀態(tài)谷遂。
對(duì)于一個(gè)字符串s，當(dāng)前字符狀態(tài)為t卖鲤，增加一個(gè)字符c轉(zhuǎn)義到狀態(tài)tc肾扰。則：
base[t]+c = base[tc]
check[tc] = t
構(gòu)建方式：
1.依次處理每個(gè)詞的每個(gè)字來(lái)構(gòu)建 2.按每個(gè)詞的首字，然后依次處理構(gòu)建
避免沖突移動(dòng)的方法
排序蛋逾，邊構(gòu)建樹(shù)邊構(gòu)建雙數(shù)組集晚，對(duì)于一群兄弟節(jié)點(diǎn)尋找一個(gè)插入點(diǎn)，使得這些節(jié)點(diǎn)未被占用区匣。
如果進(jìn)行排序后偷拔，構(gòu)建起來(lái)就會(huì)快很多。使用第二種方式構(gòu)建會(huì)減少?zèng)_突次數(shù)及數(shù)組長(zhǎng)度，加快構(gòu)建時(shí)間条摸，且更易于構(gòu)建悦污。在構(gòu)建Double Array trie時(shí)，受到了darts-java開(kāi)源項(xiàng)目的啟發(fā)钉蒲，在此深表感謝
DFS生成樹(shù)切端。
type Node struct {
? ? Code? ? ? ? ? ? ? ? ? ? rune
? ? Left, Right, Depth, Base int
? ? Children? ? ? ? ? ? ? ? []*Node
}
Code：字符編碼
Left,Right為這個(gè)節(jié)點(diǎn)在字典中索引范圍
Depth表示深度
Base為該節(jié)點(diǎn)的轉(zhuǎn)移基數(shù)，葉子節(jié)點(diǎn)為-1
base[begin+code]=子節(jié)點(diǎn)的begin
check[begin+code]=begin
構(gòu)建過(guò)程：
? ? 1.令base[0]=1;check[0]=0顷啼，排序踏枣，對(duì)根節(jié)點(diǎn)獲取子節(jié)點(diǎn)
? ? 2.對(duì)每一群兄弟節(jié)點(diǎn)，尋找一個(gè)begin值使得數(shù)組未被占用钙蒙，則每個(gè)兄弟節(jié)點(diǎn)的check[begin+code]=begin;
? ? 3.對(duì)兄弟節(jié)點(diǎn)的每個(gè)節(jié)點(diǎn)茵瀑，如果沒(méi)有孩子，則令base為負(fù)值躬厌，否則為該節(jié)點(diǎn)的子節(jié)點(diǎn)的begin值
雙數(shù)組樹(shù)和hash樹(shù)構(gòu)建完成后马昨，進(jìn)行對(duì)比。
運(yùn)行機(jī)器：2? Intel(R) Xeon(R) CPU E5-2630 v2 @ 2.60GHz Dict：61w條(黑名單)扛施；字?jǐn)?shù)：5872778 待匹配：96330條(用戶請(qǐng)求query); 字?jǐn)?shù)：887790
可以看到鸿捧，使用dfs生成樹(shù)相比hash樹(shù)，詞典構(gòu)建時(shí)間增加到50s,但內(nèi)存使用降低40.79%疙渣，查詢效率提升16.97%匙奴。
問(wèn)題：
1.現(xiàn)在實(shí)現(xiàn)的雙數(shù)組trie樹(shù)build時(shí)間有些長(zhǎng)，能否縮短構(gòu)建時(shí)間妄荔？
2.AC自動(dòng)機(jī)的構(gòu)建是BFS泼菌，這需要我們構(gòu)建完trie樹(shù)后再構(gòu)建AC自動(dòng)機(jī)，這一步也會(huì)增加時(shí)間啦租，能否邊構(gòu)建雙數(shù)組trie樹(shù)的時(shí)候邊構(gòu)建AC自動(dòng)機(jī)哗伯？
3.查詢效率確實(shí)比hash trie高，這個(gè)查詢時(shí)間能否再度優(yōu)化篷角？
問(wèn)題關(guān)鍵點(diǎn)：
1.轉(zhuǎn)移基數(shù)存儲(chǔ)的子節(jié)點(diǎn)的索引笋颤，如果改為BFS構(gòu)建，如何保證AC自動(dòng)機(jī)的Fail狀態(tài)和雙數(shù)組Trie樹(shù)狀態(tài)對(duì)應(yīng)内地，同步構(gòu)建如何保證構(gòu)建過(guò)程可控
2.dfs構(gòu)建時(shí)增加了一個(gè)單獨(dú)的葉子節(jié)點(diǎn)伴澄，這個(gè)節(jié)點(diǎn)能否省掉？如果可以不但能減少一次查詢阱缓，同時(shí)也會(huì)減少構(gòu)建時(shí)間非凌，降低內(nèi)存占用，提升查詢效率荆针。
解決辦法：
1.bfs生成樹(shù)
2.葉子節(jié)點(diǎn)壓縮
? ? 1）縮短了為孩子節(jié)點(diǎn)尋找未被占用空間的時(shí)間敞嗡，減少構(gòu)建時(shí)間
? ? 2）縮小了數(shù)組占用的空間
? ? 3）提升了查詢速度
type Node struct {
? ? Code? ? ? ? ? ? ? ? ? ? ? ? ? ? rune
? ? Depth, Base, Index, Left, Right int
? ? Term? ? ? ? ? ? ? ? ? ? ? ? ? ? bool
? ? Children? ? ? ? ? ? ? ? ? ? ? ? []*Node
}
Term標(biāo)識(shí)當(dāng)前節(jié)點(diǎn)是否葉子節(jié)點(diǎn)
Index標(biāo)識(shí)當(dāng)前節(jié)點(diǎn)在雙數(shù)組中的索引
BFS生成樹(shù)構(gòu)建步驟：
1.令base[0]=1;check[0]=0; 獲取根節(jié)點(diǎn)的子節(jié)點(diǎn)
2.為每個(gè)子節(jié)點(diǎn)和其孩子節(jié)點(diǎn)設(shè)置base&check:
? ? 對(duì)每個(gè)子節(jié)點(diǎn)獲取孩子節(jié)點(diǎn),為孩子節(jié)點(diǎn)尋找空閑插入點(diǎn)begin颁糟，如果當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則該節(jié)點(diǎn)base取反喉悴，同時(shí)設(shè)置孩子節(jié)點(diǎn)的Base[pos]=begin棱貌。Check[pos]=parent.Index
優(yōu)化后，再來(lái)看下對(duì)比：
運(yùn)行機(jī)器：2? Intel(R) Xeon(R) CPU E5-2630 v2 @ 2.60GHz Dict：61w條(黑名單)箕肃；字?jǐn)?shù)：5872778 待匹配：96330條(用戶請(qǐng)求query); 字?jǐn)?shù)：887790
可以看到構(gòu)建時(shí)間大幅下降婚脱，內(nèi)存占用下降11.11%，查詢效率提升12.4%勺像。
AC自動(dòng)機(jī)的一個(gè)極速實(shí)現(xiàn)
有了上面的基礎(chǔ)后障贸，實(shí)現(xiàn)ac自動(dòng)機(jī)就容易了。但是理論誰(shuí)都會(huì)講幾句吟宦，真正實(shí)現(xiàn)起來(lái)并不那么容易篮洁。
下面介紹下筆者用go寫(xiě)的一個(gè)非常快速的實(shí)現(xiàn)殃姓。倉(cāng)庫(kù)地址
基于雙數(shù)組Trie樹(shù)的一種極速實(shí)現(xiàn)袁波。可用于模糊匹配蜗侈，違禁詞標(biāo)記篷牌。
常用使用場(chǎng)景為：
1.聊天時(shí)，對(duì)用戶輸入的query進(jìn)行命中違禁詞時(shí)進(jìn)行屏蔽宛篇。
?2.判斷用戶輸入詞是否命中了違禁詞黑名單，然后就行后續(xù)邏輯處理薄湿。
等需要高性能模糊匹配的場(chǎng)景叫倍。
優(yōu)化
本算法除了基于雙數(shù)組進(jìn)行構(gòu)建外，還做有額外的優(yōu)化豺瘤，保證更高的效率：
1.在構(gòu)造算法時(shí)吆倦，雙數(shù)組和fail指針及輸出項(xiàng)會(huì)同時(shí)構(gòu)建，大幅度提升構(gòu)建速度坐求，減少字典構(gòu)建時(shí)間蚕泽。
2.壓縮輸出項(xiàng)，減少構(gòu)建時(shí)長(zhǎng)及內(nèi)存占用及gc桥嗤。
3.壓縮了葉子節(jié)點(diǎn)须妻，減少內(nèi)存占用，提升檢索效率泛领。
對(duì)壓縮輸出項(xiàng)的解釋?zhuān)?/p>
如：違禁詞詞典為：
????he
????she
輸入為: ushe荒吏，則返回的命中項(xiàng)為：she.
解釋?zhuān)喝绻蛔鲚敵鲰?xiàng)壓縮，則命中項(xiàng)為：he,she渊鞋；其最長(zhǎng)輸出項(xiàng)為she绰更。
考慮到在實(shí)際業(yè)務(wù)中瞧挤，不管是對(duì)違禁詞做屏蔽（如上文中的ushe，屏蔽違禁詞后為u***）儡湾，還是只判斷是否命中了違禁詞特恬，都不需要冗余的輸出項(xiàng)，對(duì)輸出項(xiàng)做壓縮徐钠，不僅可以減少構(gòu)建時(shí)長(zhǎng)癌刽，還能減少內(nèi)存占用，對(duì)于go來(lái)說(shuō)丹皱，還可以減少gc掃描妒穴。
性能
對(duì)比一個(gè)star數(shù)較多的cloudflare/ahocorasick 并返回相同的結(jié)果（使用api:MultiPatternIndexes(content []rune) []int）進(jìn)行對(duì)比（對(duì)比代碼見(jiàn)test文件）。
字典：dictionary.txt 字符串個(gè)數(shù)：153151摊崭。字符數(shù)：401552 （平均每條2.6個(gè)字符）
待檢索文件：text.txt 字符數(shù)：815006
（字典和待檢索文件已在倉(cāng)庫(kù)內(nèi)）
運(yùn)行機(jī)器：聯(lián)想小新pro13 Ryzen 5 3550H
對(duì)待檢索文件匹配100遍
go版本：1.15
待匹配前先進(jìn)行一次gc(runtime.Gc())
可以看出讼油，性能比cloudflare/ahocorasick快64%（檢索一遍81.5w的字符僅需54ms）,得益于雙數(shù)組實(shí)現(xiàn)和對(duì)輸出項(xiàng)的優(yōu)化，執(zhí)行一次gc的時(shí)間可以忽略不記(持有的指針僅為四個(gè)數(shù)組header)呢簸。另外占用內(nèi)存僅為14.2M矮台。
但得益于上面的各種優(yōu)化，使得構(gòu)建時(shí)間優(yōu)化到2.4s根时，雖然仍較cloudflare/ahocorasick長(zhǎng)瘦赫，但是考慮到構(gòu)建時(shí)較復(fù)雜，而且大部分應(yīng)用只需在啟動(dòng)時(shí)構(gòu)建一次蛤迎，秒級(jí)對(duì)于感官時(shí)間較短确虱，構(gòu)建時(shí)長(zhǎng)可控（筆者用一個(gè)業(yè)務(wù)的61w行黑名單詞測(cè)試，構(gòu)建時(shí)間3.5s）替裆，但帶來(lái)的更高的可量化的各項(xiàng)指標(biāo)收益校辩，這個(gè)是值得的。
