阿牛CPP

“中国就有这么一群奇怪的人, 本身是最底阶层, 利益每天都在被损害,却具有统治阶级的意识. 在动物世界里找这么弱智的东西都几乎不可能。” ——林语堂

字符串相似度算法( Levenshtein Distance算法)

昨天论坛看到的,简单写了一下
题目: 一个字符串可以通过增加一个字符,删除一个字符,替换一个字符得到另外一个字符串,假设,我们把从字符串A转换成字符串B,前面3种操作所执行的最少次数称为AB相似度
如  abc adc  度为 1
      ababababa babababab 度为 2
      abcd acdb 度为2


 字符串相似度算法可以使用 Levenshtein Distance算法(中文翻译:编辑距离算法) 这算法是由俄国科学家Levenshtein提出的。其步骤

Step Description
1 Set n to be the length of s.
Set m to be the length of t.
If n = 0, return m and exit.
If m = 0, return n and exit.
Construct a matrix containing 0..m rows and 0..n columns.
2 Initialize the first row to 0..n.
Initialize the first column to 0..m.
3 Examine each character of s (i from 1 to n).
4 Examine each character of t (j from 1 to m).
5 If s[i] equals t[j], the cost is 0.
If s[i] doesn't equal t[j], the cost is 1.
6 Set cell d[i,j] of the matrix equal to the minimum of:
a. The cell immediately above plus 1: d[i-1,j] + 1.
b. The cell immediately to the left plus 1: d[i,j-1] + 1.
c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost.
7 After the iteration steps (3, 4, 5, 6) are complete, the distance is found in cell d[n,m].

C++实现如下
#include <iostream>
#include 
<vector>
#include 
<string>
using namespace std;

//算法
int ldistance(const string source,const string target)
{
    
//step 1

    
int n=source.length();
    
int m=target.length();
    
if (m==0return n;
    
if (n==0return m;
    
//Construct a matrix
    typedef vector< vector<int> >  Tmatrix;
    Tmatrix matrix(n
+1);
    
for(int i=0; i<=n; i++)  matrix[i].resize(m+1);

    
//step 2 Initialize

    
for(int i=1;i<=n;i++) matrix[i][0]=i;
    
for(int i=1;i<=m;i++) matrix[0][i]=i;

     
//step 3
     for(int i=1;i<=n;i++)
     
{
        
const char si=source[i-1];
        
//step 4
        for(int j=1;j<=m;j++)
        
{

            
const char dj=target[j-1];
            
//step 5
            int cost;
            
if(si==dj){
                cost
=0;
            }

            
else{
                cost
=1;
            }

            
//step 6
            const int above=matrix[i-1][j]+1;
            
const int left=matrix[i][j-1]+1;
            
const int diag=matrix[i-1][j-1]+cost;
            matrix[i][j]
=min(above,min(left,diag));

        }

     }
//step7
      return matrix[n][m];
}

int main(){
    
string s;
    
string d;
    cout
<<"source=";
    cin
>>s;
    cout
<<"diag=";
    cin
>>d;
    
int dist=ldistance(s,d);
    cout
<<"dist="<<dist<<endl;
}

#include 
<iostream>
#include 
<vector>
#include 
<string>
using namespace std;

//算法
int ldistance(const string source,const string target)
{
    
//step 1

    
int n=source.length();
    
int m=target.length();
    
if (m==0return n;
    
if (n==0return m;
    
//Construct a matrix
    typedef vector< vector<int> >  Tmatrix;
    Tmatrix matrix(n
+1);
    
for(int i=0; i<=n; i++)  matrix[i].resize(m+1);

    
//step 2 Initialize

    
for(int i=1;i<=n;i++) matrix[i][0]=i;
    
for(int i=1;i<=m;i++) matrix[0][i]=i;

     
//step 3
     for(int i=1;i<=n;i++)
     
{
        
const char si=source[i-1];
        
//step 4
        for(int j=1;j<=m;j++)
        
{

            
const char dj=target[j-1];
            
//step 5
            int cost;
            
if(si==dj){
                cost
=0;
            }

            
else{
                cost
=1;
            }

            
//step 6
            const int above=matrix[i-1][j]+1;
            
const int left=matrix[i][j-1]+1;
            
const int diag=matrix[i-1][j-1]+cost;
            matrix[i][j]
=min(above,min(left,diag));

        }

     }
//step7
      return matrix[n][m];
}

int main(){
    
string s;
    
string d;
    cout
<<"source=";
    cin
>>s;
    cout
<<"diag=";
    cin
>>d;
    
int dist=ldistance(s,d);
    cout
<<"dist="<<dist<<endl;
}

posted on 2008-09-21 03:03 whn 阅读(20265) 评论(15)  编辑 收藏 引用 所属分类: 算法

评论

# re: 字符串相似度算法( Levenshtein Distance算法) 2008-09-21 10:13 fejay

我也在论坛上看到了。学习学习  回复  更多评论   

# re: 字符串相似度算法( Levenshtein Distance算法) 2008-09-21 22:35 Post

在哪里看到的?  回复  更多评论   

# re: 字符串相似度算法( Levenshtein Distance算法) 2008-09-22 16:30 Vinson

kind of like DP..  回复  更多评论   

# re: 字符串相似度算法( Levenshtein Distance算法) 2008-10-05 13:20 kina

請問:
把从字符串A转换成字符串B,如果最少執行次數為3,那這3次的執行動作要如何印出來?需把程式加在哪裡?
  回复  更多评论   

# re: 字符串相似度算法( Levenshtein Distance算法) 2009-05-13 12:39 shinjikun

如果不需要得到执行动作的话你这个算法空间复杂度高了(应该是O(n))。
如果需要的话,只要回溯就可以了。  回复  更多评论   

# re: 字符串相似度算法( Levenshtein Distance算法) 2009-05-17 12:36 whn

@shinjikun
不知道你是怎么做的 不过 回溯 速度很慢的   回复  更多评论   

# re: 字符串相似度算法( Levenshtein Distance算法) 2009-05-25 01:06 test01x

我也比较关心国家大事 kina 提出的问题。
另外,我还没有搞清楚这个算法和KMP算法的原理和实现的不同支出,能指点一下吗?谢谢!
我会时常关注评论。  回复  更多评论   

# re: 字符串相似度算法( Levenshtein Distance算法) 2009-05-25 01:07 test01x

晕,输入法智能联想问题。原本应该是:
我也比较关心 kina 提出的问题。
另外,我还没有搞清楚这个算法和KMP算法的原理和实现的不同之处,能指点一下吗?谢谢!
我会时常关注评论。  回复  更多评论   

# re: 字符串相似度算法( Levenshtein Distance算法) 2009-05-26 10:19 whncpp

@test01x
两个算法解决的问题是完全不一样的,kmp解决模式匹配的LD 是解决相似度的 问题,  回复  更多评论   

# re: 字符串相似度算法( Levenshtein Distance算法) 2009-05-30 13:50 ray040123

dp算法

如果想打印,用一个数组c[i][j] 记录每步的决策(above,left,diag)
之后从c[n,m] 倒推,记录,输出即可  回复  更多评论   

# re: 字符串相似度算法( Levenshtein Distance算法) 2011-06-16 15:46 splash

代码有瑕疵。因为matrix[0][0]没有初始化。  回复  更多评论   

# re: 字符串相似度算法( Levenshtein Distance算法) 2012-04-24 11:43 peter4431

@splash
说明你没看懂 matrix[0][0]就没用到  回复  更多评论   

# re: 字符串相似度算法( Levenshtein Distance算法) 2012-06-14 08:48 safds

请问这个在哪个环境里通过了?

REDMOND # 139.com谢谢  回复  更多评论   

# re: 字符串相似度算法( Levenshtein Distance算法)[未登录] 2016-01-07 11:50 max

@peter4431
我只是路过,感谢楼主的分享,但是这个地方确实是用到啦,像扫雷一样,周边都是度,可能确实要初始化一下。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理