Les arbres de suffixe peuvent-ils être utilisés pour trouver toutes les sous-chaînes courantes?

J'essaie d'utiliser des arbres de suffixes pour comparer les séquences de chaînes. J'ai trouvé des implémentations / théorie pour le problème de sous-chaîne commun le plus long en utilisant des arbres de suffixes. Cependant, ce que je recherche est une discussion du problème connexe - "toutes les sous-chaînes courantes". Plus précisément, j'ai un problème dans lequel je dois d'abord trouver la sous-chaîne commune la plus longue, puis trouver la sous-chaîne commune la plus longue suivante qui n'inclut pas les indices lcs déjà trouvés, et ainsi de suite jusqu'à une longueur minimale. Ce problème peut-il être résolu en ne construisant l'arborescence des suffixes généralisés (GST) qu'une seule fois pour les deux séquences. Je sais que cela peut être résolu en construisant à plusieurs reprises une TPS après chaque itération de recherche et de suppression du LCS. Mais, je me demande si je manque une astuce intéressante où la TPS n'est construite qu'une seule fois.

Oui, des arborescences de suffixes peuvent être utilisées pour trouver toutes les sous-chaînes courantes. Je dirais d'utiliser un tableau de suffixes à la place, mais si vous avez déjà un arbre de suffixes, la construction d'un tableau de suffixes à partir d'un arbre de suffixes prend du temps linéaire par DFS. Donc, le reste de ma réponse supposera que nous travaillons avec un tableau de suffixes.

Compte tenu d' un texte , un tableau de suffixes pour S est un tableau d'entiers de 0 à$S = s_1 , ..., s_n$$S$$0$ spécifiant l'ordre lexicographique des n + 1 suffixes de la chaîne S $$n$$n+1$$S$

Nous voulons coupler le tableau de suffixe avec le , les plus longs préfixes communs. Nous pouvons construire la matrice de L C P s en temps linéaire comme mentionné dans l'article de Kasai et al . Les tableaux de suffixes et leurs tableaux lcp s'alignent de manière à ce que, étant donné un index dans le tableau lcp, disons l c p [ k ] où k est le numéro d'index, alors s a [ k ] sera le début d'une instance du commun sous-chaîne et s a [ k - 1 $LCPs$$LCPs$$lcp[k]$$k$$sa[k]$$sa[k-1]$sera l'index de début de la deuxième instance. La longueur est bien sûr la valeur du tableau lcp.

J'ai une idée qui pourrait fonctionner. Nous commençons par un arbre suffixe généralisé pour les séquences et T . Chaque nœud interne avec des suffixes S et T dans son sous-arbre correspond à une sous-chaîne commune des séquences. Appelons ces nœuds non triviaux. La sous-chaîne commune est maximale, si le nœud correspondant n'a pas d'enfants non triviaux. Si le nœud v est non trivial, nous stockons la plus grande profondeur de chaîne d'un nœud non trivial dans son sous-arbre sous la forme l c s ( v ) . Si r est la racine, alors est la longueur de la plus longue sous-chaîne commune de$S$$T$$S$$T$$v$$lcs(v)$$r$$lcs(r)$ et T .$S$$T$

La mise à jour de l'arborescence après la suppression d'une sous-chaîne de l'une des séquences ne devrait pas être trop difficile. Nous supprimons d'abord les feuilles correspondant aux suffixes supprimés, en mettant à jour leurs ancêtres si nécessaire. Ensuite, nous commençons à traiter les suffixes précédant la sous-chaîne supprimée. Soit l'ancêtre non trivial le plus bas de la feuille courante. Si la longueur du suffixe est k (nous sommes à k pas de la suppression) et k < l c s ( v ) , nous devons déplacer le suffixe à sa position appropriée dans l'arbre, en mettant à jour les ancêtres si nécessaire. Si k ≥ l c s ( v $v$$k$$k$$k < lcs(v)$$k \ge lcs(v)$, nous avons terminé, car nous ne sommes pas intéressés par les sous-arbres avec des racines triviales.

L'algorithme global trouve à plusieurs reprises la sous-chaîne commune la plus longue de et T et supprime l'une de ses occurrences des deux séquences, tant que la longueur du LCS est suffisamment grande.$S$$T$

Il y a quelques détails techniques, mais l'idée générale devrait fonctionner.

Commencez avec le texte concaténé S $ T , où $ n'apparaît nulle part dans * ou T . Construisez un arbre / tableau de suffixes à partir de ce texte. Il est maintenant facile de parcourir cette structure de données de suffixe pour collecter toutes les bonnes répétitions maximales. En examinant le contexte de gauche, filtrez les répétitions maximales non gauches. Ce filtrage vers la gauche pourrait être implémenté en utilisant la table Burrows-Wheeler comme dans Abouelhoda et al, bien que je ne pense pas que cela soit nécessaire. Les répétitions se produisent uniquement en S ou uniquement en Tdevrait également être éliminé à ce stade. Les répétitions qui n'ont pas été éliminées sont ensuite placées dans une file d'attente prioritaire, la priorité étant définie par la longueur. Après la traversée, comme les répétitions enregistrées sont supprimées de la priorité, le filtrage final (pour le confinement de la sous-chaîne) peut être effectué. Étant donné l'utilisation de phrases maximales, cependant, je soupçonne que très peu de ce filtrage serait nécessaire.

Cet algorithme est ma propre invention. Je ne le classerais pas comme très intelligent, mais cela devrait fonctionner.

$S$$s$$T$$t$$s$$t$$S$$T$