编辑距离算法

在 Mon 18 April 2016 发布于 文本算法 分类

编辑距离, 又叫Levenshtein距离。在wiki上的解释是: 两个不同的字符串, 其中一个字符串转在单字符操作(替换, 插入, 删除)下换成另外一个字符串所需的最少的编辑次数。

例如, 字符串"kitten"转换为字符串"sitting"的编辑次数为3, 且没有比这更少的编辑次数, 过程如下:

  1. kitten --> sitten(k替换成s)

  2. sitten --> sittin(i替换成e)

  3. sittin --> sitting(在字符串末端插入g)

其算法描述的:

现有两个字符串 \(a\)\(b\), 其长度分别为\(m\)\(n\)\(i\)\(j\)分别代表\(a\)中下标为\(i\)的字符\(a_{i}\)以及\(b\)中下标为\(j\)的字符\(b_{j}\)。如果\(a_{i} = b_{j}\)则其编辑距离为0,否则,其编辑距离就为1。 我们最终需要解决的是怎样求得\(a[0...i]\)转换到\(b[0...j]\)的编辑距离。先来看看最简单的情况:

\(m = 0 或 n = 0\)时,其编辑距离是非空字符串的长度(即插入操作)。

\(m = n = 1\)时, 其编辑距离无非就是1或者0。

\(m > 1, n > 1\)是,这时分以下三种情况:

  1. 如果把字符串\(a[0..i]\)转换为\(b[0...j-1]\)需要的的编辑距离为\(Len_{a, b}(i -1, j)\),那把\(b[j]\)加到\(a\)的后面(插入操作),完成\(a[0...i]\) 转换为\(b[0...j]\)的编辑距离为\(Len_{a,b}(i, j-1) + 1\)

  2. 如果把字符串\(a[0...i-1]\)转换为\(b[0...j]\)需要的编辑距离为\(Len_{a,b}(i - 1, j)\), 那把\(a[i]\)\(a\)的后面删除(删除操作), 完成\(a[0...i]\)转换为\(b[0...j]\)的编辑距离为\(Len_{a,b}(i - 1, j) + 1\)

  3. 如果把字符串\(a[0...i-1]\)转换为\({b[0...j-1]}\)的编辑距离为\(Len_{a,b}(i - 1, j - 1)\), 那完成\(a[0...i]\)转换为\(b[0...j]\)的编辑距离就是\(Len_{a, b}(i - 1, j -1) + 1_(a_{i} != a_{j})\)

取上述三种情况下,编辑距离最小的为最终的编辑距离。

根据上面的算法描述,可以得到一个公式:

下面给出算法的实现(Python版本):

def LevenshteinDistance(strA, strB):
    lenA = len(strA)
    lenB = len(strB)
    LevenshteinMap = {(x, y) : 0 for x in range(lenA + 1) for y in range(lenB + 1)} 
    for i in range(0, lenA + 1): 
        LevenshteinMap[(i, 0)] = i 
    for j in range(0, lenB + 1): 
        LevenshteinMap[(0, j)] = j 
    for j in range(1, lenB + 1): 
        for i in range(1, lenA + 1): 
            if strA[i-1] == strB[j-1]:
                cost = 0 
            else:
                cost = 1 
            if i == 0 and j ==0:
                LevenshteinMap[(0, 0)] = cost
                continue
            LevenshteinMap[(i, j)] = min(LevenshteinMap[(i -1, j)] + 1,
                                        LevenshteinMap[(i, j - 1)] + 1,
                                        LevenshteinMap[(i - 1 , j - 1)] + cost)
    return LevenshteinMap[(lenA, lenB)]