«1. Введение

В этой статье мы опишем расстояние Левенштейна, также известное как расстояние редактирования. Описываемый здесь алгоритм был разработан русским ученым Владимиром Левенштейном в 1965 году.

Мы предоставим итеративную и рекурсивную реализацию этого алгоритма на языке Java.

2. Что такое расстояние Левенштейна?

Расстояние Левенштейна — это мера несходства между двумя строками. Математически, учитывая две строки x и y, расстояние измеряет минимальное количество правок символов, необходимых для преобразования x в y.

Обычно разрешены три типа редактирования:

  1. Insertion of a character c
  2. Deletion of a character c
  3. Substitution of a character c with c‘

Пример: если x = «выстрел» и y = «точка», расстояние редактирования между ними равно 1, потому что «выстрел» можно преобразовать на «spot», заменив «h» на «p».

В некоторых подклассах проблемы стоимость, связанная с каждым типом редактирования, может быть разной.

Например, меньше стоимость замены символом, расположенным рядом на клавиатуре, и больше стоимость в противном случае. Для простоты в этой статье мы будем считать все затраты равными.

Некоторые применения расстояния редактирования:

  1. Spell Checkers – detecting spelling errors in text and find the closest correct spelling in dictionary
  2. Plagiarism Detection (refer – IEEE Paper)
  3. DNA Analysis – finding similarity between two sequences
  4. Speech Recognition (refer – Microsoft Research)

3. Формулировка алгоритма

Возьмем две строки x и y длины m и n соответственно. Мы можем обозначить каждую строку как x[1:m] и y[1:n].

Мы знаем, что в конце преобразования обе строки будут иметь одинаковую длину и иметь совпадающие символы в каждой позиции. Итак, если мы рассмотрим первый символ каждой строки, у нас есть три варианта:

  1. Substitution:
    1. Determine the cost (D1) of substituting x[1] with y[1]. The cost of this step would be zero if both characters are same. If not, then the cost would be one
    2. After step 1.1, we know that both Strings start with the same character. Hence the total cost would now be the sum of the cost of step 1.1 and the cost of transforming the rest of the String x[2:m] into y[2:n]
  2. Insertion:
    1. Insert a character in x to match the first character in y, the cost of this step would be one
    2. After 2.1, we have processed one character from y. Hence the total cost would now be the sum of the cost of step 2.1 (i.e., 1) and the cost of transforming the full x[1:m] to remaining y (y[2:n])
  3. Deletion:
    1. Delete the first character from x, the cost of this step would be one
    2. After 3.1, we have processed one character from x, but the full y remains to be processed. The total cost would be the sum of the cost of 3.1 (i.e., 1) and the cost of transforming remaining x to the full y

Следующая часть решения состоит в том, чтобы выяснить, какой вариант выбрать из этих трех. Поскольку мы не знаем, какой вариант приведет к минимальным затратам в конце, мы должны попробовать все варианты и выбрать лучший.

4. Наивная рекурсивная реализация

Мы можем видеть, что второй шаг каждой опции в разделе № 3 в основном представляет собой ту же проблему расстояния редактирования, но на подстроках исходных строк. Это означает, что после каждой итерации мы сталкиваемся с одной и той же проблемой, но с меньшими строками.

Это наблюдение является ключом к формулировке рекурсивного алгоритма. Рекуррентное соотношение можно определить как:

D(x[1:m], y[1:n]) = min {

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. When both Strings are empty, then the distance between them is zero
  2. When one of the Strings is empty, then the edit distance between them is the length of the other String, as we need that many numbers of insertions/deletions to transform one into the other:
    • Example: if one String is “dog” and other String is “” (empty), we need either three insertions in empty String to make it “dog”, or we need three deletions in “dog” to make it empty. Hence the edit distance between them is 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. Sub-problems of D(x[1:m], y[1:n]) are D(x[2:m], y[2:n]), D(x[1:m], y[2:n]) and 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])

Во всех трех случаях одной из подзадач является D(x[2:m], y[ 2:н]). Вместо того, чтобы вычислять это три раза, как мы делаем в наивной реализации, мы можем вычислить это один раз и повторно использовать результат, когда это необходимо снова.

Эта задача имеет множество пересекающихся подзадач, но если мы знаем решение подзадач, мы можем легко найти ответ на исходную проблему. Следовательно, у нас есть оба свойства, необходимые для формулирования решения динамического программирования, т. Е. Перекрывающиеся подзадачи и оптимальная подструктура.

Мы можем оптимизировать наивную реализацию, введя мемоизацию, т. е. сохраняя результат подзадач в массиве и повторно используя кешированные результаты.

В качестве альтернативы, мы также можем реализовать это итеративно, используя подход, основанный на таблицах: 

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()];
}

Этот алгоритм работает значительно лучше, чем рекурсивная реализация. Однако это связано со значительным потреблением памяти.

«Это можно дополнительно оптимизировать, заметив, что нам нужно значение только трех соседних ячеек в таблице, чтобы найти значение текущей ячейки.

6. Заключение

В этой статье мы описали, что такое расстояние Левенштейна и как его можно рассчитать с помощью рекурсивного подхода и подхода, основанного на динамическом программировании.

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

Как всегда, полную реализацию примеров можно найти на GitHub.