Как да изчислим разстоянието на Левенщайн в Java?

1. Въведение

В тази статия ние описваме разстоянието на Левенщайн, алтернативно известно като Редактиране на разстоянието. Обясненият тук алгоритъм е измислен от руски учен Владимир Левенщайн през 1965 г.

Ще осигурим итеративно и рекурсивно изпълнение на Java на този алгоритъм.

2. Какво е разстоянието на Левенщайн?

Разстоянието на Левенщайн е мярка за различие между две струни. Математически, като се имат предвид два низа x и y , разстоянието измерва минималния брой редакции на символи, необходими за трансформиране на x в y .

Обикновено се допускат три вида редакции:

  1. Вмъкване на знак c
  2. Изтриване на символ c
  3. Замяна на знак c с c '

Пример: Ако x = 'изстрел' и y = 'място' , разстоянието за редактиране между двете е 1, защото 'изстрелът' може да бъде преобразуван в 'място', като замести ' h ' на ' p '.

В някои подкласове на проблема разходите, свързани с всеки вид редактиране, могат да бъдат различни.

Например по-малко разходи за заместване с символ, разположен наблизо на клавиатурата, и повече разходи в противен случай. За по-голяма простота ще разгледаме всички разходи за еднакви в тази статия.

Някои от приложенията за редактиране на разстояние са:

  1. Проверка на правописа - откриване на правописни грешки в текста и намиране на най-близкия правилен правопис в речника
  2. Откриване на плагиатство (вижте - IEEE Paper)
  3. ДНК анализ - намиране на сходство между две последователности
  4. Разпознаване на реч (вижте - Microsoft Research)

3. Формулиране на алгоритъм

Нека вземем два низа x и y с дължини m и n съответно. Можем да обозначим всеки низ като x [1: m] и y [1: n].

Знаем, че в края на трансформацията и двата низа ще бъдат с еднаква дължина и ще имат съвпадащи символи на всяка позиция. Така че, ако разгледаме първия символ на всеки низ, имаме три възможности:

  1. Заместване:
    1. Определете цената ( D1 ) от заместването на x [1] с y [1] . Цената на тази стъпка ще бъде нула, ако и двата знака са еднакви. Ако не, тогава цената ще бъде една
    2. След стъпка 1.1 знаем, че и двата низа започват с един и същ символ. Следователно общите разходи сега ще бъдат сумата от цената на стъпка 1.1 и разходите за трансформиране на останалата част от String x [2: m] в y [2: n]
  2. Вмъкване:
    1. Вмъкнете символ в x, за да съответства на първия знак в y , цената на тази стъпка ще бъде една
    2. След 2.1 сме обработили един знак от y . Следователно общите разходи сега ще бъдат сумата от цената на стъпка 2.1 (т.е. 1) и разходите за трансформиране на пълния x [1: m] в оставащия y (y [2: n])
  3. Изтриване:
    1. Изтрийте първия знак от x , цената на тази стъпка ще бъде една
    2. След 3.1 сме обработили един символ от x , но пълното y остава да бъде обработено. Общата цена ще бъде сумата от разходите от 3.1 (т.е. 1) и разходите за трансформиране на оставащото x в пълното y

Следващата част от решението е да разберете коя опция да изберете от тези три. Тъй като не знаем коя опция би довела до минимални разходи в края, трябва да изпробваме всички опции и да изберем най-добрата.

4. Наивно рекурсивно изпълнение

Можем да видим, че втората стъпка на всяка опция в раздел # 3 е предимно същият проблем за редактиране на разстоянието, но за поднизовете на оригиналните низове. Това означава, че след всяка итерация се оказваме със същия проблем, но с по-малки низове.

Това наблюдение е ключът към формулирането на рекурсивен алгоритъм. Рецидивиращата връзка може да се определи като:

D (x [1: m], y [1: n]) = мин. {

D (x [2: m], y [2: n]) + разходи за замяна на x [1] на y [1],

D (x [1: m], y [2: n]) + 1,

D (x [2: m], y [1: n]) + 1

}

Трябва също така да дефинираме базови случаи за нашия рекурсивен алгоритъм, който в нашия случай е, когато единият или двата низа стават празни:

  1. Когато двата низа са празни, тогава разстоянието между тях е нула
  2. Когато един от низовете е празен, тогава разстоянието за редактиране между тях е дължината на другия низ, тъй като се нуждаем от толкова много вмъквания / изтривания, за да трансформираме един в друг:
    • Пример: ако един String е „dog“, а другият String е „“ (празен), имаме нужда или от три вмъквания в празния String, за да го направим „dog“ , или се нуждаем от три изтривания в „dog“, за да го направим празен. Следователно разстоянието за редактиране между тях е 3

Наивна рекурсивна реализация на този алгоритъм:

public class EditDistanceRecursive { static int calculate(String x, String y) { if (x.isEmpty()) { return y.length(); } if (y.isEmpty()) { return x.length(); } int substitution = calculate(x.substring(1), y.substring(1)) + costOfSubstitution(x.charAt(0), y.charAt(0)); int insertion = calculate(x, y.substring(1)) + 1; int deletion = calculate(x.substring(1), y) + 1; return min(substitution, insertion, deletion); } public static int costOfSubstitution(char a, char b) { return a == b ? 0 : 1; } public static int min(int... numbers) { return Arrays.stream(numbers) .min().orElse(Integer.MAX_VALUE); } }

Този алгоритъм има експоненциална сложност. На всяка стъпка се разклоняваме на три рекурсивни повиквания, изграждайки сложност O (3 ^ n) .

В следващия раздел ще видим как да подобрим това.

5. Подход за динамично програмиране

При анализирането на рекурсивните извиквания забелязваме, че аргументите за подзадачи са суфикси на оригиналните низове. Това означава, че може да има само m * n уникални рекурсивни повиквания (където m и n са редица суфикси на x и y ). Следователно сложността на оптималното решение трябва да бъде квадратична, O (m * n) .

Нека разгледаме някои от подпроблемите (според рецидивиращата връзка, дефинирана в раздел # 4):

  1. Подзадачите на D (x [1: m], y [1: n]) са D (x [2: m], y [2: n]), D (x [1: m], y [2 : n]) и D (x [2: m], y [1: n])
  2. Sub-problems of D(x[1:m], y[2:n]) are D(x[2:m], y[3:n]), D(x[1:m], y[3:n]) and D(x[2:m], y[2:n])
  3. Sub-problems of D(x[2:m], y[1:n]) are D(x[3:m], y[2:n]), D(x[2:m], y[2:n]) and D(x[3:m], y[1:n])

In all three cases, one of the sub-problems is D(x[2:m], y[2:n]). Instead of calculating this three times like we do in the naive implementation, we can calculate this once and reuse the result whenever needed again.

This problem has a lot of overlapping sub-problems, but if we know the solution to the sub-problems, we can easily find the answer to the original problem. Therefore, we have both of the properties needed for formulating a dynamic programming solution, i.e., Overlapping Sub-Problems and Optimal Substructure.

We can optimize the naive implementation by introducing memoization, i.e., store the result of the sub-problems in an array and reuse the cached results.

Alternatively, we can also implement this iteratively by using a table based approach:

static int calculate(String x, String y) { int[][] dp = new int[x.length() + 1][y.length() + 1]; for (int i = 0; i <= x.length(); i++) { for (int j = 0; j <= y.length(); j++) { if (i == 0) { dp[i][j] = j; } else if (j == 0) { dp[i][j] = i; } else { dp[i][j] = min(dp[i - 1][j - 1] + costOfSubstitution(x.charAt(i - 1), y.charAt(j - 1)), dp[i - 1][j] + 1, dp[i][j - 1] + 1); } } } return dp[x.length()][y.length()]; } 

This algorithm performs significantly better than the recursive implementation. However, it involves significant memory consumption.

This can further be optimized by observing that we only need the value of three adjacent cells in the table to find the value of the current cell.

6. Conclusion

В тази статия описахме какво е разстоянието на Левенщайн и как може да се изчисли с помощта на рекурсивен и базиран на динамично програмиране подход.

Разстоянието на Левенщайн е само една от мерките за подобие на низовете, някои от другите показатели са Подобност на косинусите (която използва подход, основан на символи и разглежда струните като вектори), Коефициент на зарове и т.н.

Както винаги пълното изпълнение на примери може да бъде намерено в GitHub.