Le Pattern Matching est largement utilisé en informatique et dans de nombreux autres domaines. Les algorithmes de correspondance de modèles sont utilisés pour rechercher des modèles dans un texte ou un ensemble de données plus vaste. L'un des algorithmes les plus populaires pour la correspondance de modèles est le Boyer Moore , qui a été publié pour la première fois en 1977. Dans cet article, nous discuterons des algorithmes de correspondance de modèles en C et de leur fonctionnement.
Qu’est-ce qu’un algorithme de correspondance de modèles ?
Les algorithmes de correspondance de modèles sont utilisés pour trouver des modèles dans un plus grand ensemble de données ou de texte. Ces algorithmes fonctionnent en comparant un modèle avec un ensemble de données ou un texte plus grand et en déterminant si le modèle est présent ou non. Les algorithmes de correspondance de modèles sont importants car ils nous permettent de rechercher rapidement des modèles dans de grands ensembles de données.
qu'est-ce que l'objet Java
Algorithme de correspondance de modèles de force brute :
La correspondance de modèles par force brute est l’algorithme de correspondance de modèles le plus simple. Il s’agit de comparer les caractères du motif avec les caractères du texte un à un. Si tous les caractères correspondent, l'algorithme renvoie la position de départ du motif dans le texte. Dans le cas contraire, l'algorithme passe à la position suivante dans le texte et répète la comparaison jusqu'à ce qu'une correspondance soit trouvée ou que la fin du texte soit atteinte. La complexité temporelle de l'algorithme de force brute est O(MXN) , où M désigne la longueur du texte et N désigne la longueur du motif.
Algorithme naïf de correspondance de modèles :
L'algorithme Naive Pattern Matching est une amélioration par rapport à l'algorithme Brute Force. Cela évite les comparaisons inutiles en sautant certaines positions dans le texte. L'algorithme commence à comparer le motif avec le texte en première position. Si les caractères correspondent, il passe à la position suivante et répète la comparaison. Si les caractères ne correspondent pas, l'algorithme passe à la position suivante dans le texte et compare à nouveau le motif avec le texte. La complexité temporelle de l'algorithme Naive est également O(MXN) , mais il est plus rapide que l'algorithme Brute Force dans la plupart des cas.
Algorithme de Knuth-Morris-Pratt :
Le Knuth-Morris-Pratt (KMP) L'algorithme est un algorithme de correspondance de modèles plus avancé. Elle repose sur l’observation que lorsqu’une discordance se produit, certaines informations sur le texte et le motif peuvent être utilisées pour éviter des comparaisons inutiles. L'algorithme précalcule une table contenant des informations sur le modèle. Le tableau détermine combien de caractères du modèle peuvent être ignorés en cas de non-concordance. La complexité temporelle du KMP l'algorithme est O(M+N) .
L'algorithme de Boyer-Moore :
L'un des algorithmes de correspondance de modèles les plus populaires est le Boyer Moore algorithme. Cet algorithme a été publié pour la première fois en 1977 par Robert S. Boyer et J Strother Moore. Le Boyer Moore L'algorithme compare un modèle avec un plus grand ensemble de données ou de texte de droite à gauche au lieu de gauche à droite, comme avec la plupart des autres algorithmes de correspondance de modèles.
Le Boyer Moore L'algorithme comporte deux composantes principales : la règle des mauvais caractères et la règle des bons suffixes. La règle des mauvais caractères fonctionne en comparant le caractère du modèle avec le caractère correspondant dans les données ou le texte. Si les caractères ne correspondent pas, l'algorithme déplace le motif vers la droite jusqu'à ce qu'il trouve un caractère correspondant. La bonne règle de suffixe compare le suffixe du modèle avec le suffixe correspondant des données ou du texte. Si les suffixes ne correspondent pas, l'algorithme déplace le motif vers la droite jusqu'à ce qu'il trouve un suffixe correspondant.
Le Boyer Moore L'algorithme est connu pour son efficacité et est largement utilisé dans de nombreuses applications. Il est considéré comme l’un des algorithmes de correspondance de modèles les plus rapides disponibles.
Implémentation de l'algorithme de Boyer-Moore en C :
Pour mettre en œuvre le Boyer Moore algorithme en C, on peut commencer par définir la règle du mauvais caractère. Nous pouvons utiliser un tableau pour stocker la dernière occurrence de chaque caractère dans le modèle. Ce tableau peut déterminer jusqu'où nous devons déplacer le motif vers la droite lorsqu'une discordance se produit.
Voici un exemple de la façon dont nous pouvons implémenter la règle des mauvais caractères en C :
méthode java
Code C :
void bad_character_rule(char *pattern, int pattern_length, int *bad_char) { int i; for (i = 0; i <no_of_chars; i++) bad_char[i]="-1;" for (i="0;" i < pattern_length; bad_char[(int) pattern[i]]="i;" } pre> <p>In this example, we first initialize the array to -1 for all characters. We then iterate through the pattern and update the array with the last occurrence of each character in the pattern.</p> <p>Next, we can implement the good suffix rule. We can use an array to store the length of the longest suffix of the pattern that matches a suffix of the data or text. This array can be used to determine how far we need to move the pattern to the right.</p> <hr></no_of_chars;>