`

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

阅读更多
软件工程部编程小结第二期
题目: 一个字符串可以通过增加一个字符,删除一个字符,替换一个字符得到另外一个字符串,假设,我们把从字符串A转换成字符串B,前面3种操作所执行的最少次数称为AB相似度
如  abc adc  度为 1
      ababababa babababab 度为 2
      abcd acdb 度为2


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

StepDescription
1Set 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].


#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==0) return n;
    if (n==0) return 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==0) return n;
    if (n==0) return 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;
}
分享到:
评论

相关推荐

    字符串相似度算法 字符串相似度算法 字符串相似度算法

    Levenshtein Distance算法是一种常用的字符串相似度算法,广泛应用于自然语言处理、数据挖掘、机器学习等领域。通过对Levenshtein Distance算法的了解,可以更好地理解和应用字符串相似度算法。

    字符串相似度算法 levenshtein distance 编辑距离算法

    **字符串相似度算法——Levenshtein Distance(编辑距离)** 在信息技术和计算机科学领域,字符串相似度计算是一个重要的概念,特别是在文本处理、搜索引擎优化、数据校验和生物信息学等多个场景中。Levenshtein ...

    Python-Levenshtein快速计算编辑距离以及字符串的相似度

    Levenshtein库提供了高效的算法来计算这个距离,并且可以用来评估字符串之间的相似度。在Python中,你可以通过以下方式导入并使用这个库: ```python from Levenshtein import distance ``` 然后,你可以用`...

    字符串相似度算法

    在IT领域,字符串相似度算法是一种非常重要的工具,特别是在数据挖掘、信息检索、文本分类以及自然语言处理等应用中。这个小例子旨在介绍如何通过计算字符串间的相似度来进行模糊匹配。我们将探讨几种常见的字符串...

    C#,字符串相似度的莱文斯坦距离(Levenshtein Distance)算法与源代码

    C#,字符串相似度的莱文斯坦距离(Levenshtein Distance)算法与源代码 莱文斯坦距离(Levenshtein Distance)用于衡量两个字符串之间的相似度。 莱文斯坦距离以俄国科学家(Vladimir I. Levenshtein)命名,他于...

    mysql 计算字符串相似度

    ### MySQL 计算字符串相似度 #### 背景与需求 在许多应用场景中,我们需要对两个字符串进行相似度比较,比如搜索引擎中的关键词匹配、文本分析中的近义词识别等。MySQL 提供了多种方法来实现字符串相似度的计算,...

    Delphi计算字符串的相似度

    总之,Delphi提供了丰富的工具和功能来处理字符串相似度计算,开发者可以根据具体需求选择合适的算法并进行实现。在实际项目中,理解和运用这些算法可以帮助我们更好地理解和比较文本数据,提升应用程序的功能和用户...

    数据挖掘与数据分析应用案例 数据挖掘算法实践基于Java的文本相似度(Levenshtein distance算法)计算.doc

    Levenshtein Distance算法提供了一种有效的方法来度量两个字符串之间的相似性,而基于关键词的空间向量模型则适用于更广泛的文本相似度计算任务。掌握这两种算法的原理及其应用场景对于从事数据挖掘、自然语言处理等...

    LD的两字符串相似度计算.zip

    Levenshtein Distance(简称LD),又称编辑距离,是衡量两个字符串相似度的一种方法。这个概念由俄国科学家Vladimir Levenshtein在1965年提出,因此得名。 编辑距离定义了将一个字符串转换成另一个字符串所需的最少...

    两个字符串的相似度算法实现——编辑距离之Levenshtein距离

    两个字符串的相似度算法实现——编辑距离之Levenshtein距离

    字符串相似度比较

    本文将深入探讨字符串相似度比较的概念、常用算法以及在JavaScript中的实现,同时关注潜在的性能和内存管理问题。 字符串相似度比较旨在量化两个或多个字符串之间的相似程度,通常以百分比形式表示。这种比较不仅...

    使用最短编辑距离算法判断两个字符串的相似度

    总之,最短编辑距离算法是计算字符串相似度的一种基础且重要的方法,它在文本处理领域有着广泛的应用。理解和掌握这一算法,对于开发相关的软件功能,如自动纠错、搜索引擎优化等,都是非常有益的。

    字符串相似度比较T-2021-7-1.rar

    总的来说,字符串相似度比较是信息技术中的基础工具,深入理解和灵活运用这些算法能帮助我们解决多种实际问题。通过“字符串相似度比较T-2021-7-1.rar”中的内容,我们可以系统学习这一领域的知识,提升处理文本数据...

    Java字符串相似度:各种字符串相似度和距离算法的实现:Levenshtein,Jaro-winkler,n-Gram,Q-Gram,Jaccard索引,最长公共子序列编辑距离,余弦相似度..

    Java字符串相似度 一个实现不同字符串相似度和距离度量的库。 当前实现了十二种算法(包括Levenshtein编辑距离和同级,Jaro-Winkler,最长公共子序列,余弦相似性等)。 查看下面的摘要表以获取完整列表... 下载 ...

    Oracle字符相似度函数

    - **EDITDISTANCE()**:编辑距离(Levenshtein距离)函数,计算将一个字符串转换为另一个字符串所需的最少单字符编辑(插入、删除或替换)次数。返回值是具体的编辑距离,数值越小表示越接近。 在实际应用中,...

    计算字符串相似度(支持中英文,编辑距离算法,余弦,繁体转简体)

    在IT领域,字符串相似度计算是一项重要的技术,广泛应用于文本分析、信息检索、自然语言处理等多个方面。本项目提供了一个简单易用的demo,支持中英文字符串的相似度比较,采用了编辑距离算法和余弦相似度这两种经典...

    c#字符串相似度源码 编辑距离 余弦相似性 SimHash

    本文将详细解析C#编程语言中实现的四种字符串相似度计算方法:编辑距离(Levenshtein Distance)、余弦相似性(Cosine Similarity)以及SimHash算法。 首先,编辑距离是一种衡量两个字符串之间差异的度量,它表示由...

    编辑长求字符串相似度Delphi源代码

    首先,我们需要了解几种常见的字符串相似度算法: 1. **Levenshtein距离**:这个算法衡量的是通过插入、删除或替换操作将一个字符串转换成另一个字符串所需的最少步骤数。在Delphi中,你可以创建一个动态数组来存储...

    字符串识别,相似度匹配

    除此之外,还有一些专门为文本处理和字符串相似度匹配设计的库: - **Boost**: 提供了`boost::algorithm`库,包含字符串算法如`find_similar()`用于模糊匹配。 - **SeqAn**: 一个专门针对生物信息学序列处理的高...

Global site tag (gtag.js) - Google Analytics