Chinaunix首页 | 论坛 | 博客
  • 博客访问: 389526
  • 博文数量: 62
  • 博客积分: 388
  • 博客等级: 一等列兵
  • 技术积分: 1032
  • 用 户 组: 普通用户
  • 注册时间: 2012-02-03 20:18
文章分类

全部博文(62)

文章存档

2017年(5)

2016年(3)

2015年(3)

2014年(8)

2013年(15)

2012年(28)

分类:

2012-02-07 09:42:20

作者: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值。

大致的代码如下:
  1. static void cal_next_table(const char *pattern, int len, int *table)
  2. {
  3.    int i,j;
     /* table[0] 为哨兵 */  
     table[0] = 1;
  1.     for (i = 1; i <= len; ++i) {
  2.         table[i] = table[i-1];
  3.         for (j = table[i]; j < i; ++j) {
  4.             if (0 != strncmp(pattern, pattern+j, i-j-1)) {
  5.                 table[i]++;
  6.             }
  7.             else {
  8.                 break;
  9.             }
  10.         }
  11.     }
  12. }
通过上面的函数,将生成右移的table表。当第n个不匹配时,可以向右滑动table[n]个字符。

下面是测试代码:
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>

  4. static void cal_next_table(const char *pattern, int len, int *table)
  5. {
  6.     int i,j;

  7.      table[0] = 1;
  8.     for (i = 1; i <= len; ++i) {
  9.         table[i] = table[i-1];
  10.         for (j = table[i]; j < i; ++j) {
  11.             if (0 != strncmp(pattern, pattern+j, i-j-1)) {
  12.                 table[i]++;
  13.             }
  14.             else {
  15.                 break;
  16.             }
  17.         }
  18.     }
  19. }


  20. int main()
  21. {
  22.     char pattern[] = "abcabcdef";
  23.     int table[sizeof(pattern)+1] = {};

  24.     cal_next_table(pattern, sizeof(pattern), table);

  25.     int i;
  26.     printf("%s\n", pattern);

  27.     for (i = 1; i < sizeof(pattern); ++i) {
  28.         printf("%d", table[i]);
  29.     }
  30.     printf("\n");

  31.     return 0;
  32. }
结果如下:
  1. abcabcdef
  2. 112333378


最后总结一下,我们从KMP算法中可以获得什么?除了知道这个字符串匹配算法,我们还要争取 获得更多的东西,比如即尽可能的从已经处理过得操作或数据中获得更多的信息。
阅读(794) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~