Сложность пространства для вычисления оптимального выравнивания строки для расстояния редактирования Левенштейна

12

Если нам даны две строки размером и , стандартное вычисление расстояния редактирования Левенштейна выполняется с помощью динамического алгоритма с временной сложностью и пространственной сложностью . (Некоторые улучшения могут быть сделаны в зависимости от расстояния редактирования , но мы не предполагаем, что особенно мало.) Если вас интересует только значение расстояния редактирования (т. Е. Минимальное количество правок), Хорошо известное улучшение обычного алгоритма (где вы сохраняете только предыдущую и текущую строку таблицы выравнивания) уменьшает сложность пространства до .n 2 O ( n 1 n 2 ) On1n2O(n1n2)O(n1n2)ddO(max(n1,n2))

Однако, если вы хотите получить фактические правки оптимального сценария редактирования, возможно ли добиться большего успеха, чем использование памяти O(n1n2) , возможно, за счет времени выполнения?

a3nm
источник

Ответы:

15

Нет необходимости в компромиссе, который предлагает Ювал. Вся оптимальная последовательность редактирования может быть вычислена во времени и в пространстве , используя смесь динамического программирования и «разделяй и властвуй», впервые описанную Дэном Хиршбергом. ( Алгоритм линейного пространства для вычисления максимальных общих подпоследовательностей. Commun. ACM 18 (6): 341–343, 1975.)O ( n + m )O(nm)O(n+m)

Интуитивно понятно, что идея Хиршберга состоит в том, чтобы вычислить одну операцию редактирования в середине оптимальной последовательности редактирования, а затем рекурсивно вычислить две половины последовательности. Если мы рассматриваем оптимальную последовательность редактирования как путь от одного угла таблицы памятки к другому, нам понадобится измененное повторение, чтобы записать, где этот путь пересекает среднюю строку таблицы. Одно повторение, которое работает, является следующим:

Half(i,j)={if i<m/2jif i=m/2Half(i1,j)if i>m/2 and Edit(i,j)=Edit(i1,j)+1Half(i,j1)if i>m/2 and Edit(i,j)=Edit(i,j1)+1Half(i1,j1)otherwise

Значения могут быть вычислены одновременно с таблицей расстояний редактирования с использованием времени . Поскольку каждая строка таблицы памятки зависит только от строки над ней, для вычисления как и требуется только место.E d i t ( i , j ) O ( m n ) E d i t ( m , n )Half(i,j)Edit(i,j)O(mn)Edit(m,n)O ( m + n )Half(m,n)O(m+n)

введите описание изображения здесь

Наконец, оптимальная последовательность редактирования, преобразующая входные строки в состоит из оптимальных последовательностей, преобразующих в последующей оптимальной последовательностью, преобразующей в . Если мы вычисляем эти две подпоследовательности рекурсивно, общее время выполнения подчиняется следующему повторению: Нетрудно доказать, чтоA[1..m]B[1..n]A[1..m/2]B[1..Half(m,n)]A[m/2+1..m]B[Half(m,n)+1..n]

T(m,n)={O(n)if m1O(m)if n1O(mn)+maxh(T(m/2,h)+T(m/2,nh))otherwise
O ( m + n )T(m,n)=O(mn), Точно так же, поскольку нам требуется только пространство для одного прохода динамического программирования за один раз, общая граница пространства по-прежнему равна . (Пространство для стека рекурсии незначительно.)O(m+n)
Jeffε
источник
5
Потому что я пропустил это, когда Дэн спросил меня на моем квалификационном экзамене, вот почему.
Джефф
я помню, как выполнял это (руководствуясь) упражнением и думал, что это было довольно здорово
Сашо Николов
3

Алгоритм, который вы описываете, который работает в пространстве фактически восстанавливает окончательное редактирование и состояние непосредственно перед финальным редактированием. Таким образом, если вы запустите этот алгоритм раз, вы сможете восстановить всю последовательность редактирования за счет увеличения времени выполнения. В общем, существует компромисс между временем и пространством, который контролируется количеством строк, которые вы сохраняете в данный момент. Двумя крайними точками этого компромисса являются пространство и пространство , и между ними произведение времени и пространства является постоянным (вплоть до больших O).O ( n 1 + n 2 ) O ( n 1 n 2 ) O ( n 1 + n 2 )O(n1+n2)O(n1+n2)O(n1n2)O(n1+n2)

Юваль Фильмус
источник