Відстань Левенштейна

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

Опис алгоритму

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

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

Дивіться також: