Brevet FR2837951A1 — publié le 20031003

voyageur en ayant fait la demande. - 1 La présente invention se rapporte d'une manière générale à des procédés pour chercher utilisant des expressions de recherche définies par l'utilisateur. Le procédé de l' invention concerne de manière plus spécifique des procédés pour chercher dans une structure de données. La plupart des recherches typiques nocessite une expression de recherche définie par l'utilisateur (par exemple une séquence de recherche définie par l'utilisateur) et une structure de donnces (par exemple une base de données, un arbre de radicaux ou un dictionnaire) pour chercher l' expression de recherche définie par l'utilisateur. D'une manière générale, l' expression de recherche est un motif unique et il a souvent la forme d'une expression régulière. Une expression régulière est une expression qui contient un motif "joker", telle une séquence qui s'accorde (1) à un caractère quelconque (par exemple, "."), (2) à zéro ou plusieurs caractères (par exemple, ".*") ou (3) à zéro ou une fois la séquence à l'intérieur des parenthèses (par exemple "()?"). Par exemple, une expression réqulière "Al(fred I len I ly).*" s'accordera à des expressions non régulières (c'est-à- dire une expression sans motif joker) incluant "Al", "Alfred", "Allen" et "Ally". Typiquement, un utilisateur entre une expression régulière (c'est-à- dire une expression avec des motifs jokers) pour chercher dans une structure de données avec de multiples séquences d' expressions non régulières et un procédé pour chercher doit chercher dans toutes les séquences dans la structure des données pour renvoyer 2 - toutes les correspondances. Cependant, le processus consomme un temps considérable, dépendant de la taille de la structure des données, puisque chaque séquence dans la structure des données doit être examinée et comparée. Un autre procédé pour chercher disponible met en jeu une seule expression de recherche définie par l'utilisateur, qui est une expression non réqulière (c' est-à-dire une expression sans motif joker), pour chercher des expressions réqulières ou non régulières dans une structure de données. Parce que les valeurs de la structure de données sont définies par des expressions à la fois régulières et non réqulières, la structure de données est plus compliquée puisque que chaque expression régulière peut contenir de nombreuses variations. Par conséquent, un processus typique pour chercher, utilisant le procédé traditionnel pour chercher chaque séquence dans une structure de données, prendra un temps encore plus long. Il en résulte que ceci peut ne pas étre réalisable pour des structures de donnces contenant des milliers de motifs, tels que des listes nettes ("neLlists", listes de connexions) électriques. Une liste nette électrique est utilisée d'une manière générale pour décrire un groupe de n_uds reliés d'une manière logique, comprenant des données de connectivité pour chaque n_ud, dans une puce d'un circuit. Par exemple, la liste nette peut contenir une liste de commandes qui doivent étre appliquées à un objet conçu, tel que par exemple des connexions, des instances, des cellules et/ ou des ports. En outre, les objets conçus auxquels les commandes sont appliquées peuvent étre exprimés dans une expression réqulière. Par exemple, "clk" est un terme utilisé d'une manière commune pour désigner une horloge dans la conception d'un circuit et le terme "clk" est en général suivi d'un autre objet, tel que "buf", "in" ou "out". Le terme "clk" peut être exprimé dans une expression régulière "clk_(in I out I buf).*" pour inclure "clk_in", "clk_out" ou "clk_buf", et une seule valeur est utilisée plutôt que trois valeurs séparées. Un autre exemple est le terme "buf", qui est utilisé d'une manière générale après un autre objet dans une liste nette, nous pouvons utiliser une expression régulière ".*bufs" et capturer de nombreuses entrées avec juste une seule valeur. Par conséquent, l'utilisation d'une expression réqulière devient particulièrement utile, en particulier avec des listes nettes d'une taille et d'une complexité énormes. Une autre exécution mettant en jeu une structure similaire est un dictionnaire de mots. Par exemple, une expression réqulière consistant à "follow(s I ed I ing)?" est utilisée pour représenter follow, follows, followed et following ou une variation d'épellation d'un mot, par exemple "instruct[ie]r", peut être 2 0 util isé inclure des épel lat ions convenables et non convenables de "instructor". Le procédé typique n'est pas conçu pour rechercher ces expressions régulières d'une manière efficace et il en résulte que le temps nécessaire pour terminer une recherche est étendu de manière non nécessaire. Dans un premier aspect, l' invention propose un procédé pour chercher une liste de valeurs définies par des motifs et des données associées en correspondance à une expression de recherche définie par l'utilisateur, dans lequel une structure de donnces est utilisée pour stocker une pluralité de valeurs reliées par des clefs associées à une collection de n_uds ordonnés, ledit procédé comprenant les étapes consistant à: définir un 4 - 2837951 index clé comme un premier terme dans l' expression de recherche; définir un n_ud de recherche comme un premier n_ud dans la structure de données i définir une valeur de recherche comme une première valeur ayant un motif et des données associces dans le n_ud de recherche; effectuer une comparaison d'expression réqulière entre l' expression de recherche et le motif de la valeur de recherche; déterminer si une correspondance est trouvée à partir de la comparaison d' expression réqulière; et si une correspondance est trouvoe, ajouter la valeur de recherche à une liste de correspondances. Dans une variante de mode de réalisation du procédé de l' invention, il est prévu qu'un premier terme dans l'expression de recherche se rapporte à un préfixe défini par au moins un caractère ou une partie d'un caractère situé au début de l' expression de recherche ou un suffixe défini par au moins un caractère ou une partie d'un caractère situé à la fin de l' expression de recherche. Dans une autre variante de mode de réalisation du procédé de l' invention, il est prévu que ladite étape consistant à déterminer si une correspondance est trouvée à partir d'une comparaison d'expression régulière puisse comprendre en outre les étapes consistant à: si une correspondance n'est pas trouvée, avancer la valeur à une valeur suivante dans le n_ud de recherche; déterminer s'il existe une valeur suivante dans le n_ud de recherche; si une valeur suivante existe dans le n_ud de recherche, définir la valeur de recherche comme étant la valeur suivante et répéter depuis l'étape consistant à effectuer une comparaison d'expression réqulière entre l' expression de recherche et le motif de la valeur de recherche; et s'il n'y a pas de valeur suivante dans le n_ud de recherche, - 5 - 2837951 déterminer si l' index clé a dépassé l'extrémité de l'expression de recherche. Dans cette variante de mode de réalisation du procédé selon l' invention, il est prévu que ladite étape consistant à déterminer si l' index clé a dépassé une extrémité de l'expression de recherche puisse comprendre en outre les étapes consistant à: si l' index clé n'a pas dépassé l'extrémité de l' expression de recherche, déterminer si l'on trouve l' index clé comme une clé dans la structure de données; et, si l' index clé a dépassé l'extrémité de l' expression de recherche, renvoyer la liste des correspondances. Dans cette variante précise de mode de réalisation du procédé selon l' invention, il est prévu que ladite étape consistant à déterminer si l'on trouve l' index clé comme une clé dans la structure de données puisse comprendre en outre l'étape consistant à: si l'on ne trouve pas l' index clé dans la structure de données, renvoyer la liste des correspondances i et si l'on trouve l' index clé dans la structure de données, définir le n_ud de recherche comme étant le n_ud avec l' index clé. Dans cette variante de mode de réalisation du procédé selon l' invention, il est prévu que ladite étape consistant à définir le n_ud de recherche comme étant le n_ud avec l' index clé puisse comprendre en outre l'étape consistant à: avancer jusqu'à un terme suivant dans l' expression de recherche; définir l' index clé comme le terme suivant dans l'expression de recherche; et répéter depuis ladite étape consistant à déterminer une première valeur dans le n_ud de recherche. Dans un autre aspect, l' invention propose un procédé pour chercher une liste de valeurs définies par des motifs et des données associées en correspondance à - 6 - 2837951 une expression de recherche définie par l'utilisateur, dans lequel une structure de données est utilisée pour stocker une pluralité de valeurs reliées par des clés associées à une collection de n_uds ordonnés de telle sorte qu'au moins un n_ud pour stocker des valeurs avec un premier terme soit un terme d'expression réqulière et qu'au moins un n_ud pour stocker des valeurs avec un premier terme ne soit pas une expression régulière, ledit procédé comprenant les étapes consistant à: effectuer une comparaison d' expression régulière entre l'expression de recherche et le motif de chaque valeur dans au moins un n_ud stockant des valeurs un premier terme étant un terme d'expression réqulière; effectuer une comparaison d'expression régulière entre l' expression de recherche et le motif de chaque valeur dans un n_ud stockant des valeurs avec un premier terme correspondant à premier terme dans l'expression de recherche; et si l'on trouve une correspondance, ajouter la valeur à une liste des correspondances. Dans un autre aspect, l' invention propose un procédé pour construire une structure de données avec une liste de valeurs définies par l'utilisateur, dans lequel chaque valeur est définie par un motif et des données associces, ledit procédé comprenant les étapes consistant à: sélectionner une valeur définie par l'utilisateur ayant un motif et des données associces à partir de la liste; définir un motif sélectionné comme étant le motif de la valeur sélectionnée; définir un préfixe comme étant une séquence vide pour le motif sélectionné; définir un index de motif comme étant un premier terme dans le motif sélectionné; déterminer si l' index de motif est un terme d' expression réqulière; si l' index de motif est un terme d'expression régulière, ajouter le préfixe comme une clé et ajouter le motif sélectionné avec ses données associées comme - 7 - 2837951 une valeur pour la structure de données; si l' index de motif n' est pas un terme d' expression régulière, aj outer l' index de motif courant au préfixe et avancer à un terme suivant dans le motif sélectionné. Dans cette variante de mode de réa l i sat ion de ce procédé selon l' invention, il est prévu que ladite étape consistant à avancer jusqu'à un terme suivant dans le motif sélectionné puisse comprendre en outre les étapes consistant à: déterminer s'il y a un terme suivant dans le motif sélectionné; s'il y a un terme suivant dans le motif sélectionné, définir l' index de motif comme le terme suivant et répéter depuis ladite étape consistant à déterminer si l' index de motif est un terme d'expression réqulière; s'il n'y a pas de terme suivant dans le motif sélectionné, répéter depuis ladite étape consistant à aj outer un préfixe comme une clé et ajouter le motif sélectionné avec ses données associées comme une valeur à la structure de données. Dans cette variante de mode de réalisation du procédé selon l' invention, il est prévu que ladite étape consistant à aj outer le préfixe comme une clé et à ajouter le motif sélectionné avec ses données associées comme une valeur à la structure de données puisse comprendre en outre l'étape consistant à: déterminer si chaque motif des valeurs définies par l'utilisateur est ajouté à la structure de données; si chaque motif n'a pas été ajouté à la structure de données, répéter depuis ladite étape consistant à sélectionner une valeur définie par l'utilisateur ayant un motif et des donnces associées à partir depuis la liste; et si chaque motif a été ajouté à la structure de données, renvoyer la structure de données. DESCRIPTION DES DESSINS La figure 1 montre un diagramme par blocs d'un - 8 - 2837951 système informatique comprenant une structure de données organisée pour exécuter un mode de réalisation de l' invention; la figure 2 est un organigramme conforme à un mode de réalisation de la présente invention, illustrant la fonctionnalité d'un procédé pour chercher une expression de recherche dans une structure de données; la figure 3 est un organigramme montrant un mode de réalisation de la présente invention illustrant la fonctionnalité d'un procédé pour construire une structure de données; la figure 4 montre des clés formant des radicaux donnés à titre d'exemple utilisant des entrées définies par l'utilisateur de motifs et de donnces associées engendrés à partir du procédé montré à la figure 3 i et la figure 5 montre une structure de donnces formant un arbre de radicaux donnée à titre d'exemple utilisant des entrées définies par l'utilisateur de motifs et de données associées et les clés formant des radicaux montrées à la figure 4. DESCRIPTION DETAILLEE Dans la présente invention, seules des parties de la structure de données seront utilisées pour chercher l' expression de recherche. Il n'est pas nécessaire de traiter chaque point (c' est-à-dire clé d'un n_ud) de la structure de données, mais plutôt la présente invention traite la partie de la structure de données qui correspondrait de la manière la plus vraisemblable à l'expression de recherche. Il en résulte que la longueur du temps de recherche dépend de la longueur de l' expression de recherche plutôt que de la longueur de la structure de données. Un diagramme par blocs d'un système informatique conforme à un mode de réalisation de la présente - 9 - invention est montré à la figure 1 et est indiqué d'une manière générale par 10. Comme dans la plupart des systèmes informatiques typiques, il a un dispositif afficheur 12 pour afficher des donnces vers les utilisateurs, un processeur 14 pour traiter les donnces, un dispositif d'entrée 16 pour que des utilisateurs entrent des donnces, et une mémoire 18 pour stocker les données. Le processeur 14 accède à la mémoire 18 qui peut stocker, entre autres, des structures de données 20, des expressions de recherche 22, des listes de correspondances 24 et une liste de motifs 26. Les structures de données 20 sont engendrces par le processeur 14 à partir d'une liste de motifs 26 définie et entrce par des utilisateurs. Dans un mode de réalisation, la structure de données est un arbre de radicaux, qui est un genre spécial d'arbre binaire utilisé pour stocker des collections de séquences de bits de longueurs arbitraires. Cependant, on comprendra que d'autres structures de données, par exemple une base de données, peuvent aussi être exécutées avec la présente invention. Il en résulte que ces différentes exéautions sont dans la portée de la présente invention. Lorsque la structure de données 20 a été engendrce (par exemple, un arUre de radicaux), une expression de recherche 22, de préférence définie par l'utilisateur, est utilisée pour chercher dans une structure de données spécifiée, ce qui est exécuté par le processeur 14. Une liste des correspondances 24 est par conséquent engendrée par le processus pour chercher, et est stockée dans la mémoire 18. Le résultat de l'analyse peut alors être affiché sur le dispositif afficheur 12 vers les utilisateurs. Du fait des nombreuses exécutions possibles de la présente invention, une explication du mode de - 10 - 2837951 réalisation courant du système informatique est donnée à titre d'exemple. Cependant, il faut comprendre que la présente invention peut être exécutée dans de nombreux codes informatiques, par exemple en codes de machines, et en matériel. En outre, la présente invention peut être exécutée avec différents genres de structures de données, tels que des bases de données et des dictionnaires. Par conséquent, il faut comprendre que d'autres personnes compétentes dans la technique peuvent apprécier les exécutions des multiples systèmes et configurations et ces exécutions sont dans la portée de la présente invention. Cependant, un arbre de radicaux est utilisé comme structure de données selon un mode de réalisation et la présente invention sera expliquée et décrite avec une exécution en arUre de radicaux de la structure de données. Un mode de réalisation d'un procédé pour chercher une expression de recherche 22 dans une structure de données 20 conformément à l' invention est montré à la figure 2. Le procédé est lancé par un utilisateur, par l'intermédiaire du dispositif d'entrée 16, en appelant une commande pour démarrer le procédé. Cependant, un démarrage automatique par un programme informatique est aussi envisagé, selon la conception et les besoins de l'exécution. Un utilisateur entre une expression de recherche pour chercher dans une ou plusieurs structures de données (bloc 52). S'il y a de nombreuses expressions de recherche ou/ et de nombreuses structures de données, la présente invention peut être 3Q organisce de manière automatique pour itérer le procédé sur les nombreuses expressions de recherche eti ou les nombreuses structures de données. Au démarrage du procédé (bloc 52), le procédé effectue d'abord certaines commandes d'initialisation comprenant, par exemple, une définition des variables - 11 - 2837951 nécessaires dans le procédé (bloc 54). Dans ce mode de réalisation, un n_ud de recherche est défini comme premier n_ud de la structure de données, un index clé est défini comme premier terme de l' expression de recherche entrce par l'utilisateur et la liste des correspondances est définie comme étant une liste vide (bloc 54). On notera que le premier terme dans l' expression de recherche peut être défini selon un certain nombre de manières, même si, dans ce mode de réalisation, la logique de recherche démarre depuis le début et cherche un seul caractère à la fois. Par exemple, le premier terme peut être un préfixe défini par un ou plusieurs caractères ou une partie d'un seul caractère situé au début de l' expression de recherche, ou peut aussi être un suffixe défini par un ou plusieurs caractères ou une partie d'un seul caractère situé dans l' expression de recherche. Par conséquent, ces différentes exécutions sont envisagées et elles sont dans la portée de la présente invention. Cependant, pour des raisons de clarté, un caractère se rapporte à un seul caractère dans l' expression de recherche, et un terme se rapporte à un ou plusieurs caractères ou une partie d'un seul caractère dans l 'expression de recherche précisoe par l'ingénieur du procédé pour chercher, là o la recherche doit commencer dans l' expression de recherche. En outre, les noms de ces variables et l'ordre selon lequel chaque variable est définie ne sont pas importants. En outre, les contraintes d'initialisation sont spécifiques à l'exécution. Néanmoins, toutes les variables nécessaires pour le processus sont définies au démarrage du procédé dans ce mode de réalisation. Lorsque le n_ud de recherche a été défini comme étant le premier n_ud de la structure de données (bloc 54) une variable suivante, la valeur recherchée, est - 12 - 2837951 définie comme étant la première valeur d'une liste de valeurs du n_ud de recherche (bloc 56). De manière indépendante du genre de la structure de données utilisée, la structure de donnces doit avoir un jeu de n_uds ordonnés, qui sont utilisés d'une manière générale pour faire référence à un point ou à un sommet dans un graphe. Tour à tour, chaque n_ud contiendra des clés et certaines clés sont associées à des valeurs contenant des motifs et des données associées aux motifs ("donnces associées"). Puisque la recherche démarre au début de la structure des données, le n_ud de recherche est défini comme étant le premier n_ud (c' est-à-dire point) dans la structure de données. De même, avec le premier n_ud de la structure de données, la première valeur du premier n_ud est aussi utilisée comme première valeur de recherche dans ce mode de réalisation. En définissant le n_ud de recherche et la valeur de recherche, le procédé peut démarrer du début et opérer de manière récursive jusqu'à avoir traité chaque valeur de n_ud et chaque n_ud de la structure de données. En prenant la première valeur du n_ud de recherche comme la valeur de recherche courante (bloc 56), le pas suivant consiste à effectuer une comparaison réqulière de l' expression entre l' expression de recherche et le motif dans la valeur de recherche (bloc 58). En pratique, puisqu'une expression régulière définit de nombreuses expressions non régulières, toutes les expressions non régulières possibles (c' est-à-dire les motifs) sont compilées dans une machine à états finis. A partir de la machine à états finis, on détermine alors s'il existe une correspondance pour l'expression de recherche. La comparaison d'une expression réqulière est bien connue dans la technique et différentes exécutions pour effectuer une telle comparaison sont 13 - 2837951 connues de ceux qui ont des compétences dans la technique. Lorsque la comparaison a été effectuée (bloc 58) on détermine ensuite s'il existe une correspondance pour l' expression de recherche (bloc 60). Dans l'affirmative, la valeur couramment définie comme valeur de recherche est ajoutée à la liste des correspondances 24 (bloc 62). Si soit la comparaison n'a pas trouvé de correspondance (bloc 60) soit la valeur en correspondance a été ajoutée (bloc 62), le procédé continue et avance la valeur de recherche à la valeur suivante dans la liste associée au n_ud de recherche (bloc 64). On détermine ensuite s'il existe une telle valeur suivante dans la liste des valeurs associée au n_ud de recherche (bloc 66. Puisque la première valeur est utilisée, il peut y avoir une autre valeur dans le n_ud de recherche défini couramment (bloc 66). Dans ce cas, on définit cette autre valeur comme la valeur de recherche (bloc 68) et le procédé rebouele pour effectuer une comparaison de l' expression régulière pour la valeur de recherche nouvellement définie (bloc 58). Comme cela est montré, le procédé continuera à reboucler jusqu'à avoir traité toutes les valeurs du n_ud de recherche. Cependant, une fois qu'il a déterminé qu'il n'y a pas d'autre valeur suivante associée au n_ud de recherche (bloc 66), le procédé détermine ensuite si l' index clé a dépassé l'extrémité de l' expression de recherche (bloc 70). En d'autres termes, on détermine si le terme dans la clé de recherche définie comme l' index clé a dépassé l'extrémité de l' expression de recherche. Si c'est le cas, cela indique que chaque terme dans l' expression de recherche a été traité. La liste des correspondances est renvoyée à l'utilisateur (bloc 72) et le processus - 14 - 2837951 se termine à ce point. Par contre, si l' index clé n'a pas dépassé l'extrémité de l' expression de recherche (bloc 70), on détermine alors si l' index clé, qui était le premier terme dans l 'expression de recherche (bloc 54), est défini comme un n_ud dans la structure de données (bloc 74). S'il existe un n_ud dans la structure de données qui est le même que l' index clé (bloc 74), le n_ud de recherche est redéfini pour le n_ud trouvé dans la structure de données qui correspondait à l' index clé (bloc 76). En outre, le procédé avancera l' index clé au terme suivant dans l' expression de recherche (bloc 76) et l' index clé sera aussi redéfini au terme suivant (bloc 78). A partir de ce point, le procédé reboucle vers l'étape consistant à définir la première valeur du n_ud de recherche nouvellement défini comme valeur de recherche (bloc 56). Cependant, s'il n'y a pas de n_ud dans la structure de données défini comme index clé (bloc 74), la liste des correspondances est renvoyée à l'utilisateur (bloc 72) et le processus prend fin. Du fait de la configuration du procédé pour chercher, l' expression de recherche n'est cherchée que pour des parties de la structure de donnces. En contraste aux procédés antérieurs, la présente invention ne gaspille pas de temps à chercher chaque valeur dans la structure de donnces. Au lieu de cela, elle ne parcourt que les points (c' est-à-dire les clés dans un n_ud) de la structure de données qui correspondraient de manière la plus vraisemblable à l' expression de recherche. La longueur de la recherche dépend de la longueur de l' expression de recherche, plutôt que de la longueur de la structure de donnces. La présente invention fournit aussi un procédé pour construire une structure de donnces conçue pour être utilisée avec le procédé pour chercher montré à la À 15 - 2837951 figure 2. Une mode de réalisation d'une fonctionnalité du procédé pour construire une structure de données est montré à la figure 3. Dans ce mode de réalisation, le procédé pour construire est à nouveau lancé par un utilisateur, par l'intermédiaire du dispositif d'entrée 16, en appelant une commande pour démarrer le procédé. Cependant, un lancement automatique par un programme informatique est aussi envisagé, selon la conception et les besoins de l'exécution. Un utilisateur, dans ce mode de réalisation, entre une liste de motifs et de données associées (bloc 102). Lorsque l'utilisateur a engendré une liste de motifs et de données associées pour construire la structure de données (bloc 102), le procédé pour construire commence par son initialisation en créant une structure de données vide (bloc 104). L'étape suivante consiste à déterminer si chaque motif entré par l'utilisateur a été mis dans la structure de données (bloc 106). Dans l'affirmative, cela signifie que tous les motifs entrés par l'utilisateur ont été traités et le procédé renverra la structure de données à l'utilisateur (bloc 108). Cependant, puisqu'une structure de donnces vide a été créée et qu'aucun motif n'a été traité, on déterminera que les motifs n'ont pas tous été entrés dans la structure de données (bloc 106). Dans ce cas, les variables qui sont nécessaires pour le procédé seront définies. De manière plus spécifique, un motif suivant, qui est le premier motif entré par l'utilisateur, sera défini comme motif sélectionné, et une séquence vide (c' est-à-dire " ") sera prise comme préfixe pour le motif sélectionné (bloc 110). Finalement, on définit aussi le motif d' index comme premier terme dans le motif sélectionné (110). Lorsque les variables ont été définies (bloc 110), on détermine ensuite si l' index de motif est un terme - 16- 2837951 d'expression réqulière (bloc 112). Si l' index de motif n'est pas un terme d'expression réqulière (bloc 112), on ajoute l' index de motif au préfixe et on l'avance jusqu'au terme suivant dans le motif sélectionné (bloc 114). On détermine ensuite si un tel terme suivant, en fait, existe dans le motif sélectionné (bloc 116). si c'est le cas, on redéfinit alors l' index de motif comme terme suivant (bloc 118), et on reboucle à l'étapeconsistant à déterminer si un index de motif nouvellement défini est un terme d'expression régulière (bloc 112). Le sous-programme s'exécutera jusqu'à ce que soit tous les termes dans le motif sélectionné soient traités soit, dans le motif sélectionné, on ait trouvé qu'un terme est une expression régulière. Si par contre, soit l' index de motif est un terme d'expression régulière (bloc 112) soit tous les termes du motif sélectionné ont été traités (bloc 116), on ajoute une clé et une valeur d'entrée à la structure de données (bloc 120). En particulier, on définit le préfixe comme une (ou plusieurs) clé(s) pour le (ou les) n_ud(s) et le motif avec ses donnces associces comme étant la valeur dans la structure de données (bloc 120). On reLoucle alors le procédé à l'étape consistant à déterminer si chaque motif a été mis dans la structure de données (bloc 106) et ce dernier continuera à opérer de manière réaursive jusqu'à ce que tous les motifs aient été traités et que la structure de données soit renvoyée (bloc 108). Comme nous le montrons, la structure de données est configurée de telle manière que l'on cherchera les valeurs avec un terme d'expression réqulière au début du motif à l' aide du procédé pour chercher, et on restreindra la recherche aux seules parties de la structure de données qui correspondent aux termes non réguliers situés au début ou à la fin de l' expression de recherche. Des clés formant des radicaux données à titre d'exemple, engendrées en utilisant des entrées définies par l'utilisateur de motifs et de données associces et la structure résultante de donnces d'arbre de radicaux engendrées sont respectivement montrés aux figures 4 et et indiquces d'une manière générale en 130, 140, et seront utilisées comme un exemple pour un traitement par l'intermédiaire des procédés montrés aux figures 2 et 3. En nous tournant vers la première entrée de l'utilisateur (c' est-à- dire l'entrée #1) à la figure 4 et concernant le procédé montré à la figure 3, supposons que "clk_(in I out I buf).*" soit le motif entré par l'utilisateur et défini comme le motif sélectionné (c' est-à-dire selectod pattern = "clk_(in I out I buf.*") et notons que les données associces à cette entrée sont "is_clock". Le préfixe est défini comme étant une séquence vide (c' est-à-dire prefix = " "), et l' index de motif sera alors défini à "c" (c'est- à-dire pattern index = "c"). Notons que dans cet exemple, le premier terme est configuré comme un seul caractère au début du motif. Cependant, une fois encore, on comprendra que l'on envisage plusieurs caractères à différents emplacements et que cela est dans la portée de la présente invention. Comme nous le montrons, puisque "c" n'est pas une expression réqulière, l' index de motif sera ajouté au préfixe. En d'autres termes, le préfixe sera ajouté à l' index de motif (c' est-à-dire prefix = ";c"). En nous tournant vers le terme suivant dans le motif, "l", l' index de motif est alors défini à "l" (c' est-à-dire pattern index = "l"). Celuici n'est à nouveau pas une expression réqulière, si bien que le "l" est ajouté au préfixe (c' est-à-dire prefix = " i c; l) et il en va de même pour "k_" (c' est-à-dire, prefix = " i c; li k_). Cependant, lorsque nous arrivons au - 18 - 2837951 "(" dans le motif sélectionné, lequel est une expression réqulière, on aoute à la structure de données une clé pour le préfixe et une valeur pour le motif et les données associées. Dans cet exemple, nous aurons pour clé " " (séquence vide) suivie par un "c", "l" et T'k", ce qui est l'endroit o l'on trouverait la valeur. En nous tournant maintenant vers la figure 5, nous voyons une " " (séquence vide) comme n_ud supérieur, qui débranche vers un n_ud avec un "c" et suivi par un autre n_ud avec une clé "l" et une clé "k" avec le motif et les données associées. Si toutes les entrces de la figure 4 ont été traitéss, une structure de donnces, qui est un arbre de radicaux dans un mode de réalisation montré à la figure 5, sera engendrée. De manière plus spécifique, l'arUre de radicaux montré à la figure 5 est du genre "Arbre". Cependant, on devra comprendre que la présente invention envisage aussi l'utilisation de différents genres d'arbres de radicaux et de nombreuses autres exécutions sont dans la portée de la présente invention. Cet exemple montre comment le procédé pour construire montré à la figure 3 fonctionne avec un exemple. En utilisant la structure de donnces montrée à la figure 5, on peut facilement chercher une expression de recherche, par exemple "clk_bufs", dans la structure de données en utilisant le procédé pour chercher montré à la figure 2. En premier lieu, on définit le n_ud supérieur (c'est-àdire le premier n_ud) de la structure de donnces comme n_ud de recherche (c'est-à- dire search node = " "), et on définit le premier terme de l' expression de recherche comme index clé (c'est-à- dire key index = "c"). A partir du n_ud de recherche, on définit la première valeur comme la valeur de recherche (c' est-à-dire search value = ".*bufs" et - 19 - 2837951 "set_delay 3"). Après avoir effectué une comparaison d'expressions réqulières entre l' expression de recherche (c' est-à-dire "clk_bufs") et le motif dans la valeur de recherche (c' est-à-dire ".*bufs") et après avoir trouvé une correspondance, on ajoute la valeur à la liste des correspondances. Le sous-programme continuera à reboucler pour les valeurs restantes qui sont "(n)?shift" / "is_shift_ctl" et (addlsublmult) _enable'' / "set_cap 32". Cependant, comme nous le montrons, les motifs de ces autres valeurs ne s'accordent pas à l 'expression de recherche. Après avoir terminé la recherche pour le n_ud de recherche constitué d'une chaine vide tc'est-à-dire " "), on détermine ensuite si l' index clé a dépassé l'extrémité de la clé de recherche. Puisque l' index clé (par exemple "c") est le premier terme de l'expression de recherche et que la longueur de l' expression de recherche (c' est-à-dire "clk_bufs) possède huit caractères, l' index clé, dans cette boucle, n'est pas au delà de l'extrémité de la clé de recherche. IL en résulte que l'on détermine ensuite si l' index clé, qui vaut "c", qui a été défini dans une étape ultérieure, peut être trouvé dans le n_ud. En se reportant à la figure 5, on trouve une clé "c" dans le n_ud, et on définit le n_ud de recherche à l' index clé "c" dans le n_ud. On avance aussi l' index clé au terme suivant dans la recherche en le définissant comme un index clé nouvellement défini. Le procédé reboucle à l'étape consistant à redéfinir la valeur de recherche pour le n_ud de recherche nouvellement défini. Le procédé continue à nouveau à opérer de manière récursive et, finalement, il trouvera la valeur "clk_(in I out I buf).*" / "is_clock" à la figure 5. A partir de la description précédente, on comprendra qu'un système et un procédé améliorés pour chercher une liste de valeurs en correspondance à une expression de recherche définie par l'utilisateur et pour construire une structure de données avec une liste de valeurs pour effecteur la recherche, qui possèdent plusieurs attributs et avantages souhaitables, ont été montrés et décrits. Le système et le procédé fournissent une manière plus rapide pour chercher dans une structure de données en utilisant une expression de recherche spécifiée. Bien que nous ayons montré et décrit plusieurs modes de réalisation de la présente invention, on comprendra que d'autres modifications, substitutions et variantes sont apparentes à celui qui a des compétences ordinaires dans la technique. De telles modifications, substitutions et variantes peuvent être faites sans départir de l' esprit et de la portée de l' invention lesquels doivent être déterminés à partir des revendications jointes. Différents aménagements de l' invention sont exposés dans les revendications jointes. 21 2837951 REVENDICATIONS 1. Procédé mis en _uvre dans un système informatique possédant un processeur (14) et une mémoire (18) de données pour chercher dans ladite mémoire une liste de valeurs définies par des motifs de données et des données associées en correspondance à une expression de recherche définie par l'utilisateur, dans lequel une structure de données (20) est utilisée pour stocker dans la mémoire (18) une pluralité de valeurs reliées par des clefs associées à une collection de n_uds ordonnés, ledit procédé comprenant les étapes, mises en _uvre par le processeur, consistant à: définir un index clé comme un premier terme dans l' expression de récherche (54); ' définir un n_ud de recherche comme un premier n_ud dans la structure de données (54); définir une,valeur de recherche, comme une première, valeur ayant un motif de données et des données associces dans le n_ud de recherche (56); effectuer une comparaison d'expression régulière entre l'expression de recherche et le motif de donnces de la valeur de recherche (58); déterminer si une correspondance est trouvée à partir de la comparaison d' expression réqulière (60); et si une correspondance est trouvoe, aj outer la valeur de recherche à une liste de correspondances (62). 2. Procédé conforme à la revendication 1, dans lequel un premier terme dans l'expression de recherche se rapporte à un préfixe défini par au moins un caractère ou une partie d'un caractère situé au début de 22 2837951 l' expression de recherche ou un suffixe défini par au moins un caractère ou une partie d'un caractère situé à la fin de l 'expression de recherche. 3. Procédé conforme à la revendication 1, dans lequel ladite étape consistant à déterminer si une correspondance est trouvée à partir d'une comparaison d' expression réqulière (60) comprend en outre les étapes consistant à: si une correspondance n'est pas trouvée, avancer la valeur à une valeur suivante dans le n_ud de recherche (68); déterminer s'il existe une valeur suivante dans le n_ud de recherche (66); si une valeur suivante existe dans le n_ud de recherche, définir la valeur de recherché comme étant la valeur suivante (68) et répéter depuis l'étape consistant à effectuer une comparaison d'expression régulière eptre l' expression de recherche et le motif de données de la valeur de recherche (58) i et s'il n'y a pas de valeur suivante dans le n_ud de recherche, déterminer si l' index clé a dépassé l'extrémité de l' expression de recherche (70). 4. Procédé conforme à la revendication 3, dans lequel l'étape consistant à déterminer si l' index clé a dépassé une extrémité de l' expression de recherche comprend en outre les étapes consistant à: si l' index clé n'a pas dépassé l'extrémité de l' expression de recherche, déterminer si le processeur trouve l' index clé comme une clé dans la structure de données (74); et, si l' index clé a dépassé l'extrémité de l' expression de recherche, renvoyer la liste des correspondances (72).! 23 2837951 5. Procédé conforme à la revendication 4, dans lequel ladite étape consistant à déterminer si le processeur trouve l' index clé comme une clé dans la structure de donnces (74) comprend en outre l'étape consistant à: si le processeur ne trouve pas l' index clé dans la structure de données, renvoyer la liste des correspondances (72); et si le processeur trouve l' index clé dans la structure de données, définir le n_ud de recherche comme étant le n_ud avec l' index clé (76). 6. Procédé conforme à la revendication 5, dans lequel ladite étape consistant à définir le n_ud de recherche comme étant le n_ud avec l' index clé comprend en outre l'étape consistant à: avancer jusqu'à un terme suivant dans l' expression de recherche (76); définir l' index clé comme le terme suivant dans l' expression de recherche (78); et répéter depuis ladite étape consistant à déterminer une première valeur dans le n_ud de recherche (56). 7. Procédé mis en _uvre dans un système informatique comprenant un processeur (14) et une mémoire (18) de données, pour chercher dans ladite mémoire une liste de valeurs définies par des motifs de données et des donnces associées en correspondance à une expression de recherche définie par l'utilisateur, dans lequel une structure de données (20) est utilisce pour stocker dans ladite mémoire une pluralité de valeurs relices par des clés associées à une collection de n_uds ordonnés de telle sorte qu'au moins un n_ud pour stocker des valeurs avec un premier terme soit un terme À 2837951 d' expression réqulière et qu'au moins un n_ud pour stocker des valeurs avec un premier terme ne soit pas une expression réqulière, ledit procédé comprenant les étapes, mises en _uvre par le processeur, consistant à: effectuer une comparaison d'expression réqulière entre l'expression de recherche et le motif de données de chaque valeur dans au moins un n_ud stockant des valeurs un premier terme étant un terme d'expression réqulière (58) i effectuer une comparaison d' expression régulière entre l 'expression de recherche et le motif de données de chaque valeur dans un n_ud stockant des valeurs avec un premier terme correspondant à premier terme dans l 'expression de recherche (58); et ... si le processeur trouve une correspondance, ajouter la valeur à une liste des correspondances (64). 8. Procédé mis en _uvre dans un système informatique possédant un processeur (14) et une mémoire (18) de données pour construire une structure de données (20) avec une liste de valeurs définies par l'utilisateur, dans lequel chaque valeur est déLinie par un motif de donnces et des données associées, ledit procédé comprenant les étapes, mises en _uvre par le processeur, consistant à: sélectionner une valeur définie par l'utilisateur ayant un motif de donnces et des données associées à partir de la liste i définir un motif de données sélectionné comme étant le motif de donnces de la valeur sélectionnée (110); définir un préfixe comme étant une séquence vide pour le motif de données sélectionné (110); définir un index de motif de données comme étant 2 5 2837951 un premier terme dans le motif de données sélectionné (110) i déterminer si l' index de motif de données est un terme d'expression régulière (112); si l' index de motif de données est un terme d' expression régulière, aj outer le préfixe comme une clé et ajouter le motif de données sélectionné avec ses données associées comme une valeur pour la structure de données (20); si l' index de motif de données n'est pas un terme d' expression régulière, aj outer l' index de motif de données courant au préfixe et avancer à un terme suivant dans le motif de données sélectionné (114). 9. Procédé conforme à la revendication 8, dans lequel ladite étape consistant à avancer jusqu'à un terme suivant dans le motif de données sélectionné (114) comprend en outre les étapes consistant à: déterminer s'il y a un terme suivant dans le motif de donnces sélectionné (116); s'il y a un terme suivant dans le motif de donnces sélectionné, définir l' index de motif de données comme le terme suivant (118), et répéter depuis ladite étape consistant à déterminer si l' index de motif de donnces est un terme d'expression régulière (112); s'il n'y a pas de terme suivant dans le motif de données sélectionné, répéter depuis ladite étape consistant à aj outer un préfixe comme une clé et ajouter le motif de données sélectionné avec ses données associées comme une valeur à la structure de données (120). 10. Procédé conforme à la revendication 9, dans lequel ladite étape consistant à ajouter le préfixe comme une clé et à ajouter le motif de données sélectionné avec ses donnces associées comme une valeur à la structure de données (120) comprend en outre l'étape consistant à: déterminer si chaque motif de données des valeurs définies par l'utilisateur est ajouté à la structure de données (106); si chaque motif de données n'a pas été ajouté à la structure de données, répéter depuis ladite étape consistant à sélectionner une valeur définie par l'utilisateur ayant un motif de données et des données associées à partir depuis la liste (110); et si chaque motif de données a été ajouté à la structure de données, renvoyer la structure de données (108).