Wikipédia

Algorithme de recherche de sous-chaîne

trouver une chaîne de caractères à l'intérieur d'une autre chaîne.
(Redirigé depuis Algorithmes de recherche de sous-chaîne)

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Consultez la liste des tâches à accomplir en page de discussion.

En informatique, plus précisément en algorithmique du texte, le problème de recherche de sous-chaîne (en anglais string-matching problem[1]) consiste à trouver une chaîne de caractères dans un texte. Le problème de recherche d'une sous-chaîne intervient dans beaucoup d'applications. Par exemple, dans un logiciel de traitement de texte, ou dans un navigateur Web, l'utilisateur peut rechercher une chaîne de caractères dans un document, ou une page Internet[2], en vue de remplacer un mot par un autre (par exemple, remplacer toues les occurrences du mot "rêve" par le mot "songe").

Illustration de la recherche de la sous-chaîne "longs des" dans la première strophe du poème Chanson d'automne de Paul Verlaine.

Il existe plusieurs algorithmes pour rechercher une chaîne dans un texte, comme l'algorithme naïf ou force brute (cf. p. 35 dans [1]), l'algorithme de Boyer-Moore ou encore l'algorithme de Knuth-Morris-Pratt. Ce sont des algorithmes de recherche.

La plupart des langages de programmation proposent des fonctions pour effectuer une telle recherche ; par exemple en Python, on écrit chaine in texte pour tester si la chaîne apparaît dans le texte. Par extension, on peut considérer aussi le problème de trouver toutes les occurrences d'un mot, ou alors de compter le nombre d'occurrences d'une chaîne dans un texte.

Algorithme naïf pour la recherche d'un motif

modifier

L'algorithme naïf est présenté dans plusieurs livres d'algorithmique[3],[4] ainsi que dans des livres spécialisés en algorithmique du texte[1].

Principe

modifier
L'algorithme naïf fait glisser le motif "longs des" le long du texte, d'un caractère à chaque fois. On compare le motif avec la portion de texte correspondante. On s'arrête quand le motif est trouvé.

L'algorithme naïf fait glisser le motif le long du texte[3] en le déplaçant d'une lettre à chaque fois jusqu'à avoir trouvé le motif. Au début, le motif est aligné avec le début du texte. Par exemple si l'on cherche le motif longs des dans le texte les sanglots longs des violons de l'automne blessent mon cœur d'une langueur monotone on démarre avec l'alignement suivant : 

les sanglots longs des violons de l'automne blessent mon cœur d'une langueur monotone.
longs des

On compare les caractères du motif avec le début du texte. Le premier caractère est l. Mais les deuxièmes caractères différent. On déplace alors le motif d'une lettre vers la droite : 

les sanglots longs des violons de l'automne blessent mon cœur d'une langueur monotone.
 longs des

On compare les caractères du motif et le texte à partir du second caractère. Les premiers caractères e et l sont différents. On continue donc à glisser le motif. 

les sanglots longs des violons de l'automne blessent mon cœur d'une langueur monotone.
  longs des   
   longs des  
    longs des
     longs des
      longs des
       longs des
        longs des
         longs des
          longs des
           longs des
            longs des

Au 14e alignement, les caractères coïncident : 

les sanglots longs des violons de l'automne blessent mon cœur d'une langueur monotone.
             longs des

Comme tous les caractères correspondent, on renvoie la position du premier caractère de la chaîne trouvée dans la chaîne initiale. Si jamais nous avons glissé le motif jusqu'à la fin du texte, mais que l'alignement ne coïncidait jamais, alors l'algorithme échoue. Dans certaines implémentations[Par exemple ?], l'algorithme retourne -1.

Pseudo-code

modifier

On note |m| le nombre de caractères dans m. On suppose que les indices dans les chaînes de caractères commencent à 0. Voici le pseudo-code de l'algorithme naïf : 

entrée : un motif m, un texte
sortie : la position du motif m dans le texte; ou -1 si le motif ne s'y trouve pas
fonction rechercherNaïve(m, texte)
       pour tout i = 0 à |texte| - |m| - 1
              si m = texte[i, i+|m|-1] alors
                      renvoie i
       renvoie -1

Analyse

modifier

La complexité temporelle est Θ(|texte|*|m|). Plus précisément, l'algorithme effectue |m|(|texte| - |m| - 1) comparaisons dans le pire cas[3]. Ce pire cas arrive par exemple si l'on cherche le motif aa..ab dans un texte aa..aa, comme : 

texte :            aaaaaaaaaaaaaaaaaaaaaaa
motif à chercher : aaaaab

En effet, à chaque position de la fenêtre glissante du motif, on réalise |m| comparaisons de caractères et il y a (|texte| - |m| - 1) positions différentes. Dans le meilleur des cas[3], on ne fait qu'une seule comparaison pour chaque position de fenêtre et dans ce cas on fait |texte| - |m| - 1 comparaisons.

Toutefois, pour un algorithme de plus de deux lettres, et si la distribution sur les lettres est indépendante et uniforme, alors le nombre moyen de comparaisons de caractères pour rechercher un motif avec l'algorithme naïf dans un texte est au plus 2|texte| (voir Proposition 1.1 dans[2]).

Algorithmes pour rechercher un motif

modifier

Il existe plusieurs algorithmes, souvent meilleurs que l'algorithme naïf. Souvent, ces algorithmes vont utiliser des particularités du motif ou du texte avant de faire la recherche, ce que l'on appelle le pré-traitement. Beaucoup d'algorithmes utilisent la même idée de fenêtre glissante du motif dans le texte que l'algorithme naïf. Le schéma général de ces algorithmes sont[2] : 

entrée : un motif m, un texte
sortie : la position du motif m dans le texte; ou -1 si le motif ne s'y trouve pas
fonction rechercherSchemaGeneral(m, texte)
       prétraitement
       i = 0
       tant que i <= |texte| - |m| - 1
              si m = texte[i, i+|m|-1] alors
                      renvoie i
              augmenter i d'une certaine quantité
       renvoie -1

Dans l'algorithme naïf, on décale le motif de une case vers la droite à chaque (i augmente de 1). Dans les algorithmes qui suivent on augmente i plus rapidement. Ce décalage de la fenêtre glissante dépend du motif et du texte. Souvent on peut faire un prétraitement sur le motif pour savoir de combien décaler le motif.

Tableau récapitulatif

modifier
Algorithme Complexité temporelle du prétraitement Complexité temporelle de la recherche[5] Espace utilisé
Algorithme naïf Pas de prétraitement Θ(|texte|+|motif|) en moyenne,

O(|motif|×|texte|)

Algorithme de Rabin–Karp Θ(|motif|) Θ(|motif|) en moyenne,

O(|motif|×|texte|) au pire

O(1)
Algorithme de Knuth–Morris–Pratt Θ(|motif|) Θ(|texte|) Θ(|motif|)
Algorithme de Boyer–Moore Θ(|motif| + |alphabet|) Ω(|texte|/|motif|) au mieux,

O(|motif|×|texte|) au pire

Θ(|alphabet|)[Information douteuse]
Two-way algorithm (en)[6][7] Θ(|motif|) O(|texte|) O(log(|motif|))
Backward Non-Deterministic DAWG (en) Matching (BNDM)[8][9] O(|motif|) Ω(|texte|/|motif|) au mieux,

O(|motif|×|texte|) au pire

Backward Oracle Matching (BOM)[10] O(|motif|) O(|motif|×|texte|)

Rabin-Karp

modifier

Article détaillé - Algorithme de Rabin-Karp.

L'algorithme de Rabin-Karp améliore l'algorithme naïf. Plus précisément, il améliore le test de comparaison du motif avec la portion du texte en utilisant une fonction de hachage.

Boyer-Moore et variantes

modifier

Article détaillé - Algorithme de Boyer-Moore

Article détaillé - Algorithme de Boyer-Moore-Horspool

Article détaillé - Algorithme de Raita

Dans l'algorithme de Boyer-Moore[11] la comparaison m = texte[i, i+|m|-1] s'effectue en faisant des comparaisons de caractères de droite vers la gauche (alors qu'a priori, dans l'algorithme naïf, on effectue des comparaisons de gauche à droite). Puis on augmente la valeur de i de la manière suivante. Soit j l'indice où il y a la première différence, c'est-à-dire tel que j le plus grand avec m[j] différent de t[i+j]. On augmente alors i de j - k, où k est le grand entier tel qu'avec k dans [0, ... j-1] et m[k] = t[i+j] si un tel k existe. S'il n'y a pas de tel k, alors on augmente k de j+1.

Considérons l'exemple où l'on cherche le motif m qui estabracadabra. Supposons que l'on teste l'égalité entre le motif m et texte[i, i+|m|-1]. Pour l'instant, nous avons constaté égalité des 5 dernières lettres de m et texte[i, i+10], à savoir dabra. Par contre, on constate une différence dans la 6e lettre en partant de la fin : il y a un b dans le texte alors qu'il y a un a dans le motif. 

                                  i
texte :                           ?????bdabra????
motif :                           abracadabra

L'algorithme naïf aurait décaler le motif juste d'une case (incrémenter i de un). En image : 

                                   i
texte :                           ?????bdabra????
motif :                            abracadabra               (décalage de 1)

Regardons dans les incrémentations suivantes, la prochaine qui vient placer un b sous le b du texte : 

texte :                           ?????bdabra????
                                   abracadabra               (décalage de 1)
                                    abracadabra              (décalage de 2)
                                     abracadabra             (décalage de 3)
                                      abracadabra            (décalage de 4)

L'algorithme de Boyer-Moore effectue ce décalage de 4 immédiatement, en ayant effectué un prétraitement sur le motif.

Knuth-Morris-Pratt

modifier

Article détaillé - Algorithme de Knuth-Morris-Pratt

Dans l'algorithme de Knuth-Morris-Pratt, le motif et le texte sont comparés lettre à lettre de gauche à droite. En cas de différence de lettres, on considère le début du motif qui coïncide avec la portion de texte. On décale le motif selon le plus long bord de ce début (préfixe propre du début aussi suffixe de ce début). L'algorithme reprend de là et on ne revient jamais en arrière dans le texte.

Shitf-Or/Bitap/Baeza-Yates-Gonnet

modifier

Article détaillé - Algorithme de Baeza-Yates-Gonnet

Z-Algorithm

modifier

Article détaillé - Algorithme Z

Recherche de plusieurs motifs

modifier

Les algorithmes de cette section font un pré-traitement sur le texte T ou les motifs multiples P_i d'entrée afin de comparer les multiples P_i à une portion de texte une seule fois. Quelques exemples classiques sont la détection de plagiat ou la comparaison d'un fichier suspect à des fragments de virus.

Rabin-Karp

modifier

Article détaillé - Algorithme de Rabin-Karp.

L'algorithme de Rabin-Karp se généralise à la recherche de plusieurs motifs en utilisant un filtre de Bloom[12].

Aho-Corasick

modifier

Article détaillé - Algorithme d'Aho-Corasick.

L'algorithme d'Aho-Corasick généralise l'algorithme de Knuth-Morris-Pratt à la recherche simultanée de plusieurs motifs (voir p. 367, Section 10.3 dans[13],[12]). Pour l'algorithme d'Aho-Corasick la fonction préfixe devient arborescente et est défini sur un trie.

Implémentations

modifier

La Glibc[14] implémente l'algorithme Two-way. Le compilateur gcc propose l'algorithme naïf pour les systèmes qui ne proposent pas d'implémentation pour strstr[15].

L'outil grep implémente l'algorithme de Boyer-Moore[16].

Discussions

modifier

Texte

modifier
Cette section ne cite pas suffisamment ses sources (mai 2023). 
Pour l'améliorer, ajoutez des références de qualité et vérifiables (comment faire ?) ou le modèle {{Référence nécessaire}} sur les passages nécessitant une source.

Il existe beaucoup de formats de textes dans lesquels chercher, et en conséquence tous les algorithmes sont susceptibles de connaître de fortes variations suivant le texte fourni.

Par exemple, la taille du texte peut varier de la simple ligne à la concaténation de milliers de livres. L'encodage du texte peut également avoir une influence dramatique sur la performance d'un algorithme. Notamment, des alphabets de type ADN, ASCII ou Unicode peuvent exclure d'office l'utilisation d'un algorithme particulier[pas clair].

Combinaisons et adaptations

modifier

Les algorithmes sus-cités sont académiques. En pratique ils sont fortement adaptés pour répondre aux besoins sur le terrain.

Certaines bibliothèques combinent de multiples algorithmes pour rester dans le meilleur cas de résolution possible. Par exemple stringlib/fastsearch[17] en Python utilise la force brute pour P de longueur 1 et une combinaison de Boyer-Moore-Horspool et Sunday et des filtres de Bloom pour remplacer la table de saut.

Certains programmes tel grep offrent une myriade d'optimisations[18] et sacrifient leur worst-case au best-case[19], en pariant sur le fait que P et T ont une faible probabilité d'engendrer un cas pathologique.

Enfin, les processeurs modernes offrent des jeux d'instructions SIMD particulièrement efficaces tel SSE. Certaines implémentations de libc strstr utilisent ces instructions pour accélérer la recherche.

Notes et références

modifier
  1. ↑ a b et c M. Crochemore and W. Rytter, « Text Algorithms », sur www-igm.univ-mlv.fr, 0-19-508609-0 (consulté le )
  2. ↑ a b et c http://www-igm.univ-mlv.fr/~berstel/Elements/Elements.pdf
  3. ↑ a b c et d Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre, Kim Nguyen, Laurent Sartre, Informatique MP2I/MPI: CPGE 1re et 2e années Cours et exercices corrigés, Ellipse, Chapitre 9, Section 9.5.1 p. 533-535
  4. ↑ Thomas H. Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein, Algorithmique, (lire en ligne)
  5. ↑ Asymptotic times
  6. ↑ Maxime Crochemore et Dominique Perrin, « Two-way string-matching », Journal of the ACM, vol. 38, no 3,‎ , p. 650–674 (DOI 10.1145/116825.116845, S2CID 15055316, lire en ligne [archive du ], consulté le )
  7. ↑ libc
  8. ↑ Gonzalo Navarro et Mathieu Raffinot, Combinatorial Pattern Matching, vol. 1448, Springer Berlin Heidelberg, coll. « Lecture Notes in Computer Science », , 14–33 p. (ISBN 978-3-540-64739-3, DOI 10.1007/bfb0030778), « A bit-parallel approach to suffix automata: Fast extended string matching »
  9. ↑ fuzzy+regexp
  10. ↑ H. Fan, N. Yao et H. Ma, 2009 Fourth International Conference on Internet Computing for Science and Engineering, , 56–59 p. (ISBN 978-1-4244-6754-9, DOI 10.1109/ICICSE.2009.53, S2CID 6073627), « Fast Variants of the Backward-Oracle-Marching Algorithm »
  11. ↑ Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre, Kim Nguyen, Laurent Sartre, Informatique MP2I/MPI: CPGE 1re et 2e années Cours et exercices corrigés, Ellipse, Chapitre 9, Section 9.5.1.1 p. 535-539
  12. ↑ a et b (en) K. Selçuk Candan et Maria Luisa Sapino, Data Management for Multimedia Retrieval, Cambridge University Press, (ISBN 978-1-139-48958-4, lire en ligne)
  13. ↑ « Eléments d'algorithmique (Beauquier et.al.) — Sciencinfolycee », sur wiki.inria.fr (consulté le )
  14. ↑ « str-two-way.h source code [glibc/string/str-two-way.h] - Codebrowser », sur codebrowser.dev (consulté le )
  15. ↑ (en) « gcc/libiberty/strstr.c at master · gcc-mirror/gcc », sur GitHub (consulté le )
  16. ↑ Mike Haertel, « why GNU grep is fast », sur FreeBSD-current mailing list archive,
  17. ↑ « Cpython : 9c6dcb5d8f01 Objects/stringlib/fastsearch.h », sur python.org (consulté le ).
  18. ↑ « Why GNU grep is fast », sur freebsd.org (consulté le ).
  19. ↑ « Kwset.c/src - grep.git », sur gnu.org (consulté le ).

Articles connexes

modifier

Bibliographie

modifier
  • Simone Faro et Thierry Lecroq, « The exact online string matching problem: A review of the most recent results », ACM Computing Surveys, vol. 45, no 2,‎ , article no 13 (42 p.) (DOI 10.1145/2431211.2431212).
  • Simone Faro et Thierry Lecroq, « The Exact String Matching Problem: a Comprehensive Experimental Evaluation », Arxiv,‎ (arXiv 1012.2547). — Version antérieure, et libre, de l'article précédent.

Liens externes

modifier
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Algorithme_de_recherche_de_sous-chaîne&oldid=220682997 ».