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

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

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

Определение

Расстояние Левенштейна между двумя струнами (длины и соответственно) определяется как где

где некоторой строки - это строка, состоящая из всех символов , кроме первого , и - это th символ строки , считая от 0 .

Обратите внимание, что первый элемент в минимуме соответствует удалению (от до ), второй - вставке, а третий - замене.

Это определение прямо соответствует наивной рекурсивной реализации .

Пример

Отредактируйте матрицу расстояний для двух слов, используя стоимость замены как 1 и стоимость удаления или вставки как 0,5

Например, расстояние Левенштейна между «котенком» и «сидящим» равно 3, поскольку следующие 3 правки меняют одно на другое, и нет способа сделать это с менее чем тремя правками:

  1. k itten → s itten (замена «k» на «s»),
  2. sitt e n → sitt i n (замена «i» на «e»),
  3. sittin → sittin g (вставка буквы "g" в конце).

Верхняя и нижняя границы

Расстояние Левенштейна имеет несколько простых оценок сверху и снизу. Это включает:

  • Это как минимум разница в размерах двух струн.
  • Это не больше длины более длинной струны.
  • Он равен нулю тогда и только тогда, когда строки равны.
  • Если струны имеют одинаковый размер, расстояние Хэмминга является верхней границей расстояния Левенштейна. Расстояние Хэмминга - это количество позиций, в которых соответствующие символы в двух строках различаются.
  • Расстояние Левенштейна между двумя струнами не больше суммы их расстояний Левенштейна от третьей струны ( неравенство треугольника ).

Пример, когда расстояние Левенштейна между двумя струнами одинаковой длины строго меньше расстояния Хэмминга, дается парой «изъян» и «лужайка». Здесь расстояние Левенштейна равно 2 (удалить букву «f» спереди, вставить «n» в конце). Расстояние Хэмминга равно 4.

Приложения

При приблизительном сопоставлении строк цель состоит в том, чтобы найти совпадения для коротких строк во многих более длинных текстах в ситуациях, когда ожидается небольшое количество различий. Например, короткие строки могут быть взяты из словаря. Здесь одна из струн обычно короткая, а другая произвольно длинная. Он имеет широкий спектр приложений, например, средства проверки орфографии , системы коррекции для оптического распознавания символов и программное обеспечение для помощи в переводе на естественный язык на основе памяти переводов .

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

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

Связь с другими показателями расстояния редактирования

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

Расстояние редактирования обычно определяется как параметризуемая метрика, вычисляемая с помощью определенного набора разрешенных операций редактирования, и каждой операции назначается стоимость (возможно, бесконечная). Это дополнительно обобщается алгоритмами выравнивания последовательностей ДНК , такими как алгоритм Смита – Уотермана , который заставляет стоимость операции зависеть от того, где она применяется.

Вычисление расстояния Левенштейна

Рекурсивный

Это простая, но неэффективная рекурсивная реализация HaskelllDistance функции, которая принимает две строки s и t вместе с их длинами и возвращает расстояние Левенштейна между ними:

lDistance :: ( Eq a ) => [a] -> [a] -> Int
lDistance [] t = length t   -- If s is empty, the distance is the number of characters in t
lDistance s [] = length s   -- If t is empty, the distance is the number of characters in s
lDistance (a:s') (b:t') =
  if
    a == b
  then
    lDistance s' t'         -- If the first characters are the same, they can be ignored
  else
    1 + minimum             -- Otherwise try all three possible actions and select the best one
      [ lDistance (a:s') t' -- Character is inserted (b inserted)
      , lDistance s' (b:t') -- Character is deleted  (a deleted)
      , lDistance s' t'     -- Character is replaced (a replaced with b)
      ]

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

Более эффективный метод никогда не повторит одно и то же вычисление расстояния. Например, расстояние Левенштейна всех возможных префиксов может храниться в массиве , где - расстояние между последними символами строки и последними символами строки . Таблицу легко построить по одной строке, начиная со строки 0. Когда вся таблица построена, желаемое расстояние находится в таблице в последней строке и столбце, представляя расстояние между всеми символами и всеми символами. персонажи в . stst

Итеративная с полной матрицей

(Примечание: в этом разделе используются строки с отсчетом от 1 вместо строк с отсчетом от 0.)

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

Этот алгоритм, пример снизу вверх динамического программирования , обсуждается, с вариантами, в 1974 статье The Строка в строку задачи коррекции Роберт А. Вагнер и Майкл Дж Фишер.

Это простая реализация псевдокода для функции, LevenshteinDistanceкоторая принимает две строки s длиной m и t длиной n и возвращает расстояние Левенштейна между ними:

function LevenshteinDistance(char s[1..m], char t[1..n]):
  // for all i and j, d[i,j] will hold the Levenshtein distance between
  // the first i characters of s and the first j characters of t
  declare int d[0..m, 0..n]
 
  set each element in d to zero
 
  // source prefixes can be transformed into empty string by
  // dropping all characters
  for i from 1 to m:
    d[i, 0] := i
 
  // target prefixes can be reached from empty source prefix
  // by inserting every character
  for j from 1 to n:
    d[0, j] := j
 
  for j from 1 to n:
    for i from 1 to m:
      if s[i] = t[j]:
        substitutionCost := 0
      else:
        substitutionCost := 1

      d[i, j] := minimum(d[i-1, j] + 1,                   // deletion
                         d[i, j-1] + 1,                   // insertion
                         d[i-1, j-1] + substitutionCost)  // substitution
 
  return d[m, n]

Два примера полученной матрицы (наведение курсора на помеченное число показывает операцию, выполняемую для получения этого числа):

Инвариант сохраняется в течение всего алгоритма является то , что мы можем преобразовать начальный сегмент в использовании минимума операций. В конце концов, нижний правый элемент массива содержит ответ. s[1..i]t[1..j]d[i, j]

Итеративная с двумя строками матрицы

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

Расстояние Левенштейна можно вычислить итеративно, используя следующий алгоритм:

function LevenshteinDistance(char s[0..m-1], char t[0..n-1]):
    // create two work vectors of integer distances
    declare int v0[n + 1]
    declare int v1[n + 1]

    // initialize v0 (the previous row of distances)
    // this row is A[0][i]: edit distance for an empty s
    // the distance is just the number of characters to delete from t
    for i from 0 to n:
        v0[i] = i

    for i from 0 to m - 1:
        // calculate v1 (current row distances) from the previous row v0

        // first element of v1 is A[i + 1][0]
        //   edit distance is delete (i + 1) chars from s to match empty t
        v1[0] = i + 1

        // use formula to fill in the rest of the row
        for j from 0 to n - 1:
            // calculating costs for A[i + 1][j + 1]
            deletionCost := v0[j + 1] + 1
            insertionCost := v1[j] + 1
            if s[i] = t[j]:
                substitutionCost := v0[j]
            else:
                substitutionCost := v0[j] + 1

            v1[j + 1] := minimum(deletionCost, insertionCost, substitutionCost)

        // copy v1 (current row) to v0 (previous row) for next iteration
        // since data in v1 is always invalidated, a swap without copy could be more efficient
        swap v0 with v1
    // after the last swap, the results of v1 are now in v0
    return v0[n]

Этот вариант с двумя строками является субоптимальным: объем требуемой памяти может быть уменьшен до одной строки и одного (индексного) служебного слова для лучшей локализации кэша.

Алгоритм Хиршберга сочетает этот метод с « разделяй и властвуй» . Он может вычислить оптимальную последовательность редактирования, а не только расстояние редактирования, с теми же асимптотическими временными и пространственными ограничениями.

Адаптивный вариант

Динамический вариант - не идеальная реализация. Адаптивный подход может уменьшить объем требуемой памяти и, в лучшем случае, может уменьшить временную сложность до линейной по длине самой короткой строки и, в худшем случае, не более чем квадратичной по длине самой короткой строки. . Идея состоит в том, что можно использовать эффективные библиотечные функции ( std::mismatch) для проверки общих префиксов и суффиксов и погружаться в часть DP только при несовпадении.

Автоматы

Автоматы Левенштейна эффективно определяют, имеет ли строка расстояние редактирования меньше заданной константы от данной строки.

Приближение

Расстояние Левенштейна между двумя струнами длины n можно аппроксимировать с точностью до множителя

где ε > 0 - свободный параметр, который нужно настроить за время O ( n 1 + ε ) .

Вычислительная сложность

Было показано, что расстояние Левенштейна двух цепочек длины n не может быть вычислено за время O ( n 2 - ε ) для любого ε больше нуля, если только гипотеза сильной экспоненциального времени не является ложной.

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

использованная литература

внешние ссылки