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 Compa
ratifs 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.