Chinaunix首页 | 论坛 | 博客
  • 博客访问: 7376651
  • 博文数量: 159
  • 博客积分: 10424
  • 博客等级: 少将
  • 技术积分: 14605
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-14 12:45
个人简介

啦啦啦~~~

文章分类
文章存档

2015年(5)

2014年(1)

2013年(5)

2012年(10)

2011年(116)

2010年(22)

分类: C/C++

2011-10-30 23:31:36

作者:gfree.wind@gmail.com
博客:blog.focus-linux.net  linuxfocus.blog.chinaunix.net

今天是《Algorithms In C》中关于字符串匹配算法中的最后一个,Rabin-Karp算法。

前面分析的KMP算法和BM算法的设计思路,都是通过前面已经比较过的字符,来对未来的匹配进行预判,实现最大的向右滑动。或者说通过这个预判,使下一次的比较更接近匹配的字符串。

而Rabin-Karp算法的设计思想也是利用前面已经匹配的字符。不过不同的是,Rabin-Karp算法不是未来这些信息去预判匹配的字符串,而是利用前面匹配字符的结果,使下一次匹配进行的更快。
——Rabin-Karp的具体实现请自行google。

为了实现这一目的,Rabin-Karp设计了一个巧妙的hash算法。首先计算pattern的hash值,然后在从sring的开头,计算相同长度字符串的hash值。若hash值相同,则表示匹配,若不同,则向右移动一位,计算新的hash值。

整个过程,与暴力的字符串匹配算法很相似,但由于计算hash值时,可以利用上一次的hash值,从而使新的hash值只需要加上新字母的计算,并减去上一次的第一个字母的计算,即可。这样相当于后面的每次匹配,只需要考虑一个新的字母,并减去一个老的字母,无疑极大的提高了效率——尤其是pattern的字符串很长的情况下。

那么这个hash是如何实现的呢?

hash(w[0 .. m-1])=(w[0]*2m-1w[1]*2m-2+···+ w[m-1]*20) mod q
where q is a large number.

Then, rehash(a,b,h)= ((h-a*2m-1)*2+b) mod q

上面给出这个hash的一个设计实。当不匹配时,rehash为再次hash的值,a为上次的第一个字母,b为新的字母。


下面小小的总结一下,这三个字符串匹配算法都是利用已经比较的字母,从中获得某些信息,从而提高自己的效率。而且思路却各不相同,我们需要去想,他们是如何去想出这个算法的。以前我也想过如何利用hash去实现字符串匹配,可是却觉得计算这个hash不一定比暴力算法高效多少。当时我有一个思路时,从要进行比较的字符串中,部分的进行hash,当hash不同,那么一定不匹配,hash相同则再进行字符串匹配。一般情况下,当不匹配时hash值都不同,所以可以减少一些不必要的匹配。但是还是没有想到今天这种算法。



参考:
1. 

阅读(9151) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~