字符串编辑距离之LevenshteinDistance

时间 2020-07-26 标签字符串编辑距离 levenshteindistance

概述

Levenshtein Distance是一个度量两个字符序列之间差别的字符串度量标准，两个单词之间的Levenshtein Distance是将一个单词转换为另外一个单词所需的单字符编辑（插入、删除或替换）的最小数量。Levenshtein Distance是1965年由苏联数学家Vladimir Levenshtein发明的。Levenshtein Distance也被称为编辑距离（Edit Distance）。数组

定义

对于两个字符串、，长度分别为 $\left | a \right |$ 、 $\left | b \right |$ ，它们的Levenshtein Distance $\operatorname{lev}_{a,b}(|a|,|b|)$ 为：3d

$\operatorname{lev}_{a,b}(i,j)=\left\{\begin{matrix} max(j,j)& \text{if min}(i,j)=0\\ min\left\{\begin{matrix} \operatorname{lev}_{a,b}(i-1,j)+1 \\ \operatorname{lev}_{a,b}(i,j-1)+1 \\ \operatorname{lev}_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})} \end{matrix}\right.& \text{otherwise} \end{matrix}\right.$

其中当 $a_{i}=b_{j}$ 时， $1_{(a_{i}\neq b_{j})}$ 为0，不然为1。 $\operatorname{lev}_{a,b}(i,j)$ 就是的前个字符与的前个字符的编辑距离。code

、的类似度 $Sim_{a,b}$ 为 $Sim_{a,b}=1-(\operatorname{lev}_{a,b}(\left | a \right |,\left | b \right |)/max(\left | a \right |,\left | b \right |))$ 。blog

原理

首先考虑极端状况，当或长度为0时，那么须要编辑的次数就是里一个字符串的长度。字符串

而后再考虑通常状况，此时分为三种状况：数学

在k个操做中，将a[1...i]转换为b[1...j-1]
在k个操做中，将a[1...i-1]转换为b[1...j]
在k个操做中，将a[1...i-1]转换为b[1...j-1]

针对第一种状况，只须要在a[1...i]后加上字符b[j]，便可完成a[1..i]到b[1...j]的转换，总共须要的编辑次数即为k+1。it

针对第二种状况，只须要在a[i]字符从a中移除，便可完成a[1..i]到b[1...j]的转换，总共须要的编辑次数即为k+1。io

针对第三种状况，只须要将a[i]转换为b[j]，便可完成a[1..i]到b[1...j]的转换，若是a[i]与b[i]的字符相同，则总共须要的编辑次数为k，不然即为k+1。class

因此上述三种状况分别对应于插入、删除、替换操做。原理

为了保证将a[1..i]转换为b[1..j]的操做数老是最少的，只须要从三种状况中选择操做次数最少的状况，同理为了保证三种状况的操做数也是最小的，只须要按此逻辑进行迭代保证每一步的操做数都是最小的便可。

示例

为方便理解，以字符串：abroad和：aboard为例，将求值过程当中每一步的操做数放入一个i+1行j+1列的二维数组中，即为将a[1..i]转换为b[1...j]所须要的最少的操做数。

1.首先是极端状况，即d[0][j]、d[i][0]即a为空字符串或b为空字符串时，须要操做的次数即为另外一字符串的长度。

2.而后是通常状况，即d[i][j]的值，遍历这个二维数组，从第一行开始直到最后一行，由定义可知d[i][j]的值为d[i-1][j]+一、d[i][j-1]+1以及d[i-1][j-1]+1（若是a[i]==b[j]）的最小值。即根据d[i][j]所在位置的正上方（d[i-1][j]）、左方以（d[i-1][j]）及左上方（d[i-1][j-1]）的值计算出d[i][j]的值，由此获得二维数组中全部元素的值。

3.最后的d[i][j]即为字符串a转换为b的最少操做数。

求值过程以下图：

如图字符串、的Levenshtein Distance $\operatorname{lev}_{a,b}(6,6)$ 为2，类似度 $Sim_{a,b}$ 为：

$Sim_{a,b}=1-(\operatorname{lev}_{a,b}(6,6)/max(6,6))=0.666\cdots$