计算机问题求解 – 论题4-11 - 串匹配 2017年5月3日

问题1: 什么是 string-matching problem, 直观上? 形式上?

最容易想到的算法 问题2: 为什么称它为“naïve”算法？

问题3： 为什么在最坏情况下复杂 度是平方级的？

问题4： 你能否说说naïve算法 有什么问题，为什么有 可能改进？

最容易想到的算法 逐位单字符比较

问题5： Rabin-Karp算法的基本 思想是什么？

Preprocessing 问题6: Rabin-Karp算法是采用“预处理” 方式的算法？何为“预处理”，这 个算法预处理的结果是什么？

问题7： Matching Rabin-Karp算法在“匹配”时拿 什么与什么匹配？ 这样有什么问题？是如何解决的？ 什么意思？ 值匹配仅仅是必要条件！ 如果值不匹配，一定不是match 但如果值相同，可能不是valid 什么意思？

问题8: 对T中每个长度为m的子串在匹配前 都必须计算它的“值”，这个计算 是如何被“简化”的？ 递推的方法

问题9： 影响复杂度的 关键是什么？

问题10： 这是书上开始介绍Rabin-Karp 算法时的第一段话，现在你能 解释一下了吗？ Valid hits is few! Spurious hits: Assumption : Reducing valued modulo q acts like a random mapping from Σ^∗ 𝑡𝑜 ℤ_𝑞 Then the number of spurious hits is 𝑂(𝑛/𝑞) 𝑂(𝑛)+𝑂(𝑚(𝑣+𝑛/𝑞))

有限状态机 语句::=前缀 a 前缀::= 前缀::=前缀b | 前缀aa

问题11: 你能将有限自动机与字符 串的识别联系起来吗? 欲匹配的pattern一定是可接受的“语句”的后缀！ Whenever its current state q is a member of A, the machine M has accepted the string read so far. An input that is not accepted is rejected. 问题11: 你能将有限自动机与字符 串的识别联系起来吗? 欲匹配的pattern一定是可接受的“语句”的后缀！ 有多少个有效偏移出现，就有多少个“可接受”的语句。（当然，这些语句都是输入的T的某个“前缀”）

问题12： 你能否看出构建自 动机的关键在哪里？ 待匹配的pattern 终态函数：每个状态下，需要计算出下一个输入导致的格局，拥有多长的pk，如果k=m，匹配成功。

问题13： 这个函数的 “价值”在 何处？ 告诉我们“退”到那里。 X的最后一位向前数，有多少位形成的子串（后缀）是模式P的前缀。   问题13： 这个函数的 “价值”在 何处？ X的最后一位向前数，有多少位形成的子串（后缀）是模式P的前缀。 如果这个数字是k，意味著：如果x后面出现的m-k位恰好是模式P的后几位，匹配成功 西格玛（x）=m表明什么？ 告诉我们“退”到那里。

如何构建自动机 后缀函数的意义不仅仅是告诉我们“退到哪里”！

最终目的 问题14： (Pqa)究竟怎么确定？

后缀函数递归引理 问题15： 你能解释右边的图吗？ 定义西格玛（Pqa）可以通过计算西格玛(xa) 确定(Pqa)与x无关，即与T无关。

问题16： 能不能不计算转换函数？ 可能需要代价m 考察所有可能的状态q，看在任意输入下a下，德尔塔（q，a）是什么？转到哪个状态去 K是某个状态，如果a是模式P的下一位，k在q的基础上增加1，否则要回退，直到找到模式P的最大前缀。 不计算转移函数意味着：没有返回的边 问题16： 能不能不计算转换函数？

KMP算法的基本思想 很显然，在我们只比较了5个字符，掌握了这些信息的基础上： 偏移量s+1是必定是无效的！Why？ 没有返回边，无法进行匹配。是否可以实时计算该返回到哪里？ 如果能够实时计算，比如KMP采用π数组存储每个q的有关信息，计算π只需m量级。而计算德尔塔函数却需要m西格玛量级。 很显然，在我们只比较了5个字符，掌握了这些信息的基础上： 偏移量s+1是必定是无效的！Why？ 我们有没有办法确定哪个s’偏移量可能是有效偏移？

为什么要问这个问题？ 找到那个计算最小的s’的线索 我们真正找的是P[1..k]在文本P[1..q]中的线索 s’ = s+(q-k) Max k => min s’ 找到那个计算最小的s’的线索 我们真正找的是P[1..k]在文本P[1..q]中的线索 s’ = s+(q-k)

模式的前缀函数        

KMP算法 第8行特别有意思：不再寻找新的s’了，直接比较P[q+1]和T[i]

KMP VS 有限状态机

  与KMP算法极为相似！ 一个是在T中找P，一个是P同自身比较 一个利用\pi，一个计算\pi

问题： 串匹配是否一定要查看T 中每一个字符？

Open Topics: Correctness of the prefix-function computation Correctness of the KMP algorithm

课外作业 TC Ex.32.1-: 2, 3, 4 TC Ex.32.2-: 1, 2, 3, 4 TC Ex.32.3-: 2, 3, 5