Расстояние редактирования (расстояние Левенштейна)

Вы набираете recieve, а телефон предлагает receive. Он понимает, что вы были близки, потому что слова отличаются всего на пару правок. Измерить эту близость, то есть расстояние редактирования, — классическая задача динамического программирования.

Таблица с одним словом вдоль левого края и другим вдоль верхнего, числами в клетках и оранжевым путем правок из левого верхнего угла в правый нижний
Таблица с одним словом вдоль левого края и другим вдоль верхнего, числами в клетках и оранжевым путем правок из левого верхнего угла в правый нижний

Задача

Правка меняет слово на одну букву: вставляет букву, удаляет букву или заменяет одну букву другой. Расстояние редактирования между двумя словами — наименьшее число правок, превращающих одно в другое. Между cat и cut расстояние 1, между cat и cast — 1, между cat и act — 2. Его также называют расстоянием Левенштейна в честь советского математика Владимира Левенштейна, который изучал его в 1965 году.

Таблица

Пусть d[i][j] — расстояние редактирования между первыми i буквами одного слова и первыми j буквами другого. Чтобы превратить слово в пустое, нужно по одному удалению на букву, поэтому d[i][0] = i, а чтобы построить слово с нуля, нужно по одной вставке на букву, поэтому d[0][j] = j. Если буква i равна букве j, то d[i][j] = d[i − 1][j − 1]. Иначе d[i][j] = 1 + наименьшее из d[i − 1][j − 1] (замена), d[i − 1][j] (удаление) и d[i][j − 1] (вставка).

Пример

Для kitten и sitting в таблице 7 строк и 8 столбцов. Правая нижняя клетка равна 3, и обратный ход от нее дает: заменить k на s, оставить i, t и t, заменить e на i, оставить n и вставить g. Kitten, sitten, sittin, sitting: три правки, и таблица доказывает, что более короткого списка нет.

Как считать правки в обратном порядке

Начните с правой нижней клетки и спросите, от какого соседа пришло ее значение. Если буквы совпадают и клетка равна соседу сверху слева, буква сохранена: шагните по диагонали. Если она на единицу больше соседа сверху слева, это замена; на единицу больше клетки сверху — удаление; на единицу больше клетки слева — вставка. Несколько путей могут оказаться равноценными, и каждый дает кратчайший список правок.

История и применение

Левенштейн ввел это расстояние в 1965 году, работая над кодами, исправляющими ошибки. Табличный метод публиковали несколько авторов, самые известные из них — Роберт Вагнер и Майкл Фишер в 1974 году, поэтому его часто называют алгоритмом Вагнера — Фишера. Сегодня расстояния редактирования упорядочивают варианты исправления орфографии, находят в базах данных имена с опечатками, сравнивают последовательности ДНК и белков и оценивают качество распознавания речи.

Попробуйте сами

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

Часто задаваемые вопросы

Является ли расстояние редактирования метрикой?

Да. Оно никогда не бывает отрицательным, равно 0 только для одинаковых слов, одинаково в обе стороны, и путь через третье слово никогда не сделает его короче: d(a, c) ≤ d(a, b) + d(b, c). Поэтому оно удобно для поиска близких совпадений.

Что такое расстояние Дамерау — Левенштейна?

Это расстояние редактирования с одной дополнительной правкой: перестановкой двух соседних букв. Фредерик Дамерау в 1964 году обнаружил, что вставка, удаление, замена и перестановка вместе охватывают более 80 % орфографических ошибок. С перестановками между recieve и receive расстояние 1, а не 2.

Можно ли вычислить расстояние редактирования быстрее, чем за O(m·n)?

Ненамного. В 2015 году Артурс Бакурс и Петр Индик показали, что метод, работающий за время O(n^(2 − ε)) для некоторого ε > 0, опроверг бы сильную гипотезу экспоненциального времени, в которую верит большинство исследователей. Однако для близких слов нужна лишь узкая полоса вокруг диагонали таблицы.

Как расстояние редактирования используется при сравнении ДНК?

Биологи используют ту же таблицу, но с баллами вместо счетчиков: совпадения приносят баллы, а замены и пропуски отнимают баллы, зависящие от букв. Это алгоритм Нидлмана — Вунша 1970 года для целых последовательностей и алгоритм Смита — Уотермана 1981 года для наилучших совпадающих участков.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Попробовать расстояние редактирования