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

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

Алгоритм

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

${\displaystyle \qquad d_{a,b}(i,j)={\begin{cases}\max(i,j)&{\text{ если}}\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{ если }}i,j>1{\text{ и }}a_{i}=b_{j-1}{\text{ и }}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{ иначе,}}\end{cases}}}$

где ${\displaystyle 1_{(a_{i}\neq b_{j})}}$ это индикаторная функция, равная нулю при ${\displaystyle a_{i}=b_{j}}$ и 1 в противном случае.

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

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

Реализации

На python

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]

Delphi

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;

На Ada

   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;

На Visual Basic for Applications (VBA)

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

На Java

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