字符串近似匹配算法

keehoo

字符串的近似匹配，就是允许在匹配时有一定的误差，比如在字串“以前高手好久不见”中找“以前是高手”也能成功。具体地说，错误可以有三种类型：加字符（以前也是高手）、漏字符（以前高手）和替换字符（以前石膏手）。下面的函数在text中查找子串pat，最多允许有k个错误。返回的是匹配的终点（我还没想好如何确定起点，呵呵）。
至于算法的原理，现在一下子说不清楚，只能说这是一个非确定性有限自动机，以后有时间的话再详细介绍。有兴趣的话可以自己去看文章《Faster Approximate String Matching》, Algorithmica (1999) 23: 127-158。

算法的限制：(m-k)*(k+2) <= 64, 这里m是子串的长度。那个64是因为哦用了64位整数来编码自动机的状态。如果允许两个错误，则子串最长为18个字符，对一般应用来说足够了。

1. char* amatch(const char* text, const char* pat, int k)
   
2. {
   
3.   int m = strlen(pat);
   
4.   assert(m-k&gt;0);
   
5.   assert((m-k)*(k+2)<= 64);
   
6.   int j;
   
7.   __int64 Din = 0;
   
8.   __int64 M1 = 0;
   
9.   __int64 M2 = 0;
   
10.   __int64 M3 = 0;
    
11.   __int64 G = 1 << k;
    
12.   int onekp1 = (1 << (k+1)) - 1;
    
13.   for (j=0; j<m-k; j++)
    
14.   {
    
15.     Din = (Din << (k+2))|onekp1;
    
16.     M1 = (M1 << (k+2))|1;
    
17.     if (j < m-k-1)
    
18.       M2 = (M2 << (k+2)) | 1;
    
19.   }
    
20.   M2=(M2<<(k+2))|onekp1;
    
21.   __int64 D=Din;
    
22.   const char* s=text;
    
23.   int c=*s++;
    
24.   while(c)
    
25.   {
    
26.     int found=0;
    
27.     const char* sp=pat;
    
28.     for(j=0;j<k+1;j++)
    
29.     {
    
30.       int cp=*sp++;
    
31.       if(c==cp)
    
32.       {
    
33.         found=1;
    
34.         break;
    
35.       }
    
36.     }
    
37.     if(found)
    
38.     {
    
39.       do
    
40.       {
    
41.         __int64 tc = 0;
    
42.         const char* sp = pat;
    
43.         for (j=0; j<m; j++)
    
44.         {
    
45.           int cp = *sp++;
    
46.           if (c!=cp)
    
47.           c|=(1<<j);
    
48.         }
    
49.         __int64 Tc = 0;
    
50.         for (j=0; j<m-k; j++)
    
51.         Tc = (Tc<<(k+2))|((tc&gt;>j)&onekp1);
    
52.         __int64 x = (D&gt;>(k+2))|Tc;
    
53.         D=((D<<1)|M1)&((D<<(k+3))|M2)&(((x+M1)^x)&gt;>1)&Din;
    
54.         if((D & G) == 0)
    
55.           return (char*)s;
    
56.         if(D != Din)
    
57.           c = *s++;
    
58.       }
    
59.       while ( D != Din && c);
    
60.    }
    
61.    if (c)
    
62.      c = *s++;
    
63. }
    
64. return NULL;
    
65. }  

复制代码

fanasy

谢谢分享

noword2k

看看这个吧：http://blog.youxu.info/spell-correct.html
goolge的工程师，在飞机上写的20多行的python代码。
原文的后面，有C语言的版本。

zhujiang73

keehoo 发表于 2011-12-20 11:28
字符串的近似匹配，就是允许在匹配时有一定的误差，比如在字串“以前高手好久不见”中找“以前是高手”也能 ...

     这个不错。{:3_189:}