Расстояние редактирования (расстояние Левенштейна)
Вы набираете 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 в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать расстояние редактирования