|
Algorithme de Baeza-Yates-GonnetL'algorithme de Baeza-Yates-Gonnet plus connu sous le nom de Shift-Or ou encore Bitap est un algorithme de recherche de sous-chaîne. Sa version en recherche exacte a été publiée par Bálint Dömölki en 1964 avant d'être adaptée en 1996 par Ricardo Baeza-Yates et Gaston Gonnet pour satisfaire une recherche approximative. L'algorithme utilise des opérations bit à bit ce qui lui permet d'atteindre une bonne performance. Cependant une limitation inhérente est que la sous-chaîne ne peut dépasser la taille d'un mot machine. Une autre force de Shift-Or est sa capacité à être facilement adapté pour faire des recherches approximatives. DescriptionLe pré-traitement construit une table de masques de la taille de l'alphabet ∑ ainsi qu'une table R de bits de la taille d'un mot (32/64 bits en général). Exemple de recherche exactePour un pattern P="string" de longueur p=6 et un alphabet ASCII (256 caractères) et une machine 32 bits et des entiers non signés. Pour tirer parti du décalage de bit à gauche qui insère un 0 à la droite, on fait le choix de considérer que 0 indique une correspondance et 1 indique une différence entre deux caractères. La manière "intuitive" de procéder requiert de faire l'opération R |=[Quoi ?] 1 dans la boucle[Quoi ?], ce qui serait sub-optimal. Pré-traitementChaque entrée de la table de masquage (de la taille de l'alphabet, soit 256 ici) est initialement remplie à ~0, soit 11111111111111111111111111111111 Puis pour chaque caractère de P, la table de masquage est mise à jour a l'index du caractère. l'index 's' a pour valeur ~(1 << 0) soit 11111111111111111111111111111110 l'index 't' a pour valeur ~(1 << 1) soit 11111111111111111111111111111101 l'index 'r' a pour valeur ~(1 << 2) soit 11111111111111111111111111111011 l'index 'i' a pour valeur ~(1 << 3) soit 11111111111111111111111111110111 l'index 'n' a pour valeur ~(1 << 4) soit 11111111111111111111111111101111 l'index 'g' a pour valeur ~(1 << 5) soit 11111111111111111111111111011111 La table de bits R est initialisée à ~1, soit 11111111111111111111111111111110 RecherchePour chaque caractère du texte T en partant du premier, la valeur de R est mise à jour de la façon suivante : R = R | mask[T[i]] R = R << 1 Par exemple, si le premier caractère de T est 's' (et qui donc correspond au premier caractère de P) En entrée : R = 11111111111111111111111111111110 R = 11111111111111111111111111111110 | 11111111111111111111111111111110 = 11111111111111111111111111111110 R = 11111111111111111111111111111110 << 1 = 1111111111111111111111111111100 En sortie : R = 11111111111111111111111111111100 Puis si le caractère suivant de T est 't' (correspond au second caractère de P) En entrée : R = 11111111111111111111111111111100 R = 11111111111111111111111111111100 | 11111111111111111111111111111101 = 11111111111111111111111111111101 R = 11111111111111111111111111111101 << 1 = 11111111111111111111111111111010 En sortie : R = 11111111111111111111111111111010 Admettons que chaque caractère de P soit successivement trouvé dans T En sortie : R = 11111111111111111111111110111110 Condition de sortieLa condition pour vérifier que P est présent dans T est la suivante : R & (1 << p) == 0 Comme 1 << p vaut dans notre cas : 1 << 6 = 00000000000000000000000001000000 La condition testée est donc : 11111111111111111111111110111110 & 00000000000000000000000001000000 Ce qui vaut 0 (pour rappel, il a été fait le choix de considérer que 0 indique une correspondance), donc P a été trouvé dans T à la position i. ComplexitéDans cette section, |P| est la longueur du motif, |T| est la longueur du texte, et |∑| est le nombre de symboles dans l'alphabet. En espace, Shift-Or a une complexité O(|P|+|∑|). Le pré-traitement a une complexité en temps en O(|P|+|∑|). La recherche a une complexité en temps en O(|T|). Implémentation Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ? |
