注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

平安甜橙博客

家俭则兴,人勤则健,能勤能俭,永不贫贱

 
 
 

日志

 
 
 
 

【转载】字符串编辑距离  

2017-12-11 11:13:48|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本文转载自jia_huiqiang《字符串编辑距离》

一、定义

      定义:将一个字符串转换成另一个字符串时需要付出的代价。转换可以采用插入、删除和替换三种编辑方式,转换的代价就是对字符串的编辑次数,不同的转换方法需要的编辑次数也不一样,最少的那个编辑次数就是字符串的编辑距离。

二、算法实现

递归算法实现:

int  edit_distance(char *src, char *dest)

{

      if((0==strlen(src) || (0==strlen(dest))  

            return abs(strlen(src)-strlen(dest));

     if ((dest[0]==src[0]))

           return edit_distance(src+1,dest+1);

       int insertion=edit_distance(src,dest+1)+1;

       int deletion=edit_distance(src+1,dest)+1;

       int replace=edit_distance(src+1,dest+1)+1;

       return min(min(insetion,deletion),replace);

}

 

动态规划算法实现:

typedef struct dynamic_programming

{

     long int distance;//编辑距离,初始化为0xFFFF,表示一个无效状态

    long int reference_count;//记录状态被应用的次数,0表示没有这个状态记录

}dp;

long int s_maxoflength=strlen(src);

long int t_maxoflenght=strlen(dest);

dp memory[s_maxoflenth][t_maxoflenth];

memory[0][0].distance=0xFFFF;

memory[0][0].reference_count=0;

int edit_distance(char *src,char *dest,int i,int j)

{

    if(0!=memory[i][j].referece_count)

   {

      memory[i][j].reference_count++;

     return memory[i][j].distance;

  }

  int distance=0;

  if(0==strlen(src+i))

  {

      distance=strlen(dest+j);

  }

  else if (0==strlen(dest+j))

   {

         distance=strlen(src+i);

   }

  else

   {

      if(src[i]==dest[j]) distance=edit_distance(src,dest,i+1,j+1);

     else

      {

          int insertion=edit_distance(src,dest,i,j_1)+1;

          int deletion=edit_distance(src,dest,i+1,j)+1;

          int replace=edit_distance(src,dest,i+1,j+1)+1;

          distance=min(min(insertion,deletion),replace);

       }

    }

   memory[i][j].distance=distance;

   memorty[i][j].reference_count=1;

}

确定了递推关系和边界条件的动态规划算法:

int  edit_distance(char *src,char *dest)

{

    int d[s_maxoflenth][t_maxoflenth]={0xFFFF};

    for(long int i=0;i<=strlen(src);i++) d[i][0]=i;

    for(long int j=0;j<=strlen(dest);j++) d[0][j]=j;

   for(long int i=1;i<=strlen(src);i++)

 {

         for(long int j=1;j<=strlen(dest);j++)

        {

              if(src[i-1]==dest[j=1])    d[i][j]=d[i-1][j-1];

             else

                 {

                         int insertion=d[i][j-1]+1;

                        int deletion=d[i-1][j]+1;

                         int replace=d[i-1][j-1]+1;

                        d[i][j]=min(min(insertion,deletion),replace);

                 }

         }

  }

   return d[strlen(src)][strlen(dest)];

}

  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018