1、有窮自動機的原理及應用雷鵬2013-01-05DFA 與 NFA轉移目標是一個狀態集合，可能包含多個狀態DFA 與 NFA 的轉化ADFA Acyclic DFA 無環自動機一個無環自動機表達了一個有限的字符串集合Trie最簡單，最大的 ADFAMinADFA 最小化的無環自動機又叫 DAWG (Directed Acyclic Word Graph)需要的內存很小，極端情況下可將 n 壓縮到O(log(n)隨著字符串集合的增大，MinADFA 可能反而更小后綴自動機因子自動機典型應用Regular Expression 正則表達式Lexical Analyzing 詞法分析Pattern M

2、atching 模式匹配精確匹配，前綴匹配多模匹配(AC自動機)Dictionary Compressing 詞表壓縮自動機最小化，字典序計算DFA 的最小化兩個 DFA 等價如果這兩個DFA表達的語言相同等價的兩個DFA的狀態數可能不同狀態數最小的那個DFA稱為最小的DFA更小的 DFA 需要的內存更小兩個DFA同構狀態數相等，表達的語言相同對狀態編號做一置換后，完全等同規格化的DFA：狀態編號為從初始狀態執行深度優先遍歷的序號063 的二進制串未最小化的Tree 形狀的 DFA (Trie)最小化的 DAG 形狀的 DFA (DAWG)未最小化的Tree 形狀的 DFA (Trie)最小化

3、的 DAG 形狀的 DFA (DAWG)062 的二進制串相當于將n個狀態壓縮到O(log(n)個狀態該自動機是未規格化的極端的例子：字符串 “1” “99999”未最小化的Tree 形狀的 DFA (Trie)最小化的 DAG 形狀的 DFA (DAWG)intint_tintmax_tint8_tint16_tint32_tint64_tuintuint_tuintmax_tuint8_tuint16_tuint32_tuint64_tDFA 的最小化算法Hopcroft 算法原理MyhillNerode 等價對任意輸入，同一分區(子集)中兩個狀態 p, q的行為相同，則 p, q 是 M

4、yhillNerode 等價的行為相同即：對任意w，(p,w) 與 (q,w)要么都是都是終止狀態，要么都不是都不是終止狀態Partition Refinement可直譯為分區細化分區細化Partition Refinement 是 Hopcroft 算法的一個關鍵操作，該操作使用一個函數將集合的當前切分中的每個分區進行再切分，直到不能繼續切分Hopcroft 算法偽代碼P := F, Q F ; / 表示集合減法，Q表示所有狀態的集合，F 表示終止狀態集合W := F,QF ; / 此偽代碼來源于維基百科，但維基百科此行有誤/QF也必須加入 W (WaitingSet) / 其它一些論文中將

5、 W 初始化為 min(F, Q F) , 也不對while (W is not empty) do choose and remove a set A from W for each c in do let X be the set of states for which a transition on c leads to a state in A for each set Y in P for which X Y is nonempty do replace Y in P by the two sets X Y and Y X if Y is in W replace Y in W by

6、 the same two sets else add min( X Y, Y X ) to WHopcroft 算法實現逆自動機一般DFA的逆是一個NFA，結構比較復雜Trie的逆是一棵倒長的樹，結構非常簡單用 smallmap 收集反向轉移雙向鏈表（插入、刪除均為 O(1) ）用數組下標做鏈接集合的一個切分切分可用一個置換(permutation)表達切分切分是指將一個集合切分切分成多個互不相交的子集Waiting Set可以任意次序進出棧式的Waiting Set可使算法運行得更快ADFA最小化的基本原理ADFA最小化的實用算法注冊表按右語言等價的定義，實現一個 mapTargetSet

7、 是 StateID 標識的狀態的轉移：pair(Char,Target) 的有序集合根據新的輸入（字符串）和當前狀態構造一個 TargetSet 作為Key，用該Key查找map，如果找到，則用找到的狀態替換當前狀態替換時，使用深度優先，后序遍歷（從深往淺）為什么該算法不能用在非ADFA上？數學歸納法必須有初始條件初始條件即至少一個的終止狀態不能循環論證ADFA的最小化：字典序的輸入1.一旦執行最小化，前面的自動機狀態不會再變（深度優先，后序）2.找出（當前串與上一個串的）公共前綴CommonPrefix3.從上一個串尾至CommonPrefixLen執行狀態合并（按注冊表）4.每次加入一個

8、串，整個DFA是不完全不完全最小化的，完成時需要執行一次最終的最小化ADFA的最小化：任意順序的輸入匯合狀態（Confluence State）：有多個前驅狀態的狀態需要克隆從匯合狀態開始的路徑加入當前串之后，在當前串的路徑上從后往前執行最小化每加入一個串，整個自動機是完全完全最小化的ADFA 與字典序號我們大多數情況下需要一個Map普通的ADFA只能表示 Set可行的策略：從 ADFA 中得到一個串在該 ADFA中的字典序將map 的 Value保存一個數組中最好也可以從字典序反推出ADFA中的一個串附加一些數據，即可實現每個狀態同時保存該狀態的右語言集合的尺寸或者，每個狀態轉移(圖的邊)保

9、存轉移字符小于自己的轉移字符的其它目標狀態的右語言尺寸之和這種策略對應的算法更快，直觀上看需要更多的內存，但實際上，每個狀態的第一個轉移對應的這個數字總為0，可以省去，再加上對于很多自動機，狀態的平均轉移數小于2，從而，需要的內存甚至更少（只有當平均轉移數大于2時，這種策略才需要更多的內存）！路徑壓縮將直線形的狀態序列壓縮成一個狀態序列中每個狀態只有一個后續狀態除序列起始起始狀態，其它狀態都不是匯合匯合狀態除序列末尾末尾狀態，其它狀態都不是終止終止狀態路徑壓縮一般可以將狀態數壓縮到原來的30%甚至更少路徑壓縮的DFA串匹配速度更快在壓縮的路徑上是精確的串比較，無狀態轉移路徑壓縮的適用范圍路徑壓

10、縮可以應用到任意形狀的DFA上包括有環有環的 DFARadix Tree 是一種應用了路徑壓縮的 Trie在 MinDFA 上應用路徑壓縮可進一步減小狀態數應用了路徑壓縮的DFA不再是嚴格意義上的DFA無法（很難）進行修改操作通用的DFA算法不再適用與計算字典序的算法完美兼容AC（Aho-Corasick）自動機AC自動機與 TrieAC自動機是基于Trie的每個狀態中有附加數據一個 fail link 模式串集合的一個子集因為一個模式串可能是另一個模式串的后綴AC自動機可以用 Double Array 實現AC自動機最壞情況時間復雜度是最優的擴展的AC自動機DFA 的實現最簡單的實現(需附帶

11、一個位圖保存終止狀態標志)typedef unsigned int state_id_t;typedef unsigned char char_t;typedef state_id_t automata_t256;缺點：空間消耗太大，僅適用于Demo非常小的 DFA 狀態轉移非常密集的 DFA實際應用中往往有包含數億，甚至數十億狀態的自動機，我們需要更緊湊的實現正則表達式的DFA一般比較小，也比較密，用這種簡單實現是可行的。Google RE2 中的 DFA 就是用了這種實現緊湊的實現工程實踐Double Array Trie & Bitmap Small CharSet DFA啟發式填充方法（往往可以填充到99.9%以上）Offline填充：BFS/DFS 遍歷時填充，不需重定位Online填充：無空位時需要重定位Bitmap Byte Char Set DFAmin/max char + 指針（整數表示的相對偏移）僅一個轉移時，指針直接指向目標狀態有多個轉移時，指針指向內存池中的Bitmap+數組popcnt 的合理使用在搜索項目中的應用糾