Algorithme naïf de correspondance de chaînes en Python : exemples, en vedette, avantages et inconvénients

Lorsqu'il est nécessaire de trouver un modèle d'entrée dans une chaîne de caractères, les codeurs et les programmeurs utilisent l'algorithme de correspondance de chaîne. Habituellement, dans le cas d'une chaîne courte, les programmeurs Python préfèrent utiliser l'approche naïve dans laquelle le programme vérifie chaque position dans la chaîne d'entrée pour le modèle de requête. En cas de correspondance, il donne une sortie avec le numéro de position.

L'une des principales raisons pour lesquelles l'algorithme de correspondance de chaînes naïf est utilisé est qu'il est rapide et donne des résultats assez précis. De plus, il ne nécessite pas de pré-traitement. Dans tous les cas, nous discuterons de ces avantages ultérieurement dans cet article. Commençons par comprendre l'algorithme de recherche de motifs utilisant l'approche naïve.

Algorithme de recherche de modèle naïf

Dans la recherche naïve de motif de chaîne, le programme teste la position du motif d'entrée P [1……i] dans une chaîne de caractères T [1…..m].

Notez que la longueur du texte ou de la chaîne d'entrée sera toujours supérieure ou égale à celle du motif.

Voici l'algorithme de recherche de modèle naïf pour différents langages de programmation.

Commencer

pat = patron Taille

str = taille de la chaîne

pour i = 0 à (str – pat), faire

pour j = 0 to pat, do

si texte[i+j] ≠ motif[j], alors

rompre la boucle

terminé

si j == pat, alors

afficher la position de i comme modèle trouvé

terminé

Finir

Cet algorithme est assez important en informatique, car il permet de donner des résultats de recherche en sortie.

Lire : Types d'algorithmes d'IA que vous devez connaître

Exemples de correspondance de chaîne naïve sur Python

Voici un exemple où l'approche de recherche de modèle naïf est utilisée dans un code de python.

# Programme Python pour Naive String Matching

# Algorithme de recherche

def recherche(P, T):

X = len(P)

Y = len(T)

# Une boucle pour décaler P[] un par un */

pour i dans la plage (X - Y + 1):

j = 0

# Pour l'index courant i, cochez

# pour la correspondance de motif */

pour j dans la plage (0, X):

si (txt[i + j] ! = P[j]) :

Pause

si (j == X – 1) :

print ("Motif trouvé à la position ", i)

#Code conducteur

si __nom__ == '__main__' :

T = "UPGRADUBUPGRAABUPGRADEDU"

P = "MISE À NIVEAU"

recherche(P, T)

Sortie :

Motif trouvé à la position 0

Motif trouvé à la position 17

Explication : La première position est la 0 ème position. Puisque le motif "UPGRAD" a été repéré pour la première fois ici, la sortie a montré que le motif se trouve à la position 0.

De même, le motif suivant a été trouvé à la position 17.

Meilleur cas de recherche de modèle naïf

Il n'y a qu'un seul meilleur cas pour l'algorithme de recherche de modèle naïf, contrairement aux deux pires cas.

Le meilleur cas se produit lorsque le premier caractère du texte du modèle n'est nulle part dans la chaîne d'entrée.

Exemple:

T [] = "UPGRADEDUHIJKLUPGRA" ;

P [] = "TUPGRA" ;

Et par conséquent, le nombre de cas de motifs correspondants est O(n).

Pire cas de recherche de modèle naïf

Il existe deux pires cas dans l'approche de recherche de chaîne naïve.

1. Lorsque tous les caractères du modèle sont identiques à ceux de la chaîne d'entrée.

T [] = "EEEEEEEEEEEEEEE" ;

P [] = "EEE" ;

1. Lorsque seul le dernier caractère du modèle diffère de la chaîne d'entrée.

T [] = "EEEEEEEEEED" ;

P [] = "EEEED" ;

Dans de tels cas, le nombre de comparaisons en O(m*(n-m+1)).

Fonctionnalités de l'algorithme de correspondance de chaînes naïves

L'algorithme de correspondance de chaînes est destiné à trouver toutes les occurrences d'un motif donné dans un texte.

Voici les principales caractéristiques de l'algorithme.

1. C'est la méthode la plus simple parmi toutes pour rechercher des modèles dans un texte d'entrée. Il vérifie tous les caractères un par un dans la chaîne de caractères donnée.
2. Il trouve les correspondances de chaîne exactes - qu'il s'agisse d'occurrences plus ou plus exactes du modèle.
3. Il est plus utilisé lorsqu'il y a un petit texte. De plus, il ne nécessite aucune phase de pré-traitement.
4. Cette méthode de recherche n'occupe pas d'espace supplémentaire pour travailler et rechercher les modèles dans la chaîne.

Lisez aussi : Structure de données et algorithme en Python

Avantages de la recherche de modèles naïfs

1. Aucune phase de prétraitement n'est requise dans l'approche de recherche naïve, car son temps d'exécution est égal au temps de correspondance.
2. Aucun espace de fonctionnement supplémentaire n'est nécessaire.
3. Les comparaisons des modèles avec les chaînes peuvent être faites dans n'importe quel ordre.

Inconvénients de la correspondance de chaîne naïve

Il n'y a qu'un seul inconvénient de l'approche naïve de correspondance de chaînes, c'est qu'elle est inefficace. En effet, lorsqu'il a trouvé une position, il ne l'utilise plus pour retrouver l'autre position. Il revient au point de départ et cherche à nouveau le motif. Ainsi, il n'utilise plus les informations de l'équipe précédente.

Conclusion

L'algorithme naïf de correspondance de chaînes est l'approche la plus préférée pour trouver les positions desdits modèles dans un texte donné pour diverses raisons comme aucune exigence de prétraitement, pas d'espace supplémentaire pour l'opération, etc. Cependant, il ne peut pas être utilisé pour des textes plutôt volumineux car de son inefficacité pour effectuer de grandes opérations plus rapidement.

Nous espérons que cet article vous a donné une bonne idée de l'approche de recherche de modèle naïve en python. Pour en savoir plus sur les utilisations de cette approche et avoir une compréhension plus large du sujet, contactez les experts d'upGrad. Nous avons des cours spécialement conçus pour les personnes qui cherchent à élargir leurs compétences. Contactez-nous aujourd'hui!

Si vous souhaitez en savoir plus sur l'IA, l'apprentissage automatique, consultez le diplôme PG en apprentissage automatique et IA de IIIT-B & upGrad, conçu pour les professionnels en activité et offrant plus de 450 heures de formation rigoureuse, plus de 30 études de cas et missions, Statut d'ancien de l'IIIT-B, plus de 5 projets de synthèse pratiques et aide à l'emploi avec les meilleures entreprises.