void sa_init() ( sz = last = 0 ; st[ 0 ] .len = 0 ; st[ 0 ] .link = - 1 ; ++ sz;

Enfin, nous présentons l'implémentation de la fonction main - qui ajoute le caractère suivant à la fin de la ligne actuelle, reconstruisant la machine en conséquence :

void sa_extend (char c) ( int cur = sz++ ; st[ cur].len = st[ last].len + 1 ; int p; for (p= last; p! = - 1 && ! st[ p].next .count (c) ; p= st[ p].link ) st[ p] .next [ c] = cur; if (p == - 1 ) st[ cur].link = 0 else ( int q = st [ p].next [ c] ; if (st[ p].len + 1 == st[ q].len ) st[ cur].link = q; = st[ p].len + 1 ; st[ clone].next = st[ q].next ; st[ clone].link = st[ q].link ; pour (; p! = - 1 && st[ p ] .next [ c] == q; p= st[ p].link ) st[ p].next [ c] = clone st[ q].link = st[ cur] .link = clone =cur;

Comme mentionné ci-dessus, si vous sacrifiez de la mémoire (jusqu'à , où est la taille de l'alphabet), vous pouvez alors atteindre le temps de construction de l'automate même pour n'importe lequel - mais pour cela, vous devrez stocker un tableau de taille dans chaque état (pour rechercher rapidement une transition par la lettre souhaitée) et une liste de toutes les transitions (pour contourner ou copier rapidement toutes les transitions).

Propriétés supplémentaires de l'automate suffixe Nombre d'états Le nombre d'états dans un automate de suffixe construit pour une chaîne de longueur ,

La preuve en est l'algorithme décrit ci-dessus (puisque initialement l'automate se compose d'un état initial, exactement un état est ajouté aux première et deuxième étapes, et à chacune des étapes restantes, deux sommets pourraient être ajoutés en raison de la division des états).

Cependant, cette évaluation facile à montrer même sans connaissance de l'algorithme. Rappelons que le nombre d'états est égal au nombre de valeurs différentes des ensembles. De plus, ces ensembles forment un arbre selon le principe « le sommet parent contient des sous-ensembles de tous les enfants ». Regardons cet arbre et transformons-le un peu : tant qu'il a un sommet interne avec un fils, cela signifie que ce fils ne contient pas au moins un nombre du parent ; puis nous créerons un sommet virtuel égal à ce nombre et attribuerons ce fils au parent. En conséquence, nous obtiendrons un arbre dans lequel chaque sommet interne a un degré supérieur à un et le nombre de feuilles ne dépasse pas . Par conséquent, il n’y a que des sommets dans un tel arbre.

Nous avons donc montré cette estimation de manière indépendante, sans connaissance de l’algorithme.

Il est intéressant de noter que cette estimation ne peut être améliorée, c'est-à-dire existe test dans lequel il est atteint. Ce test ressemble à ceci :

Lors du traitement de cette ligne, à chaque itération, à partir de la troisième, l'état sera divisé, et ainsi l'estimation sera réalisée.

Nombre de transitions

Le nombre de transitions dans un automate de suffixe construit pour une chaîne de longueur , Nombre d'états Le nombre d'états dans un automate de suffixe construit pour une chaîne de longueur ,

Prouvons Ce.

Estimons le nombre de transitions continues. Considérons un arbre couvrant les chemins les plus longs de l'automate commençant dans l'état . Ce squelette sera constitué uniquement d'arêtes solides, ce qui signifie que leur nombre est inférieur d'un au nombre d'états, c'est-à-dire ne dépasse pas .

Estimons maintenant le nombre de transitions non continues. Considérons chaque transition non continue ; que la transition actuelle soit la transition par symbole. Associons-le à la chaîne , où la chaîne correspond au chemin le plus long depuis l'état initial vers , et au chemin le plus long depuis vers un état terminal. D'une part, toutes ces lignes pour toutes les transitions non continues seront différentes (puisque les lignes ne sont formées que par des transitions continues). D'un autre côté, chacune de ces chaînes, par définition de l'état terminal, sera un suffixe de la chaîne entière. Étant donné que la ligne n'a que des suffixes non vides et que, de plus, la ligne entière ne peut pas être contenue parmi ces lignes (puisque la ligne entière correspond à un chemin d'arêtes pleines), alors le nombre total de transitions non continues ne dépasse pas .

En additionnant ces deux estimations, nous obtenons l'estimation. Cependant, en gardant en tête que le nombre maximum d'états n'est atteint que sur un test de la forme , et que l'estimation n'est clairement pas obtenue sur celui-ci, nous obtenons l'estimation finale, ce que nous devions prouver.

Il est intéressant de noter qu'il existe également test sur lequel cette évaluation est réalisée:

Connexion avec l'arbre des suffixes. Construire un arbre de suffixes à partir d'un automate de suffixes et vice versa

Démontrons deux théorèmes établissant la connexion mutuelle entre un automate à suffixes et un arbre à suffixes.

Réservons tout de suite que l'on considère que la chaîne d'entrée est telle que chaque suffixe a son propre sommet dans l'arbre des suffixes (car pour les chaînes arbitraires ce n'est, en général, pas vrai : par exemple, pour la chaîne ). Ceci est généralement réalisé en ajoutant un caractère spécial (généralement représenté par un signe dollar) à la fin de la chaîne.

Pour plus de commodité, nous introduisons les notations suivantes : - ceci est une chaîne écrite dans l'ordre inverse, - ceci est un automate de suffixes construit pour la chaîne, - ceci est un arbre de suffixes de la chaîne.

Présentons le concept lien d'extension: fixe le sommet de l'arbre des suffixes et le symbole ; puis le lien qui s'étend mène au sommet de l'arbre correspondant à la rangée (si ce chemin se termine au milieu d'une arête, alors on tracera un lien vers l'extrémité inférieure de cette arête) ; s'il n'existe aucun chemin de ce type dans l'arborescence, alors le lien d'extension n'est pas défini. D’une certaine manière, les liens d’extension sont à l’opposé des liens de suffixe.

Théorème 1. L'arbre formé par les liens suffixes dans est un arbre suffixe.

Théorème 2. est un graphique de liens d'extension d'arbre de suffixes. De plus, les arêtes solides dans sont des liens de suffixe inversés dans .

Ces deux théorèmes permettent à l'une des structures (un arbre de suffixes ou un automate de suffixes) d'en construire une autre dans le temps - nous considérerons ces deux algorithmes simples ci-dessous dans les théorèmes 3 et 4.

Pour plus de clarté, nous présentons un automate de suffixes avec son arbre de liens de suffixes et l'arbre de suffixes correspondant pour la chaîne inversée. Par exemple, prenons la ligne .

Et son arbre de liens de suffixes (pour plus de clarté, nous étiquetons chaque état avec sa -string) :

:

Lemme. Les trois instructions suivantes sont équivalentes pour deux sous-chaînes et :

Sa preuve est assez évidente : si les débuts des occurrences de deux chaînes coïncident, alors une chaîne est un préfixe de l'autre, ce qui signifie qu'une chaîne se trouve dans l'arbre des suffixes sur le chemin de l'autre chaîne.

Preuve du théorème 1.

En termes de chaîne inversée, cela signifie que le lien suffixe pointe vers le préfixe le plus long de la chaîne correspondant à l'état de sorte qu'un état distinct corresponde à ce préfixe. En d’autres termes, le lien suffixe mène à l’ancêtre du nœud dans l’arbre des suffixes, ce que nous devions prouver.

Preuve du théorème 2.

Les états de l’automate des suffixes correspondent aux sommets de l’arbre des suffixes.

Considérons une transition arbitraire dans un automate à suffixe. La présence de cette transition signifie qu'il s'agit d'un état dont la classe d'équivalence contient la sous-chaîne . Dans une chaîne inversée, cela signifie qu'il s'agit de l'état auquel correspond la sous-chaîne, à partir duquel (dans le texte) correspond la sous-chaîne .

Cela signifie simplement que :

La première partie du théorème a été prouvée ; il reste à prouver la deuxième partie : que toutes les transitions continues dans l'automate correspondent à des liens suffixes dans l'arbre. Une transition continue diffère d'une transition non continue en ce que, c'est-à-dire après avoir attribué un symbole, nous nous retrouvons dans un état avec une chaîne qui est le maximum de la classe d'équivalence de cet état. Cela signifie que lorsque nous avons calculé le lien d'extension correspondant, nous sommes allés directement au sommet de l'arbre, plutôt que de descendre jusqu'au sommet de l'arbre le plus proche. Ainsi, après avoir attribué un caractère au début, nous sommes arrivés à un autre sommet de l'arbre - ce qui signifie que s'il s'agit d'un lien suffixe inversé dans l'arbre.

Le théorème est complètement prouvé.

Théorème 3. Ayant un automate de suffixes, vous pouvez construire un arbre de suffixes dans le temps.

Théorème 4. Étant donné un arbre de suffixes, il est possible de construire un automate de suffixes dans le temps.

Preuve du théorème 3.

L'arbre des suffixes contiendra autant de sommets qu'il y a d'états dans , et le sommet de l'arbre issu de l'état de l'automate correspond à une chaîne de longueur .

Selon le théorème 1, les arêtes de l'arbre sont formées sous forme de liens de suffixes inversés, et les étiquettes d'arc peuvent être trouvées sur la base de la différence des états, et en connaissant en outre pour chaque état de l'automate n'importe quel élément de son ensemble (cet élément de l'automate). l’ensemble peut être maintenu lors de la construction de l’automate).

Ainsi, avec le temps, nous pouvons créer une arborescence de suffixes avec les liens de suffixes qu'elle contient.

(Si nous considérons que la taille de l’alphabet n’est pas une constante, alors la reconstruction complète prendra du temps.)

Preuve du théorème 4.

Un automate à suffixe contiendra autant d’états qu’il y a de sommets dans . Pour chaque état, sa chaîne la plus longue correspondra au chemin inversé depuis la racine de l’arbre jusqu’au sommet.

D’après le théorème 2, pour construire toutes les transitions dans un automate à suffixes, nous devons trouver tous les liens d’extension.

Tout d’abord, notez que certains de ces liens d’extension sont directement dérivés de liens de suffixe dans l’arborescence. En fait, si pour un sommet nous considérons son lien suffixe, cela signifie que nous devons tracer un lien s'étendant de à jusqu'au premier caractère de la ligne correspondant au sommet.

Cependant, de cette façon, nous ne trouverons pas tous les liens d’extension. De plus, vous devez parcourir l'arbre des suffixes des feuilles à la racine, et pour chaque sommet, parcourir tous ses enfants, pour chaque fils, parcourir tous les liens d'extension et copier ce lien vers le sommet si le lien du sommet n'a pas encore été créé. été trouvé par ce symbole :

Ce processus prendra du temps si l’on considère que la taille de l’alphabet est constante.

Ainsi, l’algorithme décrit construit au fil du temps un automate de suffixes à partir d’un arbre de suffixes pour une chaîne inversée.

(Si l'on considère que la taille de l'alphabet est également une valeur variable, alors l'asymptotique augmentera jusqu'à .)

Applications en résolution de problèmes

Ci-dessous, nous examinerons quels problèmes peuvent être résolus à l'aide d'une machine à suffixes.

Vérification des événements

Condition. Étant donné un texte, les requêtes sont reçues sous la forme : étant donné une chaîne, vous devez vérifier si la chaîne est incluse dans le texte en tant que sous-chaîne ou non.

Asymptotiques. Prétraitement Et par demande.

Solution. Construisons un automate de suffixe basé sur du texte dans le temps .

Comment répondre à une demande maintenant. Soit l'état actuel une variable, initialement il est égal à l'état initial. Nous suivrons les caractères de la chaîne, effectuant la transition de l'état actuel au nouvel état en conséquence. Si, à un moment donné, il n'y avait pas de transition depuis l'état actuel en utilisant le symbole requis, alors la réponse à la demande est « non ». Si nous étions capables de traiter la chaîne entière, alors la réponse à la requête est « oui ».

Il est clair que cela fonctionnera avec le temps . De plus, l'algorithme recherche en fait la longueur du préfixe le plus long trouvé dans le texte - et si les échantillons d'entrée sont tels que ces longueurs sont petites, alors l'algorithme fonctionnera beaucoup plus rapidement sans traiter la chaîne entière.

Nombre de sous-chaînes différentes

Condition. Étant donné une chaîne. Vous devez connaître le nombre de sous-chaînes différentes.

Asymptotiques. .

Solution. Construisons un automate de suffixe basé sur la chaîne.

Dans un automate à suffixe, toute sous-chaîne d'une chaîne correspond à un chemin dans l'automate. Puisqu’il ne peut y avoir de lignes répétitives dans un automate, la réponse au problème est nombre de chemins différents dans un automate commençant au sommet initial .

Considérant qu'un automate à suffixe est un graphe acyclique, le nombre de chemins différents qu'il contient peut être compté à l'aide de la programmation dynamique.

Plus précisément, soit le nombre de chemins distincts partant de l'état (y compris un chemin de longueur nulle). Alors c'est vrai :

ceux. peut être exprimé comme la somme des réponses pour toutes les transitions possibles depuis l’État.

La réponse au problème sera la valeur (une est soustraite pour ignorer la sous-chaîne vide).

Longueur totale des différentes sous-chaînes

Condition. Étant donné une chaîne. Vous devez connaître la longueur totale de toutes ses différentes sous-chaînes.

Asymptotiques. .

Solution. La solution au problème est similaire à la précédente, seulement maintenant il faut calculer deux quantités en dynamique : le nombre de sous-chaînes différentes et leur longueur totale.

ceux. nous prenons la réponse pour chaque sommet et y ajoutons, attribuant ainsi, pour ainsi dire, un caractère au début de chaque ligne.

Lexicographiquement k-ème sous-chaîne

Condition. Étant donné une chaîne. Nous recevons des demandes de nombres et nous devons trouver la ème sous-chaîne d'une chaîne dans l'ordre de tri.

Asymptotiques. par requête (où est la réponse à cette requête, est la taille de l'alphabet).

Solution. La solution à ce problème repose sur la même idée que les deux problèmes précédents. Une sous-chaîne lexicographiquement ième est un chemin lexicographique ième dans une machine à suffixes. Par conséquent, en comptant le nombre de chemins qui en partent pour chaque état, nous pouvons facilement rechercher le ème chemin, en partant de la racine de l'automate.

Plus petit décalage cyclique

Condition. Étant donné une chaîne. Il est nécessaire de trouver son décalage cyclique lexicographiquement le plus petit.

Asymptotiques. .

Solution. Construisons un automate de suffixe pour la chaîne. Ensuite, cet automate contiendra tous les décalages cycliques de la chaîne sous forme de chemins.

Par conséquent, la tâche se résume à trouver un chemin de longueur lexicographiquement minimal dans l'automate, ce qui se fait de manière triviale : on part de l'état initial et on agit à chaque fois avec avidité, en parcourant la transition avec le symbole minimum.

Nombre d'occurrences

Condition. Étant donné un texte, les requêtes sont reçues sous la forme : étant donné une chaîne, vous devez savoir combien de fois la chaîne apparaît dans le texte en tant que sous-chaîne (les occurrences peuvent se chevaucher).

Asymptotiques. Prétraitement Et par demande.

Solution. Construisons un automate de suffixe basé sur du texte.

Ensuite, nous devons effectuer le prétraitement suivant : pour chaque état de la machine, calculer le nombre égal à la taille de l'ensemble. En fait, toutes les lignes correspondant à un même état apparaissent le même nombre de fois, égal au nombre de positions dans l'ensemble.

Cependant, nous ne pouvons pas explicitement prendre en charge les ensembles pour tous les états, nous apprendrons donc à compter uniquement leurs tailles.

Pour ce faire, nous procéderons de la manière suivante. Pour chaque état, s'il n'a pas été obtenu par clonage (et on ne prend pas non plus en compte l'état initial), on attribuera dans un premier temps . Ensuite, nous passerons en revue tous les états par ordre décroissant de leur longueur et transmettrons la valeur actuelle via le lien suffixe :

On fait valoir qu'en fin de compte, nous calculerons les valeurs correctes pour chaque état.

Pourquoi est-ce vrai ? Le nombre total d'états non obtenus par clonage est exactement , et le -ème d'entre eux est apparu lorsque nous avons ajouté les premiers caractères. Par conséquent, pour chacun de ces états on associe cette position, au cours du traitement de laquelle elle est apparue. Par conséquent, au départ, chacun a un tel état, et tous les autres états en ont .

1. 1. Université d'État de Khakass. N.F. Katanova Structures et algorithmes pour le traitement des données Cours : Recherche de sous-chaînes.
2. Nikolaï Grebenshikov, www.grebenshikov.ru
3. 2. Problèmes sur les chaînes Application principale : biologie moléculaire computationnelle (décodage de l'ADN).
4. Recherchez des modèles internes. Par exemple, créer une arborescence de préfixes.< x - w является префиксом строки x, то есть ∃y ∈ Σ∗, что x = wy. w = x - w является суффиксом строки x, то есть ∃y ∈ Σ∗, что x = yw. 3
5. Recherchez des modèles privés. Par exemple, recherche d'une sous-chaîne, distance de conversion, plus grande sous-séquence commune, correspondance d'expression régulière.
6. Recherchez des modèles caractéristiques. Par exemple, rechercher plusieurs sous-chaînes.
7. 1
8. 3. Recherche de sous-chaînes Donné : Texte sous la forme d'un tableau T et un échantillon sous la forme d'un tableau P, où m ≤ n. Les éléments des tableaux P et T sont des symboles de l'alphabet fini Σ. On dit que P se produit dans T avec un décalage s si 0 ≤ s ≤ n − m et T = P. Rechercher : tous les décalages autorisés avec lesquels le motif P apparaît dans le texte T.
9. 2
10. 10. Algorithme de Rabin-Karp h(P) - échantillon de hachage. (s : h(P) = h(T) ∧ 0 ≥ s ≥ n − m) est l'ensemble des décalages admissibles. Notons ts = h(T ), alors ts+1 = (d(ts − T g) + T ) mod q, où g ≡ dm−1(mod q) 9
11. 11. Algorithme de Rabin-Karp 10
12. 12. Algorithme de Rabin-Karp 11
13. 13. Problème de l'algorithme de Rabin-Karp De l'égalité h(P) = ts il ne s'ensuit pas que P = T. La solution est de vérifier les shift s par comparaison caractère par caractère.
14. 12
15. 15. Analyse de l'algorithme de Rabin-Karp Dans le pire des cas, T (n, m) = Θ(m) + Θ((n − m + 1)m). Pourquoi? En général, T (n, m) = O(n) + O(m(v + n/q)), où v est le nombre de décalages autorisés et q est le module de la fonction de hachage. Si v = O(1) ∧ q ≥ m ⇒ T (n, m) = O(m + n) = O(n), puisque n≥m 14
16. 16. Automates finis M = (Q, q0, A, Σ, δ) Q - ensemble fini d'états, q0 ∈ Q - état initial, A ⊆ Q - ensemble fini d'états admissibles, Σ - alphabet d'entrée fini, δ - transition fonction Q × Σ → Q. 15
17. 17. Machines à états finis φ - fonction d'état final. φ() = q0 φ(wa) = δ(φ(w), a) pour w ∈ Σ∗, a ∈ Σ 16< P ∧ |Pk | = k - суффиксная функция Пример, P = ab, σ() = 0, σ(ccaca) = 1, σ(ccab) = 2. Правила построения автомата: 1. Q = {0, 1, . . . m}, q0 = 0, A = m 2. δ(q, a) = σ(Pq a) 17
18. 18. Machine finie pour rechercher des sous-chaînes σ(x) = max(k : Pk = x), où Pk
19. 19. Machine à états pour l'échantillon P = ababaca 18
20. 20. Algorithme de recherche d'une sous-chaîne à l'aide d'un automate fini 19
21. 21. Algorithme de calcul de la fonction de transition 20
22. 22. Analyse de l'utilisation de machines à états finis pour rechercher une sous-chaîne Calcul de la fonction de transition - T (n, m) = O(m3|Σ|). Il existe des algorithmes - T (n, m) = O(m|Σ|) Recherche de sous-chaînes - T (n, m) = Θ(n) 21
23. 23. Pour les séminaires et les résumés Recherchez la plus grande séquence commune.
24. Algorithmes de recherche de sous-chaînes : Knuth-Morris-Pratt, Boyer-Moore, Demelka-Baze-Yats-Gonnet, Boyer-Moore-Hospool, Boyer-Moore-Sunday, Boyer-Moore-Gelil.

Algorithmes de calcul de la distance mm entre lignes : Wagner-Fischer, Heshberg, Hunt-Schimansky, Ukkonen-Myers.

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 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) = (Р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 changer 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 les 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é...

Par définition, un automate fini est un quintuplet M = (Q, q 0 , A,), où :

Q est un ensemble fini d’états ;

q 0 Q -- état initial ;

AQ est un ensemble fini d’états acceptants ;

Alphabet d'entrée final ;

Fonction Q x 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 A, alors la partie lue de la ligne est rejetée.

A l'état final M est associée une fonction appelée fonction d'état final, définie comme suit : il existe un état auquel l'automate arrivera (à partir de 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 :

· Son ensemble d'états est Q = (0,1,..., m). L'état initial est q 0 = 0. Le seul état autorisé est m ;

· La fonction de transition est définie par la relation (q -- état, -- symbole) : (q,a) = (P q a). (1)

Expliquons cette relation. Il faut construire un automate de telle sorte que lorsqu'il agit sur la chaîne T la relation

é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é.

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 un 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,a)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é (obscurci). 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 du modèle. Les flèches allant de droite à gauche représentent les échecs : le caractère saisi suivant est différent du caractère suivant dans le modèle.

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.

Établissement d'enseignement public d'enseignement professionnel supérieur

"Université humanitaire d'État de Viatka"

Faculté d'informatique

Département d'informatique et méthodes d'enseignement de l'informatique

Cours

Algorithmes de recherche d'une sous-chaîne dans une chaîne

Complété

Étudiant de 3ème année de la Faculté de Mathématiques
Belov Denis Vladimirovitch

Vérifié par un enseignant du Département d'informatique et méthodes d'enseignement de l'informatique
Ivanov S. Yu.

Kirov, 2006

Introduction. 3

Partie 1. Informations théoriques sur les algorithmes de recherche d'une sous-chaîne dans une chaîne. 5

1.1. Notions de base. 5

1.1.1 Chaîne, sa longueur, sous-chaîne. 5

1.1.2. Le concept de complexité des algorithmes. 6

1.2. Algorithmes basés sur la méthode de recherche séquentielle. 7

1.2.1. Algorithme de recherche séquentielle (directe) (The Brute Force Algorithm). 7

1.2.2. L'algorithme de Rabin. 7

1.3. Algorithme de Knuth-Morris-Pratt (KMP). 10

1.4. Algorithme de Boyer – Moore et certaines de ses modifications. 13

1.4.1. Algorithme de Boyer-Moore. 13

1.4.2. Modifications du MB. 15

1.5. Recherche de sous-chaînes à l'aide d'une machine à états finis. 17

1.5.1. La structure de la machine. 17

1.5.2. Un exemple de construction d'une machine à états finis. 19

Partie 2. Analyse expérimentale des algorithmes. 21

2.1. L'essence de l'expérience. 21

2.2. Résultats et analyse de l'expérience. 22

Conclusion. 24

Liste bibliographique. 25

Introduction

Ceux qui doivent souvent travailler avec des éditeurs de texte connaissent l'intérêt de la fonction de recherche des mots justes dans le texte, ce qui facilite grandement l'édition de documents et la recherche des informations nécessaires. En effet, les programmes de traitement de texte modernes nous ont appris la commodité de rechercher et de remplacer des fragments, et si vous développez un tel programme, l'utilisateur est en droit d'attendre que vous lui fournissiez les commandes appropriées.

Bien entendu, les fonctions de recherche sont désormais encapsulées dans de nombreux langages de programmation de haut niveau - pour rechercher une ligne dans un petit texte, vous utilisez probablement une fonction intégrée. Mais si ce type de recherche est la tâche clé de votre programme, il sera très utile de connaître les principes d'organisation des fonctions de recherche. En même temps. Dans les sous-programmes prêts à l'emploi, tout n'est pas toujours écrit de la meilleure façon. Premièrement, les fonctions standards n'utilisent pas toujours les algorithmes les plus efficaces, et deuxièmement, il est fort possible que vous deviez modifier le comportement standard de ces fonctions (par exemple, offrir la possibilité de rechercher par modèle). Enfin, la portée de la fonction de recherche ne se limite pas aux seuls éditeurs de texte. A noter l'utilisation d'algorithmes de recherche lors de l'indexation des pages par un robot de recherche, où la pertinence des informations dépend directement de la rapidité de recherche des mots-clés dans le texte de la page html. Le travail du filtre anti-spam le plus simple consiste à trouver des expressions telles que « Million en une heure » ​​ou « Promotion du site » dans le texte de la lettre. Tout ce qui précède indique la pertinence du problème abordé par le travail.

Définissons la tâche de trouver une sous-chaîne dans une chaîne. Disons une chaîne composée d'un certain nombre de caractères. Nous devons vérifier si une autre chaîne donnée est incluse dans le texte donné, et si oui, à partir de quel caractère du texte.

Dans ce travail, nous nous sommes fixés pour objectif d'identifier l'algorithme le plus optimal qui résout le problème de recherche.

Objectifs de ce travail :

· considérer les algorithmes de base qui résolvent le problème de recherche ;

· systématiser les algorithmes selon les techniques utilisées;

· identifier les algorithmes efficaces en termes de temps d'exécution.

L'ouvrage comprend deux parties principales. La première considérera les algorithmes, leurs fondements théoriques, leur modèle algorithmique et une tentative de les classer. La deuxième partie du travail fournira des données sur l'application pratique des algorithmes. En conclusion, une conclusion sera tirée sur l'algorithme le plus efficace (d'un point de vue temporel).

Partie 1. Informations théoriques sur les algorithmes de recherche d'une sous-chaîne dans une chaîne.

1.1. Notions de base.

1.1.1 Chaîne, sa longueur, sous-chaîne.

Nous fournissons ici un certain nombre de définitions que nous utiliserons pour présenter le matériel.

Définition 1 . Une chaîne (mot) est une séquence de caractères (appelés lettres) provenant d’un ensemble fini appelé alphabet.

Définition 2. Longueur de ligne – le nombre de caractères dans la ligne.

On désignera les mots par des lettres de l'alphabet latin, par exemple. X=xx…x[n] est un mot de longueur n, où x[i] (i-ième lettre du mot) appartient à l'alphabet. Longueur(X)=

Définition 3. Un mot qui ne contient pas une seule lettre est dit vide.

Un mot vide est généralement désigné par la lettre L. Longueur(L)=0.

Définition 4. Un mot X est appelé préfixe d'un mot Y s'il existe un mot Z tel que Y=XZ. De plus, le mot lui-même est un préfixe pour lui-même (puisqu'il existe un mot nul L tel que X = LX.

Exemple: Le mot ab est un préfixe du mot abcfa.

Définition 5. Un mot X est appelé suffixe d'un mot Y s'il existe un mot Z tel que Y=ZX. De même, un mot est un suffixe de lui-même.

Exemple: Le mot bfg est un suffixe du mot vsenfbfg.

Définition 6 Un mot X est appelé sous-chaîne d'une chaîne Y s'il existe des chaînes Z 1 et Z 2 telles que Y=Z 1 XZ 2 . Dans ce cas, Z 1 est appelé l'aile gauche et Z 2 l'aile droite de la sous-chaîne. Le mot lui-même peut être une sous-chaîne. Parfois, le mot X est appelé une occurrence dans le mot Y. Parmi toutes les occurrences du mot X dans le mot Y, l'occurrence avec la plus petite longueur de son aile gauche est appelée la première ou l'occurrence principale. Pour désigner une occurrence, utilisez la notation X

Exemple: les mots hrf et fhr sont des sous-chaînes des mots abhrfhr, gf

1.1.2. Le concept de complexité des algorithmes.

Le but de notre travail est de trouver un algorithme efficace, mais rien n’a encore été dit sur la méthode d’évaluation des algorithmes.

Traditionnellement en programmation, la notion de complexité des algorithmes est associée à l'utilisation des ressources informatiques : combien de temps processeur le programme nécessite-t-il pour son exécution, et quelle quantité de mémoire machine consomme-t-il ? La comptabilité de la mémoire est généralement effectuée en fonction de la quantité de données et ne prend pas en compte la mémoire consommée pour l'écriture des commandes du programme. Le temps est calculé en unités relatives afin que cette estimation soit, si possible, la même pour des machines ayant des fréquences d'horloge différentes.

Dans ce travail, deux caractéristiques de la complexité des algorithmes seront considérées : le temps et la capacité. Nous ne discuterons pas de la complexité logique du développement d'un algorithme - combien de « jours-homme » doivent être consacrés à la création d'un programme, car il n'est pas possible de donner des caractéristiques quantitatives objectives.

Nous calculerons la complexité temporelle des commandes exécutables : le nombre d'opérations arithmétiques, le nombre de comparaisons, de transferts (selon l'algorithme). La complexité capacitive sera déterminée par le nombre de variables, d'éléments de tableau, d'éléments d'enregistrement ou simplement par le nombre d'octets.

L'efficacité de l'algorithme sera également évaluée en calculant le temps nécessaire à l'algorithme pour accomplir une tâche spécifique, c'est-à-dire en utilisant une expérience, nous en parlerons davantage dans la partie 2 de ce travail.

1.2. Algorithmes basés sur la méthode de recherche séquentielle.

1.2.1. Algorithme de recherche séquentielle (directe) (The Brute Force Algorithm).

L'algorithme le plus évident. Soit S le mot dans lequel le modèle X est recherché. Soit m et n les longueurs des mots S et X, respectivement. On peut comparer avec le mot X tous les sous-mots de S qui commencent aux positions 1,2,...,m-n+1 dans le mot S ; en cas d'égalité, la position correspondante est affichée (Listing 1).

Très simple, mais très imprudent. Après tout, le nombre maximum de comparaisons sera égal à O((m-n+1)*n+1), bien que la plupart d'entre elles soient en réalité inutiles. Par exemple, après avoir trouvé la chaîne aabc et trouvé une incohérence dans le quatrième caractère (seul aab correspond), l'algorithme continuera à comparer la chaîne en commençant par le caractère suivant, même si cela ne conduira certainement pas à un résultat.