30图的表示:如何存储微博、微信等社交网络中的好友关系?.pdf
《30图的表示:如何存储微博、微信等社交网络中的好友关系?.pdf》由会员分享,可在线阅读,更多相关《30图的表示:如何存储微博、微信等社交网络中的好友关系?.pdf(15页珍藏版)》请在文库网上搜索。
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的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 30 表示 如何 存储 社交 网络 中的 好友 关系