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

Метрика компьютерной науки для сходства строк

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

Расстояние Левенштейна также может называться расстоянием редактирования , хотя этот термин может также обозначать более крупное семейство метрик расстояния, известных под общим названием расстояние редактирования . ^{[2] : 32} Оно тесно связано с попарным выравниванием строк .

Определение

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

${\displaystyle \operatorname {lev} (a,b)={\begin{cases}|a|&{\text{ if }}|b|=0,\\|b|&{\text{ if }}|a|=0,\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}&{\text{ if }}\operatorname {head} (a)=\operatorname {head} (b),\\1+\min {\begin{cases}\operatorname {lev} {\big (}\operatorname {tail} (a),b{\big )}\\\operatorname {lev} {\big (}a,\operatorname {tail} (b){\big )}\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}\\\end{cases}}&{\text{ otherwise}}\end{cases}}}$

где некоторая строка — это строка из всех символов (ie ), кроме первого, и — первый символ (ie ). Для обозначения th символа строки используется либо обозначение , либо , считая от 0 , таким образом . ${\displaystyle \operatorname {tail} }$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \operatorname {tail} (x_{0}x_{1}\dots x_{n})=x_{1}x_{2}\dots x_{n}}$ ${\displaystyle \operatorname {head} (x)}$ ${\displaystyle x}$ ${\displaystyle \operatorname {head} (x_{0}x_{1}\dots x_{n})=x_{0}}$ ${\displaystyle x[n]}$ ${\displaystyle x_{n}}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle \operatorname {head} (x)=x_{0}=x[0]}$

Первый элемент в минимуме соответствует удалению (из в ), второй — вставке, а третий — замене. ${\displaystyle a}$ ${\displaystyle b}$

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

Пример

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

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

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

Простой пример удаления можно увидеть на примере «неинформированного» и «единообразного», расстояние между которыми равно 1:

1. униформный → униформизированный ( удаление «н»).

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

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

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

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

Приложения

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

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

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

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

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

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

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

Вычисление

Рекурсивный

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

lDistance :: Eq a => [ a ] ​​-> [ a ] ​​-> Int lDistance [] t = длина 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) ]                                                            

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

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

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

В этом разделе используются строки, начинающиеся с 1, а не с 0. Если m — матрица, то — это i -я строка и j -й столбец матрицы, причем первая строка имеет индекс 0, а первый столбец — индекс 0. ${\displaystyle m[i,j]}$

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

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

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

function LevenshteinDistance ( char s [ 1 .. m ] , char t [ 1 .. n ]) : // для всех i и j, d[i,j] будет содержать расстояние Левенштейна между // первыми i символами s и первыми j символами t объявить int d [ 0 .. m , 0 .. n ] установить каждый элемент в d в ноль // исходные префиксы можно преобразовать в пустую строку, // отбросив все символы for i от 1 до m : d [ i , 0 ] := i // целевые префиксы можно получить из пустого исходного префикса , // вставив каждый символ for j от 1 до n : d [ 0 , j ] := j for j от 1 до n : for i от 1 до m : if s [ i ] = t [ j ] : substitutionCost := 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 ]                     

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

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

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

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

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

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

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

Автоматы

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

Приближение

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

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

где ε > 0 — свободный параметр, который необходимо настроить за время O ( n ^{1 + ε} ) . ^[8]

Сложность вычислений

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

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

• агреп
• Расстояние Дамерау–Левенштейна
• разница
• Динамическое искривление времени
• Евклидово расстояние
• Гомология последовательностей в генетике
• Расстояние Хэмминга
• Алгоритм Ханта-Шиманского
• индекс Жаккара
• Расстояние Яро–Винклера
• Хеширование, чувствительное к местоположению
• Проблема нахождения самой длинной общей подпоследовательности
• Lucene (поисковая система с открытым исходным кодом, реализующая расстояние редактирования)
• Манхэттенское расстояние
• Метрическое пространство
• МинХэш
• Оптимальный алгоритм сопоставления
• Числовая таксономия
• Индекс сходства Сёренсена

Ссылки

1. В. И. Левенштейн (1965). Двоичные коды с исправлением выпадений, вставок и замены символов. Доклады Академии Наук СССР . 163 (4): 845–848.Вышло на английском языке как: Levenshtein, Vladimir I. (февраль 1966). "Binary codes able of Correcting Deletions, Insertions, and Reversals". Доклады АН СССР . 10 (8): 707–710. Bibcode : 1966SPhD...10..707L.
2. Наварро, Гонсало (2001). «Путеводитель по приближенному сопоставлению строк» ​​(PDF) . ACM Computing Surveys . 33 (1): 31–88. CiteSeerX 10.1.1.452.6317 . doi :10.1145/375360.375365. S2CID  207551224. 
3. Ян Д. тен Тие; Людгер Зееваерт (1 января 2007 г.), Рецептивное многоязычие: лингвистический анализ, языковая политика и дидактические концепции, John Benjamins Publishing Company, ISBN 978-90-272-1926-8, Предполагая, что понятность обратно пропорциональна языковому расстоянию ... содержательные слова процент родственных слов (связанных напрямую или через синоним) ... лексическая связанность ... грамматическая связанность.
4. Вагнер, Роберт А.; Фишер, Майкл Дж. (1974), «Проблема коррекции строк в строки», Журнал ACM , 21 (1): 168–173, doi : 10.1145/321796.321811 , S2CID  13381535
5. Hjelmqvist, Sten (26 марта 2012 г.), Быстрый, эффективный алгоритм Левенштейна.
6. Хиршберг, Д.С. (1975). «Алгоритм линейного пространства для вычисления максимальных общих подпоследовательностей» (PDF) . Сообщения ACM (Представленная рукопись). 18 (6): 341–343. CiteSeerX 10.1.1.348.4774 . doi :10.1145/360825.360861. MR  0375829. S2CID  207694727. 
7. Шульц, Клаус У.; Михов, Стоян (2002). «Быстрая коррекция строк с помощью автоматов Левенштейна». Международный журнал анализа и распознавания документов . 5 (1): 67–85. CiteSeerX 10.1.1.16.652 . doi :10.1007/s10032-002-0082-8. S2CID  207046453. 
8. Андони, Александр; Краутгеймер, Роберт; Онак, Кшиштоф (2010). Полилогарифмическая аппроксимация для расстояния редактирования и асимметричной сложности запроса . IEEE Symp. Основы компьютерной науки (FOCS). arXiv : 1005.4033 . Bibcode : 2010arXiv1005.4033A. CiteSeerX 10.1.1.208.2079 . 
9. Backurs, Arturs; Indyk, Piotr (2015). Расстояние редактирования не может быть вычислено за строго субквадратичное время (если SETH не является ложным) . Сорок седьмой ежегодный симпозиум ACM по теории вычислений (STOC). arXiv : 1412.0348 . Bibcode : 2014arXiv1412.0348B.

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

• Блэк, Пол Э., ред. (14 августа 2008 г.), «Расстояние Левенштейна», Словарь алгоритмов и структур данных [онлайн], Национальный институт стандартов и технологий США , получено 2 ноября 2016 г.
• Реализации кода Rosetta для расстояния Левенштейна