|
|
| (не показано 36 промежуточных версий 3 участников) |
| Строка 1: |
Строка 1: |
| − | '''Расстояние Левенштейна''' (также '''редакционное расстояние''' или '''дистанция редактирования''') между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.
| + | #перенаправление [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]] |
| − | | |
| − | | |
| − | == Свойства ==
| |
| − | | |
| − | Для расстояния Левенштейна справедливы следующие утверждения:
| |
| − | * <math>\rm{d}(S_1,S_2) \ge | |S_1| - |S_2| |</math>
| |
| − | * <math>\rm{d}(S_1,S_2) \le max( |S_1| , |S_2| )</math>
| |
| − | * <math>\rm{d}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2</math>
| |
| − | где <math>\rm{d}(S_1,S_2)</math> — расстояние Левенштейна между строками <math>S_1</math> и <math>S_2</math>, а |S| - длина строки S.
| |
| − | | |
| − | == Редакционное предписание ==
| |
| − | | |
| − | ''Редакционным предписанием'' называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: '''D''' (англ. delete) — удалить, '''I''' (англ. insert) — вставить, '''R''' (англ. replace) — заменить, '''M''' (англ. match) — совпадение.
| |
| − | | |
| − | Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований:
| |
| − | {| class="wikitable" border = "1"
| |
| − | !'''M''' ||'''M''' ||'''M''' ||'''M''' ||'''R''' ||'''M''' ||'''R''' ||'''I'''
| |
| − | |-
| |
| − | |'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''1''' ||'''2''' ||'''3''' ||
| |
| − | |-
| |
| − | |'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''o''' ||'''2''' ||'''1''' ||'''4'''
| |
| − | |}
| |
| − | | |
| − | | |
| − | === Разные цены операций ===
| |
| − | | |
| − | Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность разных ошибок при вводе текста, и т. п. В общем случае:
| |
| − | * 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).
| |
| − | | |
| − | == Формула ==
| |
| − | | |
| − | Будем считать, что элементы строк нумеруются с первого, как принято в математике, а не нулевого.
| |
| − | | |
| − | Пусть <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) = \rm{D}(M,N)</math> , где
| |
| − | | |
| − | <math>\rm{D}(i, j) = \left\{\begin{array}{llcl}
| |
| − | 0&&;&i = 0,\ j = 0\\
| |
| − | i&&;&j = 0,\ i > 0\\
| |
| − | j&&;&i = 0,\ j > 0\\
| |
| − | \rm{min}(\\
| |
| − | &\rm{D}(i, j - 1) + 1\\
| |
| − | &\rm{D}(i - 1, j) + 1&;&j > 0,\ i > 0\\
| |
| − | &\rm{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>D(i, j)</math> — расстояние между префиксами строк: первыми i символами строки <math>S_1</math> и первыми j символами строки <math>S_2</math>. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной <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 или больше раз неоптимально. Значит,
| |
| − | ## Если <math>a=b</math>, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили <math>D(i-1,\ j-1)</math> операций.
| |
| − | ## Если <math>a\ne b</math>, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить <math>D(i-1,\ j-1)</math> операций, значит, всего потребуется <math>D(i-1,\ j-1)+1</math> операций.
| |
| − | | |
| − | == Алгоритм Вагнера — Фишера ==
| |
| − | | |
| − | Для нахождения кратчайшего расстояния необходимо вычислить матрицу D, используя [[#Формула|вышеприведённую формулу]]. Её можно вычислять как по строкам, так и по столбцам.
| |
| − | Псевдокод алгоритма, написанный при произвольных ценах замен, вставок и удалений(важно помнить, что элементы нумеруются с 1):
| |
| − | <code>
| |
| − | 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)
| |
| − | </code>
| |
| − | | |
| − | === Память ===
| |
| − | | |
| − | Алгоритм в виде, описанном выше, требует <math>\Theta(M \cdot N)</math> операций и такую же память. Последнее может быть неприятным: так, для сравнения файлов длиной в 10<sup>5</sup> строк потребуется около 40 гигабайт памяти.
| |
| − | | |
| − | Если требуется только расстояние, легко уменьшить требуемую память до <math>\Theta(\min(M,N))</math>. Для этого надо учесть, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после вычисления D(i, j) не нужны также D(i-1,0) … D(i-1,j-1). Поэтому алгоритм можно переписать как
| |
| − | <code>
| |
| − | для всех i от 0 до M
| |
| − | для всех j от 0 до N
| |
| − | вычислить D(i, j)
| |
| − | если i>0 и j>0
| |
| − | стереть D(i-1, j-1)
| |
| − | вернуть D(M, N)
| |
| − | </code>
| |
