问题
搜索时可能反复把模式与相同的文本位置比较。出现不匹配并不代表已匹配的信息全部无用:已匹配部分的后缀可能同时是模式的前缀。前缀函数正是记录这些可供回退的候选。
设 为长度 的非空序列, 为长度 的序列。位置从零开始。我们报告 在 中每次出现的起始位置,包括互相重叠的出现。符号可以是字符、整数或其他记号;其相等测试必须是稳定的等价关系,并把每次测试计为一次运算。我们还假设对模式和前缀表的下标访问为常数时间,逐个顺序读取文本符号也为常数时间。本单元刻意不处理空模式的约定。
边界与前缀表
定义 6.1.1
(边界与前缀函数)
序列的边界是同时为真前缀及后缀的序列;允许空序列,真是指长度严格小于整个序列。对每个 ,令 为 最长边界的长度。因此 ,而且始终有 。
引理 6.1.2
(前缀回退)
若长度 的模式前缀与已处理文本的后缀相同,而下一个符号不匹配,则在比较下一个符号前,任何能匹配已处理文本后缀的较短前缀,都是该长度 前缀的边界。当 ,最长可能的回退长度是 。重复此步骤便可考虑更短候选,无须重新读取文本。
证明
(每个可行的回退都是边界,而且边界构成一条链)
假设长度 的较短前缀也匹配同一个已处理文本的后缀。那么已匹配的长度 前缀的最后 个符号,便是模式最前面的 个符号: 是边界长度。最长的此类边界长度为 。更短的边界也必是这个最长边界的边界,所以反复应用同一规则会遍历所有剩余的边界长度,直至零。不相等排除了刚测试的候选,而可行候选不会被丢弃。
证明透视
为何边界链不会遗漏
关键一步是只通过文本来比较两个前缀:两者都等于已处理文本的同一个后缀,所以较短的那个就是较长那个的末段。这是唯一要求相等必须表现为等价关系的地方。若在整数上采用“相差至多为一”的容差关系,则 、 但 ,两个前缀可以都匹配文本,而较短的却不是较长的边界,边界链便会遗漏候选。
边界链是完整的,因为边界的边界仍是原序列的边界。过程在长度为零处结束,而零永远是一个边界。只在比较失败之后才丢弃候选是安全的,因为失败的比较表示该候选无法被下一个文本符号延长。
建表按同一条链,在模式本身上进行。
定理 6.1.3
(前缀表的构造)
对 ,先取 。只要 且 ,便令 。若 ,将 加一。然后 。每个表项只依赖较早的表项。
证明
( 的边界来自 的边界)
设 是 的一个边界长度。把前缀与后缀各去掉最后一个符号,便得到 的一个长度为 的边界,而被去掉的符号相等:。反过来,若 是 的边界长度且 ,则得到 的长度为 的边界;因为 ,它是真边界。
所以,若存在, 就是 的边界长度 中满足 的最大者。因为边界的边界仍是边界, 的边界长度由大到小依次是 ,而循环恰好按此顺序逐个测试。它在第一个满足 的 处停止,得到 。若链在 结束而 ,则不存在正长度的边界,。当 时,仍须测试相等与否,判断第一个符号能否开始一个边界。
例题 6.1.4
(为 ababaca 与 abaab 建表)
对 ,各项为 :前缀 的最长边界是 ,而符号 不能延续任何边界,所以该项降为 。
再取 。;因为 ,;。对 ,先取 ;,回退至 ,此时 ,故 。对 ,先取 ;这时 ,故 。表为 ,而 确实是 的最长边界。
不丢失重叠的扫描
定义 6.1.5
(扫描状态)
处理了文本的一个前缀之后, 是已处理文本后缀中最长的真模式前缀之长度。当长度为 的模式前缀匹配时,便检测到在当前符号结束的完整出现,并在重置 之前报告。
维持 ,表示已处理文本的某个后缀所匹配的模式前缀长度。读取下一个文本符号之前,。对每个符号 ,只要 且 ,就令 ;若 ,便把 加一。若它变成 ,报告起始位置,然后重置 。此重置保留已匹配模式的最长真边界,使后续出现可以与刚报告的出现重叠。
定理 6.1.6
(扫描恰好报告全部出现)
上述扫描按递增顺序报告 在 中每个出现的起始位置,不报告其他位置。处理每个符号及可能的报告后, 是已处理文本后缀中最长的真模式前缀之长度。
证明
(对已处理符号的个数做归纳)
在读取任何符号之前,,结论成立。设读取 之前结论成立。能匹配包含 在内的文本后缀的模式前缀,其长度为 ,前 个符号匹配较早文本的后缀,最后一个符号等于 。由归纳假设,候选的 就是从 开始的边界链:最长的是 ,其次是 、,如此类推(由前缀回退引理)。循环由长到短测试它们,在第一个满足 的 处停止,所以找到最长的延伸;若不存在,测试后 为零。若 变成 ,该后缀便是在当前位置结束的完整出现,于是报告起始位置。它的最长真边界恰是读取下一个符号所需的状态。反过来,若有一个全长前缀匹配到在当前符号结束的文本后缀,那就是长度为 的延伸,是可能的最长者,所以循环恰好在出现处达到 。因此不会漏报,也不会误报。
概念视角结构
把扫描看成有限自动机
状态 是一个确定型自动机的状态。读入符号 时,它转移到“同时是 的后缀的最长模式前缀(允许是整个模式)”的长度,这正是回退循环所计算的;完整匹配就是这个长度将会是 的事件。前缀表以回退链的形式隐含地存储转移,而不必为整个字母表存储 行转移。
例题 6.1.7
(不匹配时重用前缀)
对 ,表为 。搜索 。处理五个文本符号后,;下一个符号是 ,而 。回退至 ,同一个文本符号便能匹配。继续后找到模式,起始位置为从零计数的 。造成不匹配的文本符号无须从输入重新读取。
例题 6.1.8
(边界情形:全部符号相同,以及比模式短的文本)
取 ,,。读第一个符号得 ,读第二个得 ,报告位置 ,并重置为 。之后每个符号又把 升到 ,分别报告位置 与 。互相重叠的出现位置是 。
若 为空或比 短,任何符号序列都不可能使 达到 ,扫描以 步不报告任何位置;表仍以 建成。
反例模式
重置为零可能丢失匹配
在 中,模式 出现在位置 和 。第一次匹配后, 保留最后的 作为下一个候选的起点;若改为重置为零,便会丢失重叠的出现:接着读入的 只令 ,扫描结束时并没有报告位置 。
为何总工作量是线性
定理 6.1.9
(线性运行时间)
若相等测试为常数成本,建表需 时间,扫描文本需 时间,总运算量为 。表占 空间。
证明
(以 q 为势能做摊还分析)
扫描文本时,每个符号最多令 增加一次;每次回退都严格减少 ,而 不会变成负数。因此回退总次数不超过增加的总次数,为 ;报告后的重置是多一次减少。建表同理,对值 ,每个模式位置最多增加一次,故需 。表有 项。
若存储全部 个报告位置,输出需要 空间;逐个输出便不需该存储量。此界把符号相等测试视为常数成本;若记号本身是长字符串或结构化对象,须另计比较成本。算法处理精确相等匹配,不处理近似或语义相似。
常见错误
常见错误
(回退到 q 处的表项,而不是 q 减一处的表项)
回退使用的是 ,即长度 的已匹配前缀的边界,而不是 。在用 搜索 时,不匹配发生在 。正确值是 。若用 ,便掉到 ,其余符号 再也无法重建前缀,位置 的出现就漏掉了。
常见错误
(把整个前缀也算作边界)
边界必须是真前缀。若表允许整个前缀,则对 表会是 。匹配之后重置 , 仍等于模式长度,下一次比较就会读取模式之外的 ;而每次回退 也永远不会令 减少。
练习
快速检查
(求 的 。)
求前缀 、、、 各自的最长边界。
解答 · 答案
表为 :每个前缀的最长真边界都比它少一个末尾符号。
快速检查
(列出 在 中所有从零计数的位置,并给出第一次匹配后的重置值。)
此模式的 。
解答 · 答案
位置为 ;第一次匹配后重置为 。
快速检查
(当 且文本符号与 不同时,该符号如何处理?)
想一想有哪个非空模式前缀能以该符号结尾。
解答 · 答案
没有非空前缀能以该符号结尾,故 保持零,扫描前进至下一个符号。
快速检查
(为何一次很长的回退链不会令整次扫描变成二次时间?)
把 看成必须先赚取才能花费的量。
解答 · 答案
每次回退都减少非负的 ;整次扫描中的减少次数受先前增加次数限制,而每个文本符号最多令其增加一次。