Travail de cours : Algorithmes de recherche de sous-chaînes dans une chaîne. Résultats et analyse de l'expérience. Algorithme de recherche directe
L'application la plus typique d'une telle tâche est la recherche documentaire : un fonds de documents constitué d'une séquence de références bibliographiques est donné, chaque référence est accompagnée d'un « descripteur » indiquant le sujet de la référence correspondante. Nous devons retrouver quelques mots-clés trouvés parmi les descripteurs. Il pourrait y avoir, par exemple, une requête sur « Programmation » et « Java ». Une telle requête peut être interprétée comme suit : existe-t-il des articles contenant les descripteurs « Programmation » et « Java ».
La recherche d'une chaîne est formellement définie comme suit. Soit un tableau T de N éléments et un tableau W de M éléments, et 0
Algorithme de recherche directe
Idée d'algorithme :
1. je = 1,
2. comparer le premier caractère du tableau T avec le premier caractère du tableau W,
3. match → comparer les deuxièmes caractères et ainsi de suite,
4. inadéquation → I:=I+1 et passer au point 2,
Condition de fin de l'algorithme :
1. M comparaisons consécutives réussissent,
2. I+M>N, c'est-à-dire que le mot n'a pas été trouvé.
Complexité de l'algorithme :
Dans le pire des cas. Soit le tableau T→(AAA….AAAB), longueur │T│=N, échantillon W→(A….AB), longueur │W│=M. Évidemment, trouver une correspondance à la fin d’une chaîne nécessitera environ N*M comparaisons, c’est-à-dire O(N*M).
Inconvénients de l'algorithme :
1. complexité élevée - O(N*M), dans le pire des cas – Θ((N-M+1)*M) ;
2. après une incompatibilité, la recherche commence toujours à partir du premier caractère du modèle et peut donc inclure T caractères qui ont été précédemment consultés (si la chaîne est lue depuis la mémoire secondaire, ces retours prennent beaucoup de temps) ;
3. les informations sur le texte T obtenues lors du contrôle d'un quart de travail donné S ne sont en aucun cas utilisées lors du contrôle des quarts de travail suivants.
Algorithme de D. Knuth, D. Maurice et W. Pratt (recherche KMP)
L'algorithme de recherche KMP ne nécessite en réalité qu'environ N comparaisons, même dans le pire des cas.
Exemple.
(Les personnages comparés sont soulignés.) 
Après une correspondance partielle de la partie initiale de l'image W avec les caractères correspondants de la chaîne T, nous connaissons effectivement la partie parcourue de la chaîne et pouvons « calculer » certaines informations (basées sur l'image W elle-même), à l'aide de que nous pouvons ensuite parcourir rapidement dans le texte.
L'idée de la recherche KMP est que pour chaque décalage entre deux caractères de texte et une image, l'image est décalée de toute la distance parcourue, car des décalages plus petits ne peuvent pas conduire à une correspondance complète.
Caractéristiques de la recherche KMP :
1. un ordre de comparaisons de symboles (N+M) est nécessaire pour obtenir le résultat ;
2. Le système de recherche KMP ne donne une véritable victoire que lorsque l'échec a été précédé d'un certain nombre de correspondances. Ce n'est que dans ce cas que l'image se décale de plus d'un. Malheureusement, les coïncidences sont beaucoup moins fréquentes que les décalages. Par conséquent, le gain de la recherche KMP dans la plupart des cas de textes est très insignifiant.
Algorithme de R. Bowyer et D. Moore (recherche BM)
En pratique, l’algorithme de recherche BM est plus efficace si l’échantillon W est long et que la puissance alphabétique est suffisamment grande.
L'idée de la recherche BM est que la comparaison des caractères commence à la fin de l'échantillon, et non depuis le début, c'est-à-dire que la comparaison des caractères individuels s'effectue de droite à gauche. Ensuite, à l’aide d’une procédure heuristique, la quantité de décalage vers la droite s est calculée. Encore une fois, les caractères sont comparés en commençant par la fin du motif.
Cette méthode améliore non seulement la gestion du pire des cas, mais offre également des avantages dans les situations intermédiaires.
Presque toujours, à l'exception d'exemples spécialement construits, la recherche BM nécessite beaucoup moins que N comparaisons. Dans les circonstances les plus favorables, lorsque le dernier caractère de l'échantillon tombe toujours sur un caractère non correspondant du texte, le nombre de comparaisons est égal à (N/M), dans le pire des cas - O((N-M+ 1)*M+ p), où p est la puissance de l'alphabet.
Algorithme de Rabin-Karp (recherche RK)
Soit l'alphabet D=(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), c'est-à-dire que chaque caractère de l'alphabet est un chiffre ré-aire, où d=│D│.
Exemple. Laissez l'échantillon avoir la forme W = 3 1 4 1 5
On calcule les valeurs des nombres à partir d'une fenêtre de longueur |W|=5 mod q, q est un nombre premier.
23590(mod 13)=8, 35902(mod 13)=9, 59023(mod 13)=9, …
k1=314157(mod 13) – occurrence de l'échantillon,
k2=673997(mod 13) – fonctionnement au ralenti.
De l'égalité ki= kj (mod q) il ne résulte pas que ki= kj (par exemple, 31415=67399(mod 13), mais cela ne signifie pas que 31415=67399). Si ki= kj (mod q), alors nous devons encore vérifier si les chaînes W et T coïncident réellement.
Si le nombre premier q est suffisamment grand, le coût supplémentaire lié à l’analyse des déclencheurs inactifs sera faible.
Dans le pire des cas, le temps de fonctionnement de l'algorithme RK est Θ((N-M+1)*M), mais en moyenne il fonctionne assez rapidement - en temps O(N+M).
Exemple : combien d'opérations inactives k l'algorithme RK effectuera-t-il si
q= 11, 13, 17. Soit W=(2 6) 
26 mod 11=4 → k =3 opérations inactives,
26 mod 13=0 → k =1 fonctionnement au ralenti,
26 mod 17=9 → k =0 opérations inactives.
Il est évident que le nombre d'opérations inactives k est fonction de la valeur du nombre premier q (si la fonction de traitement de l'échantillon est mod q) et, dans le cas général, du type de fonction de traitement de l'échantillon W et du texte T.
Recherche rapide (Classification Thierry Lecroq).
Le mauvais décalage de caractères utilisé dans l'algorithme de Bowyer-Moore n'est pas très efficace pour un petit alphabet, mais lorsque la taille de l'alphabet est grande par rapport à la longueur du motif, comme c'est souvent le cas avec
Table ASCII et recherches normales dans un éditeur de texte, cela devient extrêmement utile. Utiliser uniquement celui-ci dans un algorithme peut être très efficace.
Après une tentative de combinaison de x et y , la longueur du décalage est d'au moins 1. Ainsi, le symbole y [ i + m ] sera certainement impliqué dans la prochaine tentative, ce qui signifie qu'il peut être utilisé dans la tentative en cours pour décaler le mauvais symbole. Modifions la fonction bad symbol pour prendre en compte le dernier symbole x :
bc[ a ] = min ( j | 0 j m et x[ m - 1 - j ] = a ), si a apparaît dans x,
bc[ a ] = m dans le cas contraire.
Les comparaisons entre le texte et l’échantillon peuvent être effectuées dans n’importe quel ordre.
T
Liste 6
Urbo BM (Classement Thierry Lecroq).
Turbo - BM est également une amélioration de l'algorithme Bowyer - Moore. Nous nous souviendrons du segment de texte qui correspondait au suffixe échantillon lors de la dernière tentative (et seulement si un bon suffixe a été décalé).
Cela nous apportera deux avantages :
1. Capacité à sauter par-dessus ce segment
2. Possibilité d'utiliser le « turbo shift »
Un « turbo shift » peut se produire si nous découvrons que le suffixe de motif qui correspond au texte est plus court que celui précédemment mémorisé.
Soit u le segment mémorisé et v le suffixe correspondant lors de l'essai en cours, tel que uzv soit le suffixe de x. Alors av est un suffixe de x, deux caractères a et b apparaissent à une distance p dans le texte, et le suffixe x de longueur |uzv| a une période de longueur p, ce qui signifie qu'il ne peut pas couvrir les deux apparitions des caractères a et b dans le texte. Le plus petit décalage possible a une longueur |u| - |v| (nous appelons cela « changement turbo »).
1.5. Recherche de sous-chaînes à l'aide d'une machine à états finis.
1.5.1. La structure de la machine.
Par définition, un automate fini est un cinq M = (Q, q 0 , A, 
,
), Où:
Q est un ensemble fini d’états ;
q 0 
Q - état initial ;
UN 
Q est un ensemble fini d’états acceptants ;
Alphabet d'entrée final ;
Fonction Qx 
Q, appelée fonction de transition de l'automate.
Initialement, la machine à états est dans l'état q 0 . Il lit ensuite les caractères de la chaîne d'entrée un par un. Étant dans l'état q et lisant le symbole a, l'automate passe à l'état (q,a). Si la machine est dans l'état q A on dit qu'elle accepte une partie de la chaîne d'entrée à lire. Si q 
Et puis la partie lue de la ligne est rejetée.
La fonction associée à l'état final M est 
, appelée fonction d'état final, définie comme suit : 
il existe un état auquel l'automate viendra (depuis l'état initial) après avoir lu la chaîne w. L'automate admet la chaîne w si et seulement si A
Pour chaque échantillon P, vous pouvez construire un automate fini qui recherche ce modèle dans le texte. La première étape dans la construction d'un automate correspondant à une chaîne de modèles P consiste à construire une fonction de suffixe auxiliaire à partir de P (comme dans l'algorithme KMP). Nous définissons maintenant une machine à états correspondant au modèle P comme suit :
Expliquons cette relation. Il faut construire un automate de telle manière que lorsqu'il agit sur la chaîne T la relation
(T je) = 
(Ti)
était un invariant (alors l'égalité (T i) = m équivaudra au fait que P entre dans T avec un décalage i - m, et l'automate trouvera ainsi tous les décalages admissibles). Cependant, dans ce cas, le calcul de la transition à l'aide de la formule (1) est nécessaire pour maintenir la vérité de l'invariant, qui découle des théorèmes donnés ci-dessous.
Théorème. Soit q = (x), où x est une chaîne. Alors pour tout symbole a nous avons (xa) = (P q a).
Théorème. Soit la fonction d'état final de l'automate pour rechercher la sous-chaîne P. Si T est un texte arbitraire, alors (T i) = (T i) pour i=0,1,..., n.
De ce qui précède, il s'ensuit que la tâche de recherche d'une sous-chaîne se compose de deux parties :
construire un automate basé sur un modèle (déterminer la fonction de transition pour un modèle donné) ;
utiliser cette machine pour rechercher des occurrences d'un modèle dans un texte donné.
1.5.2. Un exemple de construction d'une machine à états finis
Construisons une machine finie qui accepte la chaîne ababaca. Puisque la longueur de l’échantillon est m = 7 symboles, la machine aura m + 1 = 8 états.
Trouvons la fonction de transition. Conformément à la définition (1), (q, a) = (P q a), où est une fonction préfixe, a est un caractère arbitraire de l'alphabet, q est le numéro d'état. Ainsi, il faut pour chaque préfixe P q = P, q = 0 .. m de l'échantillon P et pour tous les symboles a de l'alphabet d'entrée trouver la longueur du préfixe maximum P, qui sera le suffixe de la chaîne P q une. La longueur de ce préfixe sera la valeur de la fonction de transition (q,a). Si a = P (le caractère suivant du texte coïncide avec le caractère suivant de l'échantillon), alors P q a = P q +1 et (q, a) = q+1.
Ce cas correspond à des étapes de recherche réussies. Sinon, q. Par exemple, pour le préfixe P = ababa et le caractère b, le suffixe maximum de la chaîne Pb = ababab, qui est aussi un préfixe P, sera abab. Sa longueur est de 4, donc la valeur de la fonction de transition (5, b) = 4.
Écrivons la fonction de transition ainsi construite sous forme de tableau (tableau 1) :
Les lignes correspondent aux symboles d'entrée, les colonnes aux états de la machine. Les cellules correspondant aux étapes de recherche réussies (le caractère saisi correspond au caractère suivant dans l'échantillon) sont surlignées en gris.
À l'aide du tableau, nous allons construire un graphe de transition pour un automate (Fig. 1) qui reconnaît le modèle ababaca. Étant dans l'état q et après avoir lu le symbole suivant a, la machine passe à l'état (q,a). Veuillez noter que son squelette est marqué d'exemples de symboles (ces transitions sont mises en évidence par des flèches en gras).
Ici 0 est l'état initial, 7 est le seul état autorisé (noirci). Si une flèche marquée de la lettre a mène du sommet i au sommet j, alors cela signifie que (i,a) = j. Notez que les transitions pour lesquelles (i,a) = 0 ne sont pas indiquées sur le graphe de transition pour le simplifier. Les flèches en gras allant de gauche à droite correspondent aux étapes réussies de recherche de la sous-chaîne P - le caractère saisi suivant correspond au caractère suivant de l'échantillon. Les flèches allant de droite à gauche correspondent aux échecs - le symbole d'entrée suivant diffère du symbole suivant dans le motif.
Ci-dessous le résultat de l'application de la machine au texte T = abababacaba. Sous chaque symbole T[g] est inscrit l'état de la machine après lecture de ce symbole (c'est-à-dire la valeur (T i)) (Tableau 2).
Une occurrence du modèle trouvé (à partir de la position 3). L'échantillon trouvé est marqué en gris dans le texte. L'état permissif de la machine (numéro d'état 7) est marqué en noir.
Partie 2. Analyse expérimentale des algorithmes.
2.1. L'essence de l'expérience.
Nous avons examiné plusieurs algorithmes et évalué leur complexité en termes de temps et de capacité. Cependant, comme déjà mentionné, ces critères d’évaluation ne permettent pas de dire avec certitude quel algorithme fonctionnera le plus rapidement. Par conséquent, pour une évaluation supplémentaire, nous procéderons à leur analyse expérimentale, c'est-à-dire Mesurons le temps nécessaire à l'algorithme pour accomplir une tâche spécifique.
Il existe plusieurs fichiers texte contenant 10 000 entrées du formulaire :
doubler
sous-chaîne (disponible dans une chaîne donnée)
lieu d'entrée
longueur de la sous-chaîne
avec différentes longueurs maximales de chaînes et de sous-chaînes.
L'alphabet se compose de 66 lettres majuscules et minuscules russes.
Qu'il s'agisse de lignes ne dépassant pas 10, 100, 250 caractères.
Recherchons des sous-chaînes dans les chaînes pour chacun des algorithmes et mesurons le temps d'exécution du programme. Ce faisant, nous prendrons en compte les éléments suivants :
Les lignes sont préchargées dans la RAM (sous forme de tableau), et le temps de lecture dans le tableau n'est pas pris en compte. Le prétraitement (création de tables de transition) est inclus dans le temps total.
Chaque algorithme est exécuté 5 fois, le temps le plus court est sélectionné.
Stand d'expérimentation.
Processeur Intel Pentium IV 2,66 GHz
1024 Mo de RAM
Compilateur Borland Delphi Enterprise, version 6.0 (Build 6.163)
Un fragment de code du programme testé est donné dans le listing 7.
Il est clair qu'une telle mesure du temps nous donnera des résultats très vagues, puisqu'elle dépend directement des caractéristiques et de la charge du processeur. Par conséquent, au cours de l'expérience, toutes les applications tierces et en arrière-plan qui n'affectent pas le fonctionnement du programme ont été désactivées. Lors de l'exécution de la même tâche, nous pouvons obtenir des temps différents, donc plusieurs exécutions sont effectuées, parmi lesquelles le meilleur résultat est sélectionné.
2.2. Résultats et analyse de l'expérience.
L'expérience a été réalisée pour quatre algorithmes - représentants de classes d'algorithmes. Tous les algorithmes ayant été placés dans les mêmes conditions, il est possible d’en faire une analyse comparative. Veuillez noter que cette analyse n'est applicable que pour ces paramètres de recherche et peut différer dans d'autres conditions.
Résultats de l'expérience Mettons-le dans le tableau (tableau 3).
Comme prévu, l'algorithme de Boyer-Moore a accompli la tâche expérimentale plus rapidement que les autres. Il convient toutefois de noter que son efficacité n’augmente qu’avec l’augmentation de la longueur de la ligne et, par conséquent, de la longueur de l’échantillon. Ainsi, lorsque la longueur de la chaîne est inférieure ou égale à 10 caractères, les résultats sont moins bons que la recherche séquentielle. L'algorithme KMP montre des résultats similaires pour les mots courts et longs. Il peut être utilisé comme universel lorsque les longueurs de chaîne et de motif sont inconnues.
L'algorithme de Rabin, malgré sa similitude avec l'algorithme séquentiel, fonctionne plus rapidement, et sa simplicité et ses faibles coûts de main-d'œuvre pour sa mise en œuvre le rendent attrayant pour une utilisation dans des programmes non spéciaux.
Le pire résultat a été montré par l’algorithme de recherche séquentielle. Comme prévu, avec seulement une légère augmentation de la longueur de la chaîne, il fonctionne plusieurs fois plus lentement que les autres algorithmes.
Cette expérience n'inclut pas d'algorithme de recherche utilisant une machine à états finis, car Nous utilisons un alphabet composé de 66 lettres de l’alphabet russe et la machine construite serait trop volumineuse. L'efficacité de cet algorithme augmente avec un petit nombre de lettres dans l'alphabet.
Conclusion.
Nous avons examiné différents algorithmes de recherche d'une sous-chaîne dans une chaîne et les avons analysés. Les résultats peuvent être présentés dans un tableau (Tableau 4).
|
Algorithme |
Heure précédente |
traitement |
Temps de recherche moyen |
Pire temps de recherche |
Coûts de mémoire |
Temps d'exécution (ms) avec une longueur de ligne ≤250 |
|
Remarques |
||||||
|
Algorithmes basés sur l'algorithme de recherche séquentielle |
Algorithme de recherche directe |
O((m-n+1)*n+1)/2 |
||||
|
Faibles coûts de main-d'œuvre pour le programme, faible efficacité. |
||||||
|
L'algorithme de Rabin |
||||||
|
Algorithme de Knuth-Morris-Pratt |
||||||
|
Algorithme universel si la longueur de l'échantillon est inconnue |
||||||
|
Algorithme de Boyer-Moore |
||||||
Les algorithmes de ce groupe sont plus efficaces dans les situations ordinaires. Les performances augmentent à mesure que le motif ou l’alphabet augmente.
Ayant tiré cette conclusion, nous avons rempli le but de ce travail, car Pour différentes classes de problèmes, notre propre algorithme efficace a été identifié.
Liste bibliographique.
1). Kurtz, St. Algorithmes fondamentaux pour un système de correspondance de modèles déclaratif [Texte]. – Bielefeld :. Université de Bielefeld, 1995. – 238 p.
2). Lecro, T. Algorithmes de correspondance exacte de chaînes [Ressource électronique]. Mode d'accès http://algolist.manual.ru/
3). Akhmetov I. Recherche de sous-chaînes à l'aide de machines à états finis [Texte] : Travaux de cours - SP Université d'État des technologies de l'information, de la mécanique et de l'optique.
4). Aho, Alfred Structure des données et algorithmes [Texte]. – M. : Maison d'édition Williams, 2000. - 384 p.
5). Belousov A. Mathématiques discrètes [Texte]. – M. : Maison d'édition MSTU im. N.E. Bauman, 2001. – 744 p.
6). Brian, K. Pratique de la programmation [Texte]. - Saint-Pétersbourg :. Dialecte Nevski, 2001. - 381 p.
7). Wirth, N. Algorithmes et structures de données [Texte]. Mir, 1989. – 360 p.
8). Gil, Art. Introduction à la théorie des automates finis [Texte]. – M., 1966. - 272 p.
9). Glushakov S. Programmation de pages Web [Texte]. – M. : AST Publishing House LLC, 2003. – 387 p.
10). Knuth, D. L'art de la programmation informatique [Texte] : Volume 3. – M :. Mir, 1978. – 356 p.
11). Sailor D. Éléments d'algèbre abstraite et informatique : Manuel. aide aux étudiants universités pédagogiques [Texte]. – M. : Centre d'édition « Académie », 2004. – 240 p.
12). Uspensky V. Théorie des algorithmes : principales découvertes et applications [Texte]. – M. : Nauka, 1987. – 288 p.
13). Shen, A. Programmation : théorèmes et problèmes [Texte]. – M. : Centre de Moscou pour la formation continue en mathématiques, 1995.
14). Kormen, T. Algorithmes : construction et analyse [Texte] / T. Kormen, Ch. Leiserson, R. Rivest - M. : MTsNMO, 2002. M. : MTsNMO, 2002.
Machine abstraite Mili
Synthèse abstraite 1. Sélection du nombre de déclencheurs. Étant donné que la machine a 5 états, q=]log25[=3 déclencheurs sont requis. 2. Codage des états internes d'entrée...
Algorithmes de recherche d'une sous-chaîne dans une chaîne
Construisons une machine à états finis qui accepte la chaîne ababaca. Puisque la longueur de l’échantillon est m = 7 symboles, la machine aura m + 1 = 8 états. Trouvons la fonction de transition. Conformément à la définition (1), (q, a) = (Рqа), où est la fonction préfixe...
Langage lexical et analyseur de haut niveau
La table de contrôle de l'analyseur lexical pour la grammaire spécifiée ci-dessus est présentée dans le tableau 2. La liste du programme qui implémente cette table de contrôle est donnée en annexe A...
Implémentation Lisp de machines à états finis
Une machine à états finis est une abstraction mathématique de la théorie des algorithmes qui permet de décrire des manières de modifier l'état d'un objet en fonction de son état actuel et des données d'entrée, à condition...
Recherche d'informations sur Internet
Une machine à états finis est une machine abstraite sans flux de sortie, dont le nombre d'états possibles est fini. Le résultat du fonctionnement de la machine est déterminé par son état final. Il existe différentes options pour spécifier une machine à états finis. Par exemple...
Application de la programmation automatique dans la pratique réelle
Il est pratique de décrire les automates à l’aide de tableaux et d’utiliser des graphiques pour plus de clarté. Lors de la description d'un tableau, deux tableaux sont spécifiés...
Synthèse d'une machine à états finis pour un dispositif de contrôle informatique
Le schéma fonctionnel généralisé de la machine à états finis KA (Fig. 1) contient un dispositif de stockage (mémoire sur les déclencheurs T1-Tn) et deux dispositifs combinatoires KU pour générer des signaux q1, q2,......
Un automate fini non déterministe est un quintuple A=(Q,V,M,S,Z), où Q est l'ensemble (alphabet) des états internes ; V - alphabet d'entrée ; M - fonction de transition...
Synthèse d'une machine de reconnaissance finie
Un automate fini déterministe est le quintuplet A=(Q,V,M,S,Z), où Q est l'alphabet des états ; V - alphabet d'entrée ; M - fonction de transition (Q*VP(Q)) ; S - état initial ; Z - ensemble d'états finaux ; SZ. Dans cette machine...
Synthèse d'une machine de reconnaissance finie
Un programme qui simule le fonctionnement d'une machine à états finis assure la distinction entre les chaînes autorisées et non autorisées. Les chaînes de caractères sont saisies à partir du clavier de l'ordinateur, le programme de distinction des chaînes dispose à la fois d'une fonction automatique...
La procédure pour construire un automate non déterministe à l'aide d'une grammaire d'automate : 1. L'ensemble d'entrée de l'automate sera l'ensemble terminal de la grammaire ; 2. L'ensemble des états de l'automate sera l'ensemble non terminal de la grammaire...
Synthèse d'une machine de reconnaissance
La procédure de passage d'un automate non déterministe à un automate déterministe : Désignations : AD - automate déterministe AN - automate non déterministe 1...
Méthode tabulaire de synthèse structurelle de machines à états finis
Pour spécifier un automate fini S, il est nécessaire de spécifier un ensemble de cinq objets : S (A, X, Y, d, d), où A = (a0,a1,a2,.,an) est l'ensemble des objets internes états de l'automate, X = (x1, x2,…, xm) - ensemble de signaux d'entrée (alphabet d'entrée), Xi est une lettre de l'alphabet d'entrée, Y = (y1, y2...
Equivalence et minimisation des machines à états finis
Différentes machines à états peuvent fonctionner de la même manière même si elles ont un nombre d’états différent. Une tâche importante est de trouver une machine à états finis minimale qui implémente un mappage d'automate donné...