编辑距离算法详解和python代码

编辑距离(Levenshtein Distance)算法详解和python代码

最近做NLP用到了编辑距离,网上学习了很多,看到很多博客写的有问题,这里做一个编辑距离的算法介绍,步骤和多种python代码实现,编辑距离有很多个定义,比如Levenshtein距离,LCS距离,汉明距离等,我们这里将Levenshtein距离默认为编辑距离。

基本概念:

编辑距离是指两个字符串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作仅包括删除、加入、取代字符串中的任何一个字符。
它是由俄罗斯科学家Vladimir Levenshtein在1965年提出,中文名叫做莱文斯坦距离。
例如将 jary 转为 jerry;

  1. jery (a→e)
  2. jerry(add r)

主要思想

假设我们可以使用d[i, j]个步骤(可以使用一个二维数组保存这个值),表示将字符串 s[ : i ] 转换为字符串 t[ : j ] 所需要的最少编辑操作次数,那么,考虑一个特殊情况,即在 i = 0,即s为空时,那么对应的d[0, j] 就是增加 j 个字符,使得 s 转化为 t;反之,在 j = 0,即t为空时,对应的d[i, 0] 就是减少 i 个字符,使得s转化为t。
然后我们考虑一般情况,利用动态规划的思想,我们要想得到将 s[ : i ]经过最少次数的增加,删除,或者替换操作就转变为 t[ : j ],那么我们就必须在最后一步操作之前可以以最少次数的增加,删除,或者替换操作,使得现在 s 和 t 只需要再做一次操作或者不做就可以完全相等。
根据动态规划和贝尔曼最优性原理,这里的"最后一步操作之前"指的是:

  1. 在k个操作内将 s[ : i ] 转换为 t[ : j-1 ]
  2. 在k个操作里面将 s[ : i-1 ] 转换为 t[ : j ]
  3. 在k个步骤里面将 s[ : i-1 ] 转换为 t[ : j -1]

于是,与之对应的最后一步操作即为:

  1. 最后将 t[j] 加上s[ : i ]就完成了匹配,这样总共就需要 k+1 个操作
  2. 最后将 s[i] 移除,也完成了匹配,所以总共需要 k+1 个操作
  3. 最后将 s[i] 替换为 t[j],完成匹配,这样总共也需要 k+1个操作。而如果在第3种情况下,s[i ]刚好等于 t[j],那我 们就仅仅使用了k个操作就完成这个过程。

所以现在问题变为:为了保证得到的操作总次数最少,我们需要从上面三种情况中选择消耗最少的一种。

基本步骤

  1. 初始化行数为m+1 列数为 n+1 的矩阵 matrix, 用来保存完成某个转换需要执行的操作的次数,那么将 s[ 1 : n ] 变为t[ 1 : m ] 所需要执行的操作次数为matrix[n][m]的值;

  2. 初始化matrix第一行为0到n,第一列为0到m。Matrix[0][j]表示第1行第j+1列的值,这个值表示将串s[1 : 0]=[]转换为 t[1 : j] 所需要执行的操作的次数,很显然将一个空串转换为一个长度为 j 的串,只需要 j 次的add操作,所以matrix[0][j]的值应该是 j,其他值以此类推。

  3. 检查每个从1到n的 s[i] 字符;

  4. 检查每个从1到m的 t[j] 字符;

  5. 将串 s 和串 t 的每一个字符进行两两比较,如果相等,则让cost为0,如果不等,则让cost为1(这个cost后面会用到);

  6. a、如果我们可以在k个操作里面将s[1:i-1]转换为t[1:j],也就是说matrix[i-1,j]=k, 那么我们就可以将s[i]移除,然后再做这k个操作,所以总共需要k+1个操作。
    b、如果我们可以在k个操作内将 s[1:i] 转换为 t[1:j-1] ,也就是说matrix[i,j-1]=k,那么我们就可以将 t[j] 加上s[1:i],这样总共就需要k+1个操作。
    c、如果我们可以在k个步骤里面将 s[1:i-1] 转换为 t [1:j-1],那么我们就可以将s[i]转换为 t[j],使得满足s[1:i] == t[1:j],这样总共也需要k+1个操作。(这里需要加上cost,是因为如果s[i]刚好等于t[j],那么就不需要再做替换操作,即可满足,如果不等,则需要再做一次替换操作,那么就需要k+1次操作)
    因为我们要取得最小操作的个数,所以我们最后还需要将这三种情况的操作个数进行比较,取最小值作为matrix[ i , j ]的值;

  7. 然后重复执行3,4,5,6,最后的结果就在matrix[m,n]中;

文字看的不清不楚没有关系,我们下面以图解解释下每一个步骤,还是以"jary" → "jerry"为例。

图解如下

步骤1:初始化矩阵如下:
编辑距离算法详解和python代码_第1张图片
步骤2:从源串"jary"的第一个字符"j"开始,自上而下与目标串"jerry"比较
编辑距离算法详解和python代码_第2张图片
如果两个字符相等,则cost = 0, 如果两个字符不相等,则cost = 1。
当前值从此位置的 左+1,上+1和 左上+cost 三个值中取最小值。
第一次,源串第一个字符“j” 与目标串的“j”对比,左+1,上+1,左上+cost三个值中取出最小的值0,因为两字符相等,所以加上0;接着,依次对比“j”→“e”,“j”→“r”,“j”→“r”,,“j”→“y” 到扫描完目标串。
编辑距离算法详解和python代码_第3张图片
步骤三:遍历整个源串与目标串每一个字符比较
编辑距离算法详解和python代码_第4张图片
编辑距离算法详解和python代码_第5张图片
编辑距离算法详解和python代码_第6张图片
步骤四:遍历完成,则matrix[m][n]即为所求编辑距离
求出编辑距离后,可以计算两个字符串的相似度Similarity = 1 − L e v e n s h t e i n max ⁡ ( s , t ) 1-\frac{Levenshtein}{\max(s,t)} 1max(s,t)Levenshtein,其中s,t分别是源串和目标串的长度。

代码实现

1. 利用python的三方库Levenshtein,调用Levenshtein.distance(str1,str2)方法即可,这是内部调用c库,优化了算法结构的,比我们按照上面那个步骤写的代码快。
2. 利用Numpy,DP,wiki上的代码 python_code.
2.一个简单的代码,用python的list实现

#!/usr/bin/env python
# -*- coding: cp936 -*-
def edit_distance(str1, str2):
'''
        :type str1: str
        :type str2: str
        :rtype: int
'''
    matrix = [[i+j for j in xrange(len(str2) + 1)] for i in xrange(len(str1) + 1)]
    for i in xrange(1,len(str1)+1):
        for j in xrange(1,len(str2)+1):
            if str1[i-1] == str2[j-1]:
                d = 0
            else:
                d = 1
            matrix[i][j] = min(matrix[i-1][j]+1,matrix[i][j-1]+1,matrix[i-1][j-1]+d)
    return matrix[len(str1)][len(str2)]

参考文献

  • 编辑距离算法详解:Levenshtein Distance算法.
  • 编辑距离.

你可能感兴趣的