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

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

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

Для поиска расстояния Левенштейна, чаще всего используют алгоритм в котором необходимо заполнить матрицу 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 (замена символа)

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

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

Заполнив матрицу для слов SATURDAY и MONDAY получим:

S A T U R D A Y
0 1 2 3 4 5 6 7 8
M 1 1 2 3 4 5 6 7 8
O 2 2 2 3 4 5 6 7 8
N 3 3 3 3 4 5 6 7 8
D 4 4 4 4 4 5 5 6 7
A 5 5 4 5 5 5 6 5 6
Y 6 6 5 5 6 6 6 6 5

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

Для начала необходимо написать метод для получения минимального из трех чисел. Проще всего это сделать с использованием тернарного оператора:

static int Minimum(int a, int b, int c) => (a = a < b ? a : b) < c ? a : c;
Запись в классической форме 
static int Minimum(int a, int b, int c)
{
    if(a > b)
    {
        a = b;
    }

    if(a > c)
    {
        a = c;
    }

    return a;
}

Итеративная реализация

static int LevenshteinDistance(string firstWord, string secondWord)
{
    var n = firstWord.Length + 1;
    var m = secondWord.Length + 1;
    var matrixD = new int[n, m];

    const int deletionCost = 1;
    const int insertionCost = 1;

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

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

    for (var i = 1; i < n; i++)
    {
        for (var j = 1; j < m; j++)
        {
            var substitutionCost = firstWord[i - 1] == secondWord[j - 1] ? 0 : 1;

            matrixD[i, j] = Minimum(matrixD[i - 1, j] + deletionCost,          // удаление
                                    matrixD[i, j - 1] + insertionCost,         // вставка
                                    matrixD[i - 1, j - 1] + substitutionCost); // замена
        }
    }

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

Рекурсивная реализация

static int LevenshteinDistance(string text1, int len1, string text2, int len2)
{
    if (len1 == 0)
    {
        return len2;
    }

    if (len2 == 0)
    {
        return len1;
    }
    
    var substitutionCost = 0;
    if(text1[len1 - 1] != text2[len2 - 1])
    {
        substitutionCost = 1;
    }

    var deletion = LevenshteinDistance(text1, len1 - 1, text2, len2) + 1;
    var insertion = LevenshteinDistance(text1, len1, text2, len2 - 1) + 1;
    var substitution = LevenshteinDistance(text1, len1 - 1, text2, len2 - 1) + substitutionCost;

    return Minimum(deletion, insertion, substitution);
}

static int LevenshteinDistance(string word1, string word2) =>
        LevenshteinDistance(word1, word1.Length, word2, word2.Length);

Программа для поиска расстояния Левенштейна

В класс программы нужно поместить метод для поиска минимального значения и одну из реализаций алгоритма, а в тело метода Main следующий код:

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

    Console.WriteLine("Расстояние Левенштейна: {0}", LevenshteinDistance(s1, s2));
    Console.ReadLine();
}

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

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