TensorFlow

Python如何计算编辑距离?

2019-01-19  本文已影响229人  妄心xyx

算法原理

在计算文本的相似性时,经常会用到编辑距离。编辑距离,又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。通常来说,编辑距离越小,两个文本的相似性越大。这里的编辑操作主要包括三种:

下面通过示例来看一下。

将字符串batyu变为beauty,编辑距离是多少呢?这需要经过如下步骤:

1、batyu变为beatyu(插入字符e)

2、beatyu变为beaty(删除字符u)

3、beaty变为beauty(插入字符u)

所以编辑距离为3。

那么,如何用Python计算编辑距离呢?我们可以从较为简单的情况进行分析。

很明显,上述算法的思想即为动态规划

求长度为m和n的字符串的编辑距离,首先定义函数——edit(i, j),它表示第一个长度为i的字符串与第二个长度为j的字符串之间的编辑距离。动态规划表达式可以写为:

最终的编辑距离即为edit(m,n)。上述示例的edit矩阵可以表示如下:

image

Python代码实现

Talk is cheap. Show me the code. Python代码也是极其简洁的,这也是动态规划的魅力:

image

扩展

那么,Python功能这么强大,有没有计算编辑距离的包呢?

答案是肯定的,Python中的Levenshtein包可以用来计算编辑距离,安装方法很简单,直接安装即可:

pip install python-Levenshtein

这样我们就可以引入包直接计算编辑距离了:

image

有同学可能想计算汉字之间的编辑距离,如下:

image

得到的结果是3而不是1。这是因为在字符串编码为utf-8时,一个汉字占用3个字节。改为unicode编码即可得到1,即:

image

那么,Levenshtein包中还有没有其它计算距离的方法呢?

这个包有很多计算距离的方法,包括如下:

总结

上一篇下一篇

猜你喜欢

热点阅读