8.4. Задача «Расстояние редактирования»

Есть множество вариантов, как применить задачу «Расстояние редактирования». Она подойдёт для обработки текстов на естественном языке, проверки правописания и других направлений. К примеру, биологи зачастую вычисляют редакционное расстояние, когда ищут мутации, вызывающие болезни.

Редакционное расстояние между двумя строками определяется как минимальное число односимвольных вставок, удалений и замен, необходимых для преобразования одной строки в другую.

• Входные данные: Две строки, состоящие из строчных букв латинского алфавита.
• Выходные данные: Редакционное расстояние между строками.
• Ограничения: Длина обеих строк не меньше и не больше .

Пример 1

Ввод	Вывод
short ports	3

• Вторую строку можно получить из первой, удалив s, заменив h на p и вставив s. Это можно компактно продемонстрировать следующим выравниванием.

Пример 2

Ввод	Вывод
editing distance	5

• Удалить e, вставить s после i, заменить i на a, заменить g на c, вставить e в конце.

Пример 3

Ввод	Вывод
ab ab	0

• Совет: будьте осторожны с рекурсией.

Рассмотрим решение задачи. Выравнивание двух строк в двухрядной матрице осуществляется таким образом, чтобы первый (второй) ряд содержал упорядоченные символы первой (второй) строки, которые перемежаются пробелами («»).
В колонке не может быть два пробела одновременно в обеих строках.

✒️ Упражнение:
Вычислите количество разных пар выравненных строк длиной и .

Мы классифицируем колонки выравнивания следующим образом (первый символ из верхней строки, второй — из нижней):

— колонка с символом и пробелом

— это удаление;

— колонка с пробелом и символом

— вставка;

— колонка с двумя одинаковыми символами

— совпадение;

— колонка с двумя разными символами

— это несоответствие.

Мы ищем выравнивание, при котором минимизируется общее количество несоответствий, удалений и вставок.

Выравнивание считается оптимальным по сравнению со всеми другими возможными вариантами, если оно содержит минимум несоответствий, удалений и вставок.
Стоит обратить внимание, что может быть несколько различных оптимальных выравниваний.

✒️ Упражнение:
Докажите, что задача на редакционное расстояние может быть сведена к поиску оптимального выравнивания двух строк.

В примере выше последняя колонка — это вставка. Отбросив эту колонку, мы получаем оптимальное выравнивание первой строки и префикса второй.

Рассмотрим идею: рассчитать редакционное расстояние между каждой парой префиксов двух строк. Это более общая постановка задачи, но важно отметить, что, решив ее, мы найдем ответ и на интересующий нас вопрос.

Имея строки и , мы рассмотрим их префиксы и длиной и и обозначим их редакционное расстояние .

Так как последняя колонка оптимального выравнивания и — это или вставка, или удаление, или несоответствие, или совпадение, имеем,

Базовый случай для этого рекуррентного соотношения — и :

Это можно выразить более кратко: если или , тогда

Псевдокод ниже делает из этого рекуррентного соотношения рекурсивный алгоритм и использует мемоизацию для избежания перевычислений.

table = associative array
    
EditDistance(A,B,i,j):
    if table[i,j] is not yet computed:
        if i=0 or j=0:
            table[i,j] = max(i,j)
        else:
            insertion = EditDistance(A,B,i,j−1)+1
            deletion = EditDistance(A,B,i−1,j)+1
            match = EditDistance(A,B,i−1,j−1)
            mismatch = EditDistance(A,B,i−1,j−1)+1
            if A[i]=B[j]:
                table[i,j] = min(insertion,deletion,match)
            else:
                table[i,j] = min(insertion,deletion,mismatch)
    return table[i,j]

Время выполнения этого алгоритма составляет , так как выполняется не больше рекурсивных вызовов, которые добавляют значения в table.

Рекурсивный алгоритм вычисляет для всех и . Из рекурсивного алгоритма можно сделать итерационный, который будет сохранять решения всех подзадач в двумерной таблице. Таблица заполняется по рядам проходами. Это гарантирует, что когда мы вычислим значение клетки , значения клеток , и будут уже готовы.

EditDistance(A[1…n],B[1…m]):
    table = 2d array of size (n+1) * (m+1)
    table[0][j] = j for all i,j
    for i from 1 to n:
        for j from 1 to m:
            insertion = table[i][j−1]+1
            deletion = table[i−1][j]+1
            match = table[i−1][j−1]
            mismatch = table[i−1][j−1]+1
            if A[i]=B[j]:
                table[i][j] = min(insertion,deletion,match)
            else:
                table[i][j] = min(insertion,deletion,mismatch)
    return table[n][m]

Итоговая таблица для нашего примера изображена на рисунке ниже. Значение каждой клетки вычисляется, исходя из значений соседних клеток сверху, слева и слева-сверху. У каждой клетки входящие стрелки указывают на один или несколько случаев (вставка, удаление, несоответствие, или совпадение), которые приводят к значению этой клетки.

Таблица соответствует ориентированному ациклическому графу, в котором все рёбра, за исключением красных, имеют длину . А красные ребра соответствуют совпадающим символам и имеют длину . Алгоритм находит на графе самый короткий путь от узла слева сверху до узла справа снизу.

Время выполнения алгоритма составляет . Ему требуется ячеек памяти для хранения двумерного массива table. Расход места может быть снижен до (и даже до ), если мы обратим внимание на то, что при заполнении текущего ряда таблицы нам нужны только клетки из текущего и предыдущего. Таким образом, вместо хранения всей таблицы достаточно сохранить текущий и предыдущие ряды.

💡 Остановитесь и подумайте:
Вы рассчитали редакционное расстояние между editing и distance. Но как найти пять операций для того, чтобы преобразовать editing в distance?

Отметим, что любой путь от до на рисунке образовывает оптимальное выравнивание строк и .

✒️ Упражнение:
Путь, изображённый на рисунке ниже, соответствует оптимальному выравниванию editing и distance. Сколько в этом выравнивании вставок, удалений, совпадений и несоответствий? Постройте оптимальное выравнивание, соответствующее этому пути.

Оптимальное выравнивание можно обнаружить с помощью перехода по стрелкам в обратную сторону от нижнего правого угла вдоль любого пути, приводящего к верхнему левому углу.