Editar distancia en espacio sublineal

19

¿Cuál es la complejidad más conocida para calcular la distancia de edición exacta entre dos cadenas de la misma longitud utilizando un espacio de trabajo que es sublineal en el tamaño de la entrada? Supongo que la entrada se almacena en algún formato de solo lectura. ¿Es este un problema previamente estudiado?

Para hacer la pregunta un poco más específica, ¿qué tal espacio dondenes la longitud de cada cadena de entrada.Θ(n)n

Editar. Siguiendo la respuesta de David Eppstein, parece que una buena pregunta es simplemente si la distancia de edición se puede encontrar en tiempo polinómico y espacio. Cualquier límite inferior también sería interesante.Θ(n)

ds.algorithms edit-distance space-time-tradeoff felix
fuente
1
En cuanto a la edición: creo que malinterpretas algo. La respuesta de David Eppstein muestra que el problema se puede resolver en NL, por lo tanto también en P.
Emil Jeřábek apoya a Monica el
1
... En realidad, el algoritmo original de Wagner-Fischer ya lo hace.
Emil Jeřábek apoya a Monica el
3
Supongo que la versión editada tenía la intención de pedir algoritmos que fueran tanto espacio sublineal como tiempo polinómico.
David Eppstein
@DavidEppstein Sí, exactamente. He editado nuevamente para aclaraciones.
Felix
Por cierto, suponiendo que el modelo de precio estándar de 1 por midmatch / delete / insert, luego, si la distancia de edición es l, entonces la ruta que realiza la ruta más corta en la matriz de distancia de edición va a una distancia como máximo l desde la diagonal principal, y luego la distancia de edición se calculará utilizando el espacio O (l). Por lo tanto, con el espacio sqrt (n), puede calcular la distancia de edición si es pequeña (es decir, más pequeña que sqrt (n)). Es solo si es grande que esto parece difícil. Por supuesto, en este caso, podría decirse que debería importarle menos.
Sariel Har-Peled

Respuestas:

16

O(log2⁡n)nO(log⁡n)

Hay algunos límites inferiores de espacio para la distancia de edición en http://arxiv.org/abs/1106.4412, pero no creo que coincidan con su versión del problema.

David Eppstein
fuente
¿Cómo verificas que la ruta que has encontrado es óptima?
Lembik
1
Búsqueda binaria o búsqueda secuencial de la distancia más pequeña para la que se puede encontrar una ruta, es decir, nada más allá de la equivalencia estándar de decisión y problemas de búsqueda. Esto no afecta las formas del espacio o el límite del tiempo.
David Eppstein
@David Creo que tienes razón, así que he eliminado mi respuesta.
SamiD
2
¿Es incluso computable en el espacio de registro?
Lembik