Algorithme d'Apostolico-Giancarlo

En informatique, l’algorithme de Apostolico–Giancarlo est une variante de l’algorithme de recherche de chaîne Boyer–Moore dont l'utilisation de base est la recherche d’occurrences d’un motif $P$ dans un texte $T$.

Comme avec d’autres recherches de chaîne par comparaison, la recherche se fait en alignant $P$ à un index particulier de $T$ et en vérifiant s’il y a concordance à cet endroit. $P$ est ensuite décalé par rapport à $T$ en suivant les règles de l’algorithme de Boyer-Moore, et le processus se répète jusqu'à atteindre la fin de $T$. L’application des règles de décalage de Boyer-Moore aboutit souvent à sauter complètement de grandes parties du texte. Concernant l’opération de décalage, Apostolico-Giancarlo est l’exact équivalent fonctionnel de Boyer-Moore. L'utilité de Apostolico-Giancarlo est d'accélérer l’opération de vérification de la concordance à un index donné. Avec Boyer-Moore, trouver une occurrence de $P$ dans $T$ exige que l’ensemble des $n$ caractères de $P$ corresponde explicitement. Pour certains motifs et textes, c’est très inefficace. Un exemple simple est celui où le motif et le texte consistent tous deux en un même caractère répété. Dans ce cas, Boyer-Moore s’exécute en $O(nm)$, où $m$ est la longueur de $T$ en caractères. Apostolico-Giancarlo accélère le processus en enregistrant le nombre de caractères qui correspondent aux alignements de $T$ dans une table, qui est combinée aux données recueillies lors du pré-traitement de $P$ pour éviter les vérifications d’égalité redondantes pour les suites de caractères que l’on sait correspondre.

Bibliographie

• (en) A. Apostolico et R. Giancarlo, « The Boyer–Moore–Galil String Searching Strategies Revisited », SIAM Journal on Computing, vol. 15, n^o 1,‎ 1986, p. 98-105 (DOI 10.1137/0215007).
• (en) M. Crochemore et T. Lecroq, « Tight bounds on the complexity of the Apostolico-Giancarlo algorithm », Information Processing Letters, vol. 63, n^o 4,‎ 1997, p. 195-203 (DOI 10.1016/S0020-0190(97)00107-5).
• (en) M. Crochemore et W. Rytter, Text Algorithms, New York, Oxford University Press, 1994, 412 p. (ISBN 0-19-508609-0, présentation en ligne).
• (en) D. Gusfield, Algorithms on Strings, Trees, and Sequences : Computer Science and Computational Biology, Cambridge/New York/Melbourne, Cambridge University Press, 1997, 534 p. (ISBN 0-521-58519-8, lire en ligne).
• Thierry Lecroq, Recherches de mot (thèse de doctorat en informatique), France, Université d’Orléans, 1992.
• (en) Thierry Lecroq, « Experimental results on string matching algorithms », Software - Practice & Experience, vol. 25, n^o 7,‎ 1995, p. 727-765 (DOI 10.1002/spe.4380250703).