有窮自動機的原理及應(yīng)用(編輯修改稿)
2024-11-16 16:27 本頁面
【文章內(nèi)容簡介】 ，后序遍歷（從深往淺 ） ? Offline 算法 ? 原 DFA 到新 (最小化的 )DFA的狀態(tài)映射 ? 計算等價狀態(tài)時使用映射后的狀態(tài) ? 比 Hopcroft算法快得多（時空復(fù)雜度： O(n)） ADFA 最小化 算法：泛化 ? Online算法用于非 ADFA 時 ? 如果原 DFA已是最小化 ? 增加 /刪除一個串之后，仍然是最小化的 ? 即使增加 /刪除的串會通過 (path through)有環(huán)的子結(jié)構(gòu) ? Offline算法用于非 ADFA 時 ? 無法將有環(huán)的子結(jié)構(gòu)最小化 ? 無環(huán)的子結(jié)構(gòu)仍然可以被最小化 ? 按 graphpostorderwalk順序 ADFA Online最小化：字典序的輸入 1. 一旦執(zhí)行最小化，前面的自動機狀態(tài)不會再變（深度優(yōu)先，后序） 2. 找出（當(dāng)前串與上一個串的）公共前綴CommonPrefix 3. 從上一個串尾至 CommonPrefixLen執(zhí)行狀態(tài)合并（按 State Register） 4. 每次加入一個串，整個 DFA是 不完全 最小化的，完成時需要執(zhí)行一次最終的最小化 ADFA的最小化：任意順序的輸入 ? 匯合狀態(tài)（ Confluence State）：有多個前驅(qū)狀態(tài)的狀態(tài) ? 需要克隆從匯合狀態(tài)開始的路徑 ? 加入當(dāng)前串之后，在當(dāng)前串的路徑上從后 往前 執(zhí)行最小化 ? 每加入一個串，整個自動機是 完全 最小化的 ? 速度稍慢，內(nèi)存用量稍大（比順序輸入） DAWG: ADFA + 字典序號 ? 我們大多數(shù)情況下需要一個 Mapstring, Data ? 普通的 ADFA只能表示 Setstring ? DAWG (Directed Acyclic Word Graph) ? 可以 從 ADFA 中得到一個串在該 ADFA中的字典序 ? 可以從字典序反 推 (還原 )出 ADFA中的一個 串 ? 將 mapKey,Value 中的 Value保存一個數(shù)組中 DAWG 的實現(xiàn) (兩種方案 ) A: 在 每個狀態(tài)上保存該狀態(tài)的右語言集合的尺寸 B: 在 每個狀態(tài)轉(zhuǎn)移 (圖的邊 )上保存轉(zhuǎn)移字符小于 自己的轉(zhuǎn)移字符的 其它目標狀態(tài)的右語言尺寸之和 ? 這種 方案 對應(yīng) 的算法更快，直觀上看需要更多的內(nèi)存，但實際上，每個狀態(tài)的第一個轉(zhuǎn)移對應(yīng)的這個數(shù)字總為 0，可以省去，再加上對于很多自動機，狀態(tài)的平均轉(zhuǎn)移數(shù)小于 2，從而，需要的 內(nèi)存 就 更 少（只有當(dāng)平均轉(zhuǎn)移數(shù)大于 2時， 這種 方案 才比 方案 A 需要 更多的內(nèi)存） ！ DFA Map 的另一種實現(xiàn) ? (key, val)用特殊字符 delim 分隔 ? 例如： key \t value ? delim 不可出現(xiàn)在 key中 ，但可以在 value中 ? 對用戶更加友好，適用性更廣 ? 更進一步： key可以是 正則表達式 ！ ? delim ∈ [0, 256), key 不能是任意二進制串 ? 擴展 Σ=[0,257)，令 delim=256 ? key就可以是任意二進制串 ? 對 多 正則表達式匹配尤其有用 路徑壓縮 ? 將直線形的狀態(tài)序列壓縮成一個狀態(tài) ? 序列中每個狀態(tài)只有一個 后續(xù) 狀態(tài) ? 除序列 起始 狀態(tài)，其它狀態(tài)都不是 匯合 狀態(tài) ? 除 序列 末尾 狀態(tài) ，其它狀態(tài)都 不是 終止 狀態(tài) ? 路徑壓縮一般可以將狀態(tài)數(shù)壓縮到原來的 30%甚至更少 ? 路徑壓縮的 DFA串匹配速度更快 ? 在壓縮的路徑上是精確的串比較 ? 無狀態(tài)轉(zhuǎn)移，對 CPU Cache 更 友好 路徑 壓縮的適用范圍 ? 與 DAWG 完美兼容 ? 可以應(yīng)用到任意形狀的 DFA上 ? 包括 有環(huán) 的 DFA ? 在 MinDFA 上應(yīng)用路徑壓縮 可進一步 減小狀態(tài) 數(shù) ? 路徑壓縮后的 DFA不再是嚴格意義上的 DFA ? 無法（很難）進行修改操作 ? 通用的 DFA算法不再適用 AC（ AhoCorasick）自動機 ? 用于 多模匹配：在目標文本中搜索一個串集合中任意串出現(xiàn)的所有位置 ? 相當(dāng)于搜索正則表達式 .?(??1|??2|…????) ? F
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1