Réseau LCP

Le tableau LCP est une structure de données issue de l' informatique , qui est principalement utilisée en combinaison avec le tableau de suffixes . La désignation «LCP» est une abréviation de « plus long préfixe commun » (le plus long préfixe commun allemand ). Le tableau lui-même contient la longueur du plus long préfixe commun de deux suffixes lexicographiquement consécutifs .

Il existe de nombreuses applications pour le tableau LCP dans le domaine de la recherche et de l'indexation de texte , comme la construction de l' arborescence de suffixes ou une recherche efficace de toutes les occurrences d'un motif de recherche dans un texte. L'espace de stockage requis du tableau LCP est linéaire par rapport à la taille du texte et il existe des algorithmes qui construisent le tableau LCP en temps linéaire à l'aide du tableau de suffixes. Il a été utilisé pour la première fois dans un article de Manber et Myers (1993) dans lequel il était appelé le tableau Hgt.

définition

Soyez un texte de longueur et soyez le tableau de suffixes au-dessus du texte . Indiquez également le suffixe et la longueur du plus long préfixe commun des deux chaînes et . ${\ displaystyle T = t_ {1}, t_ {2}, ..., t_ {n}}$${\ displaystyle n}$${\ displaystyle A}$${\ displaystyle T}$${\ displaystyle T ^ {i}}$${\ displaystyle t_ {i}, t_ {i + 1}, ..., t_ {n}}$${\ displaystyle lcp (s, t)}$${\ displaystyle s}$${\ displaystyle t}$

Le tableau LCP est un tableau de taille , avec les champs individuels définis comme suit: ${\ displaystyle H}$${\ displaystyle n}$

${\ displaystyle H [i] = {\ begin {cases} {\ text {undefined}}, & {\ text {for}} i = 1 \\ lcp (T ^ {A [i-1]}, T ^ {A [i]}), & {\ text {for}} 2 \ leq i \ leq n \ end {cases}}}$

Le tableau suffixe contient un tri lexicographique de tous les suffixes de . Pour le dire plus informellement, une entrée dans le tableau LCP fait toujours référence à deux suffixes lexicographiquement consécutifs et décrit la longueur du plus long préfixe commun des suffixes considérés. La valeur de n'est pas définie car le plus petit suffixe lexicographiquement de est et n'a pas de prédécesseur. ${\ displaystyle A}$${\ displaystyle T}$${\ displaystyle T}$${\ displaystyle H [1]}$${\ displaystyle T ^ {A [1]}}$${\ displaystyle T}$

exemple

Regardez le texte . ${\ displaystyle T = {\ text {mississippi}} \ $}$

Le tableau de suffixes de représente le tri des suffixes du texte, l'index de la première lettre du suffixe respectif étant stocké dans le tableau. Le tri des suffixes pour le texte ressemble à ceci: ${\ displaystyle T}$${\ displaystyle T}$

Le tableau LCP contient la longueur du plus long préfixe commun de deux suffixes consécutifs. Il peut être construit en comparant les suffixes dans l'ordre des suffixes caractère par caractère. Par exemple, pour calculer la valeur, les suffixes commençant par et sont comparés entre eux: Le préfixe commun le plus long de et est et a donc une longueur de 2. En conséquence, est . Les valeurs restantes du tableau LCP peuvent être calculées de la même manière. La valeur de reste indéfinie car il n'y a pas de suffixe lexicographiquement disponible . Le tableau LCP pour le texte ressemble à ceci: ${\ displaystyle H}$${\ displaystyle H [10]}$${\ displaystyle A [10]}$${\ displaystyle A [9]}$${\ displaystyle T ^ {A [10]} = T ^ {4} = {\ text {sissippi}} \ $}$${\ displaystyle T ^ {A [9]} = T ^ {7} = {\ text {sippi}} \ $}$${\ displaystyle {\ text {si}}}$${\ displaystyle H [10] = 2}$${\ displaystyle H [1]}$${\ displaystyle T ^ {A [1]} = T ^ {12} = \ $}$${\ displaystyle T}$

je	1	2	3	4e	5	6e	7e	8ème	9	dix	11	12
Salut]	${\ displaystyle \ bot}$	0	1	1	4e	0	0	1	0	2	1	3

calcul

Le moyen le plus simple de calculer le tableau LCP serait (comme dans l'exemple ci-dessus) de comparer les suffixes lexicographiquement consécutifs caractère par caractère à l'aide du tableau de suffixes afin de calculer la longueur du plus long préfixe commun. Cependant, dans le pire des cas, cette méthode entraîne une durée d'exécution de . Si un texte contient les mêmes caractères, par exemple , des comparaisons devraient être effectuées globalement . ${\ displaystyle O (n ^ {2})}$${\ displaystyle n}$${\ displaystyle 1 + 2 + 3 + ... + (n-1) = O (n ^ {2})}$

Une approche plus efficace est basée sur l'idée de base du calcul des entrées LCP dans l'ordre du texte. Supposons que et soient des valeurs consécutives dans le tableau de suffixes et et aient un préfixe commun de caractères. Les suffixes et ont ensuite des caractères communs. Cependant, et n'ont pas à être côte à côte dans le tableau de suffixes; il peut bien y avoir des suffixes lexicographiquement compris entre et . Supposons que la valeur avant la valeur se trouve dans le tableau de suffixes. Ensuite et à cause du tri lexicographique des suffixes doivent avoir au moins des caractères communs (car il se situe entre et dans le tableau de suffixes ), c'est-à - dire qu'il suffirait de comparer les deux suffixes commençant par le -ème caractère. ${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle T ^ {i}}$${\ displaystyle T ^ {j}}$${\ displaystyle h}$${\ displaystyle T ^ {i + 1}}$${\ displaystyle T ^ {j + 1}}$${\ displaystyle h-1}$${\ displaystyle i + 1}$${\ displaystyle j + 1}$${\ displaystyle T ^ {i + 1}}$${\ displaystyle T ^ {j + 1}}$${\ displaystyle k}$${\ displaystyle i + 1}$${\ displaystyle T ^ {i + 1}}$${\ displaystyle T ^ {k}}$${\ displaystyle h-1}$${\ displaystyle k}$${\ displaystyle i + 1}$${\ displaystyle j + 1}$${\ displaystyle h}$

Pour cette approche, le tableau de suffixes inverses est nécessaire pour savoir où se trouve une certaine valeur . Il s'agit de la permutation inverse de , c'est-à- dire qu'elle indique où se trouve la valeur dans le tableau de suffixes . ${\ displaystyle A ^ {- 1}}$${\ displaystyle A}$${\ displaystyle A ^ {- 1}}$${\ displaystyle A}$${\ displaystyle A ^ {- 1} [i]}$${\ displaystyle A}$${\ displaystyle i}$

Les résultats de l'algorithme suivant:

 1LCP-Array(T, A, n)
 2   for (i=1 to n)  {
 3      Ainv[A[i]] = i;
 4   }
 5   H[1] = 0;
 6   h = 0;
 7   for (i=1 to n) {
 8      if (Ainv[i] ≠ 1) {
 9         j = A[Ainv[i] - 1]
10         while T[i+h] = T[j+h]
11            h = h + 1
12         H[Ainv[i]] = h
13         h = max(0, h - 1)
14      }
15   }

Le temps de fonctionnement est linéaire, car le maximum qu'il peut supposer Comme chaque étape ne décrémente que de 1, la boucle while interne est exécutée la plupart du temps. Il en résulte une durée totale de fonctionnement de . ${\ displaystyle h}$${\ displaystyle n}$${\ displaystyle h}$${\ displaystyle O (n)}$${\ displaystyle O (n)}$

L'approche présentée ci-dessus provient de Kasai et al. (2001) et est le premier algorithme publié qui calcule le tableau LCP en temps linéaire. Manzini (2004) a développé une version améliorée qui ne nécessite aucune mémoire supplémentaire en plus du texte réel, du tableau de suffixes et du tableau LCP. Une autre amélioration est l'algorithme φ de Kärkkäinen, Manzini et Puglisi: alors que l'algorithme d'origine provoquait des erreurs de cache via un accès non séquentiel aux tableaux pour les textes longs correspondants (à savoir dans les lignes 3, 9, 10 et 12), l'algorithme φ gère avec seulement les échecs de cache. ${\ displaystyle 4n}$ ${\ displaystyle 3n}$

Les algorithmes mentionnés ci-dessus utilisent un tableau de suffixes existant pour calculer le tableau LCP. Il existe des algorithmes qui calculent le tableau LCP en même temps que le tableau de suffixes. L'algorithme de temps linéaire actuellement le plus rapide provient de Fischer (2011).

Gog & Ohlebusch (2011) ont publié deux algorithmes qui ont un temps de fonctionnement quadratique dans le pire des cas, mais qui sont plus rapides en pratique que les algorithmes de temps linéaire mentionnés ci-dessus.

Recherche de texte accélérée à l'aide du tableau LCP

Avec le tableau de suffixes, l'occurrence d'un modèle de longueur dans un texte de longueur peut être déterminée à l'aide de la recherche binaire . Étant donné que les suffixes du tableau de suffixes sont triés lexicographiquement, les comparaisons sont suffisantes pour trouver le suffixe lexicographique le plus petit (ou le plus grand) qui contient. Doit être jusqu'à pour chaque comparaison sont les caractères comparés, ce qui fait de ce processus un terme de caractéristiques. ${\ displaystyle P}$${\ displaystyle m}$${\ displaystyle T}$${\ displaystyle n}$${\ displaystyle O (\ log {n})}$${\ displaystyle P}$${\ displaystyle m}$${\ displaystyle O (m \ log {n})}$

À l'aide du tableau LCP, le runtime peut être amélioré en évitant que le motif ne soit à nouveau lu depuis le début à chaque étape de la recherche binaire . ${\ displaystyle O (m + \ log {n})}$${\ displaystyle P}$

À chaque étape de la recherche binaire, il y a une limite d'intervalle à gauche , une limite d'intervalle à droite et un élément central . Il est comparé au suffixe lexicographique (c'est-à-dire avec ). Si les deux chaînes correspondent, la recherche binaire est terminée, sinon la recherche doit être poursuivie dans la moitié gauche ou droite de l'intervalle. Nous examinons le cas qui est lexicographiquement plus petit que l' est - l'autre cas est analogue. Soit la longueur du plus long préfixe commun des deux chaînes. Cela signifie que le caractère -th de est lexicographiquement plus petit que celui de . ${\ displaystyle l}$${\ displaystyle r}$${\ displaystyle m}$${\ displaystyle P}$${\ displaystyle A [m]}$${\ displaystyle T ^ {A [m]}}$${\ displaystyle P}$${\ displaystyle T ^ {A [m]}}$${\ displaystyle k = lcp (P, T ^ {A [m]})}$${\ displaystyle k + 1}$${\ displaystyle P}$${\ displaystyle T ^ {A [m]}}$

Le nouvel intervalle a les limites et et l'élément du milieu . Soit la longueur du plus long préfixe commun entre l'ancien et le nouvel élément central. Une distinction de cas suit: ${\ displaystyle l}$${\ displaystyle m}$${\ displaystyle m '}$${\ displaystyle k '= lcp (T ^ {A [m]}, T ^ {A [m']})}$

• ${\ Displaystyle k <k '}$: Le -ème caractère des suffixes et est le même. Par conséquent, il doit également être lexicographiquement plus petit que et la recherche binaire peut être poursuivie dans la moitié gauche de l'intervalle sans autre comparaison.${\ displaystyle k + 1}$${\ displaystyle T ^ {A [m]}}$${\ displaystyle T ^ {A [m ']}}$${\ displaystyle P}$${\ displaystyle T ^ {A [m ']}}$
• ${\ displaystyle k> k '}$: En raison de , le suffixe est lexicographiquement plus petit que le suffixe . Cela signifie que le -ème caractère du suffixe doit être plus petit que le -ème caractère du suffixe . Puisque et ont un préfixe commun d'au moins caractères, il s'ensuit ici que lexicographiquement est plus petit que P et la recherche binaire se poursuit dans la moitié droite.${\ displaystyle m '<m}$${\ displaystyle T ^ {A [m ']}}$${\ displaystyle T ^ {A [m]}}$${\ displaystyle k '+ 1}$${\ displaystyle T ^ {A [m ']}}$${\ displaystyle k '+ 1}$${\ displaystyle T ^ {A [m]}}$${\ displaystyle T ^ {A [m]}}$${\ displaystyle P}$${\ displaystyle k '+ 1}$${\ displaystyle T ^ {A [m ']}}$
• ${\ displaystyle k = k '}$: et ont un préfixe commun d'au moins caractères. Les deux chaînes doivent être comparées ici, la comparaison ne devant commencer que par le -ème caractère.${\ displaystyle P}$${\ displaystyle T ^ {A [m ']}}$${\ displaystyle k}$${\ displaystyle k + 1}$

Avec la méthode décrite, il n'est jamais nécessaire de lire à nouveau les caractères dans la recherche binaire . La méthode vient de Manber et Myers. Étant donné que le tableau LCP ne contient que les valeurs des suffixes lexicographiquement consécutifs, ce qui suit montre comment toutes les valeurs de valeur peuvent être calculées efficacement. ${\ displaystyle P}$${\ displaystyle lcp}$${\ displaystyle lcp}$

En général, le préfixe commun le plus long de deux suffixes peut être trouvé à l'aide d'une requête de plage minimale sur le tableau LCP. Pour deux suffixes , considérez tous les suffixes qui sont lexicographiquement entre les deux: Si deux suffixes successifs ont un préfixe commun de longueur le plus long , et en raison du tri lexicographique, ne peuvent pas avoir un préfixe commun plus long. La valeur correspond donc exactement au minimum au-dessus des entrées LCP . Ce minimum peut être trouvé en temps constant en utilisant des méthodes appropriées pour les requêtes minimum de plage.${\ displaystyle T ^ {A [i]}, T ^ {A [j]}}$${\ displaystyle k}$${\ displaystyle T ^ {A [i]}}$${\ displaystyle T ^ {A [j]}}$${\ displaystyle lcp (T ^ {A [i]}, T ^ {A [j]})}$${\ Displaystyle H [i + 1], ..., H [j]}$

Littérature

• Algorithmes de bioinformatique d' Enno Ohlebusch : analyse de séquence, réarrangements du génome et reconstruction phylogénétique . Oldenbusch Verlag, 2013, chapitre 4.

Preuve individuelle

1. ↑ ^{a b} Udi Manber, Gene Myers: Suffix Arrays: Une nouvelle méthode pour les recherches de chaînes en ligne . Dans: SIAM Journal on Computing . 22, n ° 5, 1993, page 935. doi : 10.1137 / 0222058 .
2. ↑ Kasai, T. et al.: Calcul du préfixe commun le plus long en temps linéaire dans le suffixe . Dans: Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, 2001.
3. ^ Manzini, Giovanni: Deux astuces d'économie d'espace pour le calcul linéaire de tableau LCP en temps . Dans: Notes de cours en informatique, volume 3111, page 372, 2004.
4. ↑ Kärkkäinen, Juha; Manzini, Giovanni; Puglisi, Simon J.: Tableau de préfixes communs les plus longs permutés . Dans: Lecture Notes in Computer Science, Volume 5577, page 181, 2009.
5. ^ Fischer, Johannes: Induire le LCP-Array . Dans: Lecture Notes in Computer Science, Volume 6844, pp. 374–385, 2011.
6. ↑ Gog, Simon; Ohlebusch, Enno: Algorithmes de construction LCP-Array rapides et légers . Dans: Actes de l'atelier sur l'ingénierie des algorithmes et les expériences, ALENEX, pp.25-34, 2011.
7. ^ Fischer, J. et V. Heun: Améliorations théoriques et pratiques sur le problème RMQ, avec des applications à LCA et LCE . Dans: Combinatorial Pattern Matching . 2006, pp. 36-48. doi : 10.1007 / 11780441_5 .
8. ^ Fischer, J. et V. Heun: Schémas de prétraitement à efficacité spatiale pour les requêtes minimum de plage sur les tableaux statiques . Dans: SIAM J. Comput. 40 (avril) . 2011, pp. 465-492. doi : 10.1137 / 090779759 .