Chapitre 11 : Recherche textuelle⚓︎
Le but de ce chapitre est d'écrire des algorithmes qui permettent de savoir si un mot ou un groupe de mots est présent dans un texte ou, de façon plus générale, si un motif est présent dans une chaîne de caractères.
Dans tout le chapitre, on note \(m\) la longueur du motif recherché et \(c\) la longueur de la chaîne dans laquelle on recherche.
Si \(m \gt c\), il est évident que le motif ne peut pas apparaître dans la chaîne.
En général, \(m\) est très inférieur à \(c\). En effet, le motif recherché est généralement composé de quelques caractères, ou de quelques dizaines de caractères au maximum. La chaîne dans laquelle on recherche, en revanche, peut être composée de milliers de caractères.
Exercice : Correspondance entre motif et chaîne
Carnet Jupyter à télécharger ici
Corrigé disponible ici
Premier algorithme, dit naïf⚓︎
Algorithme naïf de recherche de la présence d'un motif dans une chaine
Détermine si un motif est présent dans une chaine
Entrées
motif : chaîne de caractères
chaine : chaîne de caractères
Sortie
booléen (Vrai si le motif est présent dans la chaine, Faux sinon)
Début
c ← longueur de la chaine
m ← longueur du motif
k ← 0
Tant que k <= (c - m) faire
Si le motif correspond aux caractères de la chaine entre l'indice k et l'indice (k + m - 1) alors
Renvoyer Vrai
Fin Si
k ← k + 1
Fin Pour
Renvoyer Faux
Fin
Algorithme de Boyer-Moore-Horspool⚓︎
Algorithme de Boyer-Moore-Horspool
Détermine si un motif est présent dans une chaine
Entrées
motif : chaîne de caractères
chaine : chaîne de caractères
Sortie
booléen (Vrai si le motif est présent dans la chaine, Faux sinon)
Début
decalage ← dictionnaire de décalages obtenu par prétraitement du motif
c ← longueur de la chaine
m ← longueur du motif
k ← 0
Tant que k <= (c - m) faire
Si le motif correspond aux caractères de la chaine entre l'indice (k + m - 1) et l'indice k alors
Renvoyer Vrai
Fin Si
Si chaine[k + m - 1] est une clé du dictionnaire decalage alors
k ← k + decalage[chaine[k + m - 1]]
Sinon
k ← k + m
Fin Si
Fin Pour
Renvoyer Faux
Fin
Exercice : Algorithme de Boyer-Moore-Horspool
Carnet Jupyter à télécharger ici
Corrigé disponible ici