Brevet FR2813414A1 — publié le 20020301

La présente invention concerne une méthode de recherche rapide d'un motif dans un texte et fonctionnant dans un automate programmable. Elle a des applications dans la recherche automatisée de séquences particulières de signes dans des textes formés d'une combinaison de signes, l'ensemble des signes formant un alphabet et la séquence particulière à rechercher étant définie par le motif formé d'une combinaison de symboles. Des produits pour mise en oeuvre de la méthode sont également revendiqués. Dans le texte qui suit, les termes motif ou sous-chaîne sont équivalents et correspondent à ce qui est recherché. De même chaîne, texte ou phrase sont équivalents et correspondent à l'objet dans lequel est effectué la recherche. Une phrase peut également être formée d'une combinaison de mots. Enfin, les termes caractère, lettre ou signe sont équivalents et correspondent à des unités élémentaires servant à construire le texte et le motif et dont l'ensemble forme un alphabet. Dans le cadre du fonctionnement des automates programmables et en particulier ceux pouvant manipuler un alphabet du type caractères du type de ceux utilisés pour l'écriture, on connaît des procédés de recherche automatisés de souschaînes de caractères, dans des chaînes de caractères. Dans sa forme la plus simple, le motif est formé d'une suite continue de caractères et l'on compare chacun des caractères du motif avec une portion de la suite de caractères de la chaîne de caractères, chacun des caractères du motif devant être retrouvé dans la chaîne dans sa position relative, le motif balayant la chaîne en se déplaçant d'un caractère à la fois jusqu'à ce qu'une correspondance entre le motif et la portion de chaîne soit retrouvée ou la fin de la chaîne atteinte. Ce type de procédé peut être mis en oeuvre dans tout dispositif automatisé, que ce soit un automate câblé ou programmable et en particulier un dispositif à micro processeur du type micro ordinateur. L'alphabet est alors représenté par des suites de bits, états électriques binaires, dont la taille dépend d'un codage. Ces suites de bits ou "mots machine" peuvent être manipulées dans l'automate qui comporte de la mémoire et des moyens de calcul. Cet alphabet peut aussi bien servir à représenter des phrases dans un langage quelconque, que des sons ou des images, les suites de bits étant de longueur appropriée. Par exemple pour un alphabet servant à représenter des écrits, 8 bits peuvent être utilisés comme par exemple dans le codage dit ASCII ou ses dérivés, le "mot machine" étant alors appelé "octet". Par exemple pour des sons 16 bits ou moins et pour des images noir et blanc 1 bit peuvent être mis en oeuvre. On préfère en général utiliser un nombre de bits qui correspond à une ou des valeurs standards du dispositif et pour lesquels les opérations logiques et/ou arithmétiques sont immédiates. Ce nombre de bits est ainsi généralement de 8, 16,24, 32,64 dans les microprocesseurs et unités de traitement numérique du signal. D'autre part, l'utilisation d'une taille standard permet d'utiliser les possibilités de traitement par parallélisme dans des zones de mémoire ou des registres de l'automate, ces traitements pouvant s'effectuer sur les "mots machine" mais, également lorsque cela est possible, directement sur chaque bit indépendamment des autres. Des stratégies plus ou moins élaborées ont été développées à partir de ce principe de base pour optimiser la recherche et aboutir à des procédés ayant chacun des étapes particulières. Toutefois ces procédés sont encore relativement simples car à chaque signe du motif doit correspondre un seul signe du texte. Il est cependant nécessaire de pouvoir retrouver d'une manière efficiente un motif qui comporte des alternatives de signes pour une position donnée dans le motif. Par exemple dans le cas d'une recherche portant sur des mots dans une écriture occidentale, il peut être nécessaire de pouvoir retrouver le masculin et le féminin d'un même mot. Ainsi, si l'on recherche le mot "nouveau" au masculin ou au féminin, les motifs seront "nouveau" ou "nouvelle". Un premier procédé de recherche consiste donc à effectuer deux recherches du type précédent et de regrouper les résultats. Une seconde stratégie consiste à définir des symboles définissant des alternatives pour une position de signe et permettant de mettre en oeuvre un seul motif et procédé spécifique de recherche utilisant lesdits symboles. Ainsi le symbole pour un sous ensemble de l'alphabet, un tel sous ensemble étant encore appelé liste ou classe, peut être défini par la suite des signes à chercher pour une position donnée, ladite suite étant placée entre crochets. Dans cet exemple, le motif se définira par: [n][o][u][v][e][al][ul][e]. De même il peut être utile d'effectuer la recherche d'un motif dont certain des signes sont séparés par un nombre variable mais prédéfini de caractères quelconques. On peut par exemple être amené à rechercher dans le cas d'une chaîne, des sous chaînes commençant par les deux signes "in" et se terminant par la suite de signes "ion ", et séparés par un nombre minimum a et un nombre maximum b de caractères quelconques de l'alphabet dans la chaîne. Une telle recherche pourra indiquer une correspondance pour, par exemple, "invention", "intention", "involution", "indication"... Un symbole du type x (a,b) être utilisé pour définir une telle recherche. Il est donc possible de définir un motif comportant des symboles définissant soit un sous ensemble de l'alphabet, défini par la suite des signes entre des crochets, pour un signe du texte dans laquelle la recherche de correspondance est effectuée, soit une suite continue bornée d'un nombre de signes quelconques de l'alphabet, ladite suite étant nommée saut borné et notée x (a,b) ledit nombre étant compris entre a et b signes quelconques dans le texte, avec 0 ≤ a Une recherche avec un motif comportant de tels symboles, par exemple [RK]-x(2,3)-[DE]-x(2,3)-[Y], peut être réalisée à partir du procédé précédemment mentionné en décomposant le motif. Toutefois, un tel procédé est peu efficace et on a proposé des procédés plus performants. On connaît ainsi les procédés de recherche par balayage en avant ou en en arrière utilisant des techniques dites "Shift-Or" ou "Shift-And", ou d'autres dont on pourra, par exemple, trouver une description dans l'article en langue anglaise "R. Baesa-Yates, Text retrieval: theory and practice, In 12th IFIP World Computer Congress, Volume I, pages 465-476, Elsevier Science, September 1992". La présente invention propose une nouvelle méthode de recherche qui est globalement plus efficace que les méthodes connues. L'invention concerne donc une méthode de recherche rapide d'un motif P dans un texte T fonctionnant dans un automate, le texte T étant formé d'une suite de n signes élémentaires T1..T n, les signes étant notés génériquement c , l'ensemble des signes élémentaires formant un ensemble E, le motif P étant formé d'un assemblage ordonné de s symboles, P1..Ps, chacun desdits symboles pouvant définir: - soit un sous ensemble C noté [c] de l'ensemble E, l'ensemble vide et l'ensemble lui même étant exclus, - soit une suite continue bornée d'un nombre de signes quelconques de #, ladite suite étant nommée saut borné et notée x (a,b) et ledit nombre étant compris entre a et b signes quelconques, avec 0 ≤ a complémentation notée - , le ET noté &, le OU noté #, le décalage noté , l'addition notée +, la soustraction notée - et la multiplication notée # les étapes de la recherche étant représentées par un graphe formé d'une succession de L états notés S,...,S,,...SL et de liens entre lesdits états, le nombre L correspondant à la longueur maximum de signes d'une correspondance, le statut d'un état i indiquant le résultat de la recherche de correspondance pour la position i étant stocké dans un bit d, d'une zone de mémoire D formée d'un ensemble de bits dL" .d1, ladite zone de mémoire D étant initialisée avant le début de la recherche de correspondance et le balayage. Selon l'invention, dans le cas où, à la suite de l'état S,, le symbole suivant est un saut borné x(a,b), on crée : - b états SI+1'" SI+b; - b liens notés x successivement entre lesdits états ; - b-a transitions #; et qu'il comporte au moins les étapes suivantes: - on crée une première zone de mémoire 1 comportant L bits, on met à 0 l'ensemble des L bits de # puis on met à 1 les bits correspondant aux états d'où partent des transitions #, - on crée une seconde zone de mémoire F comportant L bits, on met à 0 l'ensemble des L bits de F puis on met à 1 les bits correspondant à chacun des états terminaux suivant le dernier recevant une transition #, et en ce que la zone de mémoire D est modifié par D = D #( ( F - ( D & I ) ) & - F). Dans divers modes de mise en oeuvre, les moyens suivants pouvant être combinés selon toutes les possibilités techniquement possibles sont mis en #uvre: # le balayage est effectué en avant, le texte étant balayé à partir de son premier signe T1 et le bit d, de D prend la valeur 1 lorsque PiP2...p, correspond au texte jusqu'au dit état, les L bits de la zone de mémoire D étant initialement mis à 0 par D = 0L,et le procédé comporte en outre au moins une étape dans laquelle si, à la suite de l'état Si, le symbole suivant est un sous ensemble C de #, un nouvel état SI+1 est créé ainsi qu'un lien noté C, et le résultat de la recherche sur le signe t, de T et correspondant audit état S,+1 étant stocké dans D, la zone de mémoire D étant modifié par D = ( (D 1 ) 1 0'-' - 1 ) & B[Tj], que dans le cas où, à la suite de l'état Si, le symbole suivant est un saut borné x(a,b): - les b liens notés x sont successivement placés entre les états Sj à Sj+1 avec j E i...i+b-1; - les b-a transitions s sont placées entre l'état S, et chacun des états SI+1",SI+b-a; - l'état d'où part la première transition s étant notés Sk, l'état terminal correspondant est Sk+b-a+1, et il comporte en outre au moins une étape consistant, dans le cas d'un symbole [c] définissant un sous ensemble de E, à mettre en #uvre dans au moins une zone de mémoire une table B de masquage comportant pour chaque signe c de E un masque B[c] formé de m bits (bL...b1), ledit masque B [c] initialement mis à 0 et le bit bi dudit masque B [c] prenantla valeur 1 seulement si un des signes du sous ensemble défini par le symbole Pi correspond au masque B[c] correspondant au signe c, # le procédé comporte les étapes successives suivantes dans le cas d'une recherche d'un motif P1 m dans un texte Tu nu (a) - on crée une variable L que l'on initialise avec la valeur correspondant au nombre maximum de signes d'une correspondance ; (b) - pour chacun des signes de l'ensemble E on crée et initialise à 0 un masque B[c] comportant L bits; (c) - on crée et initialise à 0 une variable 1 comportant L bits; (d) - on crée et initialise à 0 une variable F comportant L bits; (e) - on crée et initialise à 0 une variable i ; (f) - on crée et initialise à 1 une variable j ; (g) - on effectue le test suivant: si Pj est de la forme x(a,b) on effectue les opérations (gO) suivantes: (gO) = )(1 (i-1)): (gO) F = F I(1 (i+b-a)); (gO) on crée et initialise à i une variable k; (gO) (ga) on effectue les opérations suivante pour chacun des signes c de E: (9) B[c]=B[c] (1 k); (g0) on incrémente k : k=k+1; (g0) on retourne en (ga) si k est inférieur ou égal à i+b- 1; (g0) on incrémente i: i=i+b ; dans le cas contraire correspondant au cas où Pj défini un sous ensemble on effectue les opérations (g1) suivantes : (g1) pour tout signe c appartenant au sous ensemble Pj on effectue l'opération B[c]= B[c] (1 i); (g1) on incrémente i: i=i+1; (h) - on incrémente j : j=j+1 et on retourne en (g) si j est inférieur ou égal à m; (i) - on crée une variable r de L bits que l'on initialise par complémentation de F: r = -F; (j) - on crée une variable M de L bits que l'on initialise par l'opération : M =1 (L-1); (k) - on crée et initialise à 0 la variable D comportant L bits; (I)- on réutilise la variable j que l'on initialise à 1: j =1; (m) - on effectue un test sur le résultat de l'opération D & M: si ce résultat est différent de 0L alors il y a correspondance entre le motif et une portion du texte se terminant à la position j-1; (n)- on effectue une opération modifiant D de telle façon que: D = ( (D 1 ) 1 OL-1 1 ) & B[Tj]; (o)- on effectue une opération modifiant D de telle façon que: D = D 1 ( F - ( D & 1 ) ) & F); (p)- on incrémente j: j= j+1; (q) - on retourne en (m) tant que j est inférieur ou égal à n, # le balayage est effectué en arrière, le texte étant balayé à partir de son dernier signe Tn. # le procédé comporte les étapes successives suivantes dans le cas d'une recherche d'un motif P1 m dans un texte T1 n: (a) - on crée une variable L que l'on initialise avec la valeur correspondant au nombre maximum de signes d'une correspondance ; (b) - on crée une variable , que l'on initialise avec la valeur correspondant au nombre minimum de signes d'une correspondance ; (c) - pour chacun des signes de l'ensemble E on crée et initialise à 0 un premier masque Bf[c] comportant L bits; (d) - pour chacun des signes de l'ensemble 2 on crée et initialise à 0 un premier masque Bb[c] comportant L bits; (e) - on crée et initialise à 0 une variable If comportant L bits; (f) - on crée et initialise à 0 une variable Ff comportant L bits; (g) - on crée et initialise à 0 une variable lb comportant L bits; (h) - on crée et initialise à 0 une variable Fb comportant L bits; (i) - on crée et initialise à 0 une variable i; (j) - on crée et initialise à 1 une variable j ; (k) - on effectue le test suivant: si Pj est de la forme x (a,b) effectue les opérations (kO) suivantes : (k) if= lf (1 (i~1)); (kO) lb= b(1 (L~(i+b)-1)); (kO) Ff = Ff 1 (1 (i+b-a ; (kO) Fb = Fb 1(l (L-i-a ; (kO) on crée et initialise à i une variable k : k=i ; (kO) (ka) on effectue les opérations suivante pour chacun des signes c de E: (kO) Bf[c]=Bf[c] # (1 k); (kO) Bb[C]=Bb[Cl ((1 (L-k-1)); (kO) on incrémente k : k=k+1; (kO) on retourne en (ka) si k est inférieur ou égal à i+b- 1; (kO) on incrémente i : i=i+b ; dans le cas contraire correspondant au cas où Pj défini un sous ensemble on effectue les opérations (k1) suivantes : (k1) pour tout signe c appartenant au sous ensemble Pj on effectue les deux opérations suivante sur Bf: Bf[c] =Bf[c] (1 i) et sur Bb: Bb[c] =Bb[c] (1 (L-i-1 )); (k1) on incrémente i : i=i+1; (I)- on incrémente j : j=j+1et on retourne en (k) si j est inférieur ou égal à m ; (m) - on crée une variable rf de L bits que l'on initialise par complémentation de Ff: rf = -Ff; (n)- on crée une variable rb de L bits que l'on initialise par complémentation de Fb: rb = -Fb; (o)- on crée une variable M de L bits que l'on initialise par l'opération: M =1 (L-1); (p) - on crée et initialise à 0 une variable pos ; (q) - tant que pos est inférieur ou égal à n-I on effectue les opérations (qO) suivantes : (qO) on réutilise la variable j que l'on initialise à À.: j X; (qO) on crée et initialise à 1L la variable Db comportant L bits: Db = 1 ; (qO) tant que Db est différent de 0 et tant que j est supérieur à 0 on effectue les opérations (q1) suivantes : (q1) Db = Db ôc Bb[Tp05+j]; (q1) Db = Db 1 Fb - (Db & b)) & rb); (q1) on décrémente j : j =J-1;(q1) on effectue le test suivant: si Db est différent de 0 et si j est nul alors on effectue les opérations (q2) suivantes: (q2) on crée et initialise à 0L-1 el la variable Df comportant L bits: Df = 0L-1 #1; (q2) on crée et initialise à 1 une variable v ; (q2) tant que Df est différent de 0 et que pos+v est inférieur ou égal à n on effectue les opérations (q3) suivantes : (q3) Of = Of & Bf[T P05+V]; (q3) Df ' Df 1 (( Ff - (Df & f)) & rf); (q3) on effectue un test sur le résultat de l'opération Df & M : si ce résultat est différent de 0L alors il y a correspondance entre le motif et une portion du texte commençant en pos+1 et on réinitialise la variable Df à 0: Df=0L; (q3) on effectue un décalage sur Df: Df = (Df 1); (q3) on incrémente v : v = v+1; (q1) on effectue un décalage sur Db: Db = (Db 1); (qO) on incrémente pos : pos = pos+j+1. #l'ensemble S est un alphabet constitué de signes chacun sous forme d'une donnée binaire formée d'un ensemble d'un nombre de bits (0,1) compris entre 1 et 64 et, de préférence, par un alphabet binaire constitué d'un bit ou par un alphabet ASCII sur 7 bits ou de ses dérivés sur 8 bits, ' le texte utilisant l'alphabet est une image, un son ou un écrit, # l'automate est un ordinateur numérique ou un circuit logique spécialisé. L'invention concerne également un procédé de sélection d'une méthode de recherche rapide d'un motif P dans un texte T fonctionnant dans un automate. Selon le procédé, la méthode est mise en oeuvre selon l'une quelconque des caractéristiques précédentes et l'automate effectue les opérations arithmétiques: Rc = ( G + 1 ) / # avec G le maximum des longueurs de zones de caractères quelconques et , la longueur minimale d'une suite de caractère de la chaîne qui peut correspondre au motif, et si Rc est supérieur à un seuil Rs alors l'automate effectue une recherche avant selon l'une des caractéristiques correspondantes précédentes et que, dans le cas contraire, si Rc est inférieur ou égal à Rs alors l'automate effectue une recherche arrière selon l'une des caractéristiques correspondantes précédentes. Selon un mode de mise en oeuvre du procédé, Rs est approximativement égal à 0,5. L'invention concerne également un produit "programme d'ordinateur" chargeable directement dans la mémoire interne d'un ordinateur numérique, comprenant des portions de code de logiciel pour l'exécution des étapes de la méthode selon les caractéristiques précédentes lorsque ladite méthode est exécutée dans un automate qui est un ordinateur. L'invention concerne également un produit "programme d'ordinateur" enregistré sur un support utilisable dans un ordinateur, comprenant des moyens de programmation lisibles par ordinateur pour mettre en #uvre par un ordinateur la méthode selon les caractéristiques précédentes lorsque ladite méthode est exécutée dans un automate qui est un ordinateur. L'invention concerne également un produit "configuration logique de circuit" sur un support utilisable pour la fabrication d'un circuit logique spécialisé, ledit circuit étant destiné à mettre en oeuvre la méthode selon les caractéristiques précédentes lorsque ladite méthode est exécutée dans un automate qui est un circuit logique spécialisé. La présente invention est donc applicable dans des dispositifs automatisés, aussi bien en logique câblée que programmable, par exemple du type à microprocesseur, à la recherche de motifs formés de symboles dans des textes, ou plus généralement des structures, formés de signes élémentaires, les symboles définissant des sous ensembles de l'ensemble des signes élémentaires ou définissant un saut dans la recherche. Ces structures peuvent donc être du texte, c'est ce terme qui sera choisi par la suite sans toutefois limiter l'invention, les signes élémentaires étant alors un alphabet ou sa représentation codée dans le dispositif automatisé. Ces structures peuvent aussi être des images, les signes élémentaires étant alors réduits à un bit (0,1), l'image et le motif étant alors constitués de suites de bits. Dans le cas d'une image, les signes élémentaires peuvent être un "alphabet" plus complexe et par exemple correspondre à des combinaisons d'un nombre déterminé de bits. Par exemple si les signes élémentaires sont formés de 4 bits, "l'alphabet" de l'image sera alors composé de 16 signes élémentaires. Plus généralement la présente invention est applicable à toute structure d'information formée à partir d'un "alphabet" et qui peut être manipulée dans un dispositif automatisé. Par exemple, dans le cas de la génétique, l'alphabet peut être soit l'ensemble des mots ou des lettres (A...Z) correspondant aux noms ou codes des acides aminées et/ou unités de l'ADN et/ou ARN : SER, A, T, G, C... Dans ce même exemple, l'alphabet peut correspondre à des suites de codes numériques formés de bits, ainsi pour l'ADN il est possible d'utiliser un alphabet formé de codes en base 3 pour représenter les combinaisons entre l'ADN et les acides aminés correspondants. Dans tous ces exemples, la présente invention est applicable indépendamment du contenu informatif proprement dit des données qui sont traitées par le dispositif automatisé. L'invention est également applicable dans de nombreuses industrie et par exemple dans le cadre du post-séquençage génétique. La présente invention permet de mettre en oeuvre une technique appelée "parallélisme de registre" qui consiste à exploiter au mieux le parallélisme intrinsèque des opérations sur les registres des ordinateurs, micro-ordinateurs, micro-processeurs ou circuits spécialisés. D'autres avantages, buts et modalités de mise en #uvre de la présente invention sont donnés dans la description qui suit d'exemples de réalisation où la figure 1 représente les états et transitions dans le cas d'une recherche avant et la figure 2 dans le cas d'une recherche arrière. Dans un premier exemple qui correspond à une mise en oeuvre d'une recherche avant, la recherche s'effectue sur un texte T dont les signes élémentaires sont des caractères alphabétiques. Le motif est également formé d'un assemblage de signes alphabétiques mais il comporte en plus un saut borné noté x(1,3) qui correspond donc à un nombre compris entre 1 et 3 caractères quelconques. Ce motif est: a - b - c - x(1,3) - d - e Entre les caractères c et d il y a donc 3 transitions qui peuvent être suivies par n'importe quel caractère et qui correspond à la largeur maximum du saut. Ainsi sur la Figure 1, deux transitions notées s partent de l'état dans lequel les caractères a, b, c ont été reconnus et sautent une ou deux transitions suivantes respectivement. Cela permet de sauter un à trois caractères avant de rechercher c, d à la fin du motif. La méthode mise en oeuvre permet de faire débuter la correspondance à n'importe quelle position dans le texte. Ainsi, toujours selon la figure 1, on débute à l'état So et on lit le motif caractère par caractère ou, plus généralement, symbole par symbole, un symbole étant une classe de caractères (sous ensemble de "l'alphabet") ou un saut. Des transitions et états sont ajoutés pour chaque nouveau symbole lu. Si après la création de l'état S,, le symbole suivant du motif est une liste ou classe de caractères, un état Si+1 est créé ainsi qu'une transition C entre S, et Si+1. Par contre si le symbole suivant est un saut de la forme x (a,b), états Si+1 ... Si+b sont créés ainsi que les transitions reliant les états Sj à Sj+1 pour j # i... i+b-1. En plus, b-a transitions s sont créées des états Si aux états Si+1 ... Silb-,,. Le dernier état créé dans ce procédé est l'état final. Un tel procédé peut être mis en oeuvre dans un automate en profitant de ses capacités de travail par parallélisme de bits. Chaque état est représenté dans l'automate par un bit. L'état initial n'est cependant pas représenté car il est toujours actif. Les bits sont décalés sur la gauche et une table B indexée sur le caractère en cours du texte est mise en oeuvre. pour ce qui concerne les transitions #, les états actifs sont représentés par la valeur binaire 1 et les états inactifs par 0. Les états Si d'où partent une transition s sont appelés "saut-initial". Pour chaque "saut-initial" S, correspondant à un saut x(a,b) un état final correspondant Si+b-a+1 appelé "saut-final" est également défini. Sur la figure 1, il y a un "saut-initial" S3 et un "saut-final" S6. Un masque de bits # est créé avec la valeur 1 pour l'état de "saut-initial" et un autre masque de bits F qui a une valeur 1 pour l'état de "saut-final". Le statut de la recherche est conservé dans un masque de bits D et après les décalages, les transitions E sont opérées par l'opération: D' = 0 1 ( ( F - ( 0 & 1 )) & - F) Le but est d'isoler les états actifs pour "saut-initial" grâce à D & I. Retirer D & 1 de F peut produire deux résultats pour chaque "saut-initial" Si. Premièrement, s'il est actif, le résultat comportera des 1 pour tous les états entre S, et Si+b-a, propageant ainsi ces états actifs Si jusqu'aux états ciblés. Deuxièmement, si S, est inactif, le résultat aura seulement 1 dans Si+b-a+1 et cette valeur 1 indésirable est supprimée par l'opération & - F. Une fois que la propagation a été effectuée, un OU est effectué entre le résultat et les états déjà actifs de D. On peut noter que les propagations des différents sauts n'interfèrent pas entre elles car les soustractions ont un effet purement local. Si l'on reprend la figure 1, les masques de bits sont les suivants : # = 00000100 et F = 00100000 (ils doivent être considérés de la droite vers la gauche dans cet exemple de mise en oeuvre). On considère que les premiers caractères a, b, c ont déjà été retrouvés dans le texte et donc que D = 00000100. A cette étape de la méthode les transitions e doivent être effectuées et l'on a : D' = D 1 ( ( F - ( 0 & 1 )) & - F) = ((00100000 -00000100)&11011111), soit D' = 00011100, les états S3, S4 et S5 ayant été activés. Par contre si D = 00000010, alors D' = 00000000 et il n'y a pas de modification. Ainsi, dans ce premier exemple dit de recherche en avant, une lecture du texte de gauche à droite est effectuée pour la recherche du motif. Dans un mode préféré de mise en oeuvre, un dispositif automatisé programmable à micro processeur est utilisé. Sur un tel dispositif des programmes informatiques peuvent permettre la mise en #uvre de l'invention. Le principe général de ces programme est explicité par l'organigramme symbolique qui suit. Pour simplifier, on suppose qu'il ne peut y avoir de saut au début ou à la fin du motif, ce qui, par ailleurs est sans signification. L est la longueur maximum d'une correspondance et peut être obtenu simplement par un balayage du motif en additionnant le nombre de classes et les valeurs maximum des sauts. Les durées de traitement dépendent de l'organisation de la mémoire qui est mise en oeuvre, bit à bit ou par mots machines. De préférence on utilise l'opération dite de décalage. L'implémentation de cette recherche en avant est simple et nécessite peu de mémoire ou de registres. Elle est rapide dans de nombreux cas mais ne permet pas d'éviter de lire des caractères. L'organigramme correspondant est le suivant. Recherche~avant (P1 m , Ti. n) /* Préparation */ L # taille maximum d'une occurrence pour c # # faire B[c] # 0L I -- 0 , F E-- 0 i # 0 pour j# 1...m si P, est de la forme x(a,b) alors /* un saut */ l-l| (1 (i-1)) FF(1 (i+b-a)) pour ce Z, k e i ... i + b - 1 faire B[c] E-- B[c] (1 k) i # i + b sinon /* Pj est une classe de caractères */ pour c E Pj faire B[c] D - ((D 1 ) 1 p-'1 ) & B[t,l D - D 1 F - (D & 1 & nF) On considère maintenant une recherche arrière telle que représentée à la figure 2. L'automate crée un état initial 1 et des transitons s de cet état initial # vers tous les états. La figure 2 correspond à la recherche d'un motif: a-b-c-x(1,3)-d-e Par rapport à la recherche avant on peut signaler les différences suivantes : la mise en oeuvre d'un motif inversé Pr, le masque de bits D qui stocke les états de la recherche est initialisé avec D = 1Lafin de permettre les transitions initiales s et l'absence de boucle initiale. Cette méthode met en oeuvre une fenêtre de recherche de longueur # et qui correspond au nombre minimum de signes d'une correspondance. La fenêtre balaye, par décalage, le texte. A l'intérieur de chaque fenêtre, le texte est balayé en arrière. Si cette recherche arrière dans la fenêtre du texte échoue avant d'atteindre le début de la fenêtre, alors la fenêtre de recherche est décalée vers l'origine du plus long facteur reconnu. Si le début de la fenêtre est atteint et qu'il persiste des états actifs, alors une reconnaissance positive est obtenue pour quelque facteur de longueur #. Cependant il est encore nécessaire de vérifier l'alignement à partir du début de la fenêtre et c'est donc pour cette raison qu'une recherche avant du type précédent est mise en oeuvre dans la boucle de recherche arrière. Ainsi, la recherche arrière utilise le principe mis en oeuvre dans la méthode de recherche avant. Cette recherche avant se termine soit lorsque l'état final est atteint et donc que le motif a été retrouvé dans le texte, soit lorsqu'il n'existe plus d'état actif et donc qu'il n'y a pas de correspondance entre le motif et le texte. Ainsi, la boucle de recherche arrière se termine obligatoirement après la lecture d'au plus L caractères du texte, la fenêtre étant alors déplacée d'un caractère vers la droite et la boucle de recherche arrière reprise. Ainsi, dans ce deuxième exemple dit de recherche en arrière, la recherche est effectuée dans une fenêtre de taille # qui se déplace de gauche à droite sur le texte à la recherche du motif. Dans cette fenêtre, un balayage ou recherche en arrière d'un facteur du motif est effectuée. Si au cours de ce balayage un caractère ne pouvant appartenir au motif est trouvé, la fenêtre est déplacée après le début du facteur sur le texte. Par contre si le balayage atteint le début de la fenêtre, une vérification en avant est effectuée selon le principe de la recherche avant précédemment explicitée. Dans le cadre d'une recherche en arrière, l'algorithme suivant peut être mis en oeuvre. Cet algorithme, pour des raisons de simplification, ne comporte pas les tests qui, à l'intérieur des différentes boucles, permettent de sortir rapidement lorsqu'aucune correspondance ne pourrait être retrouvée et sans attendre la fin normale de la boucle en cours. L'organigramme correspondant est le suivant : recherche~arrière (P1..m, Ti n) L # taille maximum d'une occurrence /* Préparation */ t taille minimum d'une occurrence pour c E Z faire Bf[c] - 0, Bb[c] 'f-'f! I (1 (i-1)) 1 1b 1b (1 (L-(i+b)-1)) Ff ± Ff (1 (i+b-a)) , Fb--Fe (1 (L - i - a)) pour ce I, k e i ... i + b - 1 faire Bf[c] y- Bt[c] (1 k), Bb[c] - Bb[c] (1 (L - k - 1 )) ii+b sinon /* Pj est une classe de caractères */ pour c e Pj faire Bf[c] Bt[c] (1 i), Bb[c] - Bb[c] 1 (1 (L - i - 1 )) if-i+1 nFf j f-- f , Db .-- 1 tant que Db # 0L et j > 0 Db Db & Bb[tpos+] Db - Db Fb (Db & lb)) & nFb) j # j - 1 si Db 0L et j = 0 /* recherche avant */ D,E-0''1, vf-1 tant que Df ?" 0'' et pos + v s n Df Dt & Bf [tp..-vl Df - Df 1 (Ff - (Of & If)) & nFf) si Df & M # 0L alors marquer une occurrence commençant en pos + 1 Df # 0L Df # (Df # ) v # v + 1 Db # (Db # 1) pos # pos + j + 1 Le choix du procédé à utiliser dépend du motif à rechercher et l'on peut par exemple définir le paramètre suivant: (G+1 )/# avec G le maximum des longueurs de zones de caractères quelconques et # la longueur minimale d'une suite de caractère de la chaîne qui peut correspondre au motif. Si ce paramètre est supérieur à 0,5 alors la recherche arrière est moins efficace que la recherche avant. Toutefois cette valeur de seuil est approximative et d'autres paramètres peuvent être définis. Des test ont toutefois montré que cette valeur obtenue théoriquement correspond généralement à la réalité, les courbes de vitesse de recherche se croisant approximativement pour 0,5. Les organigrammes précédents peuvent être transposés dans des programmes informatiques écrits dans des langages divers. L'invention, telle qu'elle vient d'être décrite met en oeuvre des opérations logiques et arithmétiques sur des zones de mémoire, les opérations s'effectuant au niveau du "bit", c'est à dire au niveau de l'unité d'information la plus petite, afin d'optimiser la gestion de la mémoire du dispositif mis en oeuvre et qui peut être un ordinateur ou un circuit logique spécialisé. Cependant, on envisage que les opérations s'effectuent sur des "mots machine", c'est à dire des assemblages d'un nombre spécifique de "bits", par exemple 8 bits pour définir un "mot machine" appelé "octet", si une telle mise en oeuvre s'avère plus efficace. En effet, certaines machines peuvent ne pas comporter de moyens permettant d'effectuer certaines opérations au niveau de chaque "bit" indépendamment des autres et il peut alors être plus intéressant d'effectuer ces opérations directement sur des "mots machine". REVENDICATIONS 1. Procédé de recherche rapide d'un motif P dans un texte T fonctionnant dans un automate programmable, le texte T étant formé d'une suite de n signes élémentaires T1..Tn, les signes étant notés génériquement c , l'ensemble des signes élémentaires formant un ensemble E, le motif P étant formé d'un assemblage ordonné de s symboles, P1..Ps, chacun desdits symboles pouvant définir : - soit un sous ensemble C noté [c] de l'ensemble E, l'ensemble vide et l'ensemble lui même étant exclus, - soit une suite continue bornée d'un nombre de signes quelconques de E, ladite suite étant nommée saut borné et notée x (a,b) et ledit nombre étant compris entre a et b signes quelconques, avec 0 ≤ a d'une succession de L états notés S1,...,SI,...SL et de liens entre lesdits états, le nombre L correspondant à la longueur maximum de signes d'une correspondance, le statut d'un état i indiquant le résultat de la recherche de correspondance pour la position i étant stocké dans un bit d, d'une zone de mémoire D formée d'un ensemble de bits dL...d1, ladite zone de mémoire D étant initialisée avant le début de la recherche de correspondance et le balayage; caractérisé en ce dans le cas où, à la suite de l'état S,, le symbole suivant est un saut borné x(a,b), on crée : - b états Si+1... Si+b; - b liens notés x successivement entre lesdits états; - b-a transitions s; et qu'il comporte au moins les étapes suivantes: - on crée une première zone de mémoire 1 comportant L bits, on met à 0 l'ensemble des L bits de I puis on met à 1 les bits correspondant aux états d'où partent des transitions E, - on crée une seconde zone de mémoire F comportant L bits, on met à 0 l'ensemble des L bits de F puis on met à 1 les bits correspondant à chacun des états terminaux suivant le dernier recevant une transition #, et en ce que la zone de mémoire D est modifié par D = D #( ( F - ( D & I )) &-F). 2. Procédé selon la revendication 1 caractérisé en ce qu'on met en oeuvre un ensemble E qui est un alphabet constitué de signes chacun sous forme d'une donnée binaire formée d'un ensemble d'un nombre de bits (0,1) compris entre 1 et 64 et, de préférence, un alphabet binaire constitué d'un bit ou par un alphabet ASCII sur 7 bits ou de ses dérivés sur 8 bits. 3. Procédé selon la revendication 1 ou 2 caractérisé en ce que le texte utilisant l'alphabet est choisi parmi une image, un son ou un écrit. 4. Procédé selon l'une quelconque des revendications précédentes caractérisé en ce que l'on met en oeuvre un automate programmable qui est un ordinateur numérique ou un circuit logique spécialisé. 5. Procédé selon l'une quelconque des revendications 1 à 4 caractérisé en ce que le balayage est effectué en avant, le texte étant balayé à partir de son premier signe T1 et que le bit di de D prend la valeur 1 lorsque PlP2.,,Pl correspond au texte jusqu'au dit état, les L bits de la zone de mémoire D étant initialement mis à 0 par D = 0L, et que la méthode comporte en outre au moins une étape dans laquelle si, à la suite de l'état Si, le symbole suivant est un sous ensemble C de E, un nouvel état Si+1 est créé ainsi qu'un lien noté C, et le résultat de la recherche sur le signe tj de T et correspondant audit état Si+1 étant stocké dans D, la zone de mémoire D étant modifié par D = ( (D 1 ) 1 Ol-1 . 1 ) & B[T], et que dans le cas où, à la suite de l'état Si, le symbole suivant est un saut borné x(a,b): - les b liens notés x sont successivement placés entre les états Sj à Sj+1 avec j E i...i+b-1; - les b-a transitions # sont placées entre l'état Si et chacun des états Si+1" ,SI+b-a; - l'état d'où part la première transition s étant notés Sk, l'état terminal correspondant est Sk+b-a+1, et qu'il comporte en outre au moins une étape consistant, dans le cas d'un symbole [c] définissant un sous ensemble de E, à mettre en #uvre dans au moins une zone de mémoire une table B de masquage comportant pour chaque signe c de # un masque B[c] formé de m bits (bL...b1), ledit masque B [c] étantinitialement mis à 0 et le bit b, dudit masque B [c] prenantla valeur 1 seulement si un des signes du sous ensemble défini par le symbole Pi correspond au masque B [c] au signe c. 6. Procédé selon la revendication 5 caractérisé en ce qu'il comporte les étapes successives suivantes dans le cas d'une recherche d'un motif Pi "m dans un texte T1..n : (a) - on crée une variable L que l'on initialise avec la valeur correspondant au nombre maximum de signes d'une correspondance ; (b) - pour chacun des signes de l'ensemble E on crée et initialise à 0 un masque B[c] comportant L bits; (c) - on crée et initialise à 0 une variable # comportant L bits; (d) - on crée et initialise à 0 une variable F comportant L bits; (e) - on crée et initialise à 0 une variable i; (f) - on crée et initialise à 1 une variable j ; (g) - on effectue le test suivant: si Pj est de la forme x(a,b) on effectue les opérations (gO) suivantes : (gO) 1 = 1 1(1 (i-1)); (gO)F= F)(1 (i+b-a)); (gO) on crée et initialise à i une variable k; (g0) (ga) on effectue les opérations suivante pour chacun des signes c de E: (gO) B[c]=B[c] (# (1 k); (gO) on incrémente k : k=k+1; (gO) on retourne en (ga) si k est inférieur ou égal à i+b- 1; (gO) on incrémente i : i=i+b; dans le cas contraire correspondant au cas où Pj défini un sous ensemble on effectue les opérations (g1) suivantes : (g1) pour tout signe c appartenant au sous ensemble Pj on effectue l'opération B[c]= B[c] # (1 #i); (g1) on incrémente i : i=i+1; (h) - on incrémente j : j=j+1 et on retourne en (g) si j est inférieur ou égal à m; (i) - on crée une variable r de L bits que l'on initialise par complémentation de F: r = -F; (j) - on crée une variable M de L bits que l'on initialise par l'opération : M =1 (L-1); (k) - on crée et initialise à 0 la variable D comportant L bits; (I)- on réutilise la variable j que l'on initialise à 1 : j (m)- on effectue un test sur le résultat de l'opération D & M: si ce résultat est différent de 0L alors il y a correspondance entre le motif et une portion du texte se terminant à la position j-1; (n)- on effectue une opération modifiant D de telle façon que: D = ( (D 1 ) 1 OL-1 1 ) & B[Tjl; (o)- on effectue une opération modifiant D de telle façon que: D = D#( F - ( D & I ) ) & r); (p) - on incrémente j: j= j+1; (q) - on retourne en (m) tant que j est inférieur ou égal à n. 7. Procédé selon l'une des revendications 1 à 4 caractérisé en ce que le balayage est effectué en arrière, le texte étant balayé à partir de son dernier signe Tn. 8. Procédé selon la revendication 7 caractérisé en ce qu'il comporte les étapes successives suivantes dans le cas d'une recherche d'un motif P 1..m dans un texte T 1 . n : (a) - on crée une variable L que l'on initialise avec la valeur correspondant au nombre maximum de signes d'une correspondance ; (b) - on crée une variable X que l'on initialise avec la valeur correspondant au nombre minimum de signes d'une correspondance ; (c) - pour chacun des signes de l'ensemble E on crée et initialise à 0 un premier masque Bf[c] comportant L bits; (d) - pour chacun des signes de l'ensemble E on crée et initialise à 0 un premier masque Bb[c] comportant L bits; (e) - on crée et initialise à 0 une variable If comportant L bits; (f) - on crée et initialise à 0 une variable Ff comportant L bits; (g) - on crée et initialise à 0 une variable lb comportant L bits; (h) - on crée et initialise à 0 une variable Fb comportant L bits; (i)- on crée et initialise à 0 une variable i; (j) - on crée et initialise à 1 une variable j ; (k) - on effectue le test suivant: si Pj est de la forme x(a,b) on effectue les opérations (kO) suivantes : (k) Ir = Ir (1 (i-1 )); (kO) b = ib I(1 (L-(i+b)~1)); (kO)Ff = Ff 1(1 (i+b-a)); (kO) Fb = Fb I(1 (L-i~a)); (kO) on crée et initialise à i une variable k: k=i; (kO) (ka) on effectue les opérations suivante pour chacun des signes c de #: (kO) Bf[c]=Bf[c] # (1 k); (kO) Bb[c]=Bb[c] # (1 (L-k-1 )); (kO) on incrémente k : k=k+1; (kO) on retourne en (ka) si k est inférieur ou égal à i+b- 1; (kO) on incrémente i: i=i+b ; dans le cas contraire correspondant au cas où Pj défini un sous ensemble on effectue les opérations (k1) suivantes : (k1 ) pour tout signe c appartenant au sous ensemble Pj on effectue les deux opérations suivante sur Bf: Bf [c] =Bf[c] (1 i) et sur Bb: Bb[c] =Bb[c] I (1 (L-i-1 )); (k1) on incrémente i : i=i+1; (I)- on incrémente j : j=j+1et on retourne en (k) si j est inférieur ou égal à m; (m) - on crée une variable rf de L bits que l'on initialise par complémentation de Ff: #f = -Ff; (n)- on crée une variable rb de L bits que l'on initialise par complémentation de Fb: rb = -Fb; (o)- on crée une variable M de L bits que l'on initialise par l'opération: M =1 (L-1); (p) - on crée et initialise à 0 une variable pos; (q) - tant que pos est inférieur ou égal à n-I on effectue les opérations (qO) suivantes : (qO) on réutilise la variable j que l'on initialise à #: j = #; (qO) on crée et initialise à 1L la variable Db comportant L bits: Db = 1L; (qO) tant que Db est différent de 0 et tant que j est supérieur à 0 on effectue les opérations (q1) suivantes : (q 1 ) Db = Db & Bb[Tp05+J]; (q1 } Db - Db I (( Fb - (Db & b)} & rb} (q1) on décrémente j: j =J-1; (q1) on effectue le test suivant: si Db est différent de 0 et si j est nul alors on effectue les opérations (q2) suivantes: (q2) on crée et initialise à 0L-1 #1 la variable Df comportant L bits: Df = 0L-1 #1; (q2) on crée et initialise à 1 une variable v; (q2) tant que Df est différent de 0 et que pos+v est inférieur ou égal à n on effectue les opérations (q3) suivantes: (q3) Df = Df & Bf[TPas+l (q3) Dr = Df I (( Ff - (Df & r)) & rf) (q3) on effectue un test sur le résultat de l'opération Df & M: si ce résultat est différent de 0L alors il y a correspondance entre le motif et une portion du texte commençant en pos+1 et on réinitialise la variable Df à 0: Df=0L; (q3) on effectue un décalage sur Df: Df = (Df 1); (q3) on incrémente v : v = v+1; (q1) on effectue un décalage sur Db: Db = (Db 1); (qO) on incrémente pos : pos = pos+j+1. 9. Procédé de sélection d'un procédé de recherche rapide d'un motif P dans un texte T fonctionnant dans un automate programmable, le texte T étant formé d'une suite de n signes élémentaires T1..Tn, les signes étant notés génériquement c , l'ensemble des signes élémentaires formant un ensemble E, le motif P étant formé d'un assemblage ordonné de s symboles, P1..Ps, chacun desdits symboles pouvant définir: - soit un sous ensemble C noté [c] de l'ensemble E, l'ensemble vide et l'ensemble lui même étant exclus, - soit une suite continue bornée d'un nombre de signes quelconques de E, ladite suite étant nommée saut borné et notée x (a,b) et ledit nombre étant compris entre a et b signes quelconques, avec 0 ≤ a 10. Procédé de sélection selon la revendication 9 caractérisé en ce que Rs est approximativement égal à 0,5. 11. Produit "configuration logique de circuit" sur un support utilisable pour la fabrication d'un circuit logique spécialisé, ledit circuit étant destiné à mettre en #uvre le procédé selon l'une des revendications 4 à 8 lorsque ledit procédé est exécuté dans un circuit logique spécialisé.