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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Алгоритм[править | править вики-текст]

Расстояние Дамерау-Левенштейна между двумя строками и определяется функцией как:

где это индикаторная функция равная нулю при и 1 в противном случае.

Каждый рекурсивный вызов соответствует одному из случаев:

  • соответствует удалению символа (из a в b).
  • соответствует вставке (из a в b).
  • соответствие или несоответствие, в зависимости от совпадения символов
  • в случае перестановки двух последовательных символов.

Реализации[править | править вики-текст]

См. также[править | править вики-текст]