27-09-2023
Расстояние Левенштейна (также редакционное расстояние или дистанция редактирования) между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.
Впервые задачу упомянул в 1965 году советский математик Владимир Иосифович Левенштейн при изучении последовательностей .[1] Впоследствии более общую задачу для произвольного алфавита связали с его именем. Большой вклад в изучение вопроса внёс Гасфилд.[2]
Содержание |
Очевидно, справедливы следующие утверждения:
где — расстояние Левенштейна между строками и , а |S| - длина строки S.
Расстояние Левенштейна и его обобщения активно применяется:
С точки зрения приложений определение расстояния между словами или текстовыми полями по Левенштейну обладает следующими недостатками:
Редакционным предписанием называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: D (англ. delete) — удалить, I (англ. insert) — вставить, R (replace) — заменить, M (match) — совпадение.
Например, для 2-х строк «CONNECT» и «CONEHEAD» можно построить следующую таблицу преобразований:
M | M | M | R | R | R | R | I |
---|---|---|---|---|---|---|---|
C | O | N | N | E | C | T | |
C | O | N | E | H | E | A | D |
Найти только расстояние Левенштейна — более простая задача, чем найти ещё и редакционное предписание (подробнее см. ниже).
Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность мутаций в биологии[3], разную вероятность разных ошибок при вводе текста и т. д. В общем случае:
Необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при
Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера — Фишера, приведённый ниже. Здесь и ниже мы считаем, что все w неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ x на y, а потом с y на z не лучше, чем сразу x на z).
Если к списку разрешённых операций добавить транспозицию (два соседних символа меняются местами), получается расстояние Дамерау — Левенштейна. Для неё также существует алгоритм, требующий O(MN) операций. Дамерау показал, что 80 % ошибок при наборе текста человеком являются транспозициями. Кроме того, расстояние Дамерау — Левенштейна используется и в биоинформатике.
Здесь и далее считается, что элементы строк нумеруются с первого, как принято в математике, а не с нулевого, как принято в языках C, C++, Java.
Пусть и — две строки (длиной и соответственно) над некоторым алфавитом, тогда редакционное расстояние можно подсчитать по следующей рекуррентной формуле
, где
,
где равна нулю, если и единице в противном случае; возвращает наименьший из аргументов.
Рассмотрим формулу более подробно. Здесь — расстояние между префиксами строк: первыми i символами строки и первыми j символами строки . Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной , нужно совершить операций удаления, а чтобы получить строку длиной из пустой, нужно произвести операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.
Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:
Пускай кончается на символ «a», кончается на символ «b». Есть три варианта:
Для нахождения кратчайшего расстояния необходимо вычислить матрицу 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) в левый верхний, на каждом шаге ища минимальное из трёх значений:
Здесь (i, j) — клетка матрицы, в которой мы находимся на данном шаге. Если минимальны два из трёх значений (или равны все три), это означает, что есть 2 или 3 равноценных редакционных предписания.
Этот алгоритм называется алгоритмом Вагнера — Фишера. Он предложен Р. Вагнером (R. A. Wagner) и М. Фишером (M. J. Fischer) в 1974 году.[4]
Алгоритм в виде, описанном выше, требует операций и такую же память. Последнее может быть неприятным: так, для сравнения файлов длиной в 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, и так же быстро.
Теперь опишем алгоритм, считая, что — кратчайшая из двух строк.
Время выполнения удовлетворяет (с точностью до умножения на константу) условию
откуда следует (доказывается индукцией по M)
следовательно
Требуемая память пропорциональна
Кроме того, есть алгоритмы, экономящие память за счёт существенного замедления, например, время становится кубическим, а не квадратичным, по длине строк.
Расстояние Левенштейна.