字符串近似匹配算法

发表日期：2008-3-8

新浪微博 QQ空间 QQ微博百度搜藏腾讯朋友 QQ收藏百度空间人人网开心网

　　字符串的近似匹配，就是答应在匹配时有一定的误差，比如在字串“以前高手好久不见”中找“以前是高手”也能成功。具体地说，错误可以有三种类型：加字符（以前也是高手）、漏字符（以前高手）和替换字符（以前石膏手）。下面的函数在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);
  assert(m-k>0);
  assert((m-k)*(k+2)<= 64);
  int j;
  __int64 Din = 0;
  __int64 M1 = 0;
  __int64 M2 = 0;
  __int64 M3 = 0;
  __int64 G = 1 << k;
  int onekp1 = (1 << (k+1)) - 1;
  for (j=0; j<m-k; j++)
  {
    Din = (Din << (k+2))onekp1;
    M1 = (M1 << (k+2))1;
    if (j < m-k-1)
      M2 = (M2 << (k+2)) 1;
  }
  M2=(M2<<(k+2))onekp1;
  __int64 D=Din;
  const char* s=text;
  int c=*s++;
  while(c)
  {
    int found=0;
    const char* sp=pat;
    for(j=0;j<k+1;j++)
    {
      int cp=*sp++;
      if(c==cp)
      {
        found=1;
        break;
      }
    }
    if(found)
    {
      do
      {
        __int64 tc = 0;
        const char* sp = pat;
        for (j=0; j<m; j++)
        {
          int cp = *sp++;
          if (c!=cp)
          c=(1<<j);
        }
        __int64 Tc = 0;
        for (j=0; j<m-k; j++)
        Tc = (Tc<<(k+2))((tc>>j)&onekp1);
        __int64 x = (D>>(k+2))Tc;
        D=((D<<1)M1)&((D<<(k+3))M2)&(((x+M1)^x)>>1)&Din;
        if((D & G) == 0)
          return (char*)s;
        if(D != Din)
          c = *s++;
      }
      while ( D != Din && c);
   }
   if (c)
     c = *s++;
}
return NULL;
}

关注此文的读者还看过：
·2012-5-22 16:08:41 深入探讨C++中的引用
·2012-5-22 16:08:38 自己对三层架构理论的理解
·2012-5-22 16:08:33 限次程序C语言源码
·2012-5-22 16:07:54 有趣的分形学Mandlbrot集图形的一个C语言实现
·2012-5-22 16:07:18 ASP.NET在线用户列表精确版——解决用户意外退出在线列表无法及时更新问题
·2012-5-22 16:06:23 DShow中实现抓图的几种方法
·2012-5-22 16:06:06 有关遗传算法
·2012-5-22 16:05:35 C++箴言：最小化文件之间的编译依赖
·2012-5-22 16:03:46 C程序设计语言概论(2)

站长推荐 PS笔刷下载在线翻译系统进程广告代码

发表评论
姓　名:	验证码:
内　容:

教程搜索服务

项目外包信息

·寻会php的程序员外包网站
·派桑网络-网络营销专家
·汽车配件网站制作 50000元
·整站SEO优化
·课件门户网程序
·求长期合作网站设计制作高手
·公司网站重新改版 8000元
·asp企业网站小改动
·网站flash片头
·文化传播公司网站设计稿
·UI界面设计
·产品外观改版设计 15000元
·照明灯具网站设计 10000元
·求长期合作网站设计制作高手
·做B2C网站 20000元

发布信息

浏览信息

邮件订阅服务

输入你的邮件地址，你将不会错过任何关于<C/C++教程>的内容

网络编程文章分类

ASP教程
ASP实例
ASP技巧
ASP文摘
PHP教程
PHP技巧
PHP实例
PHP文摘
JSP教程
JSP技巧
JSP实例
JSP文摘
ASP.NET教程
ASP.NET技巧
ASP.NET实例
ASP.NET应用
xml教程
xsl教程
xml技巧
C#教程
C#应用
Delphi教程
Perl教程
Shell教程
Ajax教程
Visual Basic教程
Java教程
J2EE/J2ME教程
C/C++教程
移动解决方案
移动短信技术
移动行业动态
软件工程
WordPress
Android开发