Просмотр кода страницы Расстояние Дамерау — Левенштейна

'''Расстояние Дамерау — Левенштейна''' (названо в честь учёных {{Не переведено|Фредерик Дамерау|Фредерика Дамерау|en|Frederick J. Damerau}} и [[Левенштейн, Владимир Иосифович|Владимира Левенштейна]]) — это мера разницы двух строк символов, определяемая как минимальное количество операций вставки, удаления, замены и транспозиции (перестановки двух соседних символов), необходимых для перевода одной строки в другую. Является модификацией [[Расстояние Левенштейна|расстояния Левенштейна]]: к операциям вставки, удаления и замены символов, определённых в расстоянии Левенштейна добавлена операция [[Транспозиция (математика)|транспозиции]] (перестановки) символов.

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

<math>\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}</math>

где <math>1_{(a_i \neq b_j)}</math> это [[Индикатор (математика)|индикаторная функция]], равная нулю при <math>a_i = b_j</math> и 1 в противном случае.

Каждый рекурсивный вызов соответствует одному из случаев:
* <math>d_{a,b}(i-1,j) + 1</math> соответствует удалению символа (из ''a'' в ''b''),
* <math>d_{a,b}(i,j-1) + 1</math> соответствует вставке (из ''a'' в ''b''),
* <math>d_{a,b}(i-1,j-1) + 1_{(a_i \neq b_j)} </math> соответствие или несоответствие, в зависимости от совпадения символов,
* <math>d_{a,b}(i-2,j-2) + 1 </math> в случае перестановки двух последовательных символов.

== Реализации ==
{{начало скрытого блока |заголовок= На [[python]] }}
<syntaxhighlight lang="python3" line="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]
</syntaxhighlight>
{{конец скрытого блока}}

{{начало скрытого блока |заголовок= [[Delphi (язык программирования)|Delphi]] }}
<syntaxhighlight lang="delphi" line="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;
</syntaxhighlight>
{{конец скрытого блока}}

{{начало скрытого блока |заголовок= На [[Ада (язык программирования)|Ada]]}}
<syntaxhighlight lang="ada" line="1">
   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;
</syntaxhighlight>
{{конец скрытого блока}}

{{начало скрытого блока |заголовок= На [[Visual Basic for Applications]] (VBA)}}
<syntaxhighlight lang="vb" line="1">
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
</syntaxhighlight>
{{конец скрытого блока}}

{{начало скрытого блока |заголовок= На [[Java]]}}
<syntaxhighlight lang="java" line="1">
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);
    }
}
</syntaxhighlight>
{{конец скрытого блока}}

== См. также ==
* [[Расстояние Левенштейна]]

== Ссылки ==
* Реализации алгоритма на различных языках программирования:
** [https://metacpan.org/module/Text::Levenshtein::Damerau На языке программирования Perl в виде модуля Text::Levenshtein::Damerau]
** [https://web.archive.org/web/20140912024719/http://bitbybit.ru/article/274 На языке программирования PlPgSQL]
** [https://github.com/ifsnop/damlev Дополнительный модуль для MySQL]
{{rq|sources|img}}
{{строки}}

[[Категория:Автоматическая обработка текстов]]
[[Категория:Динамическое программирование]]
[[Категория:Строковые алгоритмы]]
[[Категория:Меры схожести строк]]