Перейти к основному содержимому

Как рассчитать расстояние Левенштейна в Java?

· 6 мин. чтения

1. Введение​

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

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

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

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

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

  1. Вставка символа c
  2. Удаление символа c
  3. Замена символа c на c '

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

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

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

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

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

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

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

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

  1. Замена:

  2. Определите стоимость ( D1 ) замены x[1] на y[1] . Стоимость этого шага будет равна нулю, если оба символа одинаковы. Если нет, то стоимость будет один

  3. После шага 1.1 мы знаем, что обе строки начинаются с одного и того же символа. Следовательно, общая стоимость теперь будет суммой стоимости шага 1.1 и стоимости преобразования остальной части строки x[2:m] в y[2:n].

  4. Вставка:

  5. Вставьте символ в x , чтобы он соответствовал первому символу в y , стоимость этого шага будет равна единице.

  6. После версии 2.1 мы обработали один символ из y . Следовательно, общая стоимость теперь будет суммой стоимости шага 2.1 (т. е. 1) и стоимости преобразования полного x[1:m] в оставшийся y (y[2:n])

  7. Удаление:

  8. Удалите первый символ из x , стоимость этого шага будет равна единице.

  9. После версии 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 (х [2: м], у [1: п]) + 1

}

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

  1. Когда обе строки пусты, расстояние между ними равно нулю
  2. Когда одна из строк пуста, расстояние редактирования между ними равно длине другой строки, так как нам нужно такое количество вставок/удалений, чтобы преобразовать одну в другую:
  • Пример: если одна строка « собака» , а другая строка «» ( пустая), нам нужно либо три вставки в пустую строку , чтобы сделать ее «собакой» , либо нам нужно три удаления в «собаке» , чтобы сделать ее пустой. Следовательно, расстояние редактирования между ними равно 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. Подзадачами D(x[1:m], y[2:n]) являются D(x[2:m], y[3:n]), D(x[1:m], y[3 :n]) и D(x[2:m], y[2:n])
  3. Подзадачами D(x[2:m], y[1:n]) являются D(x[3:m], y[2:n]), D(x[2:m], y[2 :n]) и D(x[3:m], y[1:n])

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

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

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

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

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 .