精华内容
参与话题
问答
  • 字符串编辑距离也被称为距Levenshtein距离(Levenshtein Distance),属于经典算法,常用方法使用递归,更好的方法是使用动态规划算法,以避免出现重叠子问题的反复计算,减少系统开销。 《编程之美》一书中3.3节...

      字符串的编辑距离也被称为距Levenshtein距离(Levenshtein Distance),属于经典算法,常用方法使用递归,更好的方法是使用动态规划算法,以避免出现重叠子问题的反复计算,减少系统开销。

    《编程之美》一书中3.3节中计算两个字符串的相似度,归根到底也是要求两个字符串的距离,其中问题是这样提出的:

      许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:

    •         修改一个字符(如把"a"替换为"b");
    •         增加一个字符(如把"abdd"变为"aebdd");
    •         删除一个字符(如把"travelling"变为"traveling");

        比如,对于"abcdefg"和"abcdef"两个字符串来说,我们认为可以通过增加/减少一个"g"的方式来达到目的。上面的两种方案,都仅需要一 次 。把这个操作所需要的次数定义为两个字符串的距离,而相似度等于"距离+1"的倒数。也就是说,"abcdefg"和"abcdef"的距离为1,相似度 为1/2=0.5。给定任意两个字符串,你是否能写出一个算法来计算它们的相似度呢?    

      其实这个问题的关键是要求两个字符串的编辑距离

    例如 将kitten一字转成sitting:

    1. sitten (k→s)

    2. sittin (e→i)

    3. sitting (→g)

    俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。

    问题:找出字符串的编辑距离,即把一个字符串s1最少经过多少步操作变成编程字符串s2,操作有三种,添加一个字符,删除一个字符,修改一个字符。

     

    方法1:递归法,时间复杂度O(log(max(M,N)*M*N)

    假设字符串 a, 共 m 位,从 a[1] 到 a[m]
    字符串 b, 共 n 位,从 b[1] 到 b[n]
    d[i][j] 表示字符串 a[1]-a[i] 转换为 b[1]-b[j] 的编辑距离

    那么有如下递归规律(a[i] 和 b[j] 分别是字符串 a 和 b 的最后一位):

    1. 当 a[i] 等于 b[j] 时,d[i][j] = d[i-1][j-1], 比如 fxy -> fay 的编辑距离等于 fx -> fa 的编辑距离
    2. 当 a[i] 不等于 b[j] 时,d[i][j] 等于如下 3 项的最小值:
      • d[i-1][j] + 1(删除 a[i]), 比如 fxy -> fab 的编辑距离 = fx -> fab 的编辑距离 + 1
      • d[i][j-1] + 1(插入 b[j]), 比如 fxy -> fab 的编辑距离 = fxyb -> fab 的编辑距离 + 1 = fxy -> fa 的编辑距离 + 1
      • d[i-1][j-1] + 1(将 a[i] 替换为 b[j]), 比如 fxy -> fab 的编辑距离 = fxb -> fab 的编辑距离 + 1 = fx -> fa 的编辑距离 + 1

    递归边界:

    1. a[i][0] = i, b 字符串为空,表示将 a[1]-a[i] 全部删除,所以编辑距离为 i
    2. a[0][j] = j, a 字符串为空,表示 a 插入 b[1]-b[j],所以编辑距离为 j
    int edit_distance(char *a, char *b, int i, int j)
    {
        if (j == 0) {
            return i;
        } else if (i == 0) {
            return j;
        // 算法中 a, b 字符串下标从 1 开始,c 语言从 0 开始,所以 -1
        } else if (a[i-1] == b[j-1]) {
            return edit_distance(a, b, i - 1, j - 1);
        } else {
            return min_of_three(edit_distance(a, b, i - 1, j) + 1,
                                edit_distance(a, b, i, j - 1) + 1,
                                edit_distance(a, b, i - 1, j - 1) + 1);
        }
    }
    
    edit_distance(stra, strb, strlen(stra), strlen(strb));
    

    但是有个严重的问题,就是代码的性能很低下,时间复杂度是指数增长的
    上面的代码中,很多相同的子问题其实是经过了多次求解,解决这类问题的办法是用动态规划

     

    下面我们就针对这个问题来详细阐述一下:

    我们假定函数dist(str1, str2)表示字串str1转变到字串str2的编辑距离,那么对于下面3种极端情况,我们很容易给出解答(0表示空串)。

    • dist(0, 0) = 0

    • dist(0, s) = strlen(s)

    • dist(s, 0) = strlen(s)

    对于一般的情况,dist(str1, str2)我们应该如何求解呢?

    假定我们现在正在求解dist(str1+char1, str2+char2),也就是把"str1+char1"转变成"str2+char2"。在这个转变过称中,我们要分情况讨论:

    1. str1可以直接转变成str2。这时我们只要把char1转成char2就可以了(如果char1 != char2)。

    2. str1+char1可以直接转变成str2。这时我们处理的方式是插入char2。

    3. str1可以直接转成str2+char2。这时的情况是我们需要删除char1。

      综合上面三种情况,dist(str1+char1, str2+char2)应该是三者的最小值。

    解析:

    首先定义这样一个函数——edit(i, j),它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。

    显然可以有如下动态规划公式:

    • if i == 0 且 j == 0,edit(i, j) = 0

    • if i == 0 且 j > 0,edit(i, j) = j

    • if i > 0 且j == 0,edit(i, j) = i

    • if i ≥ 1  且 j ≥ 1 ,edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) },当第一个字符串的第i个字符不等于第二个字符串的第j个字符时,f(i, j) = 1;否则,f(i, j) = 0。

    我们建立以下表格,将两个字符串按照表格1所示的样子进行摆放,规则按照以上公式进行输入,如下所示,我们可以得到每个表格中的值,如下表格2所示:

     

    0

    a

    b

    c

    d

    e

    f

    0

      

      

      

      

      

      

      

    a

      

      

      

      

      

      

      

    c

      

      

      

      

      

      

      

    e

      

      

      

      

      

      

      

               表格1(字符串摆放表格)

     

    0

    a

    b

    c

    d

    e

    f

    0

     0

    2

    3

     4

     5

     6

    a

     1

      

      

      

      

      

      

    c

     2

      

      

      

      

      

      

    e

     3

      

      

      

      

      

      

          表格2(按照规则计算i==0 或 j==0的情况)

     计算edit(1, 1),edit(0, 1) + 1 == 2,edit(1, 0) + 1 == 2,edit(0, 0) + f(1, 1) == 0 + 1 == 1,min(edit(0, 1),edit(1, 0),edit(0, 0) + f(1, 1))==1,因此edit(1, 1) == 1。依次类推,有如下表格3所示最终的矩阵:

     

    0

    a

    b

    c

    d

    e

    f

    0

     0

     1

     2

     3

     4

     5

     6

    a

     1

     0

     1

     2

     3

     4

     5

    c

     2

     1

     1

     1

     2

     3

     4

    e

     3

     2

     2

     2

     2

     2

     3

          表格3(最终计算得到的字符串相对距离)

    此时右下角即为我们所需要的两个字符串的编辑距离。即字符串 "abcdef"和"ace"的编辑距离为3.

    有了以上的步骤,相信大家已经很清楚了,使用动态规划算法的时候,需要建立子问题的表格,以上的表格就是。而且我们能够很容易的使用二维数组建立。代码实现也就易如反掌了!

    以下是我的实现过程,希望对大家有用,如果有什么可以优化或者错误的地方,希望能够得到批评指正。

     

      1 #include <iostream>
      2 #include <string>
      3 
      4 using namespace  std;
      5 
      6 int min3Value(int a, int b, int c)
      7 {
      8     int tmp = (a <= b? a:b);
      9     return (tmp<=c? tmp: c);
     10 }
     11 
     12 
     13 int Get2StringEditDis(string strA, string strB)
     14 {
     15     int nLenA = strA.length();
     16     int nLenB = strB.length();
     17     int **matrix = new int *[nLenA + 1];
     18     for (int i = 0; i != nLenA +1; i++)
     19     {
     20         matrix[i] = new int[nLenB + 1];
     21     }
     22     // 动态规划 计算
     23     // 初始化数组
     24     matrix[0][0] = 0;
     25     int p,q; 
     26     // j = 0; edit(i, j) = i
     27     for (p = 1; p!= nLenA+1; p++)
     28     {
     29         matrix[p][0] = p;
     30     }
     31     // i = 0; edit(i,j) = j
     32     for (q=1; q != nLenB+1; q++)
     33     {
     34         matrix[0][q] = q;
     35     }
     36     // i>0, j>0
     37     for (int j = 1; j != nLenA+1; j++)
     38     {
     39         for (int k = 1; k !=  nLenB+1; k++)
     40         {
     41             int Fjk = 0;
     42             if (strA[j-1] != strB[k-1])
     43             {
     44                 Fjk = 1;
     45             }
     46             matrix[j][k] = min3Value(matrix[j-1][k]+1,matrix[j][k-1]+1,matrix[j-1][k-1]+Fjk);
     47         }
     48     }
     49     
     50 
     51 
     52 
     53     // 输出距离矩阵
     54     // 第一行输出字符串b
     55     // 第一列输出字符串A
     56     cout<<"*****************************"<<endl;
     57     cout<<"字符串编辑距离矩阵如下:\n";
     58     for (p = -1; p!= nLenA +1; p++)
     59     {
     60         for (q = -1; q !=nLenB+1; q++)
     61         {
     62             //cout.width(3),cout<<matrix[p][q];
     63             cout.width(3);
     64             if (p ==-1 && q == -1)
     65             {
     66                 cout<<" ";
     67             }
     68             else if (p + q == -1)
     69             {
     70                 cout<<"NUL";
     71             }
     72             else if (p == -1 && q >0)
     73             {
     74                 cout<<strB[q-1];
     75             }
     76             else if(q == -1 && p > 0)
     77             {
     78                 cout<<strA[p-1];
     79             }
     80             else
     81             {
     82                 cout<<matrix[p][q];
     83             }
     84         }
     85         cout<<endl;
     86     }
     87     cout<<"*****************************"<<endl;
     88     //
     89     int  nEditDis = matrix[nLenA][nLenB];
     90     for (int m = 0; m!=nLenA + 1; m++)
     91     {
     92         delete[] matrix[m];
     93     }
     94     delete[] matrix;
     95 
     96 
     97     return  nEditDis;
     98 }
     99 
    100 
    101 int main()
    102 {
    103     string strA("abcdefgh");
    104     string strB("adgcf");
    105 
    106     int nDist = Get2StringEditDis(strA,strB);
    107     cout<<"The edit dis is  "<<nDist<<endl;
    108 
    109     return 0;
    110 }

     

    根据具体问题优化空间复杂度

    还是以 a = "fxy", b = "fab" 为例,例如计算 d[1][3], 也就是下图中的绿色方块, 我们需要知道的值只需 3 个,下图中蓝色方块的值

    进一步分析,我们知道,当计算 d[1] 这行的时候,我们只需知道 d[0] 这行的值, 同理我们计算当前行的时候只需知道上一行就可以了
    再进一步分析,其实我们只需要一行就可以了,每次计算的时候我们需要的 3 个值, 其中上边和左边的值我们可以直接得到,坐上角的值需要临时变量(如下代码使用 old)来记录

    代码如下:

    int edit_distance(char *a, char *b)
    {
        int lena = strlen(a);
        int lenb = strlen(b);
        int d[lenb+1];
        int i, j, old, tnmp;
    
        for (j = 0; j <= lenb; j++) {
            d[j] = j;
        }
    
        for (i = 1; i <= lena; i++) {
            old = i - 1;
            d[0] = i;
            for (j = 1; j <= lenb; j++) {
                temp = d[j];
                // 算法中 a, b 字符串下标从 1 开始,c 语言从 0 开始,所以 -1
                if (a[i-1] == b[j-1]) {
                    d[j] = old;
                } else {
                    d[j] = min_of_three(d[j] + 1, d[j-1] + 1, old + 1);
                }
                old = temp;
            }
        }
    
        return d[lenb];
    }
    

    写代码的过程中需要注意的一点就是,当一行计算好之后开始下一行的时候, 要初始化 old 和 d[0] 的值

    优化过后时间复杂度还是 O(mn), 空间复杂度降低了,以上代码是 O(n), 其实很简单可以写成 O(min(m,n)), 为了便于理解,就不具体写了

    展开全文
  • 字符串编辑距离

    2019-04-03 10:18:55
    假设给定两个字符串s1,s2,要用最少的操作将字符串s1转换成字符串s2。其中可用的操作包括: 1.插入一个字符(Insert a character) 2.删除一个字符(Delete a character) 3.修改一个字符(Replace a character) 2....

    项目github地址:bitcarmanlee easy-algorithm-interview-and-practice
    欢迎大家star,留言,一起学习进步

    1.问题描述

    假设给定两个字符串s1,s2,要用最少的操作将字符串s1转换成字符串s2。其中可用的操作包括:
    1.插入一个字符(Insert a character)
    2.删除一个字符(Delete a character)
    3.修改一个字符(Replace a character)

    2.解题思路

    该问题是一个典型的动态规划问题。
    假设dp[i][j]是将字符串 s1[0: i-1] 转变为 s2[0: j-1] 的最小步骤数。
    首先将dp[i][j]初始化
    当i=0时,相当于s1为空,此时s1变为s2为不断添加字符,dp[0][j] = j。
    当j=0时,相当于s2为空,此时s1变为s2为不断删除字符,dp[i][0] = i。

    如果s1,s2均不为空,那么求s1与s2的最小编辑距离有两种情况:
    1.如果s1与s2 的结尾字符相同,那么dp[i][i] = dp[i-1][j-1],因为此时相当于不用做任何操作。
    2.如果s1与s2的结尾字符不相同
    插入操作:dp[i][j] = dp[i][j-1] + 1,相当于在s2后面插入s1的尾字符。
    删除操作:dp[i][j] = dp[i-1][j] + 1,相当于删除s2后面的尾字符。
    替换操作:dp[i][j] = dp[i-1][j-1] + 1,相当于将s2最后的尾字符用s1最后的尾字符替换。

    3.代码

    public class MinEditDistance {
    
        public static final String s1 = "abc";
        public static final String s2 = "dec";
    
        public static void findDistance() {
            int len1 = s1.length();
            int len2 = s2.length();
            int[][] dp = new int[len1+1][len2+1];
    
            for(int i=0; i<=len1; i++) {
                dp[i][0] = i;
            }
            for(int i=0; i<=len2; i++) {
                dp[0][i] = i;
            }
    
            for(int i=1; i<=len1; i++) {
                for(int j=1; j<=len2; j++) {
                    if (s1.charAt(i-1) == s2.charAt(j-1)) {
                        dp[i][j] = dp[i-1][j-1];
                    } else {
                        int tmp = Math.min(dp[i-1][j]+1, dp[i][j-1] + 1);
                        dp[i][j] = Math.min(dp[i-1][j-1]+1, tmp);
                    }
                }
            }
    
            System.out.println("min num is: " + dp[len1][len2]);
        }
    
        public static void main(String[] args) {
            findDistance();
        }
    }
    
    展开全文
  • 字符串最短编辑距离问题

    千次阅读 2018-06-22 17:50:41
    问题: 设 A 和 B 是两个字符串。我们要用最少的字符操作次数,将字符串 ... 对任给的两个字符串 A 和 B ,计算出将字符串 A 变换为字符串 B 所用的最少字符操作次数。 样例: 2 bcodeqwrty bdq...

    问题:

    设 A 和 B 是两个字符串。我们要用最少的字符操作次数,将字符串 A 转换为字符串 B 。这里所说的字符操作共有三种:

    1. 删除一个字符;
    2. 插入一个字符;
    3. 将一个字符改为另一个字符。

    对任给的两个字符串 A 和 B ,计算出将字符串 A 变换为字符串 B 所用的最少字符操作次数。

    样例:

    2
    bcodeqwrty
    bdq
    baician
    bczdd
    

    输出:

    7
    5
    

    这个问题本质上是一个无向图的问题,固定了起点和终点,起点为字符串 A ,终点为字符串 B 。但是每一个点所对应的分支太多。所以我们需要对其进行转化。

    在以下特殊情况下,最短编辑距离容易求出:

    • 当 A 、 B 的长度都为 0 时,最短编辑距离为 0
    • 当 A 的长度为 0 , B 的长度不为 0 ,最短编辑距离为 A 的长度
    • 当 A 的长度不为 0 , B 的长度为 0 ,,最短编辑距离为 B 的长度

    我们可以将所有的字符串转化为以上的三种情况。

    可以尝试使用动态规划来解决。动态规划对于有向无环图比较合适,如果我们只对字符串 A 、 B 的最后一个字符做操作,而且将“增删改”变为“删改”,那么无向图就变成了有向无环图。

    使用动态规划,首先需要定义状态。我们可以把 A,B 变换成的子串的长度 (i,j)(i,j) 看成一个状态,然后定义状态 (i,j)(i,j) 的指标函数 d(i,j)d(i,j)(i,j)(i,j) 变为相同子串所需的最小编辑次数。

    然后观察不同状态之间是如何转移的,从状态 (i,j)(i,j) 出发有三种决策,分别对应题目中所给出的三种字符操作(三种字符操作都是对最后一个字符的操作)。

    1. 删除一个字符 ==> 删除 A 字符串的最后一个字符,转移到了 (i1,j)(i-1,j)
    2. 插入一个字符 ==> 在 A 字符串末尾插入 B 字符串的一个字符,相当于 B 字符串删除一个字符,转移到了 (i,j1)(i,j-1)
    3. 将一个字符改为另一个字符。 ==> 将 A 的最后一个字符改为 B 的最后一个字符,将状态转移到了 (i1,j1)(i-1,j-1)

    则状态转移方程为:
    d(i,j)=min{d(i1,j)+1,d(i,j1)+1,d(i1,j1)+c}d(i,j)=min \{d(i-1,j)+1,d(i,j-1)+1,d(i-1,j-1)+c\}
    式中,当子串的最后一个字符相同时, AB 的最小编辑距离与 AB 都去掉最后一个字母的最小编辑距离相同,所以 c=0c=0 ,否则 c=1c=1

    完整程序:

    //#define LOCAL
    #include <iostream>
    #include <stdio.h>
    #include <time.h>
    #include <algorithm>
    #include <cstring>
    
    using namespace std;
    
    const int maxn = 1000 + 2;
    char a[maxn];
    char b[maxn];
    int step[maxn][maxn];
    int findStep(int i, int j)
    {
        int &ans = step[i][j];
        if (ans != -1)
        {
            return ans;
        }
        if (i == 0 && j == 0)
        {
            return ans = 0;
        }
        if (i == 0)
        {
            return ans = j;
        }
        else if (j == 0)
        {
            return ans = i;
        }
        int c;
        if (a[i - 1] != b[j - 1])
        {
            c = 1;
        }
        else
        {
            c = 0;
        }
        ans = min(min(findStep(i - 1, j) + 1,
                      findStep(i, j - 1) + 1),
                  findStep(i - 1, j - 1) + c);
        return ans;
    }
    
    int main()
    {
    #ifdef LOCAL
        freopen("data.in", "r", stdin);
        freopen("data.out", "w", stdout);
    #endif // LOCAL
        int n;
        int m1, n1;
        while (cin >> n && n)
        {
    
            for (int j = 0; j < n; j++)
            {
                memset(step, -1, sizeof(step));
                cin >> a >> b;
                cout << strlen(a) << " " << strlen(b) << endl;
    
                m1 = strlen(a);
                n1 = strlen(b);
    
                cout << findStep(m1, n1) << endl;
            }
        }
        return 0;
    }
    
    展开全文
  • 下面分享字符串编辑距离的求解。 概念 字符串的编辑距离,又称为Levenshtein距离,由俄罗斯的数学家Vladimir Levenshtein在1965年提出。是指利用字符操作,把字符串A转换成字符串B所需要的最少操作数。其中,字符...

      很多程序都需要利用到字符串的比较,而字符串的编辑距离在字符串相似性比较中,应用广泛。下面分享字符串编辑距离的求解。

    概念

      字符串的编辑距离,又称为Levenshtein距离,由俄罗斯的数学家Vladimir Levenshtein在1965年提出。是指利用字符操作,把字符串A转换成字符串B所需要的最少操作数。其中,字符操作包括:

    • 删除一个字符
    • 插入一个字符
    • 修改一个字符

      例如对于字符串"if"和"iff",可以通过插入一个'f'或者删除一个'f'来达到目的。

      一般来说,两个字符串的编辑距离越小,则它们越相似。如果两个字符串相等,则它们的编辑距离(为了方便,本文后续出现的“距离”,如果没有特别说明,则默认为“编辑距离”)为0(不需要任何操作)。不难分析出,两个字符串的编辑距离肯定不超过它们的最大长度(可以通过先把短串的每一位都修改成长串对应位置的字符,然后插入长串中的剩下字符)。

    问题描述

      给定两个字符串A和B,求字符串A至少经过多少步字符操作变成字符串B。

    问题分析

      1)首先考虑A串的第一个字符

      假设存在两个字符串A和B,他们的长度分别是lenA和lenB。首先考虑第一个字符,由于他们是一样的,所以只需要计算A[2...lenA]和B[2...lenB]之间的距离即可。那么如果两个字符串的第一个字符不一样怎么办?可以考虑把第一个字符变成一样的(这里假设从A串变成B串):

    • 修改A串的第一个字符成B串的第一个字符,之后仅需要计算A[2...lenA]和B[2...lenB]的距离即可;
    • 删除A串的第一个字符,之后仅需要计算A[2...lenA]和B[1...lenB]的距离即可;
    • 把B串的第一个字符插入到A串的第一个字符之前,之后仅需要计算A[1...lenA]和B[2...lenB]的距离即可。

      2)接下来考虑A串的第i个字符和B串的第j个字符。

      我们这个时候不考虑A的前i-1字符和B串的第j-1个字符。如果A串的第i个字符和B串的第j个字符相等,即A[i]=B[j],则只需要计算A[i...lenA]和B[j...lenB]之间的距离即可。如果不想等,则:

    • 修改A串的第i个字符成B串的第j个字符,之后仅需要计算A[i+1...lenA]和B[j+1...lenB]的距离即可;
    • 删除A串的第i个字符,之后仅需要计算A[i+1...lenA]和B[j...lenB]的距离即可;
    • 把B串的第j个字符插入到A串的第i个字符之前,之后仅需要计算A[i...lenA]和B[j+1...lenB]的距离即可。

      写到这里,自然会想到用递归求解或者动态规划求解,由于用递归会产生很多重复解,所以用动态规划。

    构建动态规划方程

      用edit[i][j]表示A串从第i个字符开始和B串从第j个字符开始的距离。则从上面的分析,不难推导出动态规划方程:

    ,其中

    代码

      有了动态规划方程,程序自然也就不难写了。下面贴出我的Java代码

    复制代码

            /**
         * 计算两个字符串的编辑距离
         * @param str1 需要比较的字符串
         * @param str2 需要比较的字符串
         * @return 两个字符串的编辑距离
         */
        public int editDistance(String str1,String str2){
            
            int lenStr1=str1.length();
            int lenStr2=str2.length();
            int[][] edit=new int[lenStr1][lenStr2];
            for(int i=0;i<lenStr1;i++){
                edit[i][0]=i;
            }
            for(int j=0;j<lenStr2;j++){
                edit[0][j]=j;
            }
            
            for(int i=1;i<lenStr1;i++){
                for(int j=1;j<lenStr2;j++){
                    edit[i][j]=Integer.min(edit[i-1][j]+1,edit[i][j-1]+1);
                    if(str1.charAt(i-1)==str2.charAt(j-1)){
                        edit[i][j]=Integer.min(edit[i][j], edit[i-1][j-1]);
                    }else{
                        edit[i][j]=Integer.min(edit[i][j], edit[i-1][j-1]+1);
                    }
                }
            }
            
            return edit[lenStr1-1][lenStr2-1];
        }

    复制代码

    展开全文
  • 字符串编辑距离 -- Python

    千次阅读 2018-09-14 15:42:50
    两个字符串编辑距离 edit[i][j]表示A串从第0个字符开始到第i个字符和B串从第0个字符开始到第j个字符,这两个字串的编辑距离字符串的下标从1开始。 递推公式: 'michaelab' 变成 'michaelxy' if b==y: d[i][j]...
  • 字符串编辑距离

    2019-08-25 11:00:58
    语音识别领域和NLP领域都会接触到WER(字错率)和CER(字符错误率),但两者的计算都离不开字符串编辑距离字符串编辑距离(Edit Distance),是俄罗斯科学家Vladimir Levenshtein提出的概念。两个字符串之间的最小距离...
  • 我们可以认为Levenshtein距离就是从一个字符串修改到另一个字符串时,其中编辑单个字符(比如修改、插入、删除)所需要的最少次数。俄罗斯科学家Vladimir Levenshtein于1965年提出了这一概念。 简单例子 从字符串...
  • 字符串编辑距离

    2018-10-29 15:10:50
    字符串编辑距离(Edit Distance),是俄罗斯科学家Vladimir Levenshtein在1965年提出的概念,又称Levenshtein距离,是指两个字符串之间,由一个转成另一个所需的最少编辑操作次数。 算法介绍 判断2个字符串相似情况 ...
  • 编辑距离
  • Java实现字符串编辑距离

    万次阅读 多人点赞 2019-07-26 17:33:51
    给定一个源和目标,能够进行如下操作: 在任意位置上插入一个字符; 替换掉任意字符; 删除任意字符。 写一个程序,实现返回最小操作次数,使得对源进行上述这些操作后等于目标。 2 解决方案 此处采用动态...
  • 字符串编辑距离

    千次阅读 2016-04-03 10:13:38
    字符串编辑距离 题目描述  给定一个源串和目标串,能够对源串进行如下操作:  ·在任意位置上插入一个字符;  ·替换任意字符;  ·删除任意字符。  写一个程序,实现返回最小操作次数,使得对源串...
  • 字符串编辑距离到字符串对齐

    千次阅读 2015-12-06 22:15:10
    (一)字符串编辑距离 字符串编辑距离,也称莱文斯坦距离,它是指把一个字符串变为另一个字符串需要的最小操作步数,每一步可以在“一个字符串”上做以下三种操作之一: (1)插入一个字符; (2)删除一个字符; ...
  • 字符串编辑距离

    2014-04-10 21:13:36
    本文参考自 书籍>
  • 计算字符串编辑距离

    2015-02-09 15:09:14
    计算字符串编辑距离题目描述:给定两个字符串,要求二者之间的编辑距离。分析:字符串的编辑主要有三种方式:增加、删除和修改。这道题目按照递归的方式,逐个判断每个字符。具体而言,如果str1和str2的第一个字符...
  • 编辑距离编辑距离算法 编辑距离概念描述: 编辑距离,又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,...
  • https://www.cnblogs.com/xiuyangleiasp/p/5023717.html... 基本介绍  Levenshtein距离是一种计算两个字符串间的差异程度的字符串度量(string metric)。我们可以认为Levenshtein距离就是从一个字符串修改到另一...
  • 字符串编辑距离模板

    千次阅读 2018-09-17 20:24:14
    编辑距离,⼜又称Levenshtein距离(也叫做Edit Distance),是指两个字串串之间,由⼀一个转成 另⼀一个所需的少编辑操作次数。许可的编辑操作包括将⼀一个字符替换成另⼀一个字符,插⼊入⼀一个字 符,删除⼀一个...
  • Levenshtein Distance是一个度量两个字符序列之间差异的字符串度量标准,两个单词之间的Levenshtein Distance是将一个单词转换为另一个单词所需的单字符编辑(插入、删除或替换)的最小数量。Levenshtein Distance是...
  • 字符串编辑距离

    2013-06-26 22:06:50
    2个字符串,把s1转换到s2最少操作,并且把这个操作过程输出。 操作包括3种:删除一个字符,增加一个字符,改变一个字符,操作仅对s1执行,使其等于s2. 算法思想: 动态规划 b[i][j]表示s1[1..i]和s2[1..j]之间...
  •  题目的意思应该是:在一个给定的字典中,求与给定的字符串编辑距离不大于2的所有的单词。原先写过两片关于此问题的文章,那两片篇章文章给出两种解决思路:其一是暴力求解法,这种方法最容易想到。就是将词典中...

空空如也

1 2 3 4 5 ... 20
收藏数 30,311
精华内容 12,124
关键字:

字符串编辑距离