Русская Википедия:Расстояние Левенштейна

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

Впервые задачу поставил в 1965 году советский математик Владимир Левенштейн при изучении последовательностей <math>0-1</math>^[1], впоследствии более общую задачу для произвольного алфавита связали с его именем. Большой вклад в изучение вопроса внёс Дэн Гасфилд^[2].

Применение

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

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

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

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

Редакционное предписание

Редакционным предписанием называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: D (Шаблон:Lang-en) — удалить, I (англ. insert) — вставить, R (Шаблон:Lang-en2) — заменить, M (Шаблон:Lang-en2) — совпадение.

Например, для 2 строк «CONNECT» и «CONEHEAD» можно построить следующую таблицу преобразований:

M	M	M	R	I	M	R	R
C	O	N	N		E	C	T
C	O	N	E	H	E	A	D

Найти только расстояние Левенштейна — более простая задача, чем найти ещё и редакционное предписание (подробнее см. ниже).

Обобщения

Разные цены операций

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

w(a, b) — цена замены символа a на символ b
w(ε, b) — цена вставки символа b
w(a, ε) — цена удаления символа a

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

w(a, а) = 0
w(a, b) = 1 при a≠b
w(ε, b) = 1
w(a, ε) = 1

Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера — Фишера, приведённый ниже. Здесь и ниже мы считаем, что все w неотрицательны, и действует неравенство треугольника: замена двух последовательных операций одной не увеличит общую цену (например, замена символа x на y, а потом y на z не лучше, чем сразу x на z).

Транспозиция

Если к списку разрешённых операций добавить транспозицию (два соседних символа меняются местами), получается расстояние Дамерау — Левенштейна. Для неё также существует алгоритм, требующий O(MN) операций. Дамерау показал, что 80 % ошибок при наборе текста человеком являются транспозициями. Кроме того, расстояние Дамерау — Левенштейна используется и в биоинформатике.

Формула

Здесь и далее считается, что элементы строк нумеруются с первого, как принято в математике, а не с нулевого, как принято во многих языках программирования.

Пусть <math>S_1</math> и <math>S_2</math> — две строки (длиной <math>M</math> и <math>N</math> соответственно) над некоторым алфавитом, тогда редакционное расстояние (расстояние Левенштейна) <math>{\rm d}(S_1, S_2)</math> можно подсчитать по следующей рекуррентной формуле

<math>\ {\rm d}(S_1, S_2) = D(M,N)</math> , где

<math>D(i, j) = \left\{\begin{array}{llcl} 0,&&&i = 0,\ j = 0\\ i,&&&j = 0,\ i > 0\\ j,&&&i = 0,\ j > 0\\ \min\{\\ &D(i, j - 1) + 1,\\ &D(i - 1, j) + 1,&&j > 0,\ i > 0\\ &D(i - 1, j - 1) + {\rm m}(S_1[i], S_2[j])\\

\}

\end{array}\right. </math>,

где <math>{\rm m}(a,b)</math> равна нулю, если <math>a = b</math> и единице в противном случае; <math>\min\{\,a, b, c\,\}</math> возвращает наименьший из аргументов.

Здесь шаг по <math>i</math> символизирует удаление (D) из первой строки, по <math>j</math> — вставку (I) в первую строку, а шаг по обоим индексам символизирует замену символа (R) или отсутствие изменений (M).

Очевидно, справедливы следующие утверждения:

<math>{\rm{d}}(S_1,S_2) \geqslant \bigl| |S_1| - |S_2| \bigr|</math>
<math>{\rm{d}}(S_1,S_2) \leqslant \max\bigl( |S_1| , |S_2| \bigr)</math>
<math>\mathop{\rm{d}}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2</math>

Пример работы алгоритма.
		P	O	L	Y	N	O	M	I	A	L
	0	1	2	3	4	5	6	7	8	9	10
E	1	1	2	3	4	5	6	7	8	9	10
X	2	2	2	3	4	5	6	7	8	9	10
P	3	2	3	3	4	5	6	7	8	9	10
O	4	3	2	3	4	5	5	6	7	8	9
N	5	4	3	3	4	4	5	6	7	8	9
E	6	5	4	4	4	5	5	6	7	8	9
N	7	6	5	5	5	4	5	6	7	8	9
T	8	7	6	6	6	5	5	6	7	8	9
I	9	8	7	7	7	6	6	6	6	7	8
A	10	9	8	8	8	7	7	7	7	6	7
L	11	10	9	8	9	8	8	8	8	7	6

Доказательство

Рассмотрим формулу более подробно. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной <math>i</math>, нужно совершить <math>i</math> операций удаления, а чтобы получить строку длиной <math>j</math> из пустой, нужно произвести <math>j</math> операций вставки.

Осталось рассмотреть нетривиальный случай, когда обе строки непусты.

Для начала заметим, что в оптимальной последовательности операций их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:

Две замены одного и того же символа — неоптимально (если мы заменили x на y, потом — y на z, выгоднее было сразу заменить x на z).
Две замены разных символов можно менять местами
Два стирания или две вставки можно менять местами
Вставка символа с его последующим стиранием — неоптимально (можно их обе отменить)
Стирание и вставку разных символов можно менять местами
Вставка символа с его последующей заменой — неоптимально (излишняя замена)
Вставка символа и замена другого символа меняются местами
Замена символа с его последующим стиранием — неоптимально (излишняя замена)
Стирание символа и замена другого символа меняются местами

Пусть <math>S_1</math> кончается на символ «a», <math>S_2</math> кончается на символ «b». Есть три варианта:

Символ «а», на который кончается <math>S_1</math>, в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ «a», после чего превратили первые <math>i-1</math> символов <math>S_1</math> в <math>S_2</math> (на что потребовалось <math>D(i-1,\ j)</math> операций), значит, всего потребовалось <math>D(i-1,\ j)+1</math> операций
Символ «b», на который кончается <math>S_2</math>, в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили <math>S_1</math> в первые <math>j-1</math> символов <math>S_2</math>, после чего добавили «b». Аналогично предыдущему случаю, потребовалось <math>D(i,\ j-1)+1</math> операций.
Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального «a», то, чтобы сделать последним символом «b», мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального «a» мы не добавляли. Самого финального «a» мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа — его замена. Заменять его 2 или больше раз неоптимально. Значит,
1. Если <math>a=b</math>, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили <math>D(i-1,\ j-1)</math> операций.
2. Если <math>a\ne b</math>, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить <math>D(i-1,\ j-1)</math> операций, значит, всего потребуется <math>D(i-1,\ j-1)+1</math> операций.

Алгоритм Вагнера — Фишера

Для нахождения кратчайшего расстояния необходимо вычислить матрицу D, используя вышеприведённую формулу. Её можно вычислять как по строкам, так и по столбцам. Псевдокод алгоритма:

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

Или в более развёрнутом виде, и при произвольных ценах замен, вставок и удалений:

 D(0, 0) = 0
 для всех j от 1 до N
   D(0, j) = D(0, j - 1) + цена вставки символа S2[j]
 для всех i от 1 до M
   D(i, 0) = D(i - 1, 0) + цена удаления символа S1[i]
 для всех j от 1 до N
   D(i, j) = min{
     D(i - 1, j) + цена удаления символа S1[i],
     D(i, j - 1) + цена вставки символа S2[j],
     D(i - 1, j - 1) + цена замены символа S1[i] на символ S2[j]
   }
 вернуть D(M, N)

(Напоминаем, что элементы строк нумеруются с первого, а не с нулевого.)

Для восстановления редакционного предписания требуется вычислить матрицу D, после чего идти из правого нижнего угла (M,N) в левый верхний, на каждом шаге ища минимальное из трёх значений:

если минимально (<math>D(i - 1, j)</math>+ цена удаления символа S1[i]), добавляем удаление символа S1[i] и идём в (i-1, j)
если минимально (<math>D(i, j - 1)</math>+ цена вставки символа S2[j]), добавляем вставку символа S2[j] и идём в (i, j-1)
если минимально (<math>D(i - 1, j - 1)</math>+ цена замены символа S1[i] на символ S2[j]), добавляем замену S1[i] на S2[j] (если они не равны; иначе ничего не добавляем), после чего идём в (i-1, j-1)

Здесь (i, j) — клетка матрицы, в которой мы находимся на данном шаге. Если минимальны два из трёх значений (или равны все три), это означает, что есть 2 или 3 равноценных редакционных предписания.

Этот алгоритм называется алгоритмом Вагнера — Фишера. Он предложен Р. Вагнером (R. A. Wagner) и М. Фишером (M. J. Fischer) в 1974 году.^[4]

Память

Алгоритм в виде, описанном выше, требует <math>\Theta(M \cdot N)</math> операций и такую же память. Последнее может быть неприятным: так, для сравнения файлов длиной в 10⁵ строк потребуется около 40 гигабайт памяти.

Если требуется только расстояние, легко уменьшить требуемую память до <math>\Theta(\min\{\,M,N\,\})</math>. Для этого надо учесть, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после вычисления 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)

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

Для того, чтобы обеспечить время <math>\Theta(M \cdot N)</math> при памяти <math>\Theta(\min\{\,M,N\,\})</math>, определим матрицу E минимальных расстояний между суффиксами строк, то есть E(i, j) — расстояние между последними i символами <math>S_1</math> и последними j символами <math>S_2</math>. Очевидно, матрицу E можно вычислить аналогично матрице D, и так же быстро.

Теперь опишем алгоритм, считая, что <math>S_2</math> — кратчайшая из двух строк.

Если длина одной из строк (или обеих) не больше 1, задача тривиальна. Если нет, выполним следующие шаги.
Разделим строку <math>S_1</math> на две подстроки длиной <math>M/2</math>. (Если M нечётно, то длины подстрок будут <math>(M-1)/2</math> и <math>(M+1)/2</math>.) Обозначим подстроки <math>S_1^-</math> и <math>S_1^+</math>.
Для <math>S_1^-</math> вычислим последнюю строку матрицы D, а для <math>S_1^+</math> — последнюю строку матрицы E.
Найдём i такое, что <math>D(|S_1^-|, i) + E(|S_1^+|, N-i)</math> минимально. Здесь D и Е — матрицы из предыдущего шага, но мы используем только их последние строки. Таким образом, мы нашли разбиение <math>S_2</math> на две подстроки, минимизирующее сумму расстояния левой половины <math>S_1</math> до левой части <math>S_2</math> и расстояния правой половины <math>S_1</math> до правой части <math>S_2</math>. Следовательно, левая подстрока <math>S_2</math> соответствует левой половине <math>S_1</math>, а правая — правой.
Рекурсивно ищем редакционное предписание, превращающее <math>S_1^-</math> в левую часть <math>S_2</math> (то есть в подстроку <math>S2[1...i]</math>)
Рекурсивно ищем редакционное предписание, превращающее <math>S_1^+</math> в правую часть <math>S_2</math> (то есть в подстроку <math>S2[i+1...N]</math>).
Объединяем оба редакционных предписания.^[5]

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

<math>T(M,N)=MN+T(M/2,N')+T(M/2,N-N'),\ 0\le N'\le N</math>,

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

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

<math>T(M,N) = \Theta(M \cdot N)</math>

Требуемая память пропорциональна <math>N+N/2+N/4+...=2N</math>

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

Примечания

Шаблон:Wikibooks Шаблон:Примечания Шаблон:Строки Шаблон:Rq

↑ В. И. Левенштейн. Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академий Наук СССР, 1965. 163.4:845-848.
↑ Гасфилд. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология. Невский Диалект БВХ-Петербург, 2003.
↑ См., например: http://www.medlit.ru/medrus/mg/mg080237.htm Шаблон:Wayback
↑ R. A. Wagner, M. J. Fischer. The string-to-string correction problem. J. ACM 21 1 (1974). P. 168—173
↑ При этом во втором редакционном предписании нужно увеличить номера символов первой строки на <math>|S_1^-|</math>, а второй строки на <math>i</math>, поскольку теперь они отсчитываются с начала строк, a не с их середины.

[1] В. И. Левенштейн. Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академий Наук СССР, 1965. 163.4:845-848.

[2] Гасфилд. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология. Невский Диалект БВХ-Петербург, 2003.

[3] См., например: http://www.medlit.ru/medrus/mg/mg080237.htm Шаблон:Wayback

[4] R. A. Wagner, M. J. Fischer. The string-to-string correction problem. J. ACM 21 1 (1974). P. 168—173

[5] При этом во втором редакционном предписании нужно увеличить номера символов первой строки на <math>|S_1^-|</math>, а второй строки на <math>i</math>, поскольку теперь они отсчитываются с начала строк, a не с их середины.

[1]

[2]

[3]

[4]

[5]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Русская Википедия:Расстояние Левенштейна

Содержание