UniLecs #Task. Damerau-Levenshtein distance

Albert Davletov

Published in

UniLecs

3 min readDec 15, 2019

Справка

Дана текстовая строка. С ней можно выполнять следующие операции:

Заменить один символ строки на другой символ.
Удалить один произвольный символ.
Вставить произвольный символ в произвольное место строки.
Переставить два соседних символа местами. При этом между переставленными символами нельзя вставлять другие символы.

Например, дана строка “СОК”

при помощи 1й операции из исходной строки можно получить строку “СУК”;
при помощи 2й операции — строку “ОК”;
при помощи 3й операции — строку “СТОК”;
при помощи четвертой операции — строку “ОСК”.

Минимальное количество таких операций, при помощи которых можно из одной строки получить другую, называется расстоянием редактирования или расстоянием Дамерау-Левенштейна.

Задача

Попробуйте реализовать алгоритм определения расстояния Дамерау-Левенштейна для двух заданных строк.

Входные данные: str1, str2 — строки, длина которых не превосходит 1000 символов.

Вывод: расстояние Дамерау-Левенштейна для исходных строк.

Пример:

str1 = “XABCDE”;

str2 = “ACBYDF”

Output = 4

Пояснение к примеру:

Вторая строка может быть получена из первой при помощи четырех операций редактирования: удаления буквы X, перестановки букв B и C, вставки буквы Y и замены буквы E на букву F.

Разбор

Алгоритм вычисления расстояния Дамерау-Левенштейна между двумя словами аналогичен алгоритму нахождения наибольшей общей подпоследовательности.

Решим задачу методом динамического программирования. Целевая функция — F(i,j) — расстояние редактирования для префиксов A[:i] и B[:j]. Пусть F(i,j) — это расстояние редактирования между префиксами данных строк A′=A[:i] и B′=B[:j]. Рассмотрим последние символы этих префиксов a[i−1] и b[j−1], также, как префикс B′=B[:j] мог быть получен из префикcа A′=A[:i] при помощи разрешенных операций редактирования.

Здесь возможны следующие варианты:

Если последние символы префиксов совпадают (a[i−1]==b[j−1]), то в этом случае можно не менять эти последние символы. Тогда F(i, j)=F(i−1, j−1).
Если a[i−1] ≠ b[j−1], то тогда можно потратить 1 операцию на замену символа a[i−1] на b[j−1] и также потратить F(i−1, j−1) операцию на превращение префикса A[:i−1] в B[j−1]. Тогда F(i, j) = F(i−1, j−1)+1.
Если символ a[i−1] был удален при редактировании, тогда необходимо префикс A[:i−1] превратить в B[:j], на что необходимо F(i−1, j) операций редактирования. В этом случае F(i, j)=F(i−1, j)+1.
Если символ b[j−1] был добавлен при редактировании, тогда необходимо префикс A[:i] превратить в B[:j−1], на что необходимо F(i,j−1) операций редактирования. В этом случае F(i,j) = F(i,j−1)+1.
Если последние два символа префиксов A[:i] и B[:j] были переставлены, то F(i,j)может быть равно F(i−2,j−2)+1

Далее при вычислении F(i,j) необходимо взять минимум из всех перечисленных возможностей (при этом из случаев 1 или 2 рассматривается только один, в зависимости от условия a[i−1] == b[j−1]). Начальные значения: F(i,0)=i, F(0, j)=j.

Практическое применение

Расстояние Дамерау-Левенштейна является мерой “схожести” двух строк. Алгоритм его поиска находит применение в реализации нечёткого поиска, а также в биоинформатике (сравнение ДНК).

Дамерау показал, что 80% человеческих ошибок при наборе текстов составляют перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе. Поэтому метрика Дамерау-Левенштейна часто используется в редакторских программах для проверки правописания.