计算机安全
入侵检测与匹配算法

MP、KMP 与 AC 自动机

来源:IDS 课件第 25–62 页。统一把“状态”解释为已匹配的前缀长度;具体 next/fail 数组下标可与课件不同。

1. 先会读字符串#

文本 T 是被搜索的数据,模式 P 是要找的特征。n 是文本长度,m 是模式长度;前缀从开头取,后缀从末尾取,子串是连续的一段。

例:P=abab 的真前缀有空串、a、ab、aba;真后缀有空串、b、ab、bab。“真”表示不能取整个字符串。

蛮力算法在每个候选起点逐字符比较,最坏 O(nm)。改进算法的核心是利用已经匹配过的信息,避免无意义重比。

2. MP 的失败链接#

已经匹配的串为 q,失配后不用从零重新开始;寻找 q 的最长真后缀,同时也是 P 的前缀,保留这段已有匹配。

已匹配 ababa,下一字符不能延伸
ababa 的最长真前后缀是 aba
可退回“已匹配 aba”的状态,而不是让文本倒退

失败链接针对已匹配前缀,不是“随便找模式里相同的字符”。文本指针不需回头,状态沿 fail 回退。

3. 用一张前缀表手算#

约定 pi[i] 为 P[0..i] 的最长相等真前后缀长度:

i(从0起) 0 1 2 3 4 5 6
P=ababaca a b a b a c a
pi[i] 0 0 1 2 3 0 1

若已匹配 k 个字符后失配,常用回退写法是 k=pi[k−1],继续试当前文本字符;k=0 且仍不匹配才消耗该文本字符。

有的资料用 next[0]=−1,有的把状态编号当数组下标;不要把不同定义的数值表直接混用。

4. KMP 相对 MP 的 Knuth 优化#

若在已匹配长度 k 时,当前输入 c 已知不等于 P[k],回退到 j 后又有 P[j]=P[k],则比较 c 与 P[j] 一定还失败,可以继续跳过这个状态。

例:P=ababaca,在 k=3 时期待 b,但输入不是 b;普通 fail 退到 k=1,该状态也期待 b,因此可直接再退,避免重复确定会失败的比较。

MP 与 KMP 都可达到 O(n+m)。教材和代码中也常把基于前缀函数的常见写法统称 KMP;考试若强调两者区别,就说明这里的跳过优化。

5. 为什么总回退次数仍是线性的#

匹配状态随成功扩展最多增长 O(n) 次;每次失败回退使状态长度减少,不能无限减少而不先增长,因此总回退量也是 O(n)。这叫均摊分析,不是说每个字符只发生一次比较。

6. AC 自动机:同时找多个模式#

AC 是 MP 思路的多模式扩展:

结构 作用
Trie / follow 边 合并各模式公共前缀
fail 链 找当前串最长的、仍是某模式前缀的真后缀
output 报告当前位置匹配到哪些完整模式

Trie 的一个节点代表一个模式前缀;根表示空串。

7. 用课件模式集合演示#

模式集合 {her,iris,he,is}。

根
├─ h ─ e [he] ─ r [her]
└─ i ─ r ─ i ─ s [iris]
     └─ s [is]

上图是前缀树示意;节点 i 的两条分支分别到 ir 与 is。

  • fail(he)=根:没有非空后缀同时是这些模式前缀。
  • fail(iri)=i:其后缀 i 是模式前缀。
  • fail(iris)=is:其后缀 is 是模式前缀。
  • 到达 iris 节点时要报告 iris,同时报告 fail 链上的 is。

为什么要 output 继承?同一个结束位置可能对应多个长度不同的模式,漏掉 fail 链输出就会漏检。

8. 构造与匹配#

先插入所有模式形成 Trie,再按深度从浅到深(常用 BFS)计算 fail,最后准备输出信息。匹配时,存在所需字符边就走;没有就沿 fail 找,直到能走或回根。

设总模式长度 M、命中次数 occ。课件在固定字母表等适当实现假设下给出构造 O(M)、搜索 O(n+occ)。若用平衡树等存转移,要计入查询代价;若输出很多命中,本来就需要时间把它们报告出来。

填全每个状态每种字符的转移可获得直接查表的 DFA 风格实现,但会增加空间。速度与内存是设计权衡。

自测#

  1. 模式 aa、aaa,文本 aaa,一共多少次出现?——aa 两次,aaa 一次,共三次,可重叠。
  2. fail 是否总指向父节点?——不是,父节点删最后字符,fail 找最长可用后缀。
  3. AC 的 O(n+occ) 为什么包含 occ?——必须报告所有匹配结果。
— 本篇阅读完毕 —
来源:计算机安全知识点 / 05_入侵检测与匹配算法/03_MP_KMP与AC自动机.md 下载原文
输入关键词,在三个知识库中搜索
支持正文检索 · 直接定位章节Esc 关闭