1、32|字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？ file:/F/temp/geektime/数据结构与算法之美/32字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？.html2019/1/15 15:36:10 32|字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？ 从今天开始，我们来学习字符串匹配算法。字符串匹配这样一个功能，我想对于任何一个开发工程师来说，应该都不会陌生。我们用的最多的就是编程语言提供 的字符串查找函数，比如Java中的indexOf()，Python中的find()函数等，它们底层就是依赖接下来要讲的字符串匹配算法。 字符串匹配算法很
2、多，我会分四节来讲解。今天我会讲两种比较简单的、好理解的，它们分别是：BF算法和RK算法。下一节，我会讲两种比较难理解、但更加高 效的，它们是：BM算法和KMP算法。 这两节讲的都是单模式串匹配的算法，也就是一个串跟一个串进行匹配。第三节、第四节，我会讲两种多模式串匹配算法，也就是在一个串中同时查找多个串， 它们分别是Trie树和AC自动机。 今天讲的两个算法中，RK算法是BF算法的改进，它巧妙借助了我们前面讲过的哈希算法，让匹配的效率有了很大的提升。那RK算法是如何借助哈希算法来实现 高效字符串匹配的呢？你可以带着这个问题，来学习今天的内容。 BF算法 BF算法中的BF是Brute Forc
3、e的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。从名字可以看出，这种算法的字符串匹配方式很“暴力”，当然也就会比较简 单、好懂，但相应的性能也不高。 在开始讲解这个算法之前，我先定义两个概念，方便我后面讲解。它们分别是主串和模式串。这俩概念很好理解，我举个例子你就懂了。 比方说，我们在字符串A中查找字符串B，那字符串A就是主串，字符串B就是模式串。我们把主串的长度记作n，模式串的长度记作m。因为我们是在主串中查找 模式串，所以nm。 作为最简单、最暴力的字符串匹配算法，BF算法的思想可以用一句话来概括，那就是，我们在主串中，检查起始位置分别是0、1、2n-m且长度为m的n-m+1个 子串，看
4、有没有跟模式串匹配的。我举一个例子给你看看，你应该可以理解得更清楚。 32|字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？ file:/F/temp/geektime/数据结构与算法之美/32字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？.html2019/1/15 15:36:10 从上面的算法思想和例子，我们可以看出，在极端情况下，比如主串是“aaaaaaaaaaa”（省略号表示有很多重复的字符a），模式串是“aaaaab”。我们每次都比 对m个字符，要比对n-m+1次，所以，这种算法的最坏情况时间复杂度是O(n*m)。 尽管理论上，BF算法的时间复杂度很高，是O(
5、n*m)，但在实际的开发中，它却是一个比较常用的字符串匹配算法。为什么这么说呢？原因有两点。 第一，实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候， 就可以就停止了，不需要把m个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度是O(n*m)，但是，统计意义上，大部分情况下，算法执行效率要比这 个高很多。 第二，朴素字符串匹配算法思想简单，代码实现也非常简单。简单意味着不容易出错，如果有bug也容易暴露和修复。在工程中，在满足性能要求的前提下，简单 是首选。这也是我们常说的KISS（Keep it Simp
6、le and Stupid）设计原则。 所以，在实际的软件开发中，绝大部分情况下，朴素的字符串匹配算法就够用了。 32|字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？ file:/F/temp/geektime/数据结构与算法之美/32字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？.html2019/1/15 15:36:10 RK算法 RK算法的全称叫Rabin-Karp算法，是由它的两位发明者Rabin和Karp的名字来命名的。这个算法理解起来也不是很难。我个人觉得，它其实就是刚刚讲的BF算法的 升级版。 我在讲BF算法的时候讲过，如果模式串长度为m，主串长度为n，
7、那在主串中，就会有n-m+1个长度为m的子串，我们只需要暴力地对比这n-m+1个子串与模式串， 就可以找出主串与模式串匹配的子串。 但是，每次检查主串与子串是否匹配，需要依次比对每个字符，所以BF算法的时间复杂度就比较高，是O(n*m)。我们对朴素的字符串匹配算法稍加改造，引入哈 希算法，时间复杂度立刻就会降低。 RK算法的思路是这样的：我们通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相 等，那就说明对应的子串和模式串匹配了（这里先不考虑哈希冲突的问题，后面我们会讲到）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的
8、， 所以模式串和子串比较的效率就提高了。 32|字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？ file:/F/temp/geektime/数据结构与算法之美/32字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？.html2019/1/15 15:36:10 不过，通过哈希算法计算子串的哈希值的时候，我们需要遍历子串中的每个字符。尽管模式串与子串比较的效率提高了，但是，算法整体的效率并没有提高。有 没有方法可以提高哈希算法计算子串哈希值的效率呢？ 这就需要哈希算法设计的非常有技巧了。我们假设要匹配的字符串的字符集中只包含K个字符，我们可以用一个K进制数来表示一个子串，这个
9、K进制数转化成十 进制数，作为子串的哈希值。表述起来有点抽象，我举了一个例子，看完你应该就能懂了。 比如要处理的字符串只包含az这26个小写字母，那我们就用二十六进制来表示一个字符串。我们把az这26个字符映射到025这26个数字，a就表示0，b就表 示1，以此类推，z表示25。 在十进制的表示法中，一个数字的值是通过下面的方式计算出来的。对应到二十六进制，一个包含a到z这26个字符的字符串，计算哈希的时候，我们只需要把进 位从10改成26就可以。 32|字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？ file:/F/temp/geektime/数据结构与算法之美/32字符串匹配基
10、础（上）：如何借助哈希算法实现高效字符串匹配？.html2019/1/15 15:36:10 这个哈希算法你应该看懂了吧？现在，为了方便解释，在下面的讲解中，我假设字符串中只包含az这26个小写字符，我们用二十六进制来表示一个字符串，对 应的哈希值就是二十六进制数转化成十进制的结果。 这种哈希算法有一个特点，在主串中，相邻两个子串的哈希值的计算公式有一定关系。我这有个个例子，你先找一下规律，再来看我后面的讲解。 从这里例子中，我们很容易就能得出这样的规律：相邻两个子串si-1和si（i表示子串在主串中的起始位置，子串的长度都为m），对应的哈希值计算公式有交 集，也就是说，我们可以使用si-1的
11、哈希值很快的计算出si的哈希值。如果用公式表示的话，就是下面这个样子： 32|字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？ file:/F/temp/geektime/数据结构与算法之美/32字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？.html2019/1/15 15:36:10 不过，这里有一个小细节需要注意，那就是26(m-1)这部分的计算，我们可以通过查表的方法来提高效率。我们事先计算好260、261、26226(m-1)，并且 存储在一个长度为m的数组中，公式中的“次方”就对应数组的下标。当我们需要计算26的x次方的时候，就可以从数组的下标为x的位置取值，
12、直接使用，省去了计 算的时间。 32|字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？ file:/F/temp/geektime/数据结构与算法之美/32字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？.html2019/1/15 15:36:10 我们开头的时候提过，RK算法的效率要比BF算法高，现在，我们就来分析一下，RK算法的时间复杂度到底是多少呢？ 整个RK算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。第一部分，我们前面也分析了，可以通过设计特殊的哈希算法，只需要扫描 一遍主串就能计算出所有子串的哈希值了，所以这部分的时间复杂度是O(n)。
13、模式串哈希值与每个子串哈希值之间的比较的时间复杂度是O(1)，总共需要比较n-m+1个子串的哈希值，所以，这部分的时间复杂度也是O(n)。所以，RK算法整体 的时间复杂度就是O(n)。 这里还有一个问题就是，模式串很长，相应的主串中的子串也会很长，通过上面的哈希算法计算得到的哈希值就可能很大，如果超过了计算机中整型数据可以表 示的范围，那该如何解决呢？ 刚刚我们设计的哈希算法是没有散列冲突的，也就是说，一个字符串与一个二十六进制数一一对应，不同的字符串的哈希值肯定不一样。因为我们是基于进制来 表示一个字符串的，你可以类比成十进制、十六进制来思考一下。实际上，我们为了能将哈希值落在整型数据范围内
14、，可以牺牲一下，允许哈希冲突。这个时候 哈希算法该如何设计呢？ 哈希算法的设计方法有很多，我举一个例子说明一下。假设字符串中只包含az这26个英文字母，那我们每个字母对应一个数字，比如a对应1，b对应2，以此类 推，z对应26。我们可以把字符串中每个字母对应的数字相加，最后得到的和作为哈希值。这种哈希算法产生的哈希值的数据范围就相对要小很多了。 不过，你也应该发现，这种哈希算法的哈希冲突概率也是挺高的。当然，我只是举了一个最简单的设计方法，还有很多更加优化的方法，比如将每一个字母从小 到大对应一个素数，而不是1，2，3这样的自然数，这样冲突的概率就会降低一些。 那现在新的问题来了。之前我们只需
15、要比较一下模式串和子串的哈希值，如果两个值相等，那这个子串就一定可以匹配模式串。但是，当存在哈希冲突的时候， 有可能存在这样的情况，子串和模式串的哈希值虽然是相同的，但是两者本身并不匹配。 实际上，解决方法很简单。当我们发现一个子串的哈希值跟模式串的哈希值相等的时候，我们只需要再对比一下子串和模式串本身就好了。当然，如果子串的哈 希值与模式串的哈希值不相等，那对应的子串和模式串肯定也是不匹配的，就不需要比对子串和模式串本身了。 所以，哈希算法的冲突概率要相对控制得低一些，如果存在大量冲突，就会导致RK算法的时间复杂度退化，效率下降。极端情况下，如果存在大量的冲突，每次 都要再对比子串和模式串本
16、身，那时间复杂度就会退化成O(n*m)。但也不要太悲观，一般情况下，冲突不会很多，RK算法的效率还是比BF算法高的。 32|字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？ file:/F/temp/geektime/数据结构与算法之美/32字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？.html2019/1/15 15:36:10 解答开篇 其中, hi、hi-1 分别对应 si 和 si-1 两个子串的哈希值 - 文中这个公式，26*(hi-1-26(m-1)*hi-1)可以化简为26*hi-1*(1-26(m-1)，所以这里是不是应该改为26*(hi-1-26(m-
17、1)*si-1)，用si-1代表当前位置的字 符串的值，例如图中d的值是3，同样的公式后面加 hi+m-1是不是也是si+m-1呢 5赞 作者回复2018-12-05 05:28:21 写错了 感谢指正 已经改了 Smallfly 2018-12-05 14:36:56 思考题： 以模式串矩阵的大小，去匹配主串矩阵，每个小矩阵可以构建成字符串，就能用 RK 算法做字符串匹配了。 如果主串的大小是 M * N，模式串大小为 m * n，则时间复杂度为 (M - m + 1) * (N - n + 1)。 4赞 煦暖 2018-12-05 07:58:13 “hi = 26*(hi-1-26(m-
18、1)*hi-1) + hi+m-1;其中, hi、hi-1 分别对应 si 和 si-1 两个子串的哈希值。”老师你好，26(m-1)*hi-1中的hi-1和hi+m-1应该 是一个字符的哈希值而不应该是子串的哈希值吧？PS：用您的例子套用公式：h0 = 3*26*26+1*26+2 = 2056；h1=26*(h0-26*26*h0)+(4*26*26+3*26+4) = -36 080014 和期望的哈希值1*26*26+2*26+4=732不符。 3赞 qinggeouye 2018-12-31 14:06:56 RK 算法，计算相邻两个子串哈希值的规律，比如，相邻两个子串分别为 “db
19、c“ 和 “bce“，那么 si-1 = d，si=b ，与 a 相减意思是，它们的 ASCII 码值的 差值正好表示字母的数值； 32|字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？ file:/F/temp/geektime/数据结构与算法之美/32字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？.html2019/1/15 15:36:10 评论中有同学不明白老师给的哈希值 hi 和 hi-1 之间的关系，我想应该是 si 和 si-1 代表什么这点没明白。 2赞 大刚 2018-12-20 01:44:31 老师，下面的不懂，能不能在详细讲解下 hi = 26*(
20、hi-1-26(m-1)*(si-1-a) + (si+m-1-a); 2赞 coulson 2018-12-05 09:31:43 老师，前天面试被问到一个问题，关于地图算法的，比如线路推荐。请问地图算法会讲到么 2赞 作者回复2018-12-06 02:12:55 在高级篇那部分会涉及一点 王婵 2018-12-05 03:12:14 思考题二维数组用RK算法计算哈希值要复杂一些，i-1 j-1不越界的情况下，如果模式串的行数大于列数可以通过hi-1,j计算hi,j，如果列数大于行数可以通 过hi,j-1计算hi,j 还有更好的方法计算哈希值吗？ 另外正文里的计算哈希值的公式貌似写错了，应
21、该是 hi = 26*(hi-1-26(m-1)*(si-1-a) + (si+m-1-a); 2赞 yaya 2018-12-05 02:07:08 二维矩阵只要如果以ij为左上角，即可定义一个i.j i+1.j i. j+1 i+1.j+1的子串，其本质是和字符串相同的，即可以由rf又可以由bf解 2赞 坔坔x 2) return x; long p = 1, q = x; long mid; while (p = q) mid = (p + q) / 2; if (mid = x / mid) return mid; else if (mid float64(x) high = mid delta = mid*mid - float64(x) else low = mid delta = float64(x) - mid*mid if delta 0.01 return int(mid) func main() fmt.Println(mySqrt(8)
个人主页