74
правки
Изменения
Нет описания правки
==Упрощённый алгоритм==
Не решает задачу корректно, но бывает полезен на практике.
Здесь и далее будем использовать следующие обозначения: <tex>S</tex> и <tex>T</tex> {{---}} строки, между которыми требуется найти расстояние Дамерау {{---}} Левенштейна; <tex>M</tex> и <tex>N</tex> {{---}} их длины соответственно.
Ответ на задачу {{---}} <tex>D(M,N)</tex> , где
<tex>D(i, j) = \left\{\begin{array}{lllc}
min(A, D(i - 2, j - 2) + transposeCost)&&;&i > 1,\ j > 1,\ S[i] = T[j-1],\ S[i-1] = T[j]\\
A&&;\text{otherwise}\\
\end{array}\right.
</tex>
<tex>A = \left\{\begin{array}{llcl}
&D(i - 1, j - 1) + replaceCost\\
)
\end{array}\right.
</tex>
Таким образом для получения ответа необходимо заполнить матрицу D, пользуясь рекуррентным соотношением.
Сложность алгоритма: <tex>O\left (m M \cdot n N \right )</tex>. Затраты памяти: <tex>O\left (M \cdot N \right)</tex>.
Псевдокод алгоритма:
'''int''' DamerauLevenshteinDistance('''char''' S[1..mM], '''char''' T[1..nN]) '''int''' d[0..mM, 0..nN]
'''int''' i, j, cost
''// База динамики''
'''for''' i '''from''' 0 '''to''' mM
d[i, 0] = i
'''for''' j '''from''' 1 '''to''' nN
d[0, j] = j
'''for''' i '''from''' 1 '''to''' mM '''for''' j '''from''' 1 '''to''' n N
''// Стоимость замены''
'''if''' S[i] == T[j] '''then''' replaceCost = 0
)
'''return''' d[mM, nN]
Контрпример: <tex>S =</tex> <tex>'CA'</tex> и <tex>T =</tex> <tex>'ABC'</tex>. Расстояние Дамерау {{---}} Левенштейна между строками равно 2 (<tex>CA \rightarrow AC \rightarrow ABC</tex>), однако функция приведённая выше возвратит 3. Дело в том, что использование этого упрощённого алгоритма накладывает ограничение: любая подстрока может быть редактирована не более одного раза. Поэтому переход <tex>AC \rightarrow ABC</tex> невозможен, и последовательность действий такая: (<tex>CA \rightarrow A \rightarrow AB \rightarrow ABC</tex>).
Условие многих практических задач не предполагает многократного редактирования подстрок, поэтому часто достаточно упрощённого алгоритма. Ниже представлен более сложный алгоритм, который корректно решает задачу поиска расстояния Дамерау {{---}} Левенштейна.
==АлгоритмКорректный алгоритм==
В интересах краткости положим <tex>insertCost = deleteCost = replaceCost = transposeCost = 1</tex>. При иной формулировке задачи формулы легко обобщаются на любой случай.
Сложность алгоритма: <tex>O\left (m M \cdot n N \cdot \max(mM, nN) \right )</tex>. Затраты памяти: <tex>O\left (M \cdot N \right)</tex>. Однако скорость работы алгоритма может быть улучшена до <tex>O\left (M \cdot N \right)</tex>.
В основу алгоритма положена идея динамического программирования по префиксу. Будем хранить матрицу <tex>D[0..m M + 1][0..n N + 1]</tex>, где <tex>D[i + 1][j + 1]</tex> {{---}} расстояние Дамерау {{---}} Левенштейна между префиксами строк <tex>S</tex> и <tex>T</tex>, длины префиксов {{---}} <tex>i</tex> и <tex>j</tex> соответственно.
Будем заполнять матрицу следующим образом, используя рекуррентное соотношение, описанное ниже:
'''for''' i '''from''' 0 '''to''' mM '''for''' j '''from''' 0 '''to''' nN
вычислить D(i + 1, j + 1);
'''return''' D(m + 1, n + 1);
<tex>sd[x]</tex> {{---}} индекс последнего вхождения <tex>x</tex> в <tex>S</tex>
<tex>DBlast</tex> {{---}} на i-й итерации внешнего цикла индекс последнего символа <tex>T: T[DBlast] = S[i]</tex>
Тогда если на очередной итерации внутреннего цикла положить: <tex>i1 i' = sd[T[j]],\ j1 j' = DBlast</tex>, то
<tex>D(i, j) = min(A, D(i1i', j1j') + (i - i1 i' - 1) + 1 + (j - j1 j' - 1))</tex> <tex>(*)</tex>
, где
*Удалить некоторое количество символов, а затем переставить местами символы, ставшие соседними.
Тогда если символ <tex>S[i]</tex> встречался в <tex>T[1]..T[j]</tex> на позиции <tex>j1j'</tex>, а символ <tex>T[j]</tex> встречался в <tex>S[1]..S[i]</tex> на позиции <tex>i1i'</tex>; то <tex>T[1]..T[j]</tex> может быть получена из <tex>S[1]..S[i]</tex> удалением символов <tex>S[i1 i' + 1]..S[i - 1]</tex>, транспозицией ставших соседними <tex>S[i1i']</tex> и <tex>S[i]</tex> и вставкой символов <tex>T[j1 j' + 1]..T[j - 1]</tex>. Суммарно на это будет затрачено <tex>D(i1i', j1j') + (i - i1 i' - 1) + 1 + (j - j1 j' - 1)</tex> операций, что описано в <tex>(*)</tex>. Поэтому мы выбирали оптимальную последовательность операций, рассматрев случай с транспозицией и без неё.
Псевдокод алгоритма:
'''int''' DamerauLevenshteinDistance('''char''' S[1..mM], '''char''' T[1..nN])'''
''// Обработка крайних случаев''
'''if''' (S == "") '''then'''
'''return''' 0
'''else'''
'''return''' nN
'''else''' '''if''' (T == "") '''then'''
'''return''' mM '''int''' D[0..m M + 1, 0..n N + 1] ''// Динамика'' '''int''' INF = m M + n N ''// Большая константа''
''// База индукции''
D[0, 0] = INF;
'''for''' i '''from''' 0 '''to''' mM
D[i + 1, 1] = i
D[i + 1, 0] = INF
'''for''' j '''from''' 0 '''to''' nN
D[1, j + 1] = j
D[0, j + 1] = INF
sd[Letter] = 0
'''for''' i '''from''' 1 '''to''' mM '''int''' DB last = 0 '''for''' j '''from''' 1 '''to''' nN
'''int''' i1 = sd[T[j]]
'''int''' j1 = DBlast
'''if''' S[i] == T[j] '''then'''
D[i + 1, j + 1] = D[i, j]
'''else'''
D[i + 1, j + 1] = minimum(D[i, j], D[i + 1, j], D[i, j + 1]) + 1
sd[S[i]] = i
'''return''' D[m M + 1, n N + 1]
==См. также==
