欢迎来到天天文库
浏览记录
ID:12175377
大小:26.00 KB
页数:3页
时间:2018-07-16
《字符串近似匹配算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、字符串近似匹配算法关键字:字符串近似匹配算法作者:以前是高手 更新:2003-03-01 浏览:5628字符串的近似匹配,就是允许在匹配时有一定的误差,比如在字串“以前高手好久不见”中找“以前是高手”也能成功。具体地说,错误可以有三种类型:加字符(以前也是高手)、漏字符(以前高手)和替换字符(以前石膏手)。下面的函数在text中查找子串pat,最多允许有k个错误。返回的是匹配的终点(我还没想好如何确定起点,呵呵)。至于算法的原理,现在一下子说不清楚,只能说这是一个非确定性有限自动机,以后有时间的话再详细介绍。有兴趣的话可以自己去看文章《FasterApproximat
2、eStringMatching》,Algorithmica(1999)23:127-158。算法的限制:(m-k)*(k+2)<=64,这里m是子串的长度。那个64是因为哦用了64位整数来编码自动机的状态。如果允许两个错误,则子串最长为18个字符,对一般应用来说足够了。好了,废话少说,看算法吧。看不懂?没事了,哦也是半懂半不懂的。char*amatch(constchar*text,constchar*pat,intk){ intm=strlen(pat); assert(m-k>0); assert((m-k)*(k+2)<=64); intj; __int6
3、4Din=0; __int64M1=0; __int64M2=0; __int64M3=0; __int64G=1<4、onekp1; M1=(M1<<(k+2))5、1; if(j6、1; } M2=(M2<<(k+2))7、onekp1; __int64D=Din; constchar*s=text; intc=*s++; while(c) { 8、 intfound=0; constchar*sp=pat; for(j=0;j9、 for(j=0;j10、=(1<11、((tc>>j)&onekp1); __int64x=(D>>(k+2))12、Tc; D=((D<<1)13、M1)&((D<<(k+3))14、M2)&(((x+M1)^x)>>1)&Din; if((D&15、G)==0) return(char*)s; if(D!=Din) c=*s++; } while(D!=Din&&c); } if(c) c=*s++;}returnNULL;}
4、onekp1; M1=(M1<<(k+2))
5、1; if(j6、1; } M2=(M2<<(k+2))7、onekp1; __int64D=Din; constchar*s=text; intc=*s++; while(c) { 8、 intfound=0; constchar*sp=pat; for(j=0;j9、 for(j=0;j10、=(1<11、((tc>>j)&onekp1); __int64x=(D>>(k+2))12、Tc; D=((D<<1)13、M1)&((D<<(k+3))14、M2)&(((x+M1)^x)>>1)&Din; if((D&15、G)==0) return(char*)s; if(D!=Din) c=*s++; } while(D!=Din&&c); } if(c) c=*s++;}returnNULL;}
6、1; } M2=(M2<<(k+2))
7、onekp1; __int64D=Din; constchar*s=text; intc=*s++; while(c) {
8、 intfound=0; constchar*sp=pat; for(j=0;j9、 for(j=0;j10、=(1<11、((tc>>j)&onekp1); __int64x=(D>>(k+2))12、Tc; D=((D<<1)13、M1)&((D<<(k+3))14、M2)&(((x+M1)^x)>>1)&Din; if((D&15、G)==0) return(char*)s; if(D!=Din) c=*s++; } while(D!=Din&&c); } if(c) c=*s++;}returnNULL;}
9、 for(j=0;j10、=(1<11、((tc>>j)&onekp1); __int64x=(D>>(k+2))12、Tc; D=((D<<1)13、M1)&((D<<(k+3))14、M2)&(((x+M1)^x)>>1)&Din; if((D&15、G)==0) return(char*)s; if(D!=Din) c=*s++; } while(D!=Din&&c); } if(c) c=*s++;}returnNULL;}
10、=(1<11、((tc>>j)&onekp1); __int64x=(D>>(k+2))12、Tc; D=((D<<1)13、M1)&((D<<(k+3))14、M2)&(((x+M1)^x)>>1)&Din; if((D&15、G)==0) return(char*)s; if(D!=Din) c=*s++; } while(D!=Din&&c); } if(c) c=*s++;}returnNULL;}
11、((tc>>j)&onekp1); __int64x=(D>>(k+2))
12、Tc; D=((D<<1)
13、M1)&((D<<(k+3))
14、M2)&(((x+M1)^x)>>1)&Din; if((D&
15、G)==0) return(char*)s; if(D!=Din) c=*s++; } while(D!=Din&&c); } if(c) c=*s++;}returnNULL;}
此文档下载收益归作者所有