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

Расстояние Дамерау-Левенштейна – это метрика для определения расстояния между двумя строками. Его можно определить как минимальное количество операций удаления, вставки, замены и транспозиции (перестановки двух соседних символов), необходимых для преобразования одной строки в другую.

Расстояние Дамерау-Левенштейна отличается от классического расстояния Левенштейна тем, что включает транспонирование в число его допустимых операций в дополнение к трем классическим односимвольным операциям редактирования:

  • вставки;
  • удаления;
  • замены.

В своей работе Дамерау заявил, что более 80% из всех орфографических ошибок можно отнести к одному из четырех типов. В работе Дамерау рассматривались только орфографические ошибки, которые можно исправить не более чем одной операцией редактирования. В то время как первоначальная задача заключалась в измерении расстояния между орфографическими ошибками для улучшения приложений проверки орфографии. Расстояние Дамерау-Левенштейна также используется в биологии для измерения вариаций между белковыми последовательностями.

Описание алгоритма

Для поиска расстояния Дамерау-Левенштейна, используют алгоритм в котором необходимо заполнить матрицу D, размером n + 1 на m + 1, где n и m – длины сравниваемых строк A и B, по следующим правилам:

  • D0,0 = 0
  • Di,j = Минимальное из:
    • Di-1,j-1 + 0 (символы одинаковые)
    • Di,j-1 + wdelete (удаление символа)
    • Di-1,j + winsert (вставка символа)
    • Di-1,j-1 + wreplace (замена символа)
    • Di-2,j-2 + wtranspose (перестановка символа)

wdelete, winsert, wreplace, wtranspose – цена или вес удаления, вставки, замены и перестановки символа.

При этом Dn-1,m-1 – содержит значение расстояния Дамерау-Левенштейна.

Реализация алгоритма

using System;

class Program
{
    static int Minimum(int a, int b) => a < b ? a : b;

    static int Minimum(int a, int b, int c) => (a = a < b ? a : b) < c ? a : c;

    static int DamerauLevenshteinDistance(string firstText, string secondText)
    {
        var n = firstText.Length + 1;
        var m = secondText.Length + 1;
        var arrayD = new int[n, m];

        for (var i = 0; i < n; i++)
        {
            arrayD[i, 0] = i;
        }

        for (var j = 0; j < m; j++)
        {
            arrayD[0, j] = j;
        }

        for (var i = 1; i < n; i++)
        {
            for (var j = 1; j < m; j++)
            {
                var cost = firstText[i - 1] == secondText[j - 1] ? 0 : 1;

                arrayD[i, j] = Minimum(arrayD[i - 1, j] + 1,          // удаление
                                        arrayD[i, j - 1] + 1,         // вставка
                                        arrayD[i - 1, j - 1] + cost); // замена

                if (i > 1 && j > 1 
                    && firstText[i - 1] == secondText[j - 2]
                    && firstText[i - 2] == secondText[j - 1])
                {
                    arrayD[i, j] = Minimum(arrayD[i, j],
                                       arrayD[i - 2, j - 2] + cost); // перестановка
                }
            }
        }

        return arrayD[n - 1, m - 1];
    }

    static void Main(string[] args)
    {
        Console.Write("Первое слово: ");
        var w1 = Console.ReadLine();
        Console.Write("Второе слово: ");
        var w2 = Console.ReadLine();

        Console.WriteLine("Расстояние Дамерау-Левенштейна: {0}", DamerauLevenshteinDistance(w1, w2));
        Console.ReadLine();
    }
}

Результат работы программы:

Смотрите также: