Расстояние Левенштейна - Levenshtein distance
В теории информации , лингвистики и информатики , то расстояние Левенштейна является строка метрики для измерения разности между двумя последовательностями. Неформально расстояние Левенштейна между двумя словами - это минимальное количество односимвольных правок (вставок, удалений или замен), необходимых для преобразования одного слова в другое. Он назван в честь советского математика Владимира Левенштейна , который считал это расстояние в 1965 году.
Расстояние Левенштейна также может называться расстоянием редактирования , хотя этот термин может также обозначать более крупное семейство показателей расстояния, вместе известных как расстояние редактирования . Это тесно связано с попарным выравниванием струн .
Определение
Расстояние Левенштейна между двумя струнами (длины и соответственно) определяется как где
где некоторой строки - это строка, состоящая из всех символов , кроме первого , и - это th символ строки , считая от 0 .
Обратите внимание, что первый элемент в минимуме соответствует удалению (от до ), второй - вставке, а третий - замене.
Это определение прямо соответствует наивной рекурсивной реализации .
Пример
Например, расстояние Левенштейна между «котенком» и «сидящим» равно 3, поскольку следующие 3 правки меняют одно на другое, и нет способа сделать это с менее чем тремя правками:
- k itten → s itten (замена «k» на «s»),
- sitt e n → sitt i n (замена «i» на «e»),
- sittin → sittin g (вставка буквы "g" в конце).
Верхняя и нижняя границы
Расстояние Левенштейна имеет несколько простых оценок сверху и снизу. Это включает:
- Это как минимум разница в размерах двух струн.
- Это не больше длины более длинной струны.
- Он равен нулю тогда и только тогда, когда строки равны.
- Если струны имеют одинаковый размер, расстояние Хэмминга является верхней границей расстояния Левенштейна. Расстояние Хэмминга - это количество позиций, в которых соответствующие символы в двух строках различаются.
- Расстояние Левенштейна между двумя струнами не больше суммы их расстояний Левенштейна от третьей струны ( неравенство треугольника ).
Пример, когда расстояние Левенштейна между двумя струнами одинаковой длины строго меньше расстояния Хэмминга, дается парой «изъян» и «лужайка». Здесь расстояние Левенштейна равно 2 (удалить букву «f» спереди, вставить «n» в конце). Расстояние Хэмминга равно 4.
Приложения
При приблизительном сопоставлении строк цель состоит в том, чтобы найти совпадения для коротких строк во многих более длинных текстах в ситуациях, когда ожидается небольшое количество различий. Например, короткие строки могут быть взяты из словаря. Здесь одна из струн обычно короткая, а другая произвольно длинная. Он имеет широкий спектр приложений, например, средства проверки орфографии , системы коррекции для оптического распознавания символов и программное обеспечение для помощи в переводе на естественный язык на основе памяти переводов .
Расстояние Левенштейна также можно вычислить между двумя более длинными строками, но стоимость его вычисления, которая примерно пропорциональна произведению двух длин строк, делает это непрактичным. Таким образом, при использовании для помощи в поиске нечетких строк в приложениях, таких как связывание записей , сравниваемые строки обычно короткие, что помогает повысить скорость сравнения.
В лингвистике расстояние Левенштейна используется в качестве метрики для количественной оценки лингвистического расстояния или того, насколько два языка отличаются друг от друга. Это связано с взаимной разборчивостью : чем выше языковая дистанция, тем ниже взаимная разборчивость и чем меньше языковая дистанция, тем выше взаимная разборчивость.
Связь с другими показателями расстояния редактирования
Существуют и другие популярные меры расстояния редактирования , которые рассчитываются с использованием другого набора допустимых операций редактирования. Например,
- расстояние Дамерау – Левенштейна позволяет переставлять два соседних символа вместе с вставкой, удалением, заменой;
- расстояние самой длинной общей подпоследовательности (LCS) допускает только вставку и удаление, но не замену;
- расстояние Хэмминга допускает только замену, следовательно, оно применяется только к строкам одинаковой длины.
- Яро расстояние позволяет только транспозиции .
Расстояние редактирования обычно определяется как параметризуемая метрика, вычисляемая с помощью определенного набора разрешенных операций редактирования, и каждой операции назначается стоимость (возможно, бесконечная). Это дополнительно обобщается алгоритмами выравнивания последовательностей ДНК , такими как алгоритм Смита – Уотермана , который заставляет стоимость операции зависеть от того, где она применяется.
Вычисление расстояния Левенштейна
Рекурсивный
Это простая, но неэффективная рекурсивная реализация 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. Когда вся таблица построена, желаемое расстояние находится в таблице в последней строке и столбце, представляя расстояние между всеми символами и всеми символами. персонажи в .
s
t
s
t
Итеративная с полной матрицей
(Примечание: в этом разделе используются строки с отсчетом от 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 - ε ) для любого ε больше нуля, если только гипотеза сильной экспоненциального времени не является ложной.
Смотрите также
- соглашаться
- Расстояние Дамерау – Левенштейна
- разница
- Динамическое искажение времени
- Евклидово расстояние
- Гомология последовательностей в генетике
- Расстояние Хэмминга
- Алгоритм Ханта – Шимански
- Индекс Жаккара
- Хеширование с учетом местоположения
- Самая длинная общая проблема подпоследовательности
- Lucene (поисковая система с открытым исходным кодом, реализующая дистанционное редактирование)
- Манхэттенское расстояние
- Метрическое пространство
- MinHash
- Оптимальный алгоритм сопоставления
- Числовая таксономия
- Индекс сходства Соренсена
использованная литература
внешние ссылки
- Блэк, Пол Э., изд. (14 августа 2008 г.), «Расстояние Левенштейна», Словарь алгоритмов и структур данных [онлайн] , Национальный институт стандартов и технологий США , получено 2 ноября 2016 г.
- Реализация расстояния Левенштейна в коде Россеты