WikiSort.ru - Программирование

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

Алгоритм

Расстояние Дамерау — Левенштейна между двумя строками ${\displaystyle a}$ и ${\displaystyle b}$ определяется функцией ${\displaystyle d_{a,b}(|a|,|b|)}$ как:

${\displaystyle \qquad d_{a,b}(i,j)={\begin{cases}\max(i,j)&{\text{ if}}\min(i,j)=0,\\\min {\begin{cases}d_{a,b}(i-1,j)+1\\d_{a,b}(i,j-1)+1\\d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}\\d_{a,b}(i-2,j-2)+1\end{cases}}&{\text{ if }}i,j>1{\text{ and }}a_{i}=b_{j-1}{\text{ and }}a_{i-1}=b_{j}\\\min {\begin{cases}d_{a,b}(i-1,j)+1\\d_{a,b}(i,j-1)+1\\d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}\end{cases}}&{\text{ otherwise,}}\end{cases}}}$

где ${\displaystyle 1_{(a_{i}\neq b_{j})}}$ это индикаторная функция, равная нулю при ${\displaystyle a_{i}=b_{j}}$ и 1 в противном случае.

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

• ${\displaystyle d_{a,b}(i-1,j)+1}$ соответствует удалению символа (из a в b),
• ${\displaystyle d_{a,b}(i,j-1)+1}$ соответствует вставке (из a в b),
• ${\displaystyle d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}}$ соответствие или несоответствие, в зависимости от совпадения символов,
• ${\displaystyle d_{a,b}(i-2,j-2)+1}$ в случае перестановки двух последовательных символов.

Реализации

• На языке программирования Perl в виде модуля Text::Levenshtein::Damerau
• На языке программирования PlPgSQL (недоступная ссылка)
• Дополнительный модуль для MySQL

См. также

• Расстояние Левенштейна

Это заготовка статьи о программировании. Вы можете помочь проекту, дополнив её.