NLP-编辑距离求解

2019-10-05 本文已影响0人 Huoyo

一、简介

编辑距离在NLP中是一种比较比较实用，且原理简单的一种算法，一般用于拼写纠错，相似度计算等，特别是在搜索领域，通过计算输入词与候选词的编辑距离，可以一定量的帮助用户进行拼写纠错。

二、原理

本文没有屌炸天的数学公式，读起来不需要那么费劲！
假设你正在百度输入框中想搜索编辑距离，结果手残输成了遍地距离，坐在你身边的女朋友哈哈大笑说你不行，然后她飞快的输入，结果...编辑剧,你扭头就是一个大笑“让你看那么剧”，为了不认怂又自己来，结果，他奶奶个球的又打错了-编辑距离的，哎，带键盘了！故事到此结束，进入正题：
上述中，有了三种情况需要转换为正确的输入：

遍地距离 ->编辑距离：需要替换遍为编，地为辑，共两个替换操作，两词的距离为2

编辑剧 ->编辑距离：需要替换剧为距，再添加一个离，共一个替换操作，一个添加操作，两词的距离为2

编辑距离的 ->编辑距离：需要删除的，共一个删除操作，两词的距离为1

上文中，为了得到正确的词，一共进行了三种操作，分别是添加、删除、替换，编辑距离正是通过这三种操作进行词的变换，得到正确词的一种手段，一个操作为一个单位的距离，两词要相等需要的做的最少操作即使两词之间的编辑距离。

三、求解分析

为了求解问题，我们找一个复杂的例子来分析一下

sduyi ->study

$word1 = sduyi$
$word2 = study$

从后面开始，一个词一个词分析，为了保证末尾相等：
要么删除sduyi的 i，这样末尾相同，只用比较
$sduy(=sduyi-i)$ 和 $study(=study)$ ->editDistance(word1[:-1],word2)
要么替换sduyi的 i 为 y，这样末尾相同，只用比较
$sduy(=sduyi-i)$ 和 $stud(=study-y)$ ->editDistance(word1[:-1],word2[:-1])
要么在sduyi添加一个y，这样末尾相同，只用比较
$sduyi(=sduyi)$ 和 $stud(=study-y)$ ->editDistance(word1,word2[:-1])

那么有三种操作，到底选取哪种呢？肯定是选择这三种中距离最小的一种，而且可以发现以上的过程可以用一个递归来求解，字符创的裁剪过程是一样的，不断的调用递归即可，那么递归什么时候停止呢，有以下几种情况：

word1截取完毕，只剩下word2的个别字符word2_left，那么剩余的编辑距离就是len(word2_left)
word2截取完毕，只剩下word1的个别字符word1_left，那么剩余的编辑距离就是len(word1_left)

四、递归求解

def editDistance(word1, word2):
    # word1截取完毕
    if len(word1) == 0:
        return len(word2)
    # word2截取完毕
    if len(word2) == 0:
        return len(word1)

    # 如果word1和word2的末尾相等，那么只用比较word1[:len(word1)-1], word2[:len(word2)-1]
    if word1[-1] == word2[-1] :
        return editDistance(word1[:len(word1)-1], word2[:len(word2)-1])
    # 没有满足上述条件的时候，递归求解三种操作的最小编辑距离
    return 1 + min(
                   editDistance(word1, word2[:len(word2)-1]),
                   editDistance(word1[:len(word1)-1], word2),
                   editDistance(word1[:len(word1)-1], word2[:len(word2)-1])
                   )

五、动态规划求解

关于动态规划，https://blog.csdn.net/qq_21120275/article/details/100344151
这篇文章中已经提到过，要先找到三个关键因素

image.png

最优子问题就是上述分析中，从末尾开始，的三种操作的最距离（也可以从前面开始）即：

# +1是因为最后一位的删除、插入或者替换产生了一位的操作
  min(
        editDistance(word1, word2[:len(word2)-1])+1,
        editDistance(word1[:len(word1)-1], word2)+1,
        editDistance(word1[:len(word1)-1], word2[:len(word2)-1])+1
      )

状态转移返程也在上面的代码中体现了,min里面的三种转移过程
至于边界条件就是上述递归中的终止条件，根据以上代码如下：

def edit_distance(word1,word2):
    # 构建dp矩阵存储中间过程变量
    dp = np.zeros([len(word1)+1,len(word2)+1])
    print(dp)
    for i in range(len(word1)+1):
        for j in range(len(word2)+1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(
                    dp[i][j-1]+1,
                    dp[i-1][j]+1,
                    dp[i-1][j-1]+1
                )
    return dp[len(word1)][len(word2)]

六、现成的轮子

关于现成的轮子情参考Levenshtein，安装以后直接调用即可

本文如有什么错误还望大神指正！