Brevet FR2892847A1 — publié le 20070504

Procédé de mémorisation de données dans un circuit de mémoire pour automate de reconnaissance de caractères de type Aho-Corasick et circuit de mémorisation correspondant. L'invention concerne la reconnaissance de formes et de caractères et se rapporte plus particulièrement à un procédé dé mémorisation de données dans un circuit de mémoire d'un automate de reconnaissance de caractères. L'invention se rapporte également à un tel circuit de mémoire. Une application particulièrement intéressante d'un tel circuit de mémoire concerne l'élaboration d'une base de données pour un automate de reconnaissance de caractères déterministes à l'état fini de type Aho-Corasick pour la mise en oeuvre d'une reconnaissance d'informations multiples ou MPR, également désignée par les anglo- saxons par le terme "Multi-Pattern Recognition". Par exemple, mais non exclusivement, la reconnaissance de caractères peut être utilisée, dans le domaine informatique, pour reconnaître des signatures de virus informatiques dans des systèmes de détection d'intrusions dans lesquels des signatures d'attaques connues sont détectées. En se référant à la figure 1, un automate MPR de reconnaissance de caractères est donc basé sur l'utilisation d'une base de données B dans laquelle est stockée une liste de mots ou, de manière générale, une liste de chaînes de caractères ou de motifs à reconnaître dans un fichier incident F. Les motifs sont stockés, dans la base de données B, sous la forme d'une arborescence de noeuds dans laquelle chaque noeud correspond à un état de l'automate et à une reconnaissance d'une séquence de caractères d'un motif à reconnaître. La structure et l'élaboration d'un automate de type Aho-Corasick sont bien connues de l'homme du métier et ne seront donc pas décrites en détail par la suite. On pourra, à cet égard, se référer à l'article "A. Aho and M. Corasick : Efficient string matching, an aid to bibliographic search, in communication of the ACM, 18 (6) : 333-340, 1975". On notera cependant que la construction d'un automate Aho Corasick nécessite tout d'abord l'élaboration de la base de données B en prévoyant, pour chaque motif M à reconnaître, les états et les transitions directes qui mènent à la reconnaissance du motif. En particulier, à chaque état est associé un vecteur de transition qui sert à déterminer le ou les noeuds destinataires d'une transition. Pour ce faire, à chaque état, sont associés des paramètres de transition pour calculer au moyen d'une fonction de transition les états accessibles depuis chaque noeud. Il a été constaté que l'élaboration de la base de données est une étape très complexe à mettre en oeuvre et nécessite des moyens matériels relativement importants, en particulier en termes de mémoire. Ainsi, dans une application de recherche de signatures de virus informatiques, la taille de la mémoire nécessaire pour mettre en oeuvre un automate de type Aho-Corasick peut atteindre, voire dépasser, 100 Mo. Le but de l'invention est donc de pallier cet inconvénient et de fournir un procédé de mémorisation de données dans un circuit de mémoire d'un automate de reconnaissance de caractères de type Aho-Corasick, dans lequel la taille mémoire nécessaire pour l'élaboration d'une base de données peut être considérablement réduite. L'invention a donc pour objet, selon un premier aspect, un procédé de mémorisation de données dans un circuit de mémoire d'un automate de reconnaissance de caractères de type Aho-Corasick, dans lequel des chaînes de caractères sont reconnues par mise en oeuvre de transitions successives dans une arborescence de noeuds stockés en mémoire dans laquelle chaque noeud correspond à un état de l'automate et à une reconnaissance d'une séquence de la chaîne de caractères et dans laquelle chaque noeud est associé à un vecteur de transition servant à déterminer le ou les noeuds destinataires d'une transition. Selon une caractéristique générale de ce procédé, on teste si des vecteurs de transition pointent vers des adresses de destination communes, on combine lesdits vecteurs de transition si les adresses vers lesquelles pointent ces vecteurs sont distinctes, en élaborant un vecteur de combinaison et l'on mémorise les noeuds aux adresses mémoire pointées par le vecteur de combinaison. En d'autres termes, dans le cas où deux vecteurs de transition n'ont pas d'état destinataire en commun, on fusionne dans un même vecteur de combinaison l'ensemble des états destinataires, le vecteur de combinaison ainsi élaboré étant alors affecté aux deux états initiaux combinés pour déterminer les états destinataires qui leur correspondent respectivement. Selon une autre caractéristique de l'invention, le vecteur de combinaison est élaboré en réalisant un "OU" logique entre les vecteurs à combiner. Le test à utiliser pour déterminer si les vecteurs de transition pointent vers des états communs est, quant à lui, réalisé en effectuant une fonction logique "ET" entre les vecteurs à combiner. Selon encore une autre caractéristique de l'invention, on procède à des transformations successives d'un premier vecteur à combiner jusqu'à obtenir une configuration dudit premier vecteur dans laquelle les états vers lesquels pointe ce vecteur sont différents des états vers lesquels pointe un deuxième vecteur à combiner. De préférence, dans le cas où ladite configuration n'est pas atteinte, on combine ledit premier vecteur avec un autre vecteur. Selon une autre caractéristique de l'invention, la transformation réalisée est un décalage et une rotation des bits du vecteur. Pour la mémorisation d'un noeud pointé par le vecteur de combinaison, chaque noeud est associé en mémoire à des paramètres de transition servant à élaborer les vecteurs de transition à partir d'une fonction de transition. On modifie ainsi la valeur des paramètres de transition en fonction des transformations successives des vecteurs. Les états sont alors stockés en mémoire sous la forme d'un ensemble de segments de descripteurs, chaque segment correspondant à un symbole d'entrée et étant adressable au moyen d'un premier paramètre de transition et chaque vecteur étant adressable au moyen d'un deuxième paramètre de transition représentant la position dudit vecteur dans un segment. Selon encore une autre caractéristique de l'invention, chaque noeud est associé à une clé de confirmation sous la forme d'un ensemble de bits de codage d'un paramètre de vérification d'une transition. Dans un mode de mise en oeuvre particulier, on initialise un ensemble des vecteurs de combinaison en positionnant chaque bit desdits vecteurs à zéro et l'on combine successivement chaque vecteur de transition et chaque vecteur de combinaison. Il a été constaté que cette caractéristique permet de réduire encore l'emplacement mémoire. Selon un autre aspect, l'invention a également pour objet un circuit de mémoire pour automate de reconnaissance de caractères de type Aho-Corasick, dans lequel des chaînes de caractères sont reconnues par mise en oeuvre de transitions successives dans une arborescence de noeuds stockés en mémoire, dans laquelle chaque noeud correspond à un état de l'automate et à une reconnaissance d'une séquence de la chaîne de caractères et dans laquelle chaque noeud est associé à un vecteur de transition servant à déterminer le ou les noeuds destinataires d'une transition, caractérisé en ce qu'une partie au moins desdits noeuds est stockée en mémoire à des adresses correspondant à une combinaison de vecteurs de transition. D'autres buts, caractéristiques et avantages de l'invention apparaîtront à la lecture de la description suivante, donnée uniquement à titre d'exemple non limitatif, et faite en référence aux dessins annexés, sur lesquels : -la figure 1, dont il a déjà été fait mention, illustre le principe général d'une reconnaissance de caractères au moyen d'un automate de reconnaissance de type Aho-Corasick conventionnel ; -la figure 2 est un schéma synoptique montrant un exemple d'implémentation d'une base dans un circuit de mémoire conforme à l'invention ; -la figure 3 illustre l'organisation du circuit de mémoire pour la mémorisation des noeuds multiples ; -la figure 4 est un schéma synoptique illustrant un exemple de codage des noeuds en mémoire ; -la figure 5 montre un exemple particulier d'implémentation d'un automate ; -la figure 6 est un tableau distant, pour chaque état, les vecteurs de transition ; -les figures 7 à 14 montrent les étapes de combinaison des vecteurs ; -la figure 15 est un tableau récapitulatif distant, pour chaque état, les états destinataires et les valeurs des paramètres de transition ; et -la figure 16 est un tableau illustrant l'organisation mémoire des états. Tel que représenté à la figure 2, le circuit de mémoire est organisé sous la forme d'une arborescence constituée d'une succession de noeuds correspondant chacun à un état d'un automate de reconnaissance de caractères de type Aho-Corasick, c'est-à-dire un état correspondant à une reconnaissance d'une séquence de caractères d'un motif à reconnaître dans un fichier incident à analyser. Les noeuds sont liés entre eux par des transitions valides ou directes qui mènent à un état final correspondant à la reconnaissance d'un motif prédéterminé. Ainsi, à partir d'un état initial E, chaque noeud pointe vers un ou plusieurs noeuds consécutifs, de manière à aboutir vers un état final EF en passant par des états intermédiaires tels que E; pour déclarer un motif correspondant retrouvé. Toutefois, chaque noeud ne pointe pas par une transition valide que vers un ou plusieurs noeuds d'un ordre immédiatement inférieur. En l'absence de transition valide, des transitions d'échec, illustrées en gras sur la figure 2, sont prévues pour amener l'automate dans un état précédent prédéterminé. Dans l'architecture visible à la figure 2, on distingue des noeuds multiples qui pointent vers plusieurs noeuds consécutifs et des chaînes de noeuds dont les noeuds ne pointent chacun que vers un unique noeud consécutif. Chaque noeud n'est issu que d'un et un seul noeud parent. Les transitions d'échec ne permettent d'aboutir que vers un noeud multiple. Dans l'exemple illustré à la figure 2, le noeud initial s est un noeud multiple qui pointe vers deux noeuds consécutifs a et b. De même, le noeud désigné par la référence b constitue également un noeud multiple qui pointe vers plusieurs noeuds ba et bb. Les autres noeuds, en particulier le noeud ba, sont des noeuds de chaîne et pointent vers un unique noeud. A la construction du circuit de mémoire, les transitions entre noeuds sont élaborées en construisant, d'une part, des transitions valides T,, entre deux états consécutifs qui correspondent à une suite de caractères du motif à reconnaître et, d'autre part, des transitions d'échec Te mises en oeuvre en cas de non reconnaissance d'un caractère dans un état donné. Dans l'exemple représenté à la figure 2, à partir d'un état initial s, on procède à une transition d'états à chaque caractère incident. Ainsi, l'entrée de caractères "a" ou "b" permet d'atteindre les états a ou b, respectivement. A partir de l'état a, la réception d'un caractère "b" permet d'atteindre un état final ab, ce qui correspond à la reconnaissance du motif ab. A partir de l'état b, la réception du symbole "a" permet d'atteindre l'état final ba, tandis que la réception du caractère "b" permet d'atteindre l'état final bb. Enfin, à partir de l'état ba, la réception du caractère "b" permet d'atteindre un état intermédiaire bab, puis l'état final babb après réception du caractère "b". A partir de chacun des états ci-dessus mentionnés, en l'absence de transition valide, les transitions d'échec Te permettent de pointer vers un état antérieur prédéterminé en utilisant une fonction de transition prédéfinie, qui sera décrite en détail par la suite. Les noeuds de chaque chaîne de noeuds constituent des noeuds consécutifs accessibles séquentiellement lors du parcours de l'arborescence et sont implantés en mémoire à des adresses consécutives à partir d'un noeud de base et d'un décalage offset relatif par rapport à ce noeud de base. Ainsi, l'adresse address d'un noeud d'une chaîne de noeuds est donnée par la relation suivante : Address (offset) = C @ + offset dans laquelle address (offset) désigne l'adresse d'un noeud séparé d'un noeud de base d'un décalage offset ; et C @ désigne l'adresse du noeud de base. Pour le stockage en mémoire des noeuds multiples, le circuit de mémoire est divisé en espaces successifs de zones mémoire correspondant chacun à un symbole d'un alphabet. En se référant à la figure 3, la mémoire est par exemple subdivisée en A segment de A descripteur, A étant par exemple égal à 256 pour un alphabet de 256 caractères. Chaque segment comprend une série de descripteurs consécutifs, associés chacun à un symbole donné de l'alphabet, qui décrivent le chemin qui permet d'accéder au noeud dans l'arborescence, et qui servent à calculer les noeuds destinataires d'une transition conivante. Les noeuds multiples sont ainsi également mémorisés relativement aux noeuds de base s et leur adresse peut être calculée à partir de la relation : Address (s, offset) = S @ + s x offset + 1 Address (s) = S dans laquelle : address (S, offset) désigne l'adresse d'un noeud multiple espacé d'un noeud initial E d'un décalage offset ; S @ désigne l'adresse du noeud de base ; et -address (s) correspond à l'adresse du noeud de base. Dans le but de réduire la taille mémoire nécessaire au stockage des chaînes de noeuds et de noeuds multiples, ces noeuds sont codés de la manière suivante. En se référant à la figure 4, le codage des noeuds multiples est effectué de la façon suivante. Ces noeuds sont codés sous la forme d'une trame de bits servant à déterminer une transition associée à chaque noeud. Chaque noeud multiple comporte un certain nombre de champs servant à déterminer une transition associée au noeud, c'est-à-dire à déterminer le noeud ou l'état destinataire d'une transition, et des drapeaux permettant de décrire le noeud multiple ou l'état associé au noeud. En ce qui concerne le champ servant à déterminer une transition, celui-ci comporte deux paramètres T et S servant à calculer la valeur d'une fonction de transition, un champ K permettant de vérifier la validité de la transition ainsi calculée, ainsi qu'un champ FS servant à pointer vers un état d'échec dans la mémoire. Le champ T sert ainsi au codage d'un décalage du noeud dans un segment et correspond au décalage offset ci-dessus mentionné. Le champ S sert au codage du décalage du segment considéré par rapport au noeud initial E. Le champ K sert au codage d'une clé pour vérifier que la transition valide calculée à partir des champs T et S est correcte et correspond à l'adresse du noeud de départ de la transition. En d'autres termes, on vérifie qu'une transition est correcte si la clé de l'état de destination indique l'état précédent. Le champ FS sert au codage de l'adresse de l'état d'échec dans la mémoire. Par ailleurs, deux champs sont utilisés : - JUMP : ce drapeau est un bit qui indique si le noeud multiple pointe vers un noeud d'une chaîne de noeuds ; et TERM : ce drapeau est un bit qui indique si l'état en cours est un état final ou non. Si le drapeau JUMP est positionné à 1, l'état de destination de la transition est constitué par un noeud prédéterminé d'une chaîne de noeuds. L'adresse est par exemple calculée par concaténation des champs T, S et FS pour calculer un décalage offset par rapport à l'adresse d'un noeud de base C @. Au contraire, si le drapeau JUMP n'est pas positionné, le noeud de destination de la transition est constitué par un noeud multiple et est calculé à partir d'une fonction de transition Gs (a;) à partir des paramètres T et S. L'adresse de destination est alors calculée à partir de la fonction suivante : G,(a;)=.(a;O+S)+T+1 dans laquelle l'opérateur O+ réalise une opération d'addition modulo 256. Comme indiqué précédemment, l'adresse contenue dans la clé K du vecteur de destination est comparée avec l'adresse de départ de la transition afin de valider la transition. Par exemple, la détermination d'une transition peut être mise en oeuvre par un analyseur au moyen de l'algorithme suivant : State TRANS (State S, a;) { if (JUMP) { offset = concat (T, S, Fs) ; return C@ + offset ; //Aller à un noeud de chaîne. } //Noeud multiple suivant théorique pour la transition valide. Gs(a;)=Ox(a;O+ S)+T+1 ; S' = S@ + Gs(a;) x sizeof (noeud multiple) ; if (S'.K ~ @(S)) return S@ + Fs x sizeof (super node) ; else return @ (S'). A chaque noeud, est donc associé un ensemble de noeuds accessibles séquentiellement à réception de symboles d'entrée respectifs. Chaque noeud est donc associé à un vecteur de transition qui permet de déterminer l'ensemble des transitions possibles à partir de l'état correspondant. Aussi, par exemple, dans l'exemple visible à la figure 5, on considère l'alphabet A suivant : A = {ao, a1, a2 a3, a4, a5, a6, a7} A chaque état, on associe les vecteurs de transition représentés à la figure 6, la densité correspondant, sur cette figure, au nombre de noeuds destinataires de chaque état. Sur cette figure 6, un bit i d'un vecteur vaut 1 si et seulement si il existe une transition par le symbole i. Comme on le conçoit, le stockage en mémoire des vecteurs de transition nécessite des ressources relativement importantes en termes de moyens matériels de mémorisation. Dans le but de réduire la taille de la mémoire nécessaire pour le stockage des vecteurs, les vecteurs associés à deux états dont les noeuds consécutifs sont tous différents, sont combinés en élaborant un vecteur de combinaison résultant de l'ajout aux noeuds destinataires d'un premier vecteur les noeuds destinataires d'un autre vecteur. Comme cela sera décrit en détail par la suite, lorsqu'un vecteur ne peut être combiné à un autre, il est transformé, par décalages et rotations successives jusqu'à ce qu'il puisse être combiné. Selon une caractéristique de l'invention, les vecteurs de transition sont combinés à des vecteurs de combinaison préalablement initialisés à zéro. En fait, deux vecteurs peuvent être combinés si ces vecteurs n'entrent pas en conflit, c'est-à-dire si une opération logique "ET" entre ces vecteurs aboutit à un résultat nul, c'est-à-dire à un vecteur dont toutes les composantes sont nulles. En d'autres termes, deux vecteurs sont en conflit s'il existe au moins un même bit égal à 1 dans les deux vecteurs, ce qui signifie que ces deux vecteurs aboutissent à un même symbole ou que l'on transite par un même état. Dans un tel cas, ces vecteurs ne peuvent être combinés. 11 Dans le cas où l'opération logique "ET" permet aux vecteurs d'être combinés, la combinaison est effectuée en réalisant une opération logique "OU" entre les deux vecteurs. Lorsque deux vecteurs ne peuvent être combinés, on procède à une transformation de l'un des vecteurs jusqu'à obtenir une configuration selon laquelle les deux vecteurs n'ont pas au moins un bit en commun égal à 1. Cette transformation est constituée par un décalage et une rotation des bits des vecteurs. Ainsi, dans un mode de mise en oeuvre de l'invention, on procède à un décalage à droite des bits des vecteurs, le bit le plus à droite étant transféré vers le bit le plus à gauche du vecteur. Par exemple, un décalage de trois bits d'un vecteur V s'écrit : V 0 3. Ainsi, on écrit par exemple 10100103=11010002=011010 1=001101 Dans le but de réduire au maximum la taille mémoire nécessaire pour le stockage des vecteurs de transition, on cherche à combiner au maximum les vecteurs de tous les états de l'automate. Lors de l'élaboration d'un vecteur de combinaison, on assigne à chaque vecteur ainsi agrégé, des valeurs de paramètres de transition T et S résultant des transformations effectuées. Alors qu'on affecte à chaque vecteur combiné une valeur arbitraire du paramètre T, on affecte à ce vecteur de combinaison un paramètre S correspondant au nombre de décalages effectués pour obtenir une configuration permettant à un vecteur d'être combiné à un autre. On va maintenant décrire en référence aux figures 7 à 16, un exemple de mise en oeuvre d'une agrégation de vecteur conforme à l'invention. Dans le but d'obtenir une distribution optimale des états, comme visible sur la figure 6, les états sont classés en fonction de leur densité et l'on cherche, en premier lieu, à combiner les états dont la densité est la plus élevée. Comme indiqué précédemment, on procède par ailleurs à l'élaboration de vecteurs de combinaison AVo, AV1, ., AVn, vides, c'est-à-dire dont tous les bits sont à zéro, et ce en un nombre suffisant pour pouvoir traiter l'ensemble des états. On met alors en oeuvre l'algorithme de combinaison suivant, pour un alphabet de 256 caractères : Pour chaque état Si Pour chaque vecteur de combinaison AVE Pour chaque x dans [0, ..., 255], Si Vs; xET AVi =O S:=x T : = j AVE:=AV;OUVs; x S : = S + 1 dans lequel Vs; désigne un vecteur d'état associé à un état Si...DTD: Ainsi, par exemple, en se référant maintenant à la figure 7, on procède tout d'abord à une combinaison du vecteur d'état associé à l'état initial c et du premier vecteur de combinaison AVo. L'opération logique ET entre ces vecteurs aboutit à un résultat nul, de sorte que l'on combine les vecteurs VE et AV0. Les valeurs de transition d'état sont : T=0 ; S=0. On procède alors à une combinaison du vecteur Vs0 associé à l'état SD avec l'un des vecteurs de combinaison. En référence à la figure 8, on tente d'agréger le vecteur Vs0 avec le vecteur AV0. Pour ce faire, on procède à l'opération logique ET entre le vecteur Vs0 et le vecteur de combinaison AV0. Le résultat de cette opération est non nul. On procède alors à des rotations successives du vecteur Vs0 jusqu'à obtenir une configuration dans laquelle ce vecteur transformé peut être combiné au vecteur de combinaison AV0. Cette configuration ne peut être obtenue. En référence à la figure 9, on combine alors le vecteur Vs0 avec le vecteur de combinaison AV 1 suivant. Les valeurs de transition sont T=1 ; S=0. En se référant à la figure 10, on procède ensuite à l'agrégation du vecteur Vs3 avec le premier vecteur de combinaison AVo. Comme visible sur cette figure 10, cette combinaison est impossible. On tente alors de combiner ce vecteur Vs3 avec le vecteur de combinaison AV1. Comme représenté à la figure 5, une rotation de 1 bit du vecteur Vs3 permet d'obtenir une configuration dans laquelle ce vecteur transformé peut être combiné au vecteur AV1. Les paramètres de transition deviennent, pour ce vecteur de combinaison AV1 : T=1, S=1. De même, les vecteurs de transition associés aux états de S I et S4 sont successivement combinés, dans l'ordre des densités décroissantes. (Figures 12 à 14). Comme visible sur la figure 15, qui illustre pour chaque état d'origine ou état "père" l'ensemble des états destinataires ou états "fils", chaque vecteur est associé à des valeurs de paramètres de transition T et S obtenues en fonction des transformations effectuées pour réaliser les combinaisons. En se référant enfin à la figure 16, les états sont positionnés en mémoire en fonction des valeurs des paramètres de transition T et S, T correspondant à un décalage au sein d'un segment A, et S correspondant à un décalage des segments. On notera toutefois que le décalage au sein d'un segment T correspond à la valeur T du paramètre d'un état immédiatement antérieur. Par ailleurs, un segment A auquel appartient un état est égal au symbole utilisé pour atteindre cet état décalé de la valeur S. Par exemple, dans l'alphabet considéré, A6 O+ 6 = 4. REVENDICATIONS 1-Procédé de mémorisation de données dans un circuit de mémoire d'un automate de reconnaissance de caractères de type Aho-Corasick, dans lequel des chaînes de caractères sont reconnues par mise en oeuvre de transitions successives dans une arborescence de noeuds stockés en mémoire dans laquelle chaque noeud correspond à un état (So, ..., S14) de l'automate et à une reconnaissance d'une séquence de la chaîne de caractères et dans laquelle chaque noeud est associé à un vecteur de transition (Vso, ..., Vs4) servant à déterminer le ou les noeuds destinataires d'une transition, caractérisé en ce que l'on teste si des vecteurs de transition (Vso, ..., Vs4) pointent vers des adresses de destination communes, on combine lesdits vecteurs de transition si les adresses vers lesquelles pointent les vecteurs sont distinctes en élaborant un vecteur de combinaison et l'on mémorise les noeuds aux adresses mémoire pointées par le vecteur de combinaison. 2-Procédé selon la revendication 1, caractérisé en ce que le vecteur de combinaison est élaboré en réalisant un "OU" logique entre les vecteurs à combiner. 3-Procédé selon l'une des revendications 1 et 2, caractérisé en ce que l'on teste si les vecteurs de transition pointent vers des états communs en réalisant une fonction logique "ET" entre les vecteurs à combiner. 4-Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que l'on procède à des transformations successives d'un premier vecteur à combiner jusqu'à obtenir une configuration du premier vecteur dans laquelle les états vers lesquels pointe ce vecteur sont différents des états vers lesquels pointe un deuxième vecteur à combiner. 5-Procédé selon la revendication 4, caractérisé en ce que dans le cas où ladite configuration n'est pas atteinte, on combine ledit premier vecteur avec un autre vecteur. 6-Procédé selon l'une des revendications 4 et 5, caractérisé en ce que la transformation est un décalage et une rotation des bits du vecteur. 7-Procédé selon l'une quelconque des revendications 1 à 6, caractérisé en ce que chaque noeud est associé en mémoire à des paramètres de transition (T, S) servant à élaborer les vecteurs de transition à partir d'une fonction de transition. 8-Procédé selon la revendication 7, caractérisé en ce que l'on modifie la valeur des paramètres de transition (T, S) en fonction des transformations successives des vecteurs. 9-Procédé selon l'une des revendications 7 à 8, caractérisé en ce que les états sont stockés en mémoire sous la forme d'un ensemble de segments (A) de descripteurs, chaque segment correspondant à un symbole d'entrée et étant adressable au moyen d'un premier paramètre de transition (S) et chaque vecteur étant adressable au moyen d'un deuxième paramètre de transition (T) représentant la position dudit vecteur dans un segment. 10-Procédé selon l'une quelconque des revendications 1 à 9, caractérisé en ce que chaque noeud est associé à une clé (K) de confirmation sous la forme d'un ensemble de bits de codage d'un paramètre de vérification d'une transition. 11-Procédé selon l'une quelconque des revendications 1 à 10, caractérisé en ce que l'on initialise un ensemble de vecteurs de combinaison en positionnant chaque bit desdits vecteurs à zéro et l'on combine successivement chaque vecteur de transition et chaque vecteur de combinaison. 16 12. Circuit de mémoire pour automate de reconnaissance de caractères de type Aho-Corasick, dans lequel des chaînes de caractères sont reconnues par mise en oeuvre de transitions successives dans une arborescence de noeuds stockés en mémoire, dans laquelle chaque noeud correspond à un état de l'automate et à une reconnaissance d'une séquence de la chaîne de caractères et dans laquelle chaque noeud est associé à un vecteur de transition servant à déterminer le ou les noeuds destinataires d'une transition, caractérisé en ce qu'une partie au moins desdits noeuds est stockée en mémoire à des adresses correspondant à une combinaison de vecteurs de transition.