Electronic Joint Business

Solution for E-Business

字符串查找算法 (二) Rabin-Karp 算法

文章评价: 暴力字符串匹配(brute force string matching)是子串匹配算法中最基本的一种,它确实有自己的优点,比如它并不需要对文本(text)或模式串(pattern)进行预处理。然而它最大的问题就是运行速度太慢,所以在很多场合下暴力字符串匹配算法并不是那么有用。我们需要一些更快的方法来完成模式匹配的工作,然而在此之前,我们还是回过头来再看一遍暴力法匹配,以便更好地理解其他子串匹配算法。 如下图所示,在暴力字符串匹配里,我们将文本中的每一个字符和模式串的第一个字符进行比对。一旦我们找到了一个匹配,我们就将文本中写一个字符取出来和模式串的第二个字符进行比较。 该算法运行速度慢的主要原因有二:一方面,我们需要对文本中的每个字符都进行比对;另一方面,即使我们发现模式串首字符和文本中的某个字符相匹配,我们仍然需要对模式串中剩下的所有符号(字符)挨个进行比对,才知道它们是不是出现在接下来的文本中。那么,是否有别的方法可以用来判断文本是否包含模式串呢? 答案是肯定的,确实存在一种更快的方法。为了避免挨个字符对文本和模式串进行比较,我们可以尝试一次性判断两者是否相等。因此,我们需要一个好的哈希函数(hash function)。通过哈希函数,我们可以算出模式串的哈希值,然后将它和文本中的子串的哈希值进行比较。这里有一个问题,我们必须保证该哈希函数能够对一个较长的字符串返回较短的哈希值。然而,我们又不能指望较长的模式串能得到较短的哈希值。但除此之外,这个新方法在速度上应该能比暴力法有显著提升。 这种更快的方法就是Rabin-Karp算法。 概述 Michael O. Rabin和Richard M. Karp在1987年提出一个想法,即可以对模式串进行哈希运算并将其哈希值与文本中子串的哈希值进行比对。总的来说这一想法非常浅显,唯一的问题在于我们需要找到一个哈希函数,它需要能够对不同的字符串返回不同的哈希值。例如,该哈希函数可能会对每个字符的ASCII码进行算,但同时我们也需要仔细考虑对多语种文本的支持。 哈希算法可以有很多种不同的形式,它可能包含 ASCII 码字符以便对数字进行转化,但也可能是别的形式。我们唯一需要的就是将一个字符串(模式串)转化成为能够快速进行比较的哈希值。以”hello world”为例,假设它的哈希值hash(‘hello world’)=12345。那么如果hash(‘he’)=1,那么我们就可以说模式串”he”包含在文本”hello world”中。由此,我们可以每次从文本中取出长度为m(m为模式串的长度)的子串,然后将该子串进行哈希,并将其哈希值与模式串的哈希值进行比较。 实现 为了实现这一目的,Rabin-Karp设计了一个巧妙的hash算法。首先计算pattern的hash值,然后在从sring的开头,计算相同长度字符串的hash值。若hash值相同,则表示匹配,若不同,则向右移动一位,计算新的hash值。 整个过程,与暴力的字符串匹配算法很相似,但由于计算hash值时,可以利用上一次的hash值,从而使新的hash值只需要加上新字母的计算,并减去上一次的第一个字母的计算,即可。这样相当于后面的每次匹配,只需要考虑一个新的字母,并减去一个老的字母,无疑极大的提高了效率——尤其是 pattern 的字符串很长的情况下。 #define tonum(c) (c >= ‘A’ && c <= ‘Z’ ? c – ‘A’ : c – ‘a’ + 26) /* return a^p mod m */ int mod(int a,int […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.