Match est un algorithme permettant
de retrouve les occurence d'un motif particulier dans un fichier.
Match
Les besoins de plus en plus important
de cet algorithme dans de nombreux domaine ont entraine le developpement
de nombreuses versions de cet algorithme.
Dans cette etude, nous n'en verrons que 2, l'algorithme force brute qui
est le plus simple et l'algorithme de Boyer-Moore qui est un des algorithme
ayant le meilleur rendement ( cf test comparatif entre les algos ) Il
faut cependant note qu'il existe de nombreux algorithme Match ( entre
autre Rabin-Karp ou Knuth-Morris-Pratt ) pour de plus ample renseignement,
se référer a la bibliographie.
Force brute :
Cet algorithme est le plus simple et le plus naturel cependant il est
tres lent. algo : Compare le motif de taille m avec les m premiers characteres
de la chaine.
FAIRE
-----Si une correspondance est trouvees,
note la position.
-----deplace le motif d'un rang vers la droite.
-----Compare le motif de taille m avec les
m characteres suivant de la chaine
TANT QUE il reste des characteres a comparer.
L'algorithme de Boyer-Moore :
L'algorithme de Boyer-Moore est base sur l'idee que
l'algorithme peut avoir plus d'information en confrontant le motif par
la doite plutot que par la gauche. Pendant la recherche, les occurences
sont les characteres du motif Cet algorithme utilise deux fonctions heuristique.
------ delta(1) : Quand une difference
apparait, la fonction utilise les information sur l'endroit ou a eu lieu
la difference dans le motif pour produire le nouveau decalage. La longueur
du decalage depend du caractere char tire du texte. Si char n'apparait
pas dans le motif, delta(1) est la longueur du motif. Si char apparait
dans le motif on peut alors decaler le motif de facon a aligner char avec
le motif sans avoir besoin de verifier les autres occurences.
------ delta(2) : elle est fonction
de la position j dans le motif ou la difference est apparue. k est la
distance entre la derniere occurence dans le sousmotif et sa nouvelle
occurence la plus probable qui est toujours >= 1. m est la longueur du
motif -j.
L'algorithme choisira le resultat de la fonctions permetant le plus grand
deplacement.
Observation 1 : si char n'apparait pas dans le motif il n'y a pas besoin
de prendre en compte les possibillite d'une occurence a partir de la position
1 ou longueur_du_motif.
Observation 2 : Si dans le motif, l'occurence la plus a droite de char
dans le motif est delta 1
Tests Comparatifs
entre les algos
bf = Force Brute
bm = Boyer-Moore
rk = Rabin-Karp
kmp = Knuth-Morris-Pratt
Bonnées Binaires

Donnés Caractères

Données Décimales
Conclusion :
Parmi les algorithmes
présents, il est aisé de remarquer les différents
intérets de chaque algorithme.
|