Editar distância no espaço sublinear

19

Qual é a complexidade mais conhecida para calcular a distância exata de edição entre duas strings do mesmo comprimento usando espaço de trabalho sublinear no tamanho da entrada? Presumo que a entrada seja armazenada em algum formato somente leitura. Esse é um problema estudado anteriormente?

Para tornar a pergunta um pouco mais específica, que tal o espaço que é o comprimento de cada sequência de entrada.nΘ(n)n

Editar. Seguindo a resposta de David Eppstein, parece uma boa pergunta é simplesmente se a distância de edição pode ser encontrada no tempo polinomial e no espaço . Quaisquer limites inferiores também seriam interessantes.Θ(n)

ds.algorithms edit-distance space-time-tradeoff felix
fonte
11
Em relação à edição: acho que você não entendeu nada. A resposta de David Eppstein mostra o problema é solúvel em NL, portanto, também no P.
Emil Jerabek suporta Monica
11
... Na verdade, o algoritmo original de Wagner-Fischer já faz isso.
Emil Jeřábek apoia Monica
3
Suponho que a versão editada pretenda solicitar algoritmos que sejam espaço sublinear e tempo polinomial.
David Eppstein
@DavidEppstein Sim, exatamente. Eu editei novamente para esclarecimentos.
Felix
BTW, assumindo o modelo de precificação padrão de 1 por meia-partida / exclusão / inserção, se a distância de edição for l, o caminho que realiza o caminho mais curto na matriz de distância de edição estará se distanciando no máximo l da diagonal principal e, em seguida, a distância de edição seja calculada usando espaço O (l). Assim, com o espaço sqrt (n), você pode calcular a distância de edição se ela for pequena (ou seja, menor que sqrt (n)). Somente se for grande é que isso parece difícil. É claro que, nesse caso, sem dúvida, você deveria se importar menos.
Sariel Har-Peled

Respostas:

16

Apenas para fazer as coisas funcionarem, em vez de tentar resolver esse problema: existe um algoritmo não determinístico óbvio que usa logaritmicamente muitos bits de espaço (procure um único caminho através da matriz de programação dinâmica), de modo que pelo teorema de Savitch existe um algoritmo determinístico com espaço . Seu tempo deve ter a forma , quase polinomial e não exponencial.n O ( log n )O(log2⁡n)nO(log⁡n)

Existem limites inferiores de espaço para a distância de edição em http://arxiv.org/abs/1106.4412, mas não acho que eles correspondam à sua versão do problema.

David Eppstein
fonte
Como você verifica se o caminho encontrado é ideal?
Lembik
11
Pesquisa binária ou pesquisa seqüencial para a menor distância para a qual um caminho pode ser encontrado, ou seja, nada além da equivalência padrão dos problemas de decisão e pesquisa. Isso não afeta as formas do espaço ou do tempo vinculado.
David Eppstein
@ David Acho que você está correto, então eu apaguei minha resposta.
SamiD 24/08/14
2
É computável no espaço do log?
Lembik