Brevet FR2891075A1 — publié le 20070323

Circuit de mémoire pour automate de reconnaissance de caractères de type Aho-Corasick et procédé de mémorisation de données dans un tel circuit L'invention concerne la reconnaissance de formes et de caractères et se rapporte plus particulièrement à un circuit de mémoire pour automate de reconnaissance de caractères et à un procédé de mémorisation de données dans 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éterministe à états finis de type AhoCorasick 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 ou 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 séquences d'octets à 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 à une séquence d'octets d'un motif à reconnaître et dans laquelle chaque noeud correspond à un état de l'automate. La structure et l'élaboration d'un automate de type Aho-30 Corasick sont bien connues d'un homme du métier et ne sont 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 Machine, An aid to bibliographie search. in Communications 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 à reconnaître, les états et les transitions directes qui mènent à la reconnaissance du motif. On calcule alors une fonction de transition qui pointe vers un noeud consécutif qui correspond à la reconnaissance d'un caractère dans un état donné. La recherche d'un motif dans un fichier à analyser F, tel qu'un fichier vidéo ou un fichier texte, s'effectue ensuite en parcourant le graphe construit. Lorsque l'on atteint un état final, on déclare retrouvé le motif correspondant. 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. En outre, les automates de reconnaissance de caractère et de formes de type Aho-Corasick sont généralement implantés sous une forme logicielle de sorte que le transfert des données vers et à partir de la base de données s'effectue par des bus, ce qui nécessite un temps de transfert non négligeable. Au vu de ce qui précède, le but de l'invention est de pallier les inconvénients liés aux automates de reconnaissance de caractères conventionnels. Un autre but de l'invention est de permettre la construction d'un automate de reconnaissance de caractères sous forme matérielle. L'invention a donc pour objet, selon un premier aspect, un circuit de mémoire pour automate de reconnaissance de caractères de type AhoCorasick dans lequel des chaînes de caractères prédéterminées sont reconnues dans un flux de données incident par mise en oeuvre de transitions successives dans une arborescence de 2891075 3 noeuds stockée en mémoire dans laquelle chaque noeud correspond à une séquence reconnue d'une chaîne de caractères et dans laquelle une partie au moins desdits noeuds est liée à un noeud consécutif par une transition valide, d'un état initial jusqu'à des états terminaux correspondant chacun à une chaîne de caractères reconnue. Selon une caractéristique générale de l'invention, le circuit comporte des premiers ensembles d'adresses mémoires consécutives définissant respectivement des chaînes de noeuds consécutifs accessibles séquentiellement lors de transitions successives jusqu'à un état terminal et des deuxièmes ensembles d'adresses mémoires définissant des noeuds multiples pointant chacun vers plusieurs états. Grâce à cet agencement, il a été constaté que le nombre de bits nécessaires pour représenter un automate Aho-Corasick en mémoire est fortement réduit. En outre, grâce à cet agencement, les transitions peuvent être réalisées en utilisant un nombre de transitions d'horloge minimum. Selon une autre caractéristique de l'invention, les noeuds de chaque chaîne de noeuds et les noeuds multiples sont adressables à partir d'un noeud de base et d'un décalage relatif par rapport audit noeud de base. Les chaînes de noeuds sont codées en mémoire différemment des noeuds multiples. Toutefois, chaque noeud de chaque chaîne de noeuds et chaque noeud multiple est codé sous la forme d'une trame de bits de codage de caractéristiques relatives à une transition associée audit noeud. En ce qui concerne les chaînes de noeuds, la trame comporte, dans un mode de mise en oeuvre, un ensemble de bits de codage d'un drapeau indiquant la présence d'une transition valide pour le noeud vers un noeud consécutif. Cette trame comporte en outre un champ de codage de l'adresse d'un noeud de destination d'une transition pour ledit noeud en l'absence de transition valide, c'est-à-dire en cas de transition d'échec. La trame comporte en outre un ensemble de bits de codage de la longueur du champ de codage. Elle comporte en outre un ensemble de bits de codage du type de noeud de destination de la transition d'échec. Un ensemble de bits de codage d'un caractère suivant attendu pour une transition valide est également utilisé dans la trame de 5 codage de chaque noeud de la chaîne de noeuds. Cette trame comporte enfin un ensemble de bits de codage d'une information indiquant si le noeud correspond à un état terminal constituant une reconnaissance d'une séquence de chaîne de caractères. En ce qui concerne les noeuds multiples, la trame de codage comporte des bits de codage de paramètres de calcul d'une fonction de transition valide et des bits de codage d'un paramètre de vérification de la transition. Cette trame comporte en outre des bits de codage d'un noeud de destination de la transition pour le noeud, en cas de transition d'échec. Par exemple, le paramètre de validation est l'adresse d'un noeud immédiatement précédent, la transition étant validée lorsque le paramètre de validation du noeud de destination de la transition correspond à l'adresse du noeud précédent. En effet, chaque noeud ne comporte qu'un et un seul antécédent de sorte que la vérification de l'adresse du noeud précédent permet de vérifier la validité de la transition. La trame de codage comporte en outre des bits de codage d'une information indiquant si le noeud correspond à un état terminal constituant une reconnaissance d'une séquence de chaîne de caractères. Cette trame comporte enfin des bits de codage indiquant si le noeud pointe vers un noeud d'une chaîne de noeuds ou vers un noeud multiple. Selon un autre aspect, l'invention a également pour objet 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 prédéterminées sont reconnues dans un flux de données incident par mise en oeuvre de transitions successives dans une arborescence de noeuds stockée en mémoire dans laquelle chaque noeud correspond à une séquence reconnue d'une chaîne de caractères et dans laquelle une partie au moins desdits noeuds est liée à un noeud consécutif par une transition valide, d'un état initial jusqu'à des états terminaux correspondant chacun à une chaîne de caractères reconnue, caractérisé en ce que l'on stocke à des premiers ensembles d'adresses mémoire successives des premiers ensembles de noeuds définissant respectivement des chaînes de noeuds consécutifs 10 accessibles séquentiellement lors de transitions successives jusqu'à un état terminal et des deuxièmes ensembles de noeuds multiples pointant vers plusieurs états à des deuxièmes ensembles d'adresses mémoires. Selon une autre caractéristique de ce procédé, les noeuds de chaque chaîne de noeuds et les noeuds multiples sont adressables à 15 partir d'un noeud de base et d'un décalage relatif par rapport audit noeud de base. Selon encore une autre caractéristique du procédé selon l'invention, chaque noeud de chaque chaîne de noeuds et chaque noeud multiple est codé en mémoire sous la forme d'une trame de bits de codage de caractéristiques relatives à une transition associée audit noeud. 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 illustrant le stockage de données dans un circuit de mémoire conforme à l'invention; - la figure 3 montre un exemple d'implémentation d'une base dans un circuit de mémoire conforme à l'invention; - la figure 4 illustre l'organisation du circuit de mémoire pour la mémorisation des noeuds multiples; - la figure 5 est un schéma synoptique illustrant le codage des noeuds de chaque chaîne de noeuds; et - la figure 6 est un schéma synoptique illustrant le codage des noeuds multiples. 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'un motif ou 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 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 sont prévues pour ramener l'automate dans un état précédent prédéterminé. Toutefois, 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. Ainsi, par exemple, dans l'exemple illustré à la figure 2, le noeud initial E est un noeud multiple qui pointe vers huit noeuds consécutifs N1, N2; ..., N8. De même, le noeud désigné par la référence N3 constitue également un noeud multiple qui pointe vers plusieurs noeuds tels que Ni. Les autres noeuds, tels que Ni sont des noeuds de chaînes et pointent vers un unique noeud. A la construction du circuit de mémoire, les transitions entre noeuds sont élaborées en construisant, d'un part, des transitions valides Tv 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 en cas de non-reconnaissance d'un caractère dans un état donné (figure 3). Dans l'exemple représenté à la figure 3, à partir d'un état initial E, 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 final 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, des 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 constitutifs 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'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. Par exemple, la mémoire est subdivisée en A segments de A descripteurs, A étant par exemple égal à 256 (figure 4). Chaque segment correspond à une série de descripteurs consécutifs, associés chacun à un symbole donné de l'alphabet, qui décrivent le chemin qui a permis d'accéder au noeud dans l'arborescence. Les noeuds multiples sont ainsi également mémorisés relativement au noeud de base et leur adresse peut être calculée à partir de la relation: Address (s, offset) = S@ +s x offset + 1 Address (g) = S@ dans laquelle: Address(S, offset) désigne l'adresse d'un noeud multiple 20 espacé d'un noeud initial d'un décalage offset; - S@ désigne l'adresse du noeud de base; et - Address(E) 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 des noeuds multiples, ces noeuds sont codés de 25 la manière suivante. En se référant tout d'abord à la figure 5, les noeuds de chaque chaîne de noeuds sont codés en mémoire sous la forme d'une trame d'octets de longueur variable. Pour chaque noeud, la trame contient, d'une part, des octets TRANS et FS[OJ, .. , FS[nJ permettant de déterminer la transition relative au noeud, c'est-à-dire de déterminer le noeud destinataire de la transition et, d'autre part, de drapeaux constitués de champs permettant de décrire le contenu des octets servant à l'élaboration de la destination de la transition ou de décrire l'état associé au noeud ou encore le type de transition. Chaque noeud est ainsi codé à une adresse mémoire du circuit selon la trame représentée à la figure 5 qui contient les champs suivants: -TRANS permet de déterminer s'il existe une transition valide et fournit un symbole de l'alphabet pour lequel il existe une transition valide. L'état de destination est alors l'état consécutif situé à l'adresse suivante; et - FS[OJ, ... , FS[n] constitue un mot de longueur variable délivrant les 2s"' bits les moins significatifs de l'état de destination d'une transition d'échec. Les drapeaux sont, quant à eux, constitués des champs suivants: -TERM: ce champ est constitué d'un bit qui indique si l'état associé au noeud est un état terminal ou un état intermédiaire; - TRANS PRESENT: ce drapeau est constitué d'un bit qui indique s'il existe un champ TRANS dans la trame et permet ainsi de déterminer, sans avoir à décoder le champ TRANS, s'il existe une transition valide pour l'état en cours ou si la transition associée à cet état est une transition d'échec dont la destination est codée au moyen des octets FS[OJ, ..., FS[n] ; - FSLEN: ce drapeau contient plusieurs bits qui servent à indiquer la longueur du champ FS. Par exemple, une valeur 00 indique que le champ FS correspond à l'état initial E, toute autre valeur de ce champ FS_LEN spécifiant le nombre d'octets utilisés pour coder le champ FS; - S NODE: ce drapeau est constitué d'un bit qui est positionné à 1 lorsque une transition d'échec aboutit à un noeud multiple. Selon ce codage, une transition d'un premier état vers un deuxième état peut être mise en oeuvre de la manière suivante. A partir d'un état S et à réception d'un symbole d'entrée a;, un analyseur calcule l'adresse de destination de la transition comme suit. Si le drapeau TRANS_PRESENT est positionné à 1 et si la valeur contenue dans le champ TRANS correspond au symbole a;, l'état de destination est l'état S' suivant dans la chaîne de noeuds. L'adresse en octets de cet état S' est alors l'adresse de l'état S additionnée de la longueur du champ FS et de deux octets pour tenir compte d'un octet correspondant au champ TRANS et d'un octet correspondant aux drapeaux. Au contraire, si le champ TRANS_PRESENT n'est pas positionné à 1 , alors, si le champ S_NODE est positionné à 1 , l'adresse de l'état suivant S' est un noeud multiple à l'adresse codée par le champ FS. Si le drapeau S_NODE n'est pas positionné, alors l'état de destination S' est un noeud d'une chaîne de noeuds à l'adresse codée par le champ FS. Au vu de ce qui précède, l'analyseur de l'automate de reconnaissance de caractères peut déterminer les transitions au moyen de l'algorithme suivant: State TRANS (State S, a;) //transition valide: if (TRANS_PRESENT && (ai == TRANS)) return @(S) + FS LEN+2; else J t //transition d'échec: offset = concat (FS_EXT, FS[0], ..., FS[FS LEN] //Aller à un noeud multiple: if (S_NODE) return S@ + offset x sizeof (noeud multiple) ; else return C@ + offset //Aller à un noeud de chaîne. En se référant maintenant à la figure 6, le codage des noeuds multiples est effectué de la façon suivante. Ces noeuds sont également codés sous la forme d'une trame de bits servant à déterminer une transition associée aux noeuds. Chaque noeud multiple comporte également un certain nombre de champs servant à déterminer une transition associée au noeud et des drapeaux permettant de décrire le noeud multiple ou l'état associé au noeud. En ce qui concerne le champ servant à l'élaboration de la transition, celui-ci comporte deux champs T et S servant à calculer 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. 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; 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. Ainsi, 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 Cg. 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 (ai) à partir des paramètres T et S. A l'adresse de destination, comme indiqué précédemment. l'adresse contenue dans la clé K est comparée avec l'adresse du noeud 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. S //Noeud multiple suivant théorique pour la transition valide. Gs(a;) = A x (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'). REVENDICATIONS 1. Circuit de mémoire pour automate de reconnaissance de caractères de type Aho-Corasick dans lequel des chaînes de caractères prédéterminées sont reconnues dans un flux de données incident par mise en oeuvre de transitions successives dans une arborescence de noeuds stockée en mémoire dans laquelle chaque noeud (Ni) correspond à une séquence reconnue d'une chaîne de caractères et dans laquelle une partie au moins desdits noeuds est liée à un noeud consécutif par une transition valide, d'un état initial jusqu'à des états terminaux correspondant chacun à une chaîne de caractères reconnue, caractérisé en ce qu'il comporte des premiers ensembles d'adresses mémoires consécutives définissant respectivement des chaînes de noeuds consécutifs accessibles séquentiellement lors de transitions successives jusqu'à un état terminal et des deuxièmes ensembles d'adresses mémoires définissant des noeuds multiples pointant chacun vers plusieurs états. 2. Circuit de mémoire selon la revendication 1, caractérisé en ce que les noeuds de chaque chaîne de noeuds et les noeuds multiples sont adressables à partir d'un noeud de base et d'un décalage relatif par rapport audit noeud de base. 3. Circuit de mémoire selon l'une des revendications 1 et 2, caractérisé en ce que chaque noeud de chaque chaîne de noeud et chaque noeud multiple est codé en mémoire sous la forme d'une trame de bits de codage de caractéristiques relatives à une transition associée audit noeud. 4. Circuit de mémoire selon la revendication 3, caractérisé en ce que la trame de chaque noeud de la chaîne de noeuds comporte un ensemble de bits (TRANS_PRESENT) de codage d'un drapeau indiquant la présence d'une transition valide vers un noeud consécutif. 5. Circuit de mémoire selon la revendication 4, caractérisé en ce que la trame comporte un champ (FS) de codage de l'adresse d'un noeud de destination d'une transition en l'absence de transition valide. 6. Circuit de mémoire selon la revendication 5, caractérisé en ce que la trame comporte en outre un ensemble de bits (FS_LEN) de codage de la longueur du champ (FS) de codage. 7. Circuit de mémoire selon l'une dees revendications 5 et 6, caractérisé en ce que la trame de codage comporte en outre un ensemble de bits (SNODE) de codage du type de noeud de destination de la transition non valide. 8. Circuit de mémoire selon l'une quelconque des revendications 3 à 7, caractérisé en ce que la trame de codage de chaque noeud de la chaîne de noeuds comporte un ensemble de bits (TRANS) de codage d'un caractère suivant attendu pour une transition valide. 9. Circuit de mémoire selon l'une quelconque des revendications 3 à 8, caractérisé en ce que la trame de codage de chaque noeud de la chaîne de noeuds comporte un ensemble de bits (TERM) de codage d'une information indiquant si le noeud correspond à un état terminal constituant une reconnaissance d'une séquence de chaîne de caractères. 10. Circuit de mémoire selon la revendication 3, caractérisé en ce que la trame de codage de chaque noeud multiple comporte des bits (T, S) de codage de paramètres de calcul d'une fonction de transition valide et des bits de codage (K) d'un paramètre de vérification de la transition. 11. Circuit de mémoire selon la revendication 10, caractérisé en ce que la trame de codage comporte en outre des bits (FS) de codage d'un noeud de destination de la transition pour le noeud en l'absence de transition valide. 12. Circuit de mémoire selon l'une des revendications 10 et 11, caractérisé en ce que le paramètre de validation (K) est l'adresse d'un noeud immédiatement précédent, la transition étant validée lorsque le paramètre de validation du noeud de destination de la transition correspond à l'adresse du noeud précédent. 13. Circuit de mémoire l'une quelconque des revendications 10 à 12, caractérisé en ce que la trame de codage comporte en outre des bits (TERM) de codage d'une information indiquant si le noeud correspond à un état terminal constituant une reconnaissance d'une séquence de chaîne de caractères. 14. Circuit de mémoire pour automate de reconnaissance de caractères selon l'une des revendications 10 à 13, caractérisé en ce que la trame de codage comporte en outre des bits (JUMP) de codage indiquant si le noeud est un noeud d'une chaîne de noeuds ou un noeud multiple. 15. 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 prédéterminées sont reconnues dans un flux de données incident par mise en oeuvre de transitions successives dans une arborescence de noeuds stockée en mémoire dans laquelle chaque noeud correspond à une séquence reconnue d'une chaîne de caractères et dans laquelle une partie au moins desdits noeuds est liée à un noeud consécutif par une transition valide, d'un état initial jusqu'à des états terminaux correspondant chacun à une chaîne de caractères reconnue, caractérisé en ce que l'on stocke à des premiers ensembles d'adresses mémoire successives des premiers ensembles de noeuds définissant respectivement des chaînes de noeuds consécutifs accessibles séquentiellement lors de transitions successives jusqu'à un état terminal et des deuxièmes ensembles de noeuds multiples pointant vers plusieurs états à des deuxièmes ensembles d'adresses mémoires. 16. Procédé selon la revendication 15, caractérisé en ce que les noeuds de chaque chaîne de noeuds et les noeuds multiples sont adressables à partir d'un noeud de base et d'un décalage relatif par rapport audit noeud de base. 17. Procédé selon l'une des revendications 15 et 16, caractérisé chaque noeud de chaque chaîne de noeuds et chaque noeud multiple est codé en mémoire sous la forme d'une trame de bits de codage de caractéristiques relatives à une transition associée audit noeud.