Есть множество вариантов, как применить задачу «Расстояние редактирования». Она подойдёт для обработки текстов на естественном языке, проверки правописания и других направлений. К примеру, биологи зачастую вычисляют редакционное расстояние, когда ищут мутации, вызывающие болезни.
Редакционное расстояние между двумя строками определяется как минимальное число односимвольных вставок, удалений и замен, необходимых для преобразования одной строки в другую.
- Входные данные: Две строки, состоящие из строчных букв латинского алфавита.
- Выходные данные: Редакционное расстояние между строками.
- Ограничения: Длина обеих строк не меньше $1$ и не больше $100$.
Пример 1
Ввод | Вывод |
---|---|
short ports | 3 |
- Вторую строку можно получить из первой, удалив s, заменив h на p и вставив s. Это можно компактно продемонстрировать следующим выравниванием.
Пример 2
Ввод | Вывод |
---|---|
editing distance | 5 |
- Удалить e, вставить s после i, заменить i на a, заменить g на c, вставить e в конце.
Пример 3
Ввод | Вывод |
---|---|
ab ab | 0 |
- Совет: будьте осторожны с рекурсией.
Рассмотрим решение задачи. Выравнивание двух строк в двухрядной матрице осуществляется таким образом, чтобы первый (второй) ряд содержал упорядоченные символы первой (второй) строки, которые перемежаются пробелами («$-$»). В колонке не может быть два пробела одновременно в обеих строках.
✒️ Упражнение:
Вычислите количество разных пар выравненных строк длиной $n$ и $m$.
Мы классифицируем колонки выравнивания следующим образом (первый символ из верхней строки, второй — из нижней):
— колонка с символом и пробелом
— это удаление;
— колонка с пробелом и символом
— вставка;
— колонка с двумя одинаковыми символами
— совпадение;
— колонка с двумя разными символами
— это несоответствие.
Мы ищем выравнивание, при котором минимизируется общее количество несоответствий, удалений и вставок.
Выравнивание считается оптимальным по сравнению со всеми другими возможными вариантами, если оно содержит минимум несоответствий, удалений и вставок. Стоит обратить внимание, что может быть несколько различных оптимальных выравниваний.
✒️ Упражнение:
Докажите, что задача на редакционное расстояние может быть сведена к поиску оптимального выравнивания двух строк.
В примере выше последняя колонка — это вставка. Отбросив эту колонку, мы получаем оптимальное выравнивание первой строки и префикса второй.
Рассмотрим идею: рассчитать редакционное расстояние между каждой парой префиксов двух строк. Это более общая постановка задачи, но важно отметить, что, решив ее, мы найдем ответ и на интересующий нас вопрос.
Имея строки $A[1\dotsc n]$ и $B[1 \dotsc m]$, мы рассмотрим их префиксы $A[1\dotsc i]$ и $B[1 \dotsc j]$ длиной $i$ и $j$ и обозначим их редакционное расстояние $EditDistance(i,j)$.
Так как последняя колонка оптимального выравнивания $A[1 \dotsc i]$ и $B[1 \dotsc j]$ — это или вставка, или удаление, или несоответствие, или совпадение, имеем,
Базовый случай для этого рекуррентного соотношения — $i=0$ и $j=0$: $$ EditDistance(0,j)=j \quad \text{и} \quad EditDistance(i,0)=i , . $$
Это можно выразить более кратко: если $i=0$ или $j=0$, тогда $$ EditDistance(i,j)=\max{i,j}. $$
Псевдокод ниже делает из этого рекуррентного соотношения рекурсивный алгоритм и использует мемоизацию для избежания перевычислений.
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]
Время выполнения этого алгоритма составляет $O(nm)$, так как выполняется не больше $nm$ рекурсивных вызовов, которые добавляют значения в table
.
Рекурсивный алгоритм вычисляет $EditDistance(i,j)$ для всех $0 \le i \le n$ и $0 \le j \le m$. Из рекурсивного алгоритма можно сделать итерационный, который будет сохранять решения всех подзадач в двумерной таблице. Таблица заполняется по рядам проходами. Это гарантирует, что когда мы вычислим значение клетки $(i,j)$, значения клеток $(i,j-1)$, $(i-1,j)$ и $(i-1,j-1)$ будут уже готовы.
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]
Итоговая таблица для нашего примера изображена на рисунке ниже. Значение каждой клетки вычисляется, исходя из значений соседних клеток сверху, слева и слева-сверху. У каждой клетки входящие стрелки указывают на один или несколько случаев (вставка, удаление, несоответствие, или совпадение), которые приводят к значению этой клетки.
Таблица соответствует ориентированному ациклическому графу, в котором все рёбра, за исключением красных, имеют длину $1$. А красные ребра соответствуют совпадающим символам и имеют длину $0$. Алгоритм находит на графе самый короткий путь от узла слева сверху до узла справа снизу.
Время выполнения алгоритма составляет $O(nm)$. Ему требуется $O(nm)$ ячеек памяти для хранения двумерного массива table
. Расход места может быть снижен до $O(m)$ (и даже до $O(\min{n,m})$), если мы обратим внимание на то, что при заполнении текущего ряда таблицы нам нужны только клетки из текущего и предыдущего. Таким образом, вместо хранения всей таблицы достаточно сохранить текущий и предыдущие ряды.
💡 Остановитесь и подумайте:
Вы рассчитали редакционное расстояние между editing и distance. Но как найти пять операций для того, чтобы преобразовать editing в distance?
Отметим, что любой путь от $(0, 0)$ до $(n,m)$ на рисунке образовывает оптимальное выравнивание строк $A$ и $B$.
✒️ Упражнение:
Путь, изображённый на рисунке ниже, соответствует оптимальному выравниванию editing и distance. Сколько в этом выравнивании вставок, удалений, совпадений и несоответствий? Постройте оптимальное выравнивание, соответствующее этому пути.
Оптимальное выравнивание можно обнаружить с помощью перехода по стрелкам в обратную сторону от нижнего правого угла вдоль любого пути, приводящего к верхнему левому углу.