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 ${\displaystyle P}$ dans un texte ${\displaystyle T}$.

Comme avec d’autres recherches de chaîne par comparaison, la recherche se fait en alignant ${\displaystyle P}$ à un index particulier de ${\displaystyle T}$ et en vérifiant s’il y a concordance à cet endroit. ${\displaystyle P}$ est ensuite décalé par rapport à ${\displaystyle T}$ en suivant les règles de l’algorithme de Boyer-Moore, et le processus se répète jusqu'à atteindre la fin de ${\displaystyle 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 ${\displaystyle P}$ dans ${\displaystyle T}$ exige que l’ensemble des ${\displaystyle n}$ caractères de ${\displaystyle 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 ${\displaystyle O(nm)}$, où ${\displaystyle m}$ est la longueur de ${\displaystyle T}$ en caractères. Apostolico-Giancarlo accélère le processus en enregistrant le nombre de caractères qui correspondent aux alignements de ${\displaystyle T}$ dans une table, qui est combinée aux données recueillies lors du pré-traitement de ${\displaystyle P}$ pour éviter les vérifications d’égalité redondantes pour les suites de caractères que l’on sait correspondre.

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.