Complexidade de espaço para calcular o alinhamento ideal de cordas para a distância de edição de Levenshtein

12

Se recebermos duas cadeias de tamanho n1 e n2 , o cálculo padrão da distância de edição de Levenshtein é por um algoritmo dinâmico com complexidade de tempo O(n1n2) e complexidade de espaço O(n1n2) . (Algumas melhorias podem ser feitas em função da distância de edição d , mas não assumimos que dO(max(n1,n2))

No entanto, se você deseja obter as edições reais de um script de edição ideal, é possível fazer melhor que uso de memória , possivelmente à custa do tempo de execução?O(n1n2)

a3nm
fonte

Respostas:

15

Não há necessidade da troca que Yuval sugere. Toda a sequência ótima de edição pode ser calculada no tempo e no espaço , usando uma mistura de programação dinâmica e divisão e conquista descrita pela primeira vez por Dan Hirschberg. ( Um algoritmo de espaço linear para calcular as subsequências comuns máximas. Commun. ACM 18 (6): 341–343, 1975.)O ( n + m )O(nm)O(n+m)

Intuitivamente, a ideia de Hirschberg é calcular uma única operação de edição no meio da sequência de edição ideal e, em seguida, calcular recursivamente as duas metades da sequência. Se pensarmos na sequência de edição ideal como um caminho de um canto da tabela de memorização para o outro, precisamos de uma recorrência modificada para registrar onde esse caminho cruza a linha do meio da tabela. Uma recorrência que funciona é a seguinte:

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

Os valores de podem ser calculados ao mesmo tempo que a tabela de distâncias de edição , usando o tempo . Como cada linha da tabela de memorização depende apenas da linha acima, a computação de e requer apenas espaço .Half(i,j)Edit(i,j)O(mn)Edit(m,n)Half(m,n)O(m+n)

insira a descrição da imagem aqui

Finalmente, a sequência de edição ideal que transforma as seqüências de entrada em consiste nas seqüências ideais que transformam em seguido pela seqüência ótima que transforma em . Se calcularmos essas duas subsequências recursivamente, o tempo de execução geral obedecerá à seguinte recorrência: Não é difícil provar queA[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). Da mesma forma, como exigimos apenas espaço para uma passagem de programação dinâmica por vez, o espaço total vinculado ainda é . (O espaço para a pilha de recursão é insignificante.)O(m+n)
Jeffε
fonte
5
Porque eu perdi isso quando Dan me pediu no exame de qualificação, é por isso.
Jeffε
Lembro-me de ter isso como um exercício (guiada) e pensar que era muito legal
Sasho Nikolov
3

O algoritmo que você descreve que é executado no espaço na verdade recupera a edição final e o estado imediatamente antes da edição final. Portanto, se você executar esse algoritmo vezes, poderá recuperar toda a sequência de edição, à custa de aumentar o tempo de execução. Em geral, há uma troca de espaço no tempo que é controlada pelo número de linhas que você retém no momento. Os dois pontos extremos dessa troca são o espaço e o espaço e, entre eles, o produto do tempo e do espaço é constante (até o grande 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)

Yuval Filmus
fonte