Расстояние Дамерау — Левенштейна

Расстояние Дамерау — Левенштейна (названо в честь учёных Шаблон:Не переведено и Владимира Левенштейна) — это мера разницы двух строк символов, определяемая как минимальное количество операций вставки, удаления, замены и транспозиции (перестановки двух соседних символов), необходимых для перевода одной строки в другую. Является модификацией расстояния Левенштейна: к операциям вставки, удаления и замены символов, определённых в расстоянии Левенштейна добавлена операция транспозиции (перестановки) символов.

Алгоритм

Расстояние Дамерау — Левенштейна между двумя строками $a$ и $b$ определяется функцией $d_{a,b}(|a|,|b|)$ как:

$d_{a,b}(i,j)=\{\begin{array}{cc}\max (i,j)& \text{ если}\min (i,j)=0,\\ \min \{\begin{array}{c}{d}_{a,b}(i-1,j)+1\\ d_{a,b}(i,j-1)+1\\ d_{a,b}(i-1,j-1)+1_{(a_i\ne b_j)}\\ d_{a,b}(i-2,j-2)+1\end{array}& \text{ если }i,j>1\text{ и }{a}_i=b_{j-1}\text{ и }{a}_{i-1}=b_j\\ \min \{\begin{array}{c}{d}_{a,b}(i-1,j)+1\\ d_{a,b}(i,j-1)+1\\ d_{a,b}(i-1,j-1)+1_{(a_i\ne b_j)}\end{array}& \text{ иначе,}\end{array}$

где $1_{(a_i\ne b_j)}$ это индикаторная функция, равная нулю при $a_i=b_j$ и 1 в противном случае.

Каждый рекурсивный вызов соответствует одному из случаев:

• $d_{a,b}(i-1,j)+1$ соответствует удалению символа (из a в b),
• $d_{a,b}(i,j-1)+1$ соответствует вставке (из a в b),
• $d_{a,b}(i-1,j-1)+1_{(a_i\ne b_j)}$ соответствие или несоответствие, в зависимости от совпадения символов,
• $d_{a,b}(i-2,j-2)+1$ в случае перестановки двух последовательных символов.

Реализации

def damerau_levenshtein_distance(s1, s2):
    d = {}
    lenstr1 = len(s1)
    lenstr2 = len(s2)
    for i in range(-1,lenstr1+1):
        d[(i,-1)] = i+1
    for j in range(-1,lenstr2+1):
        d[(-1,j)] = j+1
 
    for i in range(lenstr1):
        for j in range(lenstr2):
            if s1[i] == s2[j]:
                cost = 0
            else:
                cost = 1
            d[(i,j)] = min(
                           d[(i-1,j)] + 1, # deletion
                           d[(i,j-1)] + 1, # insertion
                           d[(i-1,j-1)] + cost, # substitution
                          )
            if i and j and s1[i] == s2[j-1] and s1[i-1] == s2[j]:
                d[(i,j)] = min(d[(i,j)], d[i-2,j-2] + 1) # transposition
 
    return d[lenstr1-1,lenstr2-1]

function damerau_levenshtein_distance(s1, s2: string): integer;
begin
  var d: TArray<TArray<integer>>;
  SetLength(d, Length(s1) + 1);
  for var i := Low(d) to High(d) do
    SetLength(d[i], Length(s2) + 1);

  for var i := Low(d) to High(d) do
  begin
    d[i, 0] := i;
    for var j := Low(d[i]) to High(d[i]) do
      d[0, j] := j;
  end;

  for var i := Low(d) + 1 to High(d) do
    for var j := Low(d[i]) + 1 to High(d[i]) do
      d[i, j] := Min(Min(
        d[i - 1, j] + 1,
        d[i, j - 1] + 1),
        d[i - 1, j - 1] + IfThen(s1[i] = s2[j], 0, 1));

  Result := d[Length(s1), Length(s2)];
end;

   function Damerau_Levenshtein_Distance (L, R : String) return Natural is
      D : array (L'First - 1 .. L'Last, R'First - 1 .. R'Last) of Natural;
   begin
      for I in D'Range (1) loop
         D (I, D'First (2)) := I;
      end loop;

      for I in D'Range (2) loop
         D (D'First (1), I) := I;
      end loop;

      for J in R'Range loop
         for I in L'Range loop
            D (I, J) :=
              Natural'Min
                (Natural'Min (D (I - 1, J), D (I, J - 1)) + 1,
                 D (I - 1, J - 1) + (if L (I) = R (J) then 0 else 1));

            if J > R'First and then I > L'First
              and then R (J) = L (I - 1) and then R (J - 1) = L (I)
            then
               D (I, J) := Natural'Min (D (I, J), D (I - 2, J - 2) + 1);
            end if;
         end loop;
      end loop;

      return D (L'Last, R'Last);
   end Damerau_Levenshtein_Distance;

Public Function WeightedDL(source As String, target As String) As Double

    Dim deleteCost As Double
    Dim insertCost As Double
    Dim replaceCost As Double
    Dim swapCost As Double

    deleteCost = 1
    insertCost = 1
    replaceCost = 1
    swapCost = 1

    Dim i As Integer
    Dim j As Integer
    Dim k As Integer

    If Len(source) = 0 Then
        WeightedDL = Len(target) * insertCost
        Exit Function
    End If

    If Len(target) = 0 Then
        WeightedDL = Len(source) * deleteCost
        Exit Function
    End If

    Dim table() As Double
    ReDim table(Len(source), Len(target))

    Dim sourceIndexByCharacter() As Variant
    ReDim sourceIndexByCharacter(0 To 1, 0 To Len(source) - 1) As Variant

    If Left(source, 1) <> Left(target, 1) Then
        table(0, 0) = Application.Min(replaceCost, (deleteCost + insertCost))
    End If

    sourceIndexByCharacter(0, 0) = Left(source, 1)
    sourceIndexByCharacter(1, 0) = 0

    Dim deleteDistance As Double
    Dim insertDistance As Double
    Dim matchDistance As Double

    For i = 1 To Len(source) - 1

        deleteDistance = table(i - 1, 0) + deleteCost
        insertDistance = ((i + 1) * deleteCost) + insertCost

        If Mid(source, i + 1, 1) = Left(target, 1) Then
            matchDistance = (i * deleteCost) + 0
        Else
            matchDistance = (i * deleteCost) + replaceCost
        End If

        table(i, 0) = Application.Min(Application.Min(deleteDistance, insertDistance), matchDistance)
    Next

    For j = 1 To Len(target) - 1

        deleteDistance = table(0, j - 1) + insertCost
        insertDistance = ((j + 1) * insertCost) + deleteCost

        If Left(source, 1) = Mid(target, j + 1, 1) Then
            matchDistance = (j * insertCost) + 0
        Else
            matchDistance = (j * insertCost) + replaceCost
        End If

        table(0, j) = Application.Min(Application.Min(deleteDistance, insertDistance), matchDistance)
    Next

    For i = 1 To Len(source) - 1

        Dim maxSourceLetterMatchIndex As Integer

        If Mid(source, i + 1, 1) = Left(target, 1) Then
            maxSourceLetterMatchIndex = 0
        Else
            maxSourceLetterMatchIndex = -1
        End If

        For j = 1 To Len(target) - 1

            Dim candidateSwapIndex As Integer
            candidateSwapIndex = -1

            For k = 0 To UBound(sourceIndexByCharacter, 2)
                If sourceIndexByCharacter(0, k) = Mid(target, j + 1, 1) Then candidateSwapIndex = sourceIndexByCharacter(1, k)
            Next

            Dim jSwap As Integer
            jSwap = maxSourceLetterMatchIndex

            deleteDistance = table(i - 1, j) + deleteCost
            insertDistance = table(i, j - 1) + insertCost
            matchDistance = table(i - 1, j - 1)

            If Mid(source, i + 1, 1) <> Mid(target, j + 1, 1) Then
                matchDistance = matchDistance + replaceCost
            Else
                maxSourceLetterMatchIndex = j
            End If

            Dim swapDistance As Double

            If candidateSwapIndex <> -1 And jSwap <> -1 Then

                Dim iSwap As Integer
                iSwap = candidateSwapIndex

                Dim preSwapCost
                If iSwap = 0 And jSwap = 0 Then
                    preSwapCost = 0
                Else
                    preSwapCost = table(Application.Max(0, iSwap - 1), Application.Max(0, jSwap - 1))
                End If

                swapDistance = preSwapCost + ((i - iSwap - 1) * deleteCost) + ((j - jSwap - 1) * insertCost) + swapCost

            Else
                swapDistance = 500
            End If

            table(i, j) = Application.Min(Application.Min(Application.Min(deleteDistance, insertDistance), _
                            matchDistance), swapDistance)

        Next

        sourceIndexByCharacter(0, i) = Mid(source, i + 1, 1)
        sourceIndexByCharacter(1, i) = i

    Next

    WeightedDL = table(Len(source) - 1, Len(target) - 1)

End Function

import java.util.Arrays;

public class DamerauLevenshteinDistance {

    public static int calculate(String str1, String str2) {
        int[][] matrix = new int[str1.length() + 1][str2.length() + 1];

        // Инициализация первой строки и первого столбца
        for (int i = 0; i <= str1.length(); i++) {
            matrix[i][0] = i;
        }
        for (int j = 0; j <= str2.length(); j++) {
            matrix[0][j] = j;
        }

        // Заполнение матрицы
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                int cost = (str1.charAt(i - 1) == str2.charAt(j - 1)) ? 0 : 1;

                matrix[i][j] = Math.min(
                        matrix[i - 1][j] + 1, // Удаление
                        Math.min(
                                matrix[i][j - 1] + 1, // Вставка
                                matrix[i - 1][j - 1] + cost // Замена
                        )
                );

                // Проверка на перестановку
                if (i > 1 && j > 1 && str1.charAt(i - 1) == str2.charAt(j - 2) && str1.charAt(i - 2) == str2.charAt(j - 1)) {
                    matrix[i][j] = Math.min(matrix[i][j], matrix[i - 2][j - 2] + cost);
                }
            }
        }

        return matrix[str1.length()][str2.length()];
    }

    public static void main(String[] args) {
        String str1 = "kitten";
        String str2 = "sitting";

        int distance = calculate(str1, str2);
        System.out.println("Расстояние Дамерау-Левенштейна между \"" + str1 + "\" и \"" + str2 + "\": " + distance);
    }
}

См. также

• Расстояние Левенштейна

Ссылки

• Реализации алгоритма на различных языках программирования:
  • На языке программирования Perl в виде модуля Text::Levenshtein::Damerau
  • На языке программирования PlPgSQL
  • Дополнительный модуль для MySQL