Modifier la distance avec les opérations de déplacement

13

Motivation: Un co-auteur édite un manuscrit et j'aimerais voir un résumé clair des éditions. Toutes les « diff » -comme outils ont tendance à être inutile si vous êtes à la fois du texte déplacerez (par exemple, la réorganisation de la structure) et faire des modifications locales. Est-il vraiment si difficile de bien faire les choses?


Définitions: Je voudrais trouver la distance de montage minimale, où les opérations autorisées sont:

  • opérations "bon marché": ajouter / modifier / supprimer un seul caractère (les opérations Levenshtein habituelles),

  • "cher": opérations: déplacer une sous-chaîne vers un nouvel emplacement ( abcdacbd pour toutes les chaînes ,bab , c , d ).

Étant donné deux chaînes x et y et des entiers k et K , je voudrais résoudre le problème suivant:

  • pouvez-vous transformer x en y utilisant au plus k opérations bon marché et au plus K opérations coûteuses?

Des questions:

  1. Ce problème a-t-il un nom? (Cela ressemble à une question très standard dans le contexte de l'alignement de séquence.)

  2. Est-il difficile?

  3. S'il est difficile, est-il traitable à paramètres fixes avec comme paramètre?K

  4. Existe-t-il des algorithmes d'approximation efficaces? (Par exemple, trouvez une solution avec au plus bon marché et 2 K coûteuses si une solution avec k opérations bon marché et K coûteuses existe.)2k2KkK

J'ai essayé de jeter un coup d'œil aux métriques de chaîne répertoriées dans Wikipedia , mais aucune d'entre elles n'avait l'air correcte.

Jukka Suomela
la source
3
Pour , le problème est le tri par transpositions. Voir, par exemple, web.cs.dal.ca/~whidden/HThesis07.pdf Je n'ai pas rencontré votre problème, mais il semble très bien motivé. k=0
Serge Gaspers
4
La dureté NP du problème du tri par transpositions a été prouvée en 2010, voir Tri par transpositions est difficile .
Marzio De Biasi
3
Les transpositions sont difficiles, mais les insertions et les suppressions ne le sont pas. Si vous autorisez une opération coûteuse à supprimer la sous-chaîne arbitraire ou l'insertion d'une sous-chaîne de l'autre chaîne, le problème devrait devenir assez facile. La distance résultante ne serait cependant pas symétrique.
Jouni Sirén
Je suis plus curieux de la tractabilité à paramètres fixes. Y a-t-il une nouvelle découverte?
Yixin Cao

Réponses:

4

Le problème devient plus facile, si l'on considère les suppressions longues et la copie de sous-chaînes au lieu de transpositions. Supposons que nous utilisons l'algorithme de programmation dynamique standard pour éditer le calcul de distance, et qu'une opération coûteuse de longueur augmente la distance de a k + b , pour certaines constantes a , b 0 . Ces constantes peuvent être différentes pour les suppressions longues et la copie de sous-chaîne.kak+ba,b0

Une longue suppression est la suppression d'une sous-chaîne arbitraire de . Les soutenir est facile, si nous les décomposons en deux types d'opérations simples: supprimer le premier caractère (coût a + b ) et étendre la suppression d'un caractère (coût a ). En plus du tableau standard A , où A [ i , j ] est la distance d'édition entre les préfixes x [ 1 i ] et y [ 1 j ] , nous utilisons un autre tableau A dxa+baAA[i,j]x[1i]y[1j]Adpour stocker la distance d'édition, lorsque la dernière opération utilisée était une longue suppression. Avec ce tableau, il suffit de regarder , A [ i - 1 , j - 1 ] , A [ i , j - 1 ] et A d [ i - 1 , j ] lors du calcul A [ i , j ] et A dA[i1,j]A[i1,j1]A[i,j1]Ad[i1,j]A[i,j] ) . , nous permettant de le faire en O ( 1Ad[i,j]O(1)

La copie de sous-chaîne signifie l'insertion d'une sous-chaîne arbitraire de dans la chaîne éditée. Comme pour les suppressions longues, nous décomposons l'opération en deux opérations simples: l'insertion du premier caractère et l'extension de l'insertion d'un caractère. Nous utilisons également le tableau A sXUNEs pour stocker la distance d'édition entre les préfixes, à condition que la dernière opération utilisée soit la copie de la sous-chaîne.

Faire cela efficacement est plus compliqué qu'avec de longues suppressions, et je ne sais pas si nous pouvons arriver à temps amorti par cellule. Nous construisons un arbre de suffixe pour x , ce qui prend du temps O ( | x | ) , en supposant un alphabet de taille constante. Nous stockons un pointeur sur le nœud d'arbre de suffixe courant dans A s [ i , j - 1 ] , ce qui nous permet de vérifier en temps constant, si nous pouvons étendre l'insertion par le caractère y [ j ] . Si cela est vrai, nous pouvons calculerO(1)XO(|X|)UNEs[je,j-1]y[j] ] en temps constant.UNE[je,j]et UNEs[je,j]

Sinon, , où z est la sous-chaîne insérée qui a été utilisée pour calculer A s [ i , j - 1 ] , n'est pas une sous-chaîne de x . Nous utilisons l'arbre des suffixes pour trouver le suffixe le plus long z de z , pour lequel z y [ j ] est une sous-chaîne de x , dans O ( | z | - | z | )zy[j]zUNEs[je,j-1]Xzzzy[j]XO(|z|-|z|) . Pour calculer , nous devons maintenant regarder les cellules A [ i , j - | z | - 1 ] à A [ i , j - 1 ] . Trouver le suffixe z ' nécessite juste un temps O ( 1 ) amortipar cellule, mais le calcul de A s [ i , j ] avec une approche par force brute prend O ( | zUNEs[je,j]UNE[je,j-|z|-1]UNE[je,j-1]zO(1)UNEs[je,j] temps. Il existe probablement un moyen de le faire plus efficacement, mais je ne le trouve pas pour le moment.O(|z|)

Dans le pire des cas, l'algorithme prend temps, mais une meilleure analyse devrait être possible. La distance d'édition résultante avec de longues suppressions et la copie de sous-chaîne n'est pas symétrique, mais cela ne devrait pas être un problème. Après tout, il est généralement plus facile d'atteindre la chaîne vide à partir d'une chaîne non vide que l'inverse.O(min(|X||y|2,|X|2|y|))

Jouni Sirén
la source