字符串编辑距离之Damerau–Levenshtein Distance

时间 2020-07-26 标签字符串编辑距离 damerau levenshtein distance

概述

Damerau–Levenshtein Distance用来测量两个字符序列之间的编辑距离的字符串度量标准。两个词的Damerau–Levenshtein Distance是从一个词转换为另外一个词的最少操做数，与Levenshtein Distance不一样的是，除了单个字符的插入、删除和变动以外，还包括两个相邻字符的转换。函数

定义

对于两个字符串、，函数 $d_{a,b}(i,j)$ 表示的前个字符与的前个字符的编辑距离：.net

$d_{a,b}(i,j)=\begin{cases} \max(i,j) & \text {if } \min(i,j)=0 \\ \min\begin{cases} d_{a,b}(i-1,j)+1\\ d_{a,b}(i,j-1)+1\\ d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}\\ d_{a,b}(i-2,j-2)+1 \end{cases}& \text {if }i,j> 1 \text{ and }a_{i}=b_{j-1}\text{ and }a_{i-1}=b_{j}\\ \min\begin{cases} d_{a,b}(i-1,j)+1\\ d_{a,b}(i,j-1)+1\\ d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})} \end{cases}& \text{otherwise} \end{cases}$

当 $i,j> 1 \text{ and }a_{i}=b_{j-1}\text{ and }a_{i-1}=b_{j}$ 时，除了要计算Levenshtein Distance中所定义的插入、删除和变动操做的操做数之外，还要计算相邻字符转换的操做数，而后将四个操做数作对比取最小的值。code

示例

以字符串：aborad和：aboard为例，求值过程以下图：blog

图片制做中。。。图片

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

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