Ru.Wikipedia.Org - Расстояние Дамерау

Меню
Главная
Случайная статья
Настройки

Расстояние Дамерау — Левенштейна
Материал из https://ru.wikipedia.org

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

Содержание

Алгоритм

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

a

b

определяется функцией

d_{a,b}(|a|,|b|)

как:

\qquad d_{a,b}(i,j)={\begin{cases}\max(i,j)&{\text{ если}}\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{ если }}i,j>1{\text{ и }}a_{i}=b_{j-1}{\text{ и }}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{ иначе,}}\end{cases}}

где

1_{(a_{i}\neq b_{j})}

это индикаторная функция, равная нулю при

a_{i}=b_{j}

и 1 в противном случае.

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

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

Реализации

def damerau_levenshtein_distance(s1, s2):
    d = {}
    lenstr1 = len(s1)
    lenstr2 = len(s2)
    for i in range(-1,lenstr1+1):
        d[(i,-1)] = i+1
    for j in range(-1,lenstr2+1):
        d[(-1,j)] = j+1
 
    for i in range(lenstr1):
        for j in range(lenstr2):
            if s1[i] == s2[j]:
                cost = 0
            else:
                cost = 1
            d[(i,j)] = min(
                           d[(i-1,j)] + 1, # deletion
                           d[(i,j-1)] + 1, # insertion
                           d[(i-1,j-1)] + cost, # substitution
                          )
            if i and j and s1[i] == s2[j-1] and s1[i-1] == s2[j]:
                d[(i,j)] = min(d[(i,j)], d[i-2,j-2] + 1) # transposition
 
    return d[lenstr1-1,lenstr2-1]