sous-chaîne commune la plus longue

informatique , la plus longue sous-chaîne commune à deux chaînes ou plus est la plus longue chaîne qui est une sous-chaîne de chacune d'elles. Il peut exister plusieurs plus longues sous-chaînes communes. Parmi les applications, on peut citer la déduplication des données et la détection du plagiat .

Contrairement au problème de la plus longue sous-séquence commune , qui recherche des insertions ou des suppressions dans le texte commun, le problème de la plus longue sous-chaîne commune recherche une sous-chaîne contiguë partagée par les deux textes.

Les chaînes de caractères « BADANAT » et « CANADAS » partagent les sous-chaînes de longueur maximale « ADA » et « ANA ».

L'image montre deux chaînes de caractères pour lesquelles le problème admet plusieurs solutions. Bien que les occurrences des sous-chaînes se chevauchent toujours, il est impossible d'obtenir une sous-chaîne commune plus longue en les « unissant ».

Les chaînes « ABABC », « BABCA » et « ABCBA » n'ont qu'une seule sous-chaîne commune la plus longue, à savoir « ABC » de longueur 3. Les autres sous-chaînes communes sont « A », « AB », « B », « BA », « BC » et « C ».

 ABABC ||| BABCA ||| ABCBA

Définition du problème

Étant donné deux chaînes de caractères, $de longueur et de longueur Trouvez la plus longue chaîne qui soit une sous-chaîne des deux et .$

Une généralisation est le problème des k sous - chaînes communes . Étant donné l'ensemble des chaînes $, où et Trouvez pour chaque, la plus longue chaîne qui apparaît comme sous-chaîne d'au moins chaînes.$

Algorithmes

On peut trouver les longueurs et les positions de départ des plus longues sous-chaînes communes de $et dans Le temps est réduit grâce à un arbre de suffixes généralisé . Un algorithme plus rapide peut être obtenu dans le modèle de calcul de la RAM de mots si la taille de l'alphabet d'entrée est dans . Plus précisément, cet algorithme s'exécute dans temps utilisé espace. Résolution du problème par programmation dynamique des coûts Les solutions au problème généralisé prennent espace et Du temps avec la programmation dynamique et prenez temps avec un arbre de suffixes généralisé .$

Arbre des suffixes

On peut trouver les plus longues sous-chaînes communes à un ensemble de chaînes en construisant un arbre de suffixes généralisé pour ces chaînes, puis en identifiant les nœuds internes les plus profonds qui ont des feuilles issues de toutes les chaînes du sous-arbre situé en dessous. La figure de droite représente l'arbre de suffixes des chaînes « ABAB », « BABA » et « ABBA », complétées par des terminateurs uniques, pour devenir « ABAB$0 », « BABA$1 » et « ABBA$2 ». Les nœuds représentant « A », « B », « AB » et « BA » ont tous des feuilles descendantes issues de toutes les chaînes, numérotées 0, 1 et 2.

La construction de l'arbre des suffixes prend $en temps (si la taille de l'alphabet est constante). Si l'arbre est parcouru de bas en haut avec un vecteur binaire indiquant les chaînes rencontrées sous chaque nœud, le problème des k sous-chaînes communes peut être résolu en Si l'arbre des suffixes est préparé pour une recherche de l'ancêtre commun le plus récent en temps constant , il peut être résolu en temps.$

Programmation dynamique

Le pseudocode suivant trouve l'ensemble des plus longues sous-chaînes communes entre deux chaînes de caractères à l'aide de la programmation dynamique :

fonction PlusLongueSous-chaîneCommune(S[1..r], T[1..n]) L := tableau (1..r, 1..n) z := 0 # longueur de la plus longue sous-chaîne commune trouvée jusqu'à présent ret := {} pour i := 1..r pour j := 1..n si S[i] = T[j] si i = 1 ou j = 1 L[i, j] := 1 autre L[i, j] := L[i − 1, j − 1] + 1 si L[i, j] > z z := L[i, j] ret := {S[(i − z + 1)..i]} sinon si L[i, j] = z ret := ret ∪ {S[(i − z + 1)..i]} autre L[i, j] := 0 retourner ret

Cet algorithme s'exécute dans $Le tableau L stocke la longueur du plus long suffixe commun des préfixes S[1..i] et T[1..j] se terminant respectivement aux positions i et j . La variable z sert à stocker la longueur de la plus longue sous-chaîne commune trouvée jusqu'à présent. L'ensemble ret contient l'ensemble des chaînes de longueur z . Cet ensemble ret peut être optimisé en ne stockant que l'indice i, qui correspond au dernier caractère de la plus longue sous-chaîne commune (de taille z), au lieu de . Ainsi, pour chaque i dans , S[(i-z+1)..i] toutes les plus longues sous-chaînes communes seraient . ret S[(ret[i]-z)..(ret[i])]$

Les astuces suivantes peuvent être utilisées pour réduire l'utilisation de la mémoire d'une implémentation :

Ne conservez que la dernière ligne et la ligne actuelle de la table DP pour économiser de la mémoire (
au lieu de
)
- La dernière ligne et la ligne actuelle peuvent être stockées dans le même tableau 1D en parcourant la boucle interne à l'envers.
Ne stockez que les valeurs non nulles dans les lignes. On peut utiliser des tables de hachage plutôt que des tableaux. C'est particulièrement utile pour les grands alphabets.