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

редактировать

Метрика информатики для сходства строк

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

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

Содержание

1 Определение
- 1.1 Пример
- 1.2 Верхняя и нижняя границы
2 Приложения
3 Связь с другими метриками расстояния редактирования
4 Вычисление расстояния Левенштейна
- 4.1 Рекурсивный
- 4.2 Итерационный с полной матрицей
- 4.3 Итерационный с двумя строками матрицы
- 4.4 Адаптивный вариант
- 4.5 Автоматы
- 4.6 Аппроксимация
- 4.7 Вычислительная сложность
5 См. Также
6 Ссылки
7 Внешние ссылки

Определение

Расстояние Левенштейна между двумя строками $a, b {\ displaystyle a, b}$ $a, b$ (длины $| a | {\ displaystyle | a |}$ $| a |$ и $| b | {\ displaystyle | b |}$ $| b |$ соответственно) задается как $лев a, b ⁡ (| a |, | b |) {\ displaystyle \ operatorname {lev} _ {a, b} (| a |, | b |)}$ $\ operatorname {lev } _ {a, b} (| a |, | b |)$ где

lev a, b ⁡ (i, j) = {max (i, j), если min (i, j) = 0, min {lev a, b ⁡ (i - 1, j) + 1 lev a, b ⁡ (i, j - 1) + 1 лев a, b ⁡ (i - 1, j - 1) + 1 (ai ≠ bj) ot по ней. {\ displaystyle \ qquad \ operatorname {lev} _ {a, b} (i, j) = {\ begin {cases} \ max (i, j) {\ text {if}} \ min (i, j) = 0, \\\ min {\ begin {cases} \ operatorname {lev} _ {a, b} (i-1, j) +1 \\\ operatorname {lev} _ {a, b} (i, j -1) +1 \\\ operatorname {lev} _ {a, b} (i-1, j-1) +1 _ {(a_ {i} \ neq b_ {j})} \ end {cases}} {\ text {иначе.}} \ end {case}}}

{\ displaystyle \ qquad \ operatorname {lev} _ {a, b} (i, j) = {\ begin {cases} \ max (i, j) {\ text {if}} \ min (i, j) = 0, \\\ min {\ begin {cases} \ operatorname { lev} _ {a, b} (i-1, j) +1 \\\ operatorname {lev} _ {a, b} (i, j-1) +1 \\\ operatorname {lev} _ {a, b} (i-1, j-1) +1 _ {(a_ {i} \ neq b_ {j})} \ end {cases}} {\ text {в противном случае.}} \ end {ases}}}

где $1 (ai ≠ bj) {\ displaystyle 1 _ {(a_ {i} \ neq b_ {j})}}$ $1 _ {(a_ {i} \ neq b_ {j})}$ - индикаторная функция , равная 0, когда $ai = bj {\ displaystyle a_ {i} = b_ {j}}$ $a_ {i} = b_ {j}$ , и равная 1 в противном случае, и $lev a, b ⁡ (i, j) {\ displaystyle \ operatorname {lev} _ {a, b} (i, j)}$ $\ operatorname {lev} _ {a, b} (i, j)$ - расстояние между первыми $i {\ displaystyle i}$ $i$ символы $a {\ displaystyle a}$ $a$ и первые $j {\ displaystyle j}$ $j$ символы $b {\ displaystyle b}$ $b$ . $i {\ displaystyle i}$ $i$ и $j {\ displaystyle j}$ $j$ - индексы, отсчитываемые от единицы.

Обратите внимание, что первый элемент в минимуме соответствует удалению (от $a {\ displaystyle a}$ $a$ до $b {\ displaystyle b}$ $b$ ), второй - для вставки, а третий - для совпадения или несоответствия, в зависимости от того, совпадают ли соответствующие символы.

Пример

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

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

kitten → s itten (замена "s" на "k")
sitt e n → sitt i n (замена «i» на «e»)
sittin → sittin g (вставка "g" в конце).

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

Расстояние Левенштейна имеет несколько простых верхних и нижних границ. К ним относятся:

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

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

Приложения

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

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

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

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

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

расстояние Дамерау – Левенштейна допускает транспонирование двух соседних символов вместе с вставкой, удалением, заменой;
самая длинная общая подпоследовательность Расстояние (LCS) допускает только вставку и удаление, но не замену;
расстояние Хэмминга допускает только замену, следовательно, применяется только к строкам одинаковой длины.
расстояние Джаро допускает только транспонирование.

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

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

Рекурсивный

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

lDistance :: (Eq a) =>[a] ->[a] ->Int lDistance t = length t - - Если s пусто, расстояние - это количество символов в t lDistance s = длина s - Если t пусто, расстояние - это количество символов в s lDistance (a: s ') (b: t') = если a == b then lDistance s 't' - Если первые символы совпадают, их можно игнорировать, иначе 1 + минимум - В противном случае попробуйте все три возможных действия и выберите лучшее [lDistance (a: s ') t' - - Символ вставлен (вставлен b), lDistance s '(b: t') - Символ удален (a удален), lDistance s 't' - Символ заменен (a заменен на b)]

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

Более эффективный метод никогда не повторит одно и то же вычисление расстояния. Например, расстояние Левенштейна для всех возможных префиксов может быть сохранено в массиве $M {\ displaystyle M}$ $M$ , где $M [i] [j] {\ displaystyle M [i] [ j]}$ ${\ displaystyle M [i] [j]}$ - это расстояние между последними символами $i {\ displaystyle i}$ $i$ строки sи последним $j {\ displaystyle j}$ $j$ символы строки t. Таблицу легко построить по одной строке за раз, начиная со строки 0. Когда вся таблица построена, желаемое расстояние находится в таблице в последней строке и столбце, представляя расстояние между всеми символами в sи все символы в t.

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

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

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

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

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

function LevenshteinDistance (char s [1..m], char t [1..n]): // для всех i и j, d [i, j] будет удерживать расстояние Левенштейна между // первыми i символами s и первыми j символами t declare int d [0..m, 0..n] установить каждый элемент в d равным нулю // исходные префиксы могут быть преобразованы в пустая строка путем // удаления всех символов для i от 1 до m: d [i, 0]: = i // целевые префиксы могут быть достигнуты из пустого исходного префикса // путем вставки каждого символа для j от 1 до n: d [ 0, j]: = j для j от 1 до n: для i от 1 до m: если s [i] = t [j]: подстановкаCo st: = 0 else: substitutionCost: = 1 d [i, j]: = minimum (d [i-1, j] + 1, // удаление d [i, j-1] + 1, // вставка d [ i-1, j-1] + substitutionCost) // подстановка return d [m, n]

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

		k	i	t	t	e	n
	0	1	2	3	4	5	6
s	1	1	2	3	4	5	6
i	2	2	1	2	3	4	5
t	3	3	2	1	2	3	4
t	4	4	3	2	1	2	3
i	5	5	4	3	2	2	3
n	6	6	5	4	3	3	2
g	7	7	6	5	4	4	3

		S	a	t	u	r	d	a	y
	0	1	2	3	4	5	6	7	8
S	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3	2	2	2	3	3	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3

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

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

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

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

function LevenshteinDistance (char s [0..m-1], char t [0..n-1]): // создать два рабочих вектора целочисленных расстояний объявить int v0 [n + 1] declare int v1 [n + 1] // инициализировать v0 (предыдущая строка расстояний) // эта строка - A [0] [i]: изменить расстояние для пусто s // расстояние - это просто количество символов, которые нужно удалить из t для i от 0 до n: v0 [i] = i для i от 0 до m-1: // вычислить v1 (текущие расстояния между строками) из предыдущего row v0 // первым элементом v1 является A [i + 1] [0] // расстояние редактирования равно delete (i + 1) символов от s для соответствия пустым t v1 [0] = i + 1 // используем формулу для заполнения в оставшейся части строки для j от 0 до n-1: // вычисление затрат для A [i + 1] [j + 1] deletionCost: = v0 [j + 1] + 1 InsertCost: = v1 [j] + 1, если s [i] = t [j]: substitutionCost: = v0 [j] else: substitutionCost: = v0 [j] + 1; v1 [j + 1]: = minimum (deletionCost, InsertCost, substitutionCost) // копировать v1 (текущая строка) в v0 (предыдущая строка) для следующей итерации // поскольку данные в v1 всегда недействительны, замена без копирования может быть больше эффективный своп v0 с v1 // после последнего свопа результаты v1 теперь находятся в v0 return v0 [n]

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

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

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

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

Автоматы

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

Приближение

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

(log ⁡ n) O (1 / ε) {\ displaystyle (\ log n) ^ {O (1 / \ varepsilon)}}

{\ displaystyle (\ log n) ^ { O (1 / \ varepsilon)}}

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

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

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

См. также

comparep
расстояние Дамерау – Левенштейна
diff
Динамическое искажение времени
Евклидово расстояние
Гомология последовательностей в генетике
Хаммин g расстояние
алгоритм Ханта-Шимански
индекс Жаккарда
хеширование с учетом местоположения
самая длинная общая проблема подпоследовательности
Lucene (поисковая система с открытым исходным кодом, реализующая расстояние редактирования)
Manhattan расстояние
Метрическое пространство
MinHash
Оптимальный алгоритм соответствия
Числовая таксономия
Индекс сходства Соренсена

Ссылки

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

The Wikibook Реализация алгоритма имеет страницу на тему: Расстояние Левенштейна

Black, Paul E., ed. (14 августа 2008 г.), «Расстояние Левенштейна», Словарь алгоритмов и структур данных [онлайн], Национальный институт стандартов и технологий США, получено 2 ноября 2016 г.