Kha-tastrophe.net
> Cours > Informatique> Algorithmique et Analyse > Recherche de texte
9. Recherche de texte
9.1. Idée de base
On considère un "texte" (suite de caractères); on veut recherche la position dans ce texte d'un certain "motif" (autre suite de caractères). Par exemple, le motif "jour" est à recherche dans le texte "on a lu dans le journal de ce jour qu'un bandit, déjà interdit de séjour, avait commis trois agressions dans la même journée" (4 occurences). A noter que la recherche du motif " jour " (entouré d'espaces) n'aurait donné qu'une seule occurrence : "on a lu dans le journal de ce jour qu'un bandit, déjà interdit de séjour, avait commis trois agressions dans la même journée".
9.2. Algorithme naïf
L'idée est de placer le motif en regard du texte et, pour une position donnée, de comparer un par un les caractères du motif aux caractères correspondants du texte ; si aucun désaccord n'est observé, on a trouvé une occurrence du motif, sinon on arrête la comparaison dès qu'un désaccord est observé et on fait glisser le motif de 1 caractère (pour ne pas risquer de rater une coïncidence) puis on recommence la comparaison.
En conséquence, si le texte comporte Lt caractères et le motif Lm caractères et si aucun caractère du motif n'est présent dans le texte on aura fait Lt - Lm comparaisons pour épuiser le texte (l'algorithme que nous allons présenter n'en aurait que (Lt - Lm)/Lm. Si les distributions de caractères sont aléatoires, la découverte d'une différence entre motif et texte n'a lieu, en moyenne, qu'après Lm/2 comparaisons, d'où une complexité de l'ordre de Lt x Lm comparaisons.
9.3. Algorithme rusé : l'algorithme de Boyer-Moore
Une des idées de base de cet algorithme est de tenir compte du fait que dans la pratique la longueur du motif est considérablement plus courte que celle du texte ; on va donc réaliser un pré-traitement sur le motif : répérer, une fois pour toutes, les caractères qu'il contient et ceux qui en sont absents.
Nous allons expliquer le fonctionnement de l'algorithme par quelques exemples. Dans les figures qui suivent on a procédé aux comparaisons en commençant par la droite du motif :
- les cases marquées e contiennent des caractères, dont on a vérifié l'identité (motif - texte)
- les cases marquées Ct contiennent le caractère du texte pour lequel on a relevé une différence avec le caractère correspondant Cm du motif, on a aussi montré les autres occurrences utiles de ces caractères,
- les cases marquées z contiennent les caractères sans intérêt (déjà ou pas encore explorés),
- la flèche verticale pointe la première paire de cases en désaccord dans la comparaison en cours,
- la flèche horizontale montre le déplacement que l'on va pouvoir appliquer au motif avant la prochaine séquence de comparaisons.
Premier exemple :
Le caractère Ct ne figure pas dans le motif, toute autre comparaison avec les caractères de gauche du motif est donc inutile ; en conséquence, il faut avancer (vers la droite) le motif pour qu'il dépasse la position de Ct puis recommencer les comparaisons.
Deuxième exemple :
La première occurrence (en partant de la droite) du caractère Ct dans le motif figure à gauche du caractère Cm ; on avancera donc le motif pour mettre les deux caractère Ct en coïncidence avant de commencer une nouvelle comparaison.
Troisième exemple :
La première occurrence (en partant de la droite) du caractère Ct dans le motif figure à droite du caractère Cm, mais le désaccord a lieu pour la première occurence de Cm (dans cette comparaison), celui-ci ne figure donc pas dans la partie explorée du texte ; on avancera donc le motif pour que ce caractère Cm dépasse la position actuelle du motif.
Quatrième exemple :
Les caractères Ct et Cm figurent dans la partie droite, déjà explorée, du motif ; on a représenté la première occurrence (en partant de la droite) de chacun ; on peut donc avancer le motif pour que la plus à gauche de ces premières occurences (ici, Cm) dépasse la position actuelle du motif.
Le principe de l'algorithme va être relativement simple : pour chaque caractère de l'alphabet utilisé, on dresse la table des premières occurences (en partant de la droite) dans le motif ; on explore le motif de droite à gauche, en cas de désaccord, on détermine le déplacement en tenant compte des seuls caractères immédiatement connus : Cm et Ct.
Il faut donc définir avec précision les notations et conventions utilisées :
- Le motif contient Lm caractères, le texte Lt, les caractères sont numérotés de 1 à ... (de gauche à droite),
- le position du motif est définie par son déplacement Lm, distance de son caractère de gauche au caractère de gauche du texte (de 0 à Lt-Lm),
- la table des distances tdBdm contient, pour chaque caractère de l'alphabet, le nombre de caractères qui sépare son occurrence la plus à droite dans le motif, du bord droit de ce motif (de 0 pour le caractère de droite du motif, à Lm pour le caractère absent du motif).
Il ne vous reste plus qu'à écrire l'algorithme...