Modifier la distance dans l'espace sublinéaire

19

Quelle est la complexité la plus connue pour calculer la distance d'édition exacte entre deux chaînes de même longueur en utilisant un espace de travail qui est sublinéaire dans la taille de l'entrée? Je suppose que l'entrée est stockée dans un format en lecture seule. Est-ce un problème déjà étudié?

Pour rendre la question un peu plus précise, que diriez-vous de l' espace où est la longueur de chaque chaîne d'entrée.Θ(n)n

Éditer. D'après la réponse de David Eppstein, il semble qu'une bonne question soit simplement de savoir si la distance d'édition peut être trouvée dans le temps polynomial et l' espace . Toute limite inférieure serait également intéressante.Θ(n)

ds.algorithms edit-distance space-time-tradeoff Felix
la source
1
Concernant le montage: je pense que vous vous méprenez sur quelque chose. La réponse de David Eppstein montre que le problème est résoluble en NL, donc aussi en P.
Emil Jeřábek soutient Monica
1
... En fait, l'algorithme Wagner – Fischer original le fait déjà.
Emil Jeřábek soutient Monica
3
Je suppose que la version éditée visait à demander des algorithmes qui étaient à la fois l'espace sublinéaire et le temps polynomial.
David Eppstein
@DavidEppstein Oui, exactement. J'ai édité à nouveau pour des éclaircissements.
felix
BTW, en supposant que le modèle de tarification standard est de 1 par mi-match / suppression / insertion, puis si la distance de modification est l, le chemin réalisant le chemin le plus court dans la matrice de distance de modification va au plus l à partir de la diagonale principale, puis la distance d'édition soit calculée en utilisant l'espace O (l). Ainsi, avec l'espace sqrt (n), vous pouvez calculer la distance d'édition si elle est petite (c'est-à-dire plus petite que sqrt (n)). Ce n'est que s'il est grand que cela semble difficile. Bien sûr, dans ce cas, sans doute, vous devriez vous en soucier moins.
Sariel Har-Peled

Réponses:

16

O(Journal2⁡n)nO(Journal⁡n)

Il existe des limites inférieures d'espace pour la distance de modification dans http://arxiv.org/abs/1106.4412 mais je ne pense pas qu'elles correspondent à votre version du problème.

David Eppstein
la source
Comment vérifiez-vous que le chemin que vous avez trouvé est optimal?
Lembik
1
Recherche binaire ou recherche séquentielle de la plus petite distance pour laquelle un chemin peut être trouvé, c'est-à-dire rien au-delà de l'équivalence standard des problèmes de décision et de recherche. Cela n'affecte pas les formes de l'espace ou du temps.
David Eppstein du
@David Je pense que vous avez raison, j'ai donc supprimé ma réponse.
SamiD
2
Est-il même calculable dans l'espace journal?
Lembik