title: Algorithme de Baeza-Yates-Gonnet
text: # Algorithme de Baeza-Yates-Gonnet
  
  L'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.
  
  ## Description
  
  Le 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 exacte
  
  Pour 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 |= 1 dans la boucle, ce qui serait sub-optimal.
  
  ### Pré-traitement
  
  Chaque entrée de la table de masquage (de la taille de l'alphabet, soit 256 ici) est initialement remplie à
  
  Puis pour chaque caractère de P, la table de masquage est mise à jour a l'index du caractère.
  
  La table de bits R est initialisée à ~1, soit 11111111111111111111111111111110
  
  ### Recherche
  
  Pour chaque caractère du texte T en partant du premier, la valeur de R est mise à jour de la façon suivante :
  
  Par exemple, si le premier caractère de T est 's' (et qui donc correspond au premier caractère de P)
  
  Puis si le caractère suivant de T est 't' (correspond au second caractère de P)
  
  Admettons que chaque caractère de P soit successivement trouvé dans T
  
  ### Condition de sortie
  
  La condition pour vérifier que P est présent dans T est la suivante :
  
  Comme 1 << p vaut dans notre cas :
  
  La condition testée est donc :
  
  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é
  
  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|).
  
  