编辑距离4：Damerau–Levenshtein distance

2024-02-17 23:13:46

一、基本概念

1.1 基本编辑距离的定义

在学习Levenshtein 距离的时候，其定义为：

基础的编辑距离只有3种原子操作：

插入1个字符，
删除1个字符，
更改1个字符.

且3种操作的代价均为1.

设串A为a1 a2 ... am, 串B为b1 b2 ... bn；将串A经过n个操作x1 - x2 - ... - xn，使之变成串B，且该操作序列为最优操作（代价之和最小）的一种，则2个串的L氏距离即为该序列代价之和。通常3个操作的代价都为1,也有可能按某种方案加权（即3种操作的代价不一致，导致更复杂的情况，这里只讨论都是1的）

1.2 Damerau–Levenshtein distance编辑距离的定义

Damerau–Levenshtein distance定义，通俗地说，两个单词之间的 Damerau-Levenshtein 距离是将一个单词变为另一个单词所需的最小操作数：

包括单个字符的插入、
删除或
替换
或两个相邻字符的转置

可见Damerau-Levenshtein 距离与经典 Levenshtein 距离的不同之处在于，除了三个经典的单字符编辑操作（插入、删除和替换）之外，它还包括在其允许操作中的换位。

在他的开创性论文中，[5] Damerau 表示，在对信息检索系统的拼写错误的调查中，超过 80% 是由四种类型中的一种错误造成的。 Damerau 的论文只考虑了最多可以通过一次编辑操作纠正的拼写错误。虽然最初的动机是测量人类拼写错误之间的距离以改进拼写检查器等应用程序，但 Damerau-Levenshtein 距离也已在生物学中用于测量蛋白质序列之间的变异。

1.3 Damerau–Levenshtein distance编辑距离的数学定义

为了表示两个字符串 a 和 b 之间的 Damerau-Levenshtein 距离，函数 d_{a,b}(i, j) 被定义，其值为字符串a 的i-symbol 前缀（初始子串）与 b的 j-symbol 前缀之间的距离湾。受限距离函数递归定义为：[7]:

其中是当否则等于 1。每个递归调用都匹配 Damerau-Levenshtein 距离所涵盖的一种情况：

对应于删除（从 a 到 b）

对应于插入（从 a 到 b）

对应匹配或不匹配，取决于各自的符号是否相同，

对应于两个连续符号之间的转置。

然后，a 和 b 之间的 Damerau-Levenshtein 距离由完整字符串的函数值给出： {\displaystyle d_{a,b}{\big (}|a|,|b|{\big )}}{\displaystyle d_{a,b}{\big (}|a|,|b|{\big )}}，其中 {\displaystyle i=|a|}{\displaystyle i=|a|} 表示字符串 a 的长度, {\displaystyle j=|b|}{\displaystyle j=|b|} 是 b 的长度。

二、 Damerau-Levenshtein 距离的算法

这里介绍了两种算法：第一种，[8] 更简单的一种，计算所谓的最佳字符串对齐距离或受限编辑距离，[7] 而第二种[9] 计算具有相邻换位的 Damerau-Levenshtein 距离。添加转置会显着增加复杂性。两种算法之间的区别在于，最佳字符串对齐算法计算在没有子字符串被多次编辑的情况下使字符串相等所需的编辑操作数，而第二种算法则没有这样的限制。

以 CA 和 ABC 之间的编辑距离为例。 Damerau-Levenshtein 距离 LD(CA, ABC) = 2 因为 CA → AC → ABC，但最佳字符串对齐距离 OSA(CA, ABC) = 3 因为如果使用操作 CA → AC，则无法使用AC → ABC，因为这将需要多次编辑子字符串，这在 OSA 中是不允许的，因此最短的操作序列是 CA → A → AB → ABC。请注意，对于最佳字符串对齐距离，三角不等式不成立：OSA(CA, AC) + OSA(AC, ABC) < OSA(CA, ABC)，因此它不是真正的度量。

三、算法伪代码

algorithm OSA-distance is
    input: strings a[1..length(a)], b[1..length(b)]
    output: distance, integer
    
    let d[0..length(a), 0..length(b)] be a 2-d array of integers, dimensions length(a)+1, length(b)+1
    // note that d is zero-indexed, while a and b are one-indexed.
    
    for i := 0 to length(a) inclusive do
        d[i, 0] := i
    for j := 0 to length(b) inclusive do
        d[0, j] := j
    
    for i := 1 to length(a) inclusive do
        for j := 1 to length(b) inclusive do
            if a[i] = b[j] then
                cost := 0
            else
                cost := 1
            d[i, j] := minimum(d[i-1, j] + 1,     // deletion
                               d[i, j-1] + 1,     // insertion
                               d[i-1, j-1] + cost)  // substitution
            if i > 1 and j > 1 and a[i] = b[j-1] and a[i-1] = b[j] then
                d[i, j] := minimum(d[i, j],
                                   d[i-2, j-2] + 1)  // transposition
    return d[length(a), length(b)]
The difference from the algorithm for Levenshtein distance is the addition of one recurrence:

if i > 1 and j > 1 and a[i] = b[j-1] and a[i-1] = b[j] then
    d[i, j] := minimum(d[i, j],
                       d[i-2, j-2] + 1)  // transposition

码农公寓