作者:gfree.wind@gmail.com
博客:blog.focus-linux.net linuxfocus.blog.chinaunix.net
上次说过要换一种方式去学习算法,这段时间在看《Algorithm In C》,上周正好看完了String Search这一章。先拿这章中介绍的算法来试一下效果吧。
先再重复一下我这次学习算法的一些新想法,以前学算法,总是去学习算法本身的东西,而没有深究为什么算法这样设计,为什么效率高。结果导致学习的效果并不是很好。这次算法学习的过程中,决定好好的想一下这个问题。另外,对于一般开发人员来说,包括我,大部分不是研究型的开发,对于我们来说,重要的不是去通过数学的手段去定量的去证明算法的先进性——关于这一点,估计会有很多人拍砖,这只是我一点拙见,仁者见仁智者见智吧。
毕业这么多年了,数学的东西也基本忘光了,所以下面对于算法的分析,都是大白话,只探求基本原理,并不深究细节。
Knuth-Morris-Pratt 算法,又称KMP算法
主要思想:当patter在某一位置与string匹配失败时,我们除了知道从string的这个位置进行匹配失败这个结果外,是否可以从前面的匹配中获得更多的信息呢。至少还有一个信息,匹配失败前面的字符串,我们已经知道。例如:
abcabcabcdef --------- string
abcabcdef --------- pattern
当匹配到第7个字符时,虽然匹配失败了,但是除了这个结果,我们还可以知道string前面的字符串是已经匹配成功了的字符串,即abcabc。而patter本身是abcabcdef,那么就可以知道至少需要向右滑动3个字符,才可能匹配:
abcabcabcdef
abcabcdef
KMP就是利用已经匹配了的字符串这个信息,来进行尽可能的向右滑动,避免无谓的比较。
那么究竟当不匹配的时候,可以向右滑动多远呢?
以上面的pattern "abcabcdef"为例:
当第一个字符不匹配的时候,没有额外信息,那么就向右滑动1个字符。
当第二个字符不匹配的时候,说明之前匹配的字符为a,但是我们是第二个字符不匹配,还是只能向右滑动1个字符。
当第三个字符不匹配的时候,说明之前匹配的字符为ab,那么可以向右滑动2位;
当第四个字符不匹配的时候,说明之前匹配的字符为abc,那么可以向右滑动3位;
当第五个字符不匹配的时候,说明之前匹配的字符为abca,那么也只能向右滑动3位;
。。。。。。
那么KMP算法的关键问题就是计算pattern某位置匹配失败的时候,可以向右滑动的位数。
下面白话一下如何计算这个滑动位数,0匹配和1匹配时,向右滑动都为1。那么当在第n(n>=2)不匹配时,那么我们可以从偏移1位到m位进行尝试,m最大为n-1。只要0 != strncmp(pattern, pattern+m, n-m-1),那么就可以继续增加m值。
大致的代码如下:
- static void cal_next_table(const char *pattern, int len, int *table)
-
{
-
int i,j;
/* table[0] 为哨兵 */
table[0] = 1;
-
for (i = 1; i <= len; ++i) {
-
table[i] = table[i-1];
-
for (j = table[i]; j < i; ++j) {
-
if (0 != strncmp(pattern, pattern+j, i-j-1)) {
-
table[i]++;
-
}
-
else {
-
break;
-
}
-
}
-
}
-
}
通过上面的函数,将生成右移的table表。当第n个不匹配时,可以向右滑动table[n]个字符。
下面是测试代码:
- #include <stdlib.h>
-
#include <stdio.h>
-
#include <string.h>
-
-
static void cal_next_table(const char *pattern, int len, int *table)
-
{
-
int i,j;
-
-
table[0] = 1;
-
for (i = 1; i <= len; ++i) {
-
table[i] = table[i-1];
-
for (j = table[i]; j < i; ++j) {
-
if (0 != strncmp(pattern, pattern+j, i-j-1)) {
-
table[i]++;
-
}
-
else {
-
break;
-
}
-
}
-
}
-
}
-
-
-
int main()
-
{
-
char pattern[] = "abcabcdef";
-
int table[sizeof(pattern)+1] = {};
-
-
cal_next_table(pattern, sizeof(pattern), table);
-
-
int i;
-
printf("%s\n", pattern);
-
-
for (i = 1; i < sizeof(pattern); ++i) {
-
printf("%d", table[i]);
-
}
-
printf("\n");
-
-
return 0;
-
}
结果如下:
最后总结一下,我们从KMP算法中可以获得什么?除了知道这个字符串匹配算法,我们还要争取 获得更多的东西,比如即尽可能的从已经处理过得操作或数据中获得更多的信息。
阅读(794) | 评论(0) | 转发(0) |