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

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

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

Определение [ править ]

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

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

где некоторой строки - это строка, состоящая из всех символов , кроме первого , и - это th символ строки , начинающийся с символа 0.${\displaystyle \operatorname {tail} }$${\displaystyle x}$${\displaystyle x}$${\displaystyle x[n]}$${\displaystyle n}$${\displaystyle x}$

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

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

Пример [ править ]

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

Например, расстояние Левенштейна между «котенком» и «сидящим» равно 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.

Приложения [ править ]

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

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

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

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

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

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

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

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

Рекурсивный [ править ]

Это простая, но неэффективная рекурсивная реализация HaskelllDistance функции, которая принимает две строки 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,  то  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.

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

Этот алгоритм, пример снизу вверх динамического программирования , обсуждается, с вариантами, в 1974 статье The Строка в строку задачи коррекции Роберт А. Вагнер и Майкл Дж Фишер. ^[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  к  нулю  // исходные префиксы могут быть преобразованы в пустую строку  //  путем удаления всех символов для  i  с  1  до  m :  d [ i ,  0 ]  : =  i  // целевые префиксы могут быть достигнуты из пустого исходного префикса  // путем вставки каждого символа  для  j  от  1  до  n :  d [ 0 ,  j ]  : =  j  для  j  от  1  до  n :  для  i  от  1  до  m :  если  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 )  // подстановка  вернуть  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 ]) :  // создать два рабочих вектора с целочисленными расстояниями  объявить  int  v0 [ n  +  1 ]  объявить  int  v1 [ n  +  1 ] // инициализируем v0 (предыдущая строка расстояний)  // эта строка A [0] [i]: редактируем расстояние для пустого s  // расстояние - это просто количество символов, которые нужно удалить из t  для  i  от  0  до  n :  v0 [ i ]  =  i for  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  InsertCost  : =  v1 [ j ]  +  1,  если  s [ i ]  =  t [ j ] :  substitutionCost  : =  v0 [ j ]  else :  substitutionCost  : = v0 [ j ]  +  1 v1 [ j  +  1 ]  : =  минимум ( deletionCost ,  InsertCost ,  substitutionCost ) // копируем v1 (текущая строка) в v0 (предыдущая строка) для следующей итерации  // поскольку данные в v1 всегда недействительны, замена без копирования могла бы быть более эффективной  заменой  v0  на  v1  // после последней замены, результаты v1 теперь в v0  return  v0 [ n ]

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

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

Адаптивный вариант [ править ]

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

Автоматы [ править ]

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

Приближение [ править ]

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

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

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

Вычислительная сложность [ править ]

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

См. Также [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

В реализации алгоритма Викибука есть страница на тему: Расстояние Левенштейна

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