编辑距离算法

Posted on

使用的莱文斯坦算法(编辑距离算法)

wike介绍

前期了解

莱文斯坦距离，又称Levenshtein距离，是编辑距离的一种。指两个字串之间，由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
莱文斯坦距离以俄国科学家Vladimir levenshtein命名，于1965年发明了这个算法,莱文斯坦距离又称为编辑距离。
在信息论中，两个等长字符串之间的汉明距离（英语：Hamming distance）是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。
汉明重量是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是1的个数，所以11101的汉明重量是4。

这里， 和 分别表示字符串a和b的长度， 是当 时值为1，否则值为0的示性函数。这样， 是 的前 个字符和 的前 个字符之间的距离。

概念

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

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

上下界

莱文斯坦距离包括几个简单的上下界,包括:

  • 至少是两个字符串之间的差值
  • 最多是较长字符串的长度
  • 如果两个字符串相同为0
  • 如果两个字符串长度相同,汉明距离即为莱文斯坦距离上届
  • 两个字符串之间的莱文斯坦距离不大于它们与第三个字符串之间的莱文斯坦距离之和（三角形不等式）

例子

比如,字符串“kitten”和“sitting”的莱文斯坦距离为3

  • kitten → sitten (k替换为s)
  • sitten → sittin (e替换为i)
  • sittin → sitting (在结尾添加g).

下面是一个由C语言实现的简单但效率低下的莱文斯坦距离函数,函数给定两个字符串以及他们对应的长度s和t作为参数，并将编辑距离返回.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// len_s and len_t are the number of characters in string s and t respectively
int LevenshteinDistance(const char *s, int len_s, const char *t, int len_t)
{ 
  int cost;

  /* base case: empty strings */
  if (len_s == 0) return len_t;
  if (len_t == 0) return len_s;

  /* test if last characters of the strings match */
  if (s[len_s-1] == t[len_t-1])
      cost = 0;
  else
      cost = 1;

  /* return minimum of delete char from s, delete char from t, and delete char from both */
  return minimum(LevenshteinDistance(s, len_s - 1, t, len_t    ) + 1,
                 LevenshteinDistance(s, len_s    , t, len_t - 1) + 1,
                 LevenshteinDistance(s, len_s - 1, t, len_t - 1) + cost);
}

这种执行效率太低，因为它会多次从新计算相同字符串的编辑距离
一个更有效的方法是永远不会计算相同字符串的编辑距离,所有可能前缀的莱文斯坦距离都可以存储在一个数组d[][]中，
其中d[i][j]是字符串s的前i字符和字符串t的前j个字符的距离,这个表非常容易构造一张每次从0开始的行,当整张表建成后,距离为d[len_s][len_t]
计算编辑距离的依据是观察到，如果保存一个矩阵来持有第一个字符串前缀和第二个字符串前缀之间的编辑距离，然后我们可以用动态编程的方式来计算矩阵中的值，因次可以计算出两个完整字符串最后的值
该算法的解决是基于动态规划的思想，具体如下：
设 s 的长度为 n，t 的长度为 m。如果 n = 0，则返回 m 并退出；如果 m=0，则返回 n 并退出。否则构建一个数组 d[0..m, 0..n]。
将第0行初始化为 0..n，第0列初始化为0..m。
依次检查 s 的每个字母(i=1..n)。
依次检查 t 的每个字母(j=1..m)。
如果 s[i]=t[j]，则 cost=0；如果 s[i]!=t[j]，则 cost=1。将 d[i,j] 设置为以下三个值中的最小值：
紧邻当前格上方的格的值加一，即 d[i-1,j]+1
紧邻当前格左方的格的值加一，即 d[i,j-1]+1
当前格左上方的格的值加cost，即 d[i-1,j-1]+cost
重复3-6步直到循环结束。d[n,m]即为莱茵斯坦距离。

用全矩阵迭代

下面是一个简单的伪代码实现的LevenshteinDistance函数,函数给定了两个字符串,s字符串的长度为m,t字符串的长度为n,并且返回两个字符串的编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function LevenshteinDistance(char s[1..m], char t[1..n]):
  // for all i and j, d[i,j] will hold the Levenshtein distance between
  // the first i characters of s and the first j characters of t
  // note that d has (m+1)*(n+1) values
  declare int d[0..m, 0..n]
 
  set each element in d to zero
 
  // source prefixes can be transformed into empty string by
  // dropping all characters
  for i from 1 to m:
      d[i, 0] := i
 
  // target prefixes can be reached from empty source prefix
  // by inserting every character
  for j from 1 to n:
      d[0, j] := j
 
  for j from 1 to n:
      for i from 1 to m:
          if s[i-1] = t[j-1]:
            substitutionCost := 0
          else:
            substitutionCost := 1
          d[i, j] := minimum(d[i-1, j] + 1,                   // deletion
                             d[i, j-1] + 1,                   // insertion
                             d[i-1, j-1] + substitutionCost)  // substitution
 
  return d[m, n]

结果矩阵的两个示例

















































































k
i
t
t
e
n
0123456
s
1123456
i
2212345
t
3321234
t
4432123
i
5543223
n
6654332
g
7765443


























































































S
a
t
u
r
d
a
y

012345678
S
101234567
u
211223456
n
322233456
d
433334345
a
543444434
y
654455543

在整个算法中不变的是,我们可以转换初始片段s[1..i]到t[1..j]通过使用一个最小数d[i][j]的操作，在最后，数组右下角的元素包含答案

用两个矩阵进行迭代

结果表明，如果不想重新构造已编辑的输入字符串,则构造只需要表的两行(上一行和只计算的当前行)
可以使用以下迭代法计算编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function LevenshteinDistance(char s[1..m], char t[1..n]):
    // create two work vectors of integer distances
    declare int v0[n + 1]
    declare int v1[n + 1]

    // initialize v0 (the previous row of distances)
    // this row is A[0][i]: edit distance for an empty s
    // the distance is just the number of characters to delete from t
    for i from 0 to n:
        v0[i] = i

    for i from 0 to m-1:
        // calculate v1 (current row distances) from the previous row v0

        // first element of v1 is A[i+1][0]
        //   edit distance is delete (i+1) chars from s to match empty t
        v1[0] = i + 1

        // use formula to fill in the rest of the row
        for j from 0 to n-1:
            // calculating costs for A[i+1][j+1]
            deletionCost := v0[j + 1] + 1
            insertionCost := v1[j] + 1
            if s[i] = t[j]:
                substitutionCost := v0[j]
            else:
                substitutionCost := v0[j] + 1

            v1[j + 1] := minimum(deletionCost, insertionCost, substitutionCost)

        // copy v1 (current row) to v0 (previous row) for next iteration
        swap v0 with v1
    // after the last swap, the results of v1 are now in v0
    return v0[n]

这两行变种是次优的,所需的内存量减少到一行和一个字的开销
Hirschberg的算法可以将这两种方法分而治之,他可以在相同的时间和空间边界计算出最佳序列而不仅仅是编辑距离

通常编辑距离时间复杂度是O(M*N)，但通常我们只要一些简单的移动就能满足需要，降低点精确性，将时间复杂度降低到O(max(M, N)即可