Вычисление редакционного расстояния

Алгоритмы   5 Апрель 2014  Автор статьи:  

Пусть заданы две 0-индексированные строки s_1 и s_2 над некоторым алфавитом A, |s_1|=l_1, |s_2|=l_2. Над строкой s_1 разрешается производить любое количество следующих операций:
1) Удалить любой символ строки (при этом её длина уменьшается на единицу)
2) Заменить любой символ строки произвольным символом алфавита A (длина строки не меняется)
3) Вставить в произвольную позицию строки i (0 \le i \le l_1) произвольный символ алфавита A (длина строки увеличивается на единицу).

Будем считать, что каждая из этих операций обладает определенной стоимостью. Ставится задача нахождения последовательности операций минимальной суммарной стоимости, в результате выполнения которой строка s_1 преобразуется в строку s_2. Для простоты мы будем рассматривать случай, когда все операции имеют одинаковую стоимость, равную единице; в таком случае стоимость преобразования строки s_1 в строку s_2 равна просто количеству совершенных операций. Искомое минимальное количество операций называется редакционным расстоянием между строками s_1 и s_2 (или, по-другому, расстоянием Левенштейна). Саму последовательность осуществляемых операций называют редакционным предписанием. Для нахождения редакционного расстояния между двумя строками и соответствующего редакционного предписания используется алгоритм Вагнера-Фишера, основанный на идеях динамического программирования.

Пусть d_{i,j} – это редакционное расстояние между подстроками s_1[i...l_1- 1] и s_2[j...l_2- 1], 0 \le i \le l_1, 0 \le j \le l_2 (случаи, когда индекс равен длине соответствующей строки, означают, что рассматривается пустой суффикс этой строки). Базой динамического программирования является состояние (l_1,l_2), для которого значение d равно нулю (как редакционное расстояние между пустыми строками). Переходы от данной подзадачи к меньшим основаны на рассмотрении следующих случаев:
1) Если i < l_1 и j < l_2, то можно заменить символ s_1[i] символомs_2[j] и исключить эти два символа из рассмотрения (редакционное расстояние будет равно d_{i + 1,j + 1} + 1).
2) Если i < l_1, j < l_2 и при этом дополнительно s_1[i] = s_2[j], то выполнять замену необходимости нет (редакционное расстояние будет равно d_{i + 1,j + 1}).
3) Если i < l_1, то можно удалить символ s_1[i] (редакционное расстояние будет равно d_{i + 1,j} + 1).
4) Если j < l_2, то можно добавить в начало строки s_1[i...l_1- 1] символ s_2[j] и исключить эти символы из рассмотрения (редакционное расстояние будет равно d_{i,j + 1} + 1).
Из этих случаев нужно выбрать тот, который позволяет минимизировать получаемое редакционное расстояние.

Искомое редакционное расстояние между строками s_1 и s_2 будет содержаться в d_{0,0}. Для того чтобы восстановить само редакционное предписание, можно для каждого состояния (i,j) дополнительно сохранять величину p_{i,j} – код операции (вставка, удаление, замена), которая позволяет минимизировать d_{i,j}, и после построения этих массивов «обратным ходом» найти искомую оптимальную последовательность.

Асимптотическая сложность алгоритма O({l_1}{l_2}). Объем потребляемой памяти тоже пропорционален l_1 \cdot l_2, однако при отсутствии необходимости восстановления оптимального редакционного предписания его можно сократить до O({l_1}) (достаточно использовать итерационное вычисление d_{i,j}, а не рекурсию с запоминанием, и всегда хранить только текущую и следующую строки таблицы).

Реализация алгоритма на языке C++ приведена здесь.

Научиться программировать

  • на Delphi

  • на Java

  • на C++