有穷自动机的原理及应用.docx

有穷自动机的原理及应用 雷鹏 rockeet@163.com 2014-07-15 大纲 基本概念 DFA 最小化：概念 DFA 最小化：算法 AC 自动机（多模匹配） DFA 的实现 API 与工具箱 DFA 与 NFA 转移目标是一个状态集合，可能包含多个状态 DFA 到 NFA 的转化 ADFA Acyclic DFA 无环自动机 无环自动机只能表达有限的字符串集合 Trie: 最简单，最大的 ADFA MinADFA: 最小化的无环自动机 内存需求小，极端情况下压缩率是指数的 随着集合的增大，MinADFA 可能反而更小 后缀自动机: 后缀树的泛化 典型应用 Regular Expression 正则表达式 Lexical Analyzing 词法分析 Pattern Matching 模式匹配 精确匹配，前缀匹配 多模匹配(AC自动机)，多正则匹配 Dictionary Compressing 词表压缩 自动机最小化，字典序计算 DFA 的最小化：等价同构 DFA 等价 DFA表达的语言相同 等价的DFA状态数可能不同 状态数最小的那个DFA称为最小的DFA 更小的 DFA 需要的内存更小 DFA 同构 状态数相等，表达的语言相同 对状态编号做一置换后，完全等同 规格化的DFA：状态编号为从初始状态执行深度优先遍历的序号 0~63 的二进制串 未最小化的Tree 形状的 DFA (Trie) 最小化的 DAG 形状的 DFA (DAWG) 未最小化的Tree 形状的 DFA (Trie) 最小化的 DAG 形状的 DFA (DAWG) 0~62 的二进制串 相当于将n个状态压缩到O(log(n))个状态 极端的例子：字符串 “1” ~ “99999” 未最小化的Tree 形状的 DFA (Trie) 最小化的 DAG 形状的 DFA (DAWG) int int_t intmax_t int8_t int16_t int32_t int64_t uint uint_t uintmax_t uint8_t uint16_t uint32_t uint64_t DFA 的最小化算法 Hopcroft 算法原理 Myhill–Nerode 等价 对任意输入，同一分区(子集)中两个状态 p, q的行为相同，则 p, q 是 Myhill–Nerode 等价的 行为相同即：对任意w，δ(p,w) 与 δ(q,w)要么都是终止状态，要么都不是终止状态 Partition Refinement 可直译为分区细化 Partition Refinement 是 Hopcroft 算法的一个关键操作，该操作使用一个函数将集合的当前切分中的每个分区进行再切分，直到不能继续切分 Hopcroft 算法伪代码 P := {F, Q \ F }; // \ 表示集合减法，Q表示所有状态的集合，F 表示终止状态集合 W := {F, Q \ F }; // 此伪代码来源于维基百科，但维基百科此行有误 // Q \ F 也必须加入 W (WaitingSet) // 其它一些论文中将 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 the same two sets else add min( X ∩ Y, Y \ X ) to W Y X Hopcroft 算法实现 逆自动机 一般DFA的逆是一个NFA，结构比较复杂 Trie的逆是一棵倒长的树，结构非常简单 用 smallmap 收集反向转移 双向链表（插入、删除均为 O(1) ） 用数组下标做链接 集合的一个切分可用一个排列(permut