Задача о расстоянии Дамерау-Левенштейна

Определение:

Расстояние Дамерау-Левенштейна (англ. Damerau-Levenshtein distance) между двумя строками, состоящими из конечного числа символов — это минимальное число операций вставки, удаления, замены одного символа и транспозиции двух соседних символов, необходимых для перевода одной строки в другую.

Является модификацией расстояния Левенштейна, отличается от него добавлением операции перестановки.

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

Расстояние Дамерау-Левенштейна, как и метрика Левенштейна, является мерой "схожести" двух строк. Алгоритм его поиска находит применение в реализации нечёткого поиска, а также в биоинформатике (сравнение ДНК), несмотря на то, что изначально алгоритм разрабатывался для сравнения текстов, набранных человеком (Дамерау показал, что 80% человеческих ошибок при наборе текстов составляют перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе. Поэтому метрика Дамерау-Левенштейна часто используется в редакторских программах для проверки правописания).

Упрощённый алгоритм

Не решает задачу корректно, но бывает полезен на практике.

Здесь и далее будем использовать следующие обозначения: [math]S[/math] и [math]T[/math] — строки, между которыми требуется найти расстояние Дамерау-Левенштейна; [math]M[/math] и [math]N[/math] — их длины соответственно.

Рассмотрим алгоритм, отличающийся от алгоритма поиска расстояния Левенштейна одной проверкой (храним матрицу [math]D[/math], где [math]D(i, j)[/math] — расстояние между префиксами строк: первыми [math]i[/math] символами строки [math]S[/math] и первыми [math]j[/math] символами строки [math]T[/math]). Рекуррентное соотношение имеет вид:

Ответ на задачу — [math]D(M,N)[/math] , где

[math]D(i, j) = \left\{\begin{array}{lllc} \min{(A, D(i - 2, j - 2) + transposeCost)}&&;\ i \gt 1,\ j \gt 1,\ S[i] = T[j - 1],\ S[i - 1] = T[j]\\ A&&;\ \text{otherwise}\\ \end{array}\right. [/math]

[math] A = \left\{\begin{array}{llcl} 0&;\ i = 0,\ j = 0\\ i&;\ j = 0,\ i \gt 0\\ j&;\ i = 0,\ j \gt 0\\ D(i - 1, j - 1)&;\ S[i] = T[j]\\ \min{(}\\ \begin{array}{llcl} &D(i, j - 1) + insertCost\\ &D(i - 1, j) + deleteCost&&\\ &D(i - 1, j - 1) + replaceCost\\ \end{array}&;\ j \gt 0,\ i \gt 0,\ S[i] \ne T[j]\\ ) \end{array}\right. [/math]

Таким образом для получения ответа необходимо заполнить матрицу [math]D[/math], пользуясь рекуррентным соотношением. Сложность алгоритма: [math]O\left (M \cdot N \right )[/math]. Затраты памяти: [math]O\left (M \cdot N \right)[/math].

Псевдокод алгоритма:

int DamerauLevenshteinDistance(S: char[1..M], T: char[1..N]; deleteCost, insertCost, replaceCost, transposeCost: int):
    d = int[0..M][0..N] 
      
    // База динамики
    for i = 0 to M
        d[i][0] = i
    for j = 1 to N
        d[0][j] = j
    
    for i = 1 to M
        for j = 1 to N           
            // Стоимость замены
            if S[i] == T[j]
               d[i][j] = d[i - 1][j - 1]
            else
               d[i][j] = d[i - 1][j - 1] + replaceCost                   
            d[i][j] = min(
                             d[i][j],                                     // замена
                             d[i - 1][j    ] + deleteCost,                // удаление
                             d[i    ][j - 1] + insertCost                 // вставка               
                         )
            if(i > 1 and j > 1 and S[i] == T[j - 1] and S[i - 1] == T[j])
                d[i][j] = min(
                                  d[i][j],
                                  d[i - 2][j - 2] + transposeCost         // транспозиция
                             )
    return d[M][N]

Контрпример: [math]S =[/math] [math]'CA'[/math] и [math]T =[/math] [math]'ABC'[/math]. Расстояние Дамерау-Левенштейна между строками равно [math]2\ (CA \rightarrow AC \rightarrow ABC)[/math], однако функция приведённая выше возвратит [math]3[/math]. Дело в том, что использование этого упрощённого алгоритма накладывает ограничение: любая подстрока может быть редактирована не более одного раза. Поэтому переход [math]AC \rightarrow ABC[/math] невозможен, и последовательность действий такая: [math](CA \rightarrow A \rightarrow AB \rightarrow ABC)[/math].

Упрощенный алгоритм Дамерау-Левенштейна не является метрикой, так как не выполняется правило треугольника: [math]\mathtt{DLD}('CA',\ 'AC') + \mathtt{DLD}('AC',\ 'ABC') \ngeqslant \mathtt{DLD}('CA',\ 'ABC')[/math].

Условие многих практических задач не предполагает многократного редактирования подстрок, поэтому часто достаточно упрощённого алгоритма. Ниже представлен более сложный алгоритм, который корректно решает задачу поиска расстояния Дамерау-Левенштейна.

Корректный алгоритм

В основу алгоритма положена идея динамического программирования по префиксу. Будем хранить матрицу [math]D[0..M + 1][0..N + 1][/math], где [math]D[i + 1][j + 1][/math] — расстояние Дамерау-Левенштейна между префиксами строк [math]S[/math] и [math]T[/math], длины префиксов — [math]i[/math] и [math]j[/math] соответственно.

Для учёта транспозиции потребуется хранение следующей информации. Инвариант:

[math]\mathtt{lastPosition}[x][/math] — индекс последнего вхождения [math]x[/math] в [math]S[/math]

[math]\mathtt{last}[/math] — на [math]i[/math]-й итерации внешнего цикла индекс последнего символа [math]T: T[\mathtt{last}] = S[i][/math]

Тогда если на очередной итерации внутреннего цикла положить: [math]i' = \mathtt{lastPosition}[T[j]],\ j' = \mathtt{last}[/math], то

[math]D(i, j) = \min{(A, D(i', j') + (i - i' - 1) \cdot deleteCost + transposeCost + (j - j' - 1) \cdot insertCost)}[/math][math](*)[/math]

, где

[math] A = \left\{\begin{array}{llcl} 0&;\ i = 0,\ j = 0\\ i&;\ j = 0,\ i \gt 0\\ j&;\ i = 0,\ j \gt 0\\ D(i - 1, j - 1)&;\ S[i] = T[j]\\ \min{(}\\ \begin{array}{llcl} &D(i, j - 1) + insertCost\\ &D(i - 1, j) + deleteCost&&\\ &D(i - 1, j - 1) + replaceCost\\ \end{array}&;\ j \gt 0,\ i \gt 0,\ S[i] \ne T[j]\\ ) \end{array}\right. [/math]

Доказательства требует лишь формула [math](*)[/math], смысл которой — сравнение стоимости перехода без использования транспозиции [math](A)[/math] со стоимостью перехода, включающего в число операций транспозицию; остальные формулы обосновываются так же, как и в доказательстве алгоритма Вагнера-Фишера. Но действительно, при редактировании подпоследовательности несколько раз всегда существует оптимальная последовательность операций одного из двух видов:

• Переставить местами соседние символы, затем вставить некоторое количество символов между ними;
• Удалить некоторое количество символов, а затем переставить местами символы, ставшие соседними.

Тогда если символ [math]S[i][/math] встречался в [math]T[1]..T[j][/math] на позиции [math]j'[/math], а символ [math]T[j][/math] встречался в [math]S[1]..S[i][/math] на позиции [math]i'[/math]; то [math]T[1]..T[j][/math] может быть получена из [math]S[1]..S[i][/math] удалением символов [math]S[i' + 1]..S[i - 1][/math], транспозицией ставших соседними [math]S[i'][/math] и [math]S[i][/math] и вставкой символов [math]T[j' + 1]..T[j - 1][/math]. Суммарно на это будет затрачено [math]D(i', j') + (i - i' - 1) \cdot deleteCost + transposeCost + (j - j' - 1) \cdot insertCost[/math] операций, что описано в [math](*)[/math]. Поэтому мы выбирали оптимальную последовательность операций, рассмотрев случай с транспозицией и без неё.

Для корректного алгоритма Дамерау-Левенштейна правило треугольника выполняется: [math]\mathtt{DLD}(S,\ V) + \mathtt{DLD}(V,\ T) \geqslant \mathtt{DLD}(S,\ T)[/math]. Предположим обратное: [math]\mathtt{DLD}(S,\ V) + \mathtt{DLD}(V,\ T) \lt \mathtt{DLD}(S,\ T)[/math], тогда приходим к противоречию, так как [math]\mathtt{DLD}(S,\ T)[/math] является минимальным ответом по определению. При [math]insertCost = deleteCost[/math] расстояние Дамерау-Левенштейна будет являться метрикой.

Сложность алгоритма: [math]O\left (M \cdot N \cdot \max{(M, N)} \right )[/math]. Затраты памяти: [math]O\left (M \cdot N \right)[/math]. Однако скорость работы алгоритма может быть улучшена до [math]O\left (M \cdot N \right)[/math].

Псевдокод алгоритма:

int DamerauLevenshteinDistance(S: char[1..M], T: char[1..N]; deleteCost, insertCost, replaceCost, transposeCost: int):
    // Обработка крайних случаев
    if (S == "")
        if (T == "")
            return 0
        else
            return N
    else if (T == "")
        return M
    D = int[0..M][0..N]                 // Динамика
    INF = M + N                         // Большая константа
    
    // База индукции
    D[0][0] = INF
    for i = 0 to M
        D[i + 1][1] = i
        D[i + 1][0] = INF
    for j = 0 to N
        D[1][j + 1] = j
        D[0][j + 1] = INF
    
    i', j', last: int
    lastPosition: int[0..количество различных символов в S и T]
    //для каждого элемента C алфавита задано значение lastPosition[C] 
    
    foreach (char Letter in (S + T))
        lastPosition[Letter] = 0
    
    for i = 1 to M
        last = 0
        for j = 1 to N
            i' = lastPosition[T[j]]
            j' = last
            if S[i] == T[j]
                D[i + 1][j + 1] = D[i][j]
                last = j
            else
                D[i + 1][j + 1] = min(D[i][j] + replaceCost, D[i + 1][j] + insertCost, D[i][j + 1] + deleteCost)
            D[i + 1][j + 1] = min(D[i + 1][j + 1], D[i'][j'] + (i - i' - 1) [math]\cdot[/math] deleteCost + transposeCost + (j - j' - 1) [math]\cdot[/math] insertCost)
        lastPosition[S[i]] = i
     
    return D[M + 1][N + 1]

См. также

• Задача о наибольшей общей подпоследовательности
• Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
• Динамическое программирование по профилю

Источники информации

• Wikipedia — Damerau-Levenshtein distance
• Википедия — Расстояние Дамерау-Левенштейна
• Хабрахабр — Нечёткий поиск в тексте и словаре
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 3-е изд. — М.: «Вильямс», 2013. — с. 440. — ISBN 978-5-8459-1794-2