有穷自动机的原理及应用

有穷自动机的原理及应用内容摘要：

，后序遍历（从深往浅 ）  Offline 算法  原 DFA 到新 (最小化的 )DFA的状态映射  计算等价状态时使用映射后的状态  比 Hopcroft算法快得多（时空复杂度： O(n)） ADFA 最小化 算法：泛化  Online算法用于非 ADFA 时  如果原 DFA已是最小化  增加 /删除一个串之后，仍然是最小化的  即使增加 /删除的串会通过 (path through)有环的子结构  Offline算法用于非 ADFA 时  无法将有环的子结构最小化  无环的子结构仍然可以被最小化  按 graphpostorderwalk顺序 ADFA Online最小化：字典序的输入 1. 一旦执行最小化，前面的自动机状态不会再变（深度优先，后序） 2. 找出（当前串与上一个串的）公共前缀CommonPrefix 3. 从上一个串尾至 CommonPrefixLen执行状态合并（按 State Register） 4. 每次加入一个串，整个 DFA是 不完全 最小化的，完成时需要执行一次最终的最小化 ADFA的最小化：任意顺序的输入  汇合状态（ Confluence State）：有多个前驱状态的状态  需要克隆从汇合状态开始的路径  加入当前串之后，在当前串的路径上从后 往前 执行最小化  每加入一个串，整个自动机是 完全 最小化的  速度稍慢，内存用量稍大（比顺序输入） DAWG: ADFA + 字典序号  我们大多数情况下需要一个 Mapstring, Data  普通的 ADFA只能表示 Setstring  DAWG (Directed Acyclic Word Graph)  可以 从 ADFA 中得到一个串在该 ADFA中的字典序  可以从字典序反 推 (还原 )出 ADFA中的一个 串  将 mapKey,Value 中的 Value保存一个数组中 DAWG 的实现 (两种方案 ) A: 在 每个状态上保存该状态的右语言集合的尺寸 B: 在 每个状态转移 (图的边 )上保存转移字符小于 自己的转移字符的 其它目标状态的右语言尺寸之和  这种 方案 对应 的算法更快，直观上看需要更多的内存，但实际上，每个状态的第一个转移对应的这个数字总为 0，可以省去，再加上对于很多自动机，状态的平均转移数小于 2，从而，需要的 内存 就 更 少（只有当平均转移数大于 2时， 这种 方案 才比 方案 A 需要 更多的内存）。 DFA Map 的另一种实现  (key, val)用特殊字符 delim 分隔  例如： key \t value  delim 不可出现在 key中 ，但可以在 value中  对用户更加友好，适用性更广  更进一步： key可以是 正则表达式。  delim ∈ [0, 256), key 不能是任意二进制串  扩展 Σ=[0,257)，令 delim=256  key就可以是任意二进制串  对 多 正则表达式匹配尤其有用 路径压缩  将直线形的状态序列压缩成一个状态  序列中每个状态只有一个 后续 状态  除序列 起始 状态，其它状态都不是 汇合 状态  除 序列 末尾 状态 ，其它状态都 不是 终止 状态  路径压缩一般可以将状态数压缩到原来的 30%甚至更少  路径压缩的 DFA串匹配速度更快  在压缩的路径上是精确的串比较  无状态转移，对 CPU Cache 更 友好 路径 压缩的适用范围  与 DAWG 完美兼容  可以应用到任意形状的 DFA上  包括 有环 的 DFA  在 MinDFA 上应用路径压缩 可进一步 减小状态 数  路径压缩后的 DFA不再是严格意义上的 DFA  无法（很难）进行修改操作  通用的 DFA算法不再适用 AC（ AhoCorasick）自动机  用于 多模匹配：在目标文本中搜索一个串集合中任意串出现的所有位置  相当于搜索正则表达式 .∗(𝑠1|𝑠2|…𝑠𝑛)  F。