一、原理
AC自動(dòng)機(jī)首先將模式組記錄為Trie字典樹(shù)的形式，以節(jié)點(diǎn)表示不同狀態(tài)，邊上標(biāo)以字母表中的字符，表示狀態(tài)的轉(zhuǎn)移。根節(jié)點(diǎn)狀態(tài)記為0狀態(tài)，表示起始狀態(tài)。當(dāng)一個(gè)狀態(tài)處有一個(gè)模式串終結(jié)則標(biāo)記一下。
目前流傳較多的講解多大同小異，尤其是配圖，基本采用的是Aho和Corasiek兩位巨巨的文章efficient string matching an aid to bibliographic search里的，竊以為那張示意圖存在失配點(diǎn)靠前的特點(diǎn)（什么是失配？往下看），看起來(lái)稍稍費(fèi)勁。
我找了樣例畫了一套新圖，主要目標(biāo)是通過(guò)稍微的夸張（失配點(diǎn)遠(yuǎn)離）讓過(guò)程更清晰。
匹配的過(guò)程是：從0狀態(tài)起點(diǎn)開(kāi)始，以字符流輸入，進(jìn)行適當(dāng)?shù)臓顟B(tài)轉(zhuǎn)移，如果可以抵達(dá)某一標(biāo)記終結(jié)的狀態(tài)，則成功匹配模式，串值為從0到終結(jié)點(diǎn)的路徑。
按照傳統(tǒng)的說(shuō)法，狀態(tài)機(jī)有三個(gè)主要函數(shù)支撐：goto（狀態(tài)正常轉(zhuǎn)移），fail（狀態(tài)失配轉(zhuǎn)移），output（傳回匹配結(jié)果），而我認(rèn)為與其規(guī)定是具體的函數(shù)，倒不如說(shuō)是三個(gè)功能的模塊，有不同于函數(shù)的實(shí)現(xiàn)形式。
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動(dòng)安全 [無(wú)線安全]玩轉(zhuǎn)無(wú)線電——不安全的藍(lán)牙鎖 2017-07-26
- 消息隊(duì)列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標(biāo)分割】 2017-07-26
- 詞向量-LRWE模型-更好地識(shí)別反義詞同義詞 2017-07-26
- 從棧不平衡問(wèn)題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實(shí)現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動(dòng)安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來(lái)看看(二) 2017-07-26
學(xué)習(xí)是年輕人改變自己的最好方式