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

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

Расстояние Дамерау — Левенштейна между двумя строками ${\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}$ в случае перестановки двух последовательных символов.

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);
    }
}

На C#^[1]

private static int DamerauLevenshteinDistance(string str1, string str2)
{
    int len1 = str1.Length;
    int len2 = str2.Length;

    char[] arr1 = str1.ToCharArray();
    char[] arr2 = str2.ToCharArray();

    int[,] matrix = new int[len1 + 1, len2 + 1];

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

    // Заполнение матрицы
    for (int i = 1; i <= len1; i++)
    {
        for (int j = 1; j <= len2; j++)
        {
            int cost = (arr1[i - 1] == arr2[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 && arr1[i - 1] == arr2[j - 2] && arr1[i - 2] == arr2[j - 1])
            {
                matrix[i, j] = Math.Min(matrix[i,j], matrix[i - 2, j - 2] + cost);
            }
        }
    }

    return matrix[len1, len2];
}

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

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