首页 相关文章 字符串近似匹配算法

字符串近似匹配算法


  字符串的近似匹配,就是答应在匹配时有一定的误差,比如在字串“以前高手好久不见”中找“以前是高手”也能成功。具体地说,错误可以有三种类型:加字符(以前也是高手)、漏字符(以前高手)和替换字符(以前石膏手)。下面的函数在text中查找子串pat,最多答应有k个错误。返回的是匹配的终点(我还没想好如何确定起点,呵呵)。
  至于算法的原理,现在一下子说不清楚,只能说这是一个非确定性有限自动机,以后有时间的话再具体介绍。有爱好的话可以自己去看文章《Faster Approximate String Matching》, Algorithmica (1999) 23: 127-158。
  
  算法的限制:(m-k)*(k+2) = 64, 这里m是子串的长度。那个64是因为哦用了64位整数来编码自动机的状态。假如答应两个错误,则子串最长为18个字符,对一般应用来说足够了。
  
  好了,废话少说,看算法吧。看不懂?没事了,哦也是半懂半不懂的。
  
  char* amatch(const char* text, const char* pat, int k)
  {
   int m = strlen(pat);[ 查看全文 ]

2016-02-19 标签:

字符串近似匹配算法的相关文章

手机页面
收藏网站 回到头部