Алгоритмы: Расстояние Левенштайна

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

Применение

Расстояние Левенштейна и его обобщения активно применяется:

• для исправления ошибок в слове (в поисковых системах, базах данных, при вводе текста, при автоматическом распознавании отсканированного текста или речи).
• для сравнения текстовых файлов утилитой diff и ей подобными. Здесь роль «символов» играют строки, а роль «строк» — файлы.
• в биоинформатике для сравнения генов, хромосом и белков.

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

При перестановке местами слов или частей слов получаются сравнительно большие расстояния;

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

Память

Алгоритм в виде, описанном выше, требует 

операций и такую же память. Последнее может быть неприятным: так, для сравнения файлов длиной в 105 строк потребуется около 40 гигабайт памяти.

Если требуется только расстояние, легко уменьшить требуемую память до

Для этого надо учесть, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после вычисления D(i, j) не нужны также D(i-1,0) … D(i-1,j-1). Поэтому алгоритм можно переписать как

 для всех i от 0 до M
   для всех j от 0 до N
     вычислить D(i, j)
   если i>0
     стереть строку D(i-1)
 вернуть D(M, N)

или даже

 для всех i от 0 до M
   для всех j от 0 до N
     вычислить D(i, j)
     если i>0 и j>0
       стереть D(i-1, j-1)
 вернуть D(M, N)

Если требуется редакционное предписание, экономия памяти усложняется.

Для того, чтобы обеспечить время 

 

при памяти 

, 

определим матрицу E минимальных расстояний между суффиксами строк, то есть E(i, j) — расстояние между последними i символами и последними j символами . Очевидно, матрицу E можно вычислить аналогично матрице D, и так же быстро. 

• Теперь опишем алгоритм, считая, что — кратчайшая из двух строк.
• 
  
• Если длина одной из строк (или обеих) не больше 1, задача тривиальна. Если нет, выполним следующие шаги.
• Разделим строку на две подстроки длиной . (Если M нечётно, то длины подстрок будут   и   
• Обозначим подстроки и .
• Для вычислим последнюю строку матрицы D, а для — последнюю строку матрицы E.
• Найдём i такое, что  
• минимально. Здесь D и Е — матрицы из предыдущего шага, но мы используем только их последние строки. Таким образом, мы нашли разбиение на две подстроки, минимизирующее сумму расстояния левой половины {\displaystyle S_{1}} до левой части и расстояния правой половины до правой части . Следовательно, левая подстрока соответствует левой половине , а правая — правой.
• Рекурсивно ищем редакционное предписание, превращающее в левую часть (то есть в подстроку ).
• Рекурсивно ищем редакционное предписание, превращающее в правую часть (то есть в подстроку ).
• Объединяем оба редакционных предписания.

Время выполнения удовлетворяет (с точностью до умножения на константу) условию

,

откуда следует (доказывается индукцией по M)

следовательно

Требуемая память пропорциональна 

Кроме того, есть алгоритмы, экономящие память за счёт существенного замедления, например, время становится кубическим, а не квадратичным, по длине строк.

Пример

В этом разделе показано, как расстояние Левенштейна вычисляется, когда исходная строка «GUMBO», а целевая строка - «GAMBOL».

Шаги 1 и 2

		G	U	M	B	O
	0	1	2	3	4	5
G	1
A	2
M	3
B	4
O	5
L	6

Шаги 3 - 6. Когда i = 1

		G	U	M	B	O
	0	1	2	3	4	5
G	1	0
A	2	1
M	3	2
B	4	3
O	5	4
L	6	5

Шаги 3 - 6. Когда i = 2

		G	U	M	B	O
	0	1	2	3	4	5
G	1	0	1
A	2	1	1
M	3	2	2
B	4	3	3
O	5	4	4
L	6	5	5

Шаги 3 - 6. Когда i = 3

		G	U	M	B	O
	0	1	2	3	4	5
G	1	0	1	2
A	2	1	1	2
M	3	2	2	1
B	4	3	3	2
O	5	4	4	3
L	6	5	5	4

Шаги 3 - 6. Когда i = 4

		G	U	M	B	O
	0	1	2	3	4	5
G	1	0	1	2	3
A	2	1	1	2	3
M	3	2	2	1	2
B	4	3	3	2	1
O	5	4	4	3	2
L	6	5	5	4	3

Шаги 3 - 6. Когда  i = 5

		G	U	M	B	O
	0	1	2	3	4	5
G	1	0	1	2	3	4
A	2	1	1	2	3	4
M	3	2	2	1	2	3
B	4	3	3	2	1	2
O	5	4	4	3	2	1
L	6	5	5	4	3	2

Шаг 7

Расстояние находится в нижнем правом углу матрицы, то есть 2. Это соответствует нашей интуитивной реализации, что «GUMBO» можно преобразовать в «GAMBOL», заменив «A» на «U» и добавив «L» (одна подстановка и 1 вставка = 2 изменения).