Brevet FR2914451A1 — publié le 20081003

La présente invention se rapporte à un procédé et un dispositif d'évaluation d'une expression, notamment d'une expression de type XPath, sur des éléments d'un document structuré. Elle trouve une application générale dans le traitement de flux de données XML et plus précisément sur des fichiers au format XML. Le langage de balisage XML, acronyme de eXtensible Markup Language , c'est-à-dire un langage à balise extensible, est une syntaxe pour la définition de langages informatiques. Ce langage est standardisé par le comité de standardisation W3C (une description du langage peut être trouvée à l'adresse http://www.w3.org/TR/REC-xml). Le langage XML est une syntaxe permettant de définir de nouveaux langages. Ainsi, il est rendu possible de définir une pluralité de langages XML qui peuvent être traités en utilisant des outils génériques. Le langage XML définit une syntaxe particulière pour mélanger les informations structurelles et les informations de contenu. Le langage XML définit plusieurs types d'items pour décrire les informations structurelles et les informations de contenu. Selon cette syntaxe, chaque élément est défini par une balise ouvrante comportant le nom de l'élément (par exemple: ), une balise fermante comportant elle aussi le nom de l'élément (par exemple: ). Chaque élément peut contenir d'autres éléments ou des données textuelles. Un élément peut aussi être précisé par des attributs. L'attribut est un item localisé dans la balise ouvrante d'un élément et contient, outre le contenu même de l'attribut, un identifiant pour le définir (par exemple : ). La syntaxe XML permet aussi de définir des commentaires (par exemple : ) et des instructions de traitement ( Processing Instruction selon la terminologie anglo-saxonne), qui peuvent préciser à une application informatique quels traitements appliquer au document XML (par exemple: ). L'ensemble des objets décrits par la syntaxe XML, à savoir les éléments, les attributs, les données textuelles, les commentaires et les instructions de traitement, est regroupé sous la désignation de noeud XML. Enfin, la syntaxe XML est textuelle et peut être lue ou écrite aisément par un utilisateur. Plusieurs langages XML différents peuvent contenir des éléments de même nom. Ainsi, pour pouvoir mélanger plusieurs langages XML différents, la syntaxe XML permet de définir des espaces de nommage ( Namespace selon la terminologie anglo-saxonne). De cette manière, deux éléments sont identiques s'ils ont le même nom et se trouvent dans le même espace de nommage. Un espace de nommage est défini par un identifiant uniforme de ressource aussi appelé URI ( Uniform Resource Identifier en terminologie anglo-saxonne), par exemple : http://canon.crf.fr/xml/monlangage . L'utilisation d'un espace de nommage dans un document XML est réalisée par la définition d'un préfixe qui est un raccourci vers l'identifiant uniforme de ressource de cet espace de nommage. Ce préfixe est défini au moyen d'un attribut spécifique. Par exemple, l'expression xmins:ml="http://canon.crf.fr/xml/monlangage" associe le préfixe ml à l'identifiant uniforme de ressource http://canon.crf.fr/xml/monlangage . Ensuite, l'espace de nommage d'un élément ou d'un attribut est précisé en faisant précéder le nom par le préfixe associé à l'espace de nommage suivi de deux-points : tel qu'illustré dans l'exemple suivant : . Le langage XPath (acronyme de XML Path Language ) est issu d'une spécification du consortium W3C appelée Spécification XPath 1.0 , présente à l'adresse www.w3.org/TR/xpath. Ce langage a pour objectif de définir une syntaxe adaptée à adresser des parties d'un document structuré de type XML. Ce langage a été développé initialement pour fournir une base commune à différentes applications, par exemple aux applications XSLT ( eXtensible Stylesheet Language Transformations en terminologie anglo-saxonne) et XQuery, traitant des documents de type XML. La syntaxe de ce langage utilise une syntaxe similaire à celle utilisée dans les expressions relatives à des chemins de localisation dans un système de fichiers, par exemple l'expression relative à un chemin de localisation /librairie/livre . Les chemins de localisation ( LocationPath selon la syntaxe du langage XPath) définissent un ensemble de noeuds XML et les relations entre ces noeuds. Par exemple, le chemin /a/b désigne l'ensemble des éléments b fils d'un élément a racine du document XML. Un chemin de localisation est ainsi constitué d'un ensemble d'étapes de localisation ( Steps en terminologie anglo-saxonne), chaque étape de localisation précisant une filiation, aussi appelé axe selon la syntaxe XPath ( AxisSpecifier en terminologie anglo-saxonne), un test de noeud ( NodeTest en terminologie anglo-saxonne) et éventuellement un ensemble de prédicats ( Predicate en terminologie anglo-saxonne). La relation de filiation permet de définir la relation entre le noeud sélectionné par l'étape de localisation et le(s) noeud(s) contextuel(s). Pour la première étape de localisation, le noeud contextuel est soit la racine du document, soit le noeud courant. Pour les autres étapes de localisation, les noeuds contextuels sont ceux sélectionnés par l'étape de localisation précédente. Par défaut, si la relation de filiation n'est pas précisée, l'étape de localisation courante concerne les enfants directs des noeuds contextuels. D'autres relations de filiation existent permettant de naviguer facilement dans l'ensemble du document XML. Par exemple, le chemin /a/descendant::b désigne l'ensemble des 30 éléments b descendant, directement ou non, d'un élément a racine du document XML. A l'inverse, le chemin b/ancestor::a désigne l'ensemble des éléments a ancêtre, directement ou non, d'un élément b enfant du noeud courant. Selon un autre exemple, le chemin /descendant::a/following::b 5 désigne l'ensemble des éléments b suivant un élément a situé à une quelconque profondeur dans le document. Une relation de filiation spécifique permet de désigner les attributs d'un élément. Par exemple, le chemin /a/attribute::b retourne l'attribut b de l'élément a racine du document XML. 10 Les relations de filiation comprennent, d'une part, les relations de filiation vers l'avant ou descendante ( forward axis en terminologie anglo-saxonne) qui décrivent des relations dans l'ordre du document, c'est-à-dire des relations qui vont sélectionner des noeuds apparaissant dans le document après le noeud contextuel, et, d'autre part, les relations de filiation vers l'arrière 15 ou ascendante ( reverse axis en terminologie anglo-saxonne) qui décrivent des relations inverses à l'ordre du document, c'est-à-dire des relations qui vont sélectionner des noeuds apparaissant dans le document avant le noeud contextuel. Le test de noeud permet de préciser les caractéristiques des noeuds 20 recherchés. Un exemple de test de noeud est le test sur le nom des noeuds à rechercher. Par exemple, l'expression /descendant::a retourne l'ensemble des éléments a du document. 25 Selon un autre test de noeud, il est permis d'obtenir tous les éléments quel que soit leur nom. Par exemple, l'expression /descendant::* retourne l'ensemble des éléments du document. Selon encore un autre test de noeud, il est permis de retourner les 30 éléments ayant un type défini. Par exemple, l'expression /descendant::comment() retourne tous les noeuds du document de type commentaire. Les prédicats permettent d'imposer une ou plusieurs conditions supplémentaires pour la recherche de noeuds qui sont solutions d'une étape de localisation. Ces conditions peuvent prendre la forme d'une position. Par exemple, l'expression /a/b[2] désigne le deuxième élément b fils de l'élément racine a . Elles peuvent aussi prendre la forme d'un test. Par exemple, l'expression /a/b[c] désigne l'ensemble des éléments b fils de l'élément racine a et ayant un élément fils c . Les conditions peuvent aussi permettre de vérifier le contenu d'un élément ou d'un attribut. Ainsi, par exemple, l'expression /a/b[c="valeur"] désigne l'ensemble des éléments b fils de l'élément racine a ayant un élément fils c dont la valeur textuelle est valeur . De façon similaire, l'expression /a/b[@c="valeur"] désigne l'ensemble des éléments b fils de l'élément racine a ayant un attribut c dont la valeur est valeur . Une étape d'un chemin de localisation peut comporter plusieurs prédicats. Ces prédicats sont appliqués successivement pour sélectionner les éléments désignés par l'étape de localisation. Par exemple, l'expression /a/b[c][2] désigne le deuxième élément b , fils de l'élément racine a et ayant un élément fils c . De manière générale, l'ordre des prédicats est important. Ainsi, par exemple, l'expression /a/b[2][c] est différente de l'expression précédente, et désigne le deuxième élément b , fils de l'élément racine a et vérifie en outre que cet élément a un élément fils c . En plus des chemins de localisation, la syntaxe XPath décrit un ensemble d'expressions algébriques et d'expressions de comparaison, permettant notamment l'expression de conditions dans les prédicats, ainsi qu'un ensemble de fonctions permettant par exemple d'exprimer des prédicats ou de traiter l'ensemble des noeuds désignés par un chemin de localisation. Pour effectuer l'évaluation d'une expression XPath selon une première méthode, on divise un chemin de localisation en un ensemble d'étapes de localisation et on traite chaque étape successivement. Par exemple, lors de l'évaluation de l'expression /a/b[2] , il est, dans un premier temps, recherché l'ensemble des éléments a qui sont des éléments racines du document XML, puis ensuite, pour chacun de ces éléments, il est recherché l'ensemble des éléments fils b . Enfin, parmi cet ensemble, il est sélectionné le deuxième élément. II est à noter que si le document XML est correctement écrit, celui-ci comprend un unique élément racine. Une telle méthode est décrite dans le document US 2004060007 de Georg Gottlob, Christopher Koch et Reinhard Pichler. Cette méthode d'évaluation d'une expression XPath est basée sur la décomposition de l'expression en un ensemble de sous-expressions élémentaires, et sur l'évaluation de chaque sous-expression élémentaire séparément. Le résultat de l'évaluation d'une sous-expression élémentaire est mémorisé dans une table appelée table de contexte-valeur, le contexte correspondant au contexte d'évaluation de la sous-expression élémentaire et la valeur correspondant au résultat de l'évaluation de la sous-expression élémentaire. Les résultats des différentes sous-expressions élémentaires sont ensuite combinés pour générer un résultat global. La mémorisation des résultats obtenus permet d'éviter de réaliser le calcul d'une même expression une pluralité de fois dans le même contexte et ainsi d'optimiser le temps de calcul pour certaines expressions. Selon une première application de cette méthode, l'évaluation débute par l'évaluation des sous-expressions élémentaires. Ensuite, les résultats sont combinés pour réaliser l'évaluation des expressions complexes. L'évaluation de chaque sous-expression élémentaire est mémorisée dans une table de contexte-valeur. Selon cette méthode, cette table peut être de taille très importante. En outre, selon cette méthode, de nombreux résultats intermédiaires inutiles sont calculés lors de l'évaluation du résultat. Selon une seconde application de cette méthode, l'évaluation des sous-expressions élémentaires est effectuée dans un ordre correspondant à la sémantique de l'expression XPath. Ainsi, lors de l'évaluation d'une sous-expression élémentaire, 5 l'ensemble des contextes d'évaluation est connu évitant de la sorte le calcul des résultats intermédiaires inutiles. Une application spécifique de cette méthode peut être réalisée en modifiant une mise en oeuvre d'un processeur XPath afin d'éviter que ce processeur n'évalue plusieurs fois une même sous-expression élémentaire pour 10 un même contexte. Cette modification consiste à mémoriser le résultat de chaque évaluation dans une table de contexte-valeur. Toutefois, une telle méthode présente plusieurs inconvénients. En effet, selon cette méthode, l'ensemble du document doit être présent en mémoire afin de réaliser l'évaluation d'une expression XPath. En effet, pour des 15 appareils ayant des capacités mémoire limitées, par exemple pour une caméra vidéo, cette méthode ne permet pas d'évaluer une expression XPath sur un document XML de taille importante. Dans le cas d'appareil de faibles capacités mémoire, le traitement d'un document XML est en général réalisé à l'aide d'un parseur de type SAX 20 ( Simple API for XML en terminologie anglo-saxonne). Le parseur de type SAX est apte à traiter séquentiellement les noeuds du document XML, c'est-à-dire les éléments, les commentaires et les valeurs textuelles. Cependant, l'utilisation d'un parseur SAX lors de l'évaluation d'une 25 expression XPath ne permet pas de revenir en arrière dans le document XML. Par conséquence, il n'est pas possible de réaliser directement l'évaluation d'expressions comprenant une relation de filiation vers l'arrière. Néanmoins, il est possible de construire des méthodes permettant d'évaluer une expression XPath sur un document XML à l'aide d'un parseur de 30 type SAX ou équivalent. Ainsi, selon une méthode connue du document US 2004068487 de Charles Barton, Philippe Charles, Deepak Goyal et Mukund Raghavachari, une expression XPath est évaluée en utilisant un parseur SAX. Pour ce faire, une représentation de l'expression XPath ne comportant que des relations vers l'avant est créée. De cette manière, il n'est plus nécessaire de revenir en arrière dans le document. Cependant, selon cette méthode, l'évaluation ne peut être réalisée que sur une expression XPath utilisant une sous-partie du langage XPath. En particulier, cette méthode ne permet de traiter que les prédicats contenant des chemins XPath. Elle ne s'applique donc pas aux tests de position ou de valeur, aux expressions arithmétiques ni aux fonctions. Compte tenu de ce qui précède, il serait par conséquent intéressant de pouvoir évaluer une expression, notamment des expressions XPath, en utilisant un parseur de type SAX quelque soit l'expression en limitant les ressources mémoires nécessaires et en s'affranchissant d'au moins certains des inconvénients mentionnés ci-dessus. La présente invention vise en premier lieu à fournir un procédé d'évaluation d'une expression sur des items d'un document structuré, une expression comprenant un ensemble de sous-expressions élémentaires, caractérisé en ce qu'il comprend les étapes préalables suivantes : -génération, à partir de l'expression, d'un ensemble des noeuds cibles correspondant à des items à rechercher dans le document structuré ; -génération d'une représentation logique de l'expression, une représentation logique comprenant un ensemble de noeuds, représentant les sous-expressions élémentaires de l'expression, reliés en fonction des relations entre ces sous-expressions élémentaires ; et une étape de -évaluation de l'expression sur des items du document structuré à partir de l'ensemble des noeuds cibles généré et de la représentation logique 30 générée. L'invention prévoit de trouver parmi les items d'un document structuré, les items répondant à l'évaluation d'une expression, notamment d'une expression XPath. Les items d'un document structuré sont, notamment, décrits dans un langage de balisage structurant les données, par exemple, en utilisant le langage XML. Pour permettre cette évaluation, le procédé selon l'invention prévoit de générer, d'une part, un ensemble de noeuds cibles correspondant à des items à rechercher, et d'autre part, une représentation logique de l'expression. A partir de l'ensemble de noeuds cibles générés et de la représentation logique, l'évaluation de l'expression peut être réalisée. Selon l'invention, il est donc évité de calculer de nombreux résultats intermédiaires inutiles dans l'évaluation du résultat. De plus, l'évaluation d'une expression est rendue possible sur des 15 appareils ayant de faibles capacités mémoires. Selon un mode de réalisation particulier, l'étape de génération d'un ensemble des noeuds cibles comprend, en outre, la génération d'une représentation des relations entre les noeuds cibles. Selon cette caractéristique, les noeuds cibles sont organisés selon 20 leurs relations. En effet, il peut être utile de rechercher un second élément seulement si un premier élément a été trouvé. Selon une caractéristique particulière, l'étape d'évaluation de l'expression comprend : - une étape de filtrage des items du document à partir de l'ensemble 25 des noeuds cibles ; et - une étape d'évaluation des items filtrés à partir de la représentation logique. Selon ces caractéristiques, les items sont filtrés de sorte à ne conserver que les événements utiles à l'évaluation de l'expression. 30 Selon une autre caractéristique particulière, l'étape de filtrage des items du document à partir de l'ensemble des noeuds cibles comprend une étape d'identification des items du document correspondant à des noeuds cibles de l'ensemble des noeuds cibles. Selon une autre caractéristique particulière, l'étape d'évaluation des items filtrés comprend une étape de création d'un noeud solution associé à un noeud de la représentation logique, ce noeud solution représentant un résultat d'évaluation pour le noeud de la représentation logique. Selon un mode de réalisation, l'étape de création d'un noeud solution associé à un noeud de la représentation logique comprend une étape d'association d'un item filtré avec ce noeud solution. Selon une caractéristique particulière, l'étape d'évaluation des items filtrés comprend en outre une étape de création d'une relation entre un premier noeud solution associé à un premier noeud de la représentation logique et au moins un deuxième noeud solution associé à un deuxième noeud de la représentation logique conformément à la relation entre le premier noeud de la représentation logique et le deuxième noeud de la représentation logique. Selon une caractéristique particulière, l'étape d'évaluation de l'expression comprend en outre une étape de vérification de la complétude d'une solution comprenant les sous-étapes suivantes : -vérification de l'existence pour chaque noeud de la représentation logique d'au moins un noeud solution associé ; - sélection pour chaque noeud de la représentation logique d'un noeud solution associé, l'ensemble des noeuds solutions sélectionnés formant une solution ; - pour chaque relation entre deux noeuds de la représentation logique, vérification qu'une relation similaire existe entre les noeuds solutions associés sélectionnés. Selon une caractéristique, l'étape d'évaluation de l'expression comprend, si l'étape de vérification de la complétude d'une solution est positive, une étape de génération d'un résultat à partir de la solution. Selon une caractéristique particulière, un contexte de recherche est associé à un item filtré correspondant à un noeud de la représentation logique et à un noeud de la représentation logique descendant du noeud correspondant à l'item filtré. Selon cette caractéristique, le contexte de recherche permet de déterminer si la recherche de solutions pour des items est terminée. Selon une autre caractéristique particulière, un contexte de recherche comprend une information d'identification d'une partie du document dans laquelle est recherché un item correspondant au noeud descendant. Selon une autre caractéristique particulière, il comprend une étape de transmission d'un résultat dès la fin de l'évaluation de l'expression. Selon une caractéristique, le procédé comprend une étape de suppression d'un noeud solution, la suppression d'un noeud solution étant réalisée en fonction d'un critère de validité du noeud solution. Selon une autre caractéristique particulière, le critère de validité d'un noeud solution dépend des relations existant entre ce noeud solution et d'autres noeuds solutions et des contextes de recherches associés au noeud de la représentation logique associé à ce noeud solution. L'invention vise également un dispositif d'évaluation d'une expression sur des items d'un document structuré, une expression comprenant un ensemble de sous-expressions élémentaires, caractérisé en ce qu'il comprend : - des moyens de génération, à partir de l'expression, d'un ensemble des noeuds cibles correspondant à des items à rechercher dans le document structuré ; - des moyens de génération d'une représentation logique de 25 l'expression, une représentation logique comprenant un ensemble de noeuds, représentant les sous-expressions élémentaires de l'expression, reliés en fonction des relations entre ces sous-expressions élémentaires ; et - des moyens d'évaluation de l'expression sur des items du document structuré à partir de l'ensemble des noeuds cibles généré et de la 30 représentation logique générée. Ce dispositif présente les mêmes avantages que le procédé brièvement décrit ci-dessus et ils ne seront donc pas rappelés ici. La présente invention vise aussi un moyen de stockage d'informations, éventuellement amovible partiellement ou totalement, lisible par un ordinateur ou un microprocesseur conservant des instructions d'un programme d'ordinateur, permettant la mise en oeuvre du procédé tel qu'exposé ci-dessus. La présente invention vise enfin un produit programme d'ordinateur pouvant être chargé dans un appareil programmable, comportant des séquences d'instructions pour mettre en oeuvre le procédé tel qu'exposé ci-dessus, lorsque ce programme est chargé et exécuté par l'appareil programmable. D'autres aspects et avantages de la présente invention apparaîtront plus clairement à la lecture de la description qui va suivre, cette description étant donnée uniquement à titre d'exemple non limitatif et faite en référence aux dessins annexés, dans lesquels : - la Figure 1 représente un exemple d'expression XPath qui est à évaluer conformément à l'invention ; - la Figure 2 illustre l'ensemble des noeuds cibles générés par l'invention à partir de l'expression XPath de la Figure 1 ; - la Figure 3 illustre une représentation logique de l'expression 20 XPath de la Figure 1 conformément à l'invention ; - la Figure 4 illustre un exemple de document XML sur lequel est appliqué l'expression XPath de la Figure 1 ; - la Figure 5 illustre les noeuds solutions créés après le traitement de l'événement correspondant à la balise vide a référencée en 435 sur la 25 Figure 4 ; - la Figure 6 représente le contexte nommé ctx-b dans la Figure 5; - la Figure 7 représente le contexte nommé ctx-c dans la Figure 5 ; 30 - la Figure 8 représente un organigramme général d'évaluation d'une expression conformément à l'invention ; - la Figure 9 représente les différentes étapes de traitement d'une expression XPath pour générer les noeuds cibles et la représentation logique correspondant à cette expression conformément à l'invention ; - la Figure 10 illustre un algorithme d'évaluation d'une expression 5 XPath sur un document XML conformément à l'invention ; - la Figure 11 illustre un algorithme de construction des résultats à partir des événements filtrés par les cibles conformément à l'invention ; et - la Figure 12 illustre une architecture matérielle sur laquelle peut être mise en oeuvre l'invention. 10 L'invention consiste à décomposer l'évaluation d'une expression, notamment d'une expression XPath, en deux parties. La première partie consiste à filtrer les événements reçus du parseur SAX pour ne conserver que les événements utiles à l'évaluation de l'expression. Les événements filtrés 15 représentent un ensemble de noeuds cibles recherchés pour l'évaluation de l'expression XPath. La deuxième partie consiste à combiner les événements filtrés pour réaliser l'évaluation proprement dite de l'expression. Cette combinaison consiste à créer des solutions potentielles contenant l'état d'évaluation des différents candidats pouvant être résultats de l'expression 20 XPath. L'expression 10 en Figure 1 illustre un exemple d'expression XPath apte à être traitée selon l'invention. Selon cette expression, des éléments a fils d'un élément a situé à n'importe quelle profondeur dans le document et ayant au moins deux 25 enfants directs b et un ancêtre c sont recherchés. La Figure 2 représente l'ensemble des noeuds cibles générés conformément à l'invention à partir de l'expression XPath 10 de la Figure 1. Les noeuds cibles de la Figure 2 correspondent aux noeuds XML recherchés pour l'évaluation de l'expression XPath. L'élément r (noeud cible 30 21) correspond à la racine du document XML, et l'élément c (noeud cible 22), l'élément a (noeud cible 23) et l'élément b (noeud cible 24) correspondent aux noeuds recherchés dans le document XML au moyen de l'expression XPath. Les noeuds cibles sont utilisés pour filtrer les événements reçus par l'entité apte à réaliser l'évaluation d'une expression XPath sur un document XML aussi appelée processeur XPath ( XPath Processor en terminologie anglo-saxonne). Ainsi, les noeuds cibles correspondent aux tests de noeud de l'expression XPath. Pour chaque test de noeud de l'expression XPath, un noeud cible est généré. Cependant, si plusieurs noeuds cibles identiques sont générés, ils sont regroupés en un seul noeud cible. Conformément à l'invention, un noeud cible généré permet de filtrer tous les noeuds XML correspondant à ce noeud cible. Par exemple, selon l'expression 10 de la Figure 1, un seul noeud cible est généré pour l'ensemble des éléments a . En effet, un noeud cible ayant pour rôle de filtrer les noeuds du document XML, un seul noeud cible suffit pour réaliser ce filtrage. En outre, afin d'optimiser le processus de recherche des noeuds, les noeuds cibles sont organisés en fonction de leurs relations d'ordre d'apparition dans le document telles qu'elles sont définies par les relations de filiations de l'expression XPath. De cette manière, selon l'exemple illustré en Figures 1 et 2, un élément b est recherché uniquement après avoir trouvé un élément a . De la même manière, un élément a est recherché uniquement après avoir trouvé un élément c . Ces relations d'ordre d'apparition sont représentées sur la Figure 2 par des flèches. Le processus de recherche est optimisé davantage par une description précise des relations d'ordre d'apparition exprimées dans l'expression XPath. Ainsi, selon l'exemple illustré en Figures 1 et 2, la relation entre la cible c et la cible a est, notamment, une différence de profondeur d'au moins un . De même, il est possible de décrire précisément une relation de filiation de type noeud frère suivant ( following-sibling selon la spécification XPath) comme enfant du même élément, avec un numéro d'ordre supérieur . Cette précision dans la description des relations d'ordre d'apparition est à l'origine de la flèche partant du noeud cible a et allant sur lui-même. En effet, de cette manière, il est indiqué qu'après avoir trouvé un élément a , on poursuit la recherche d'un élément a fils de cepremier élément a . La Figure 3 illustre une représentation logique de l'expression XPath 10 de la Figure 1 conformément à l'invention. Cette représentation logique permet d'évaluer l'expression XPath à partir des noeuds filtrés par les noeuds cibles générés tel que décrit en Figure 2. Selon cette représentation logique, chaque sous-expression élémentaire de l'expression XPath est représentée par un noeud logique. Par exemple, la sous-expression élémentaire descendant::a est représentée par un noeud logique descendant::a . Les liens entre les noeuds logiques décrivent leurs relations au sein de l'expression XPath. Durant l'évaluation d'une expression XPath, cette représentation logique permet en outre de construire les solutions de l'expression XPath. Pour cela, un noeud logique reçoit les événements filtrés par les noeuds cibles et les utilise pour construire des noeuds solutions représentant cet événement au sein d'une solution potentielle pour l'expression XPath. Chaque noeud solution représente une valeur vérifiant une partie élémentaire de l'expression XPath. La partie élémentaire de l'expression XPath vérifiée par le noeud solution correspond au noeud logique associé à ce noeud solution. Une solution potentielle regroupe un ensemble de noeuds solutions en respectant la logique de l'expression XPath. Quand une solution potentielle contient un noeud solution pour chaque noeud logique de l'expression XPath, cette solution potentielle vérifie l'intégralité de l'expression XPath et permet donc de générer une solution pour l'expression XPath. Ainsi, lorsqu'un événement a est reçu, il est détecté par le noeud cible a de la Figure 2 et transmis aux deux noeuds logiques a de la Figure 3, à savoir le noeud logique descendant::a 300 et le noeud logique child::a 310. A partir de l'événement a , les noeuds logiques 300 et 310 mettent à jour les solutions potentielles de l'expression XPath en créant un ou plusieurs 5 noeuds solution représentant cet événement a . II est maintenant décrit en référence à la Figure 4 un exemple de document XML sur lequel peut être appliquée l'expression XPath 10 de la Figure 1. Selon cet exemple, le résultat de l'évaluation de l'expression XPath 10 10 sur le document XML de la Figure 4 est le deuxième élément a de ce document XML. Lors du traitement du document XML par le parseur SAX, des événements décrivant le document XML sont transmis au processeur XPath. II est maintenant décrit les actions du processeur XPath qui ont pour 15 objet l'évaluation de l'expression XPath sur le document XML décrit par ces événements. Sur réception de l'événement Début du document , celui-ci est reçu par le noeud cible r 21. Ce noeud cible crée un noeud solution r pour représenter cet événement. En outre, le noeud cible c 22 est activé, 20 avec un contexte d'activation correspondant à l'ensemble du document XML. Ensuite, lors de la réception de l'événement balise ouvrante m 400, celui-ci n'est reçu par aucune cible, il est donc ignoré. L'événement suivant est l'événement balise ouvrante c 405. Cet événement est reçu par le noeud cible c . Le noeud cible a est activé 25 avec un contexte d'activation correspondant à l'ensemble des noeuds descendant de cet élément c . En outre, un noeud solution et est créé pour représenter cet événement et est associé au noeud solution r en tant que fils de ce noeud. Le document XML comprend ensuite une balise vide b 410. 30 L'événement associé n'est reçu par aucun noeud cible. En effet, le noeud cible b n'a pas été activé. Ensuite, l'événement suivant est l'événement balise fermante c 415. Cet événement est reçu par le noeud cible c . Cet événement marque la fin du contexte d'activation du noeud cible a . Ce noeud cible est donc désactivé. De plus, le noeud solution et est supprimé. En effet, il n'y a pas d'élément a dont l'élément c qu'il représente est l'ancêtre et comme le contexte d'activation du noeud cible a est terminé, il n'est plus possible de trouver un tel élément a . L'événement suivant est l'événement balise ouvrante c 420. Cet événement est reçu par le noeud cible c et le noeud cible a est activé avec un contexte d'activation correspondant à l'ensemble des noeuds descendant de cet élément c . En outre, un noeud solution c2 est créé et associé au noeud solution r en tant que fils de ce noeud. Ensuite, l'événement suivant est l'événement balise ouvrante a 425. Cet événement est reçu par le noeud cible a . Le noeud cible b est activé avec un contexte d'activation correspondant à l'ensemble des noeuds enfant de cet élément a . En outre, le contexte d'activation du noeud cible a est augmenté par l'ensemble des noeuds enfant de cet élément a . L'événement a est transmis aux deux noeuds logiques a 300 et 310 de la Figure 3. Le premier noeud logique a 300 utilise cet événement pour créer un noeud solution al . En outre, un noeud solution and1 est créé en tant que fils du noeud solution al et le noeud solution c2 est associé au noeud solution and1 en tant que fils de ce noeud. Comme le noeud solution c2 forme un résultat pour le chemin de localisation qu'il constitue, ce résultat est transmis au noeud solution and1 . Toutefois, le noeud solution and1 n'ayant la connaissance que de la valeur d'un seul de ses opérandes, il ne peut être évalué. Le deuxième noeud logique a 310 ignore cet événement, puisqu'il 30 ne correspond pas à un élément a fils d'un autre élément a pour lequel un noeud solution existe. L'événement suivant est l'événement balise vide b 430. Cet événement est reçu par le noeud cible b . Un noeud solution b1 est créé, fils du noeud solution and1 pour représenter cet élément b . Un autre noeud solution 2-1 est créé fils de ce noeud b1 , représentant le prédicat [2] et correspondant au noeud logique 2 340. Etant donné que le prédicat du noeud solution b1 est évalué à faux, ces deux noeuds nouvellement créés, à savoir b1 et 2-1 , ne peuvent participer à une solution de l'expression XPath et sont donc supprimés. L'événement suivant est l'événement balise vide a 435. Cet événement est reçu par le noeud cible a et l'événement a est transmis aux deux noeuds logiques a 300 et 310. Le premier noeud logique, le noeud 300 de la Figure 3, utilise cet événement pour créer un noeud solution a2 , avec son noeud solution fils and2 . Le noeud solution c2 est associé à and2 en tant que fils de ce noeud. Toutefois, comme l'élément a est vide et qu'il ne peut donc avoir de sous-élément fils b , ces deux noeuds solutions sont immédiatement supprimés. Le deuxième noeud logique a , à savoir le noeud 310 de la Figure 3 crée un noeud solution a3 , fils du noeud solution a1 . Ce noeud solution 20 a3 est un résultat possible pour l'expression XPath. Toutefois, étant donné que l'ensemble des prédicats de al n'est pas encore vérifié, le noeud solution a3 ne peut être retourné comme résultat à ce moment de l'évaluation. La Figure 5 représente les noeuds solutions créés après le traitement 25 de l'événement correspondant à la balise vide a 435. Il est à noter que pour chaque noeud solution créé, l'algorithme mémorise les contextes de recherche de noeuds solutions fils représentant des éléments du document XML. La Figure 6 représente le contexte nommé ctx-b dans la Figure 5 30 correspondant au contexte de recherche pour des noeuds solutions correspondant à des éléments b fils de l'élément a présent en référence 425 de la Figure 4. Il s'agit, en fait, des éléments permettant de vérifier la partie de prédicat b[2] de l'expression XPath 10 de la Figure 1. La Figure 7 représente le contexte nommé ctx-c dans la Figure 5 correspondant au contexte de recherche pour des noeuds solutions correspondant à des éléments c ancêtre de l'élément a présent en référence 425 de la Figure 4. II s'agit, en fait, des éléments permettant de vérifier la partie du prédicat ancestor::c de l'expression XPath 10 de la Figure 1. De retour à la Figure 4, l'événement suivant l'événement 435 est l'événement balise vide b 440. Cet événement est reçu par le noeud cible b et un noeud solution b2 est créé, fils du noeud solution and1 . Un autre noeud solution 2-2 est créé fils de ce noeud b2 . Etant donné que le prédicat du noeud solution b2 est vérifié, un résultat est généré pour le chemin de localisation qu'il représente. Ce résultat est transmis au noeud solution and1 , qui peut être entièrement évalué à vrai . Ce résultat d'évaluation est transmis au noeud solution al . L'ensemble des prédicats du chemin constitué par les noeuds solutions al et a3 étant vérifié, le résultat représenté par a3 peut 20 maintenant être retourné. En outre, le noeud solution a3 est supprimé. En effet, le résultat représenté par ce noeud a été retransmis, il n'est donc plus nécessaire de le conserver. D'autre part, les noeuds solutions and1 et b2 sont supprimés, ces derniers ayant été complètement évalués et ne pouvant servir à d'autres 25 évaluations. Par contre, le noeud solution c2 est conservé. En effet, il peut prendre part à d'éventuelles autres solutions, notamment s'il y a d'autres éléments a dans la suite du document XML. L'ensemble des événements suivants est traité de manière similaire, 30 servant principalement à supprimer les noeuds solutions restants. II est maintenant décrit, en référence à la Figure 8, l'organigramme général d'évaluation d'une expression conformément à l'invention. Tel que décrit précédemment, un fichier XML 800 est traité par un parseur SAX afin de générer des événements décrivant les données contenues dans le fichier XML. Ces événements sont filtrés par un filtre d'événements 810 à partir des noeuds cibles générés à partir de l'expression XPath. Les événements ayant passé le filtre d'événements 810 sont ensuite utilisés par l'évaluateur de solutions 820 pour créer des solutions potentielles à l'expression XPath, notamment à l'aide de la représentation logique de l'expression XPath. Enfin, les solutions potentielles entièrement vérifiées génèrent des résultats 830. Il est à noter que ces différents processus peuvent être exécutés simultanément. Ainsi, dès qu'une solution potentielle est entièrement vérifiée, le résultat correspondant peut être généré immédiatement. Il est maintenant décrit, en référence à la figure 9, les différentes 15 étapes de traitement d'une expression XPath pour générer les noeuds cibles et la représentation logique correspondant à cette expression. L'algorithme débute à l'étape 900 par l'obtention de l'expression XPath. Selon un mode de réalisation, l'expression XPath est obtenue sous 20 une forme textuelle. L'étape suivante (étape 910) consiste à analyser cette expression préalablement à son traitement. Lors de cette analyse, une représentation interne de l'expression XPath à traiter est générée. Selon un mode de réalisation, cette analyse est réalisée de manière classique à l'aide d'un 25 analyseur lexical et d'un analyseur syntaxique. L'algorithme se poursuit à l'étape 920 au cours de laquelle, à partir de cette représentation interne, les noeuds cibles correspondant à l'expression XPath sont générés. Pour ce faire, l'expression XPath est analysée. 30 Ainsi, pour chaque unité lexicale de type étape de localisation ( location step en terminologie anglo-saxonne), un noeud cible est créé. Un noeud cible correspond au test de noeud contenu dans l'étape de localisation. En outre, un noeud cible est créé pour représenter la racine de la recherche. Selon le type d'expression XPath, la racine de la recherche est soit 5 la racine du document XML, soit l'élément courant du document XML. Si deux noeuds cibles identiques sont créés, alors ils sont regroupés en un unique élément. Les relations entre les différentes étapes de localisation sont analysées et mémorisées dans des liens entre les différents noeuds cibles. 10 Pour deux étapes de localisation successives d'un même chemin de localisation, la relation correspond à la relation de filiation vers la deuxième étape de localisation. Dans les autres cas, la relation dépend de la relation de filiation de l'une des étapes de localisation et de la sémantique de la sous-expression 15 élémentaire XPath reliant les deux étapes de localisation. Ainsi, pour une étape de localisation présente dans un prédicat d'une autre étape de localisation, la relation entre ces deux étapes correspond à la relation de filiation de l'étape de localisation située dans le prédicat. Les liens entre les différents noeuds cibles sont créés dans un ordre 20 correspondant à l'ordre du document XML. De cette manière, si un noeud cible c est un ancêtre d'un noeud cible a , un lien est créé du noeud cible c vers le noeud cible a . D'autre part, si un noeud cible n'a aucun lien incident, alors un lien entre le noeud cible représentant la racine et ce noeud cible est créé. 25 L'algorithme se poursuit à l'étape 930 consistant à générer une représentation logique correspondant à l'expression XPath à partir de la représentation interne préalablement générée. Pour ce faire, l'expression XPath est analysée. Chaque unité lexicale de l'expression est représentée par un noeud 30 logique dans un arbre, les liens entre les noeuds logiques correspondant aux relations sémantiques entre les unités lexicales. Ainsi, l'ensemble de l'arbre représente l'expression XPath dans son ensemble. En outre, chaque noeud logique représentant une unité lexicale de type étape de localisation est relié au noeud cible correspondant. De cette manière, un noeud cible transmet les événements qu'il filtre aux noeuds logiques qui vont à leur tour traiter cette information pour évaluer l'expression XPath. II est maintenant décrit, en référence à la Figure 10, un algorithme d'évaluation d'une expression XPath sur un document XML conformément à l'invention. Cet algorithme est précédé par l'exécution de l'algorithme décrit en référence à la Figure 9 afin de créer les différentes structures nécessaires à l'évaluation de l'expression XPath. Toutefois, une seule exécution de l'algorithme décrit en référence à la Figure 9 est nécessaire pour ensuite évaluer une pluralité de fois une même expression XPath. L'algorithme de la Figure 10 débute par l'étape 1000 au cours de 15 laquelle un document XML est obtenu. Le document XML peut être lu depuis un fichier, reçu à partir d'un réseau de télécommunications ou fourni de toute autre manière à l'algorithme. Pour traiter le document XML, un parseur génère des événements aptes à représenter le document XML. 20 Des parseurs connus sont par exemple un parseur de type SAX ou un parseur de type pull. Toutefois, un parseur de type DOM peut être utilisé par itération sur les noeuds XML créés par ce parseur pour générer les événements XML. Les différentes étapes de l'algorithme traitent successivement 25 l'ensemble des événements décrivant le document XML. Ainsi, l'étape 1000 est suivie de l'étape 1010 au cours de laquelle un premier événement XML e est obtenu. Lors de cette étape 1010, le contexte courant est aussi mis à jour. Le contexte courant représente la position courante du parseur XML dans le 30 document XML. Il correspond donc à la position de l'événement e au sein du document XML. Ensuite, l'algorithme se poursuit à l'étape 1020 consistant à rechercher un noeud cible c correspondant à cet événement e . Pour ce faire, l'ensemble des noeuds cibles de l'expression XPath est parcouru et l'événement e reçu est comparé au test de noeud représenté par le noeud cible. Si l'événement e vérifie le test de noeud, alors le noeud cible correspond à cet événement e . II est à noter que dans le cas d'un élément correspondant à un noeud cible, alors l'événement représentant la balise ouvrante de cet élément et 10 l'événement représentant la balise fermante de cet élément correspondent à cette cible. L'événement représentant la balise ouvrante est nécessaire pour décrire l'existence de l'élément correspondant. De plus, l'événement représentant la balise fermante est nécessaire 15 pour décrire la fin de l'élément et permettre, d'une part, l'évaluation de certaines fonctions, par exemple le comptage du nombre d'enfants de cet élément, et d'autre part, la mise à jour de certaines solutions potentielles. Par exemple, un prédicat portant sur les enfants d'un élément est entièrement évalué lorsque l'événement représentant la balise fermante de l'élément est reçu. Ainsi, lors de 20 la réception de cet événement, le résultat de l'évaluation peut être propagé vers le reste de la solution potentielle. A titre de variante, si un noeud cible c correspondant à cet événement e est trouvé et si cet événement e correspond à une balise ouvrante d'élément, alors les noeuds cibles liés au noeud cible c par un lien 25 incident voient leurs contextes d'activation mis à jour. Pour réaliser cette mise à jour, pour chacun de ces noeuds cibles, un nouveau contexte d'activation est créé, à partir du contexte courant et en fonction du lien de filiation entre le noeud cible c et le noeud cible traité. L'algorithme se poursuit à l'étape 1030 au cours de laquelle on teste 30 si un noeud cible c correspondant à l'événement e existe. A titre de variante, l'étape 1030 teste, en plus de l'existence d'un noeud cible c correspondant à l'événement e , Si ce noeud cible c est actif. Un noeud cible c est actif si l'un des contextes d'activation du noeud cible c contient le contexte courant. Si tel est le cas, alors l'algorithme se poursuit à l'étape 1040 consistant à transmettre l'événement e aux noeuds associés au noeud cible c . Cette étape est décrite en détail ci-après en référence à la Figure 11. L'étape 1040 est suivie de l'étape 1050. De même, si le test de l'étape 1030 est négatif, alors l'étape 1030 est suivie de l'étape 1050. Au cours de l'étape 1050, on vérifie les contextes de recherche 10 associés aux différents noeuds solutions existant. Ainsi, si le contexte courant n'appartient plus à un contexte de recherche et ne peut plus y appartenir, alors l'évaluation du noeud solution concerné est mise à jour et le résultat de cette évaluation est propagé tel que décrit ci-après en référence à l'étape 1120 de la Figure 11. 15 A titre de variante, l'étape 1050 met aussi à jour les contextes d'activation des noeuds cibles. Pour chaque noeud cible et pour chacun de ses contextes d'activation, l'étape 1050 vérifie que le contexte courant est situé avant la fin de ce contexte d'activation (c'est-à-dire que soit le contexte courant est contenu dans le contexte d'activation, soit le contexte courant pourra être 20 contenu dans le contexte d'activation). Si ce n'est pas le cas, ce contexte d'activation est supprimé. Lors de l'étape suivante (étape 1060), on vérifie s'il reste d'autres événements décrivant le document XML à traiter. Si tel est le cas, alors l'algorithme se poursuit à l'étape 1010 25 précédemment décrite consistant à obtenir l'événement suivant. Dans le cas contraire, il est mis fin à l'algorithme à l'étape 1070. II est maintenant décrit, en référence à la Figure 11, un algorithme de construction des résultats à partir des événements filtrés par les cibles conformément à l'invention. 30 Cet algorithme débute par le traitement effectué sur les événements correspondant à un début d'item XML ou à une fin d'item XML. Il s'applique donc, en particulier, aux événements générés à partir du document XML représentant une balise ouvrante ou une balise fermante. Concernant les autres événements, par exemple un contenu textuel ou un commentaire, l'algorithme est exécuté deux fois de manière consécutive, la première pour signifier le début de l'item, la seconde pour signifier sa fin. Selon un mode de réalisation particulier, pour l'ensemble des événements représentant un item XML complet, les deux parties de cet algorithme correspondant au traitement du début de l'item et de la fin de l'item sont combinées en un algorithme réalisant l'ensemble des étapes contenues dans ces deux parties. Lors de la mise en oeuvre de l'algorithme décrit en référence à la Figure 11, l'événement e à traiter a été sélectionné au moyen d'un noeud cible c lors des étapes 1020 et 1030 de la Figure 10 et est associé à un noeud logique r lors de l'étape 1040 de la Figure 10. En outre, si le noeud cible c est associé à plusieurs noeuds logiques, alors cet algorithme est mis en oeuvre pour chacun de ces noeuds logiques. L'algorithme débute à l'étape 1100 consistant à tester si l'événement e traité est un événement de début d'item ou un événement de fin d'item. Si l'événement est un événement de début d'item, alors l'algorithme se poursuit à l'étape 1105 de création d'un noeud solution n pour représenter l'item. Ce noeud solution mémorise l'item représenté et sa position dans le document XML. En outre, si le noeud logique r est relié à d'autres noeuds logiques descendant de ce noeud logique r dans la représentation logique et représentant des fonctions ou des opérateurs, alors un noeud solution est créé pour chacun de ces noeuds logiques. Ces noeuds solutions nouvellement créés sont reliés au noeud solution n . De plus, pour chacun des chemins de localisation qui est fils de l'un des noeuds solutions créés, le contexte de recherche pour ce chemin de localisation est mémorisé. Ce contexte de recherche est notamment fonction du noeud solution n et de la relation de filiation reliant le noeud solution au chemin de localisation. Ce contexte de recherche permet, par exemple, de déterminer la fin de la recherche de solutions pour le chemin de localisation considéré. Ainsi, dans l'exemple illustré en Figures 1 à 7, lorsqu'un événement correspondant à un élément a associé au noeud logique 300 est traité, un noeud solution est créé pour représenter cet élément a et un autre noeud solution est créé pour représenter l'opérateur and décrit par le noeud logique 320. Par contre, lorsqu'un événement correspondant à un élément c associé au noeud logique 350 est traité, alors seul le noeud solution représentant l'élément c est créé. En outre, lorsque cet élément a est créé, un contexte de recherche est créé pour les noeuds solutions associés au noeud logique 310, ctx-a . Ce contexte de recherche est associé au noeud solution représentant cet élément a . Deux autres contextes de recherche sont créés pour le noeud solution représentant l'opérateur and , le premier contexte correspondant aux noeuds solutions associés au noeud logique ctx-b référencé 330 en Figure 3, le second contexte correspondant aux noeuds solutions associés au noeud logique ctx-c référencé 340 en Figure 3. Le contexte de recherche ctx-c a été entièrement exploré, ainsi aucun noeud solution c pouvant être relié au noeud solution a ne peut plus être trouvé. S'il n'existe pas encore de noeud solution c pouvant être relié au noeud solution a , le noeud solution a ne peut être intégré à une solution de l'expression XPath, il peut donc être détruit immédiatement. L'algorithme se poursuit par la recherche de noeuds solutions liés à l'un de ces noeuds solutions nouvellement créés. On considère que deux noeuds solutions sont liés s'ils vérifient deux conditions : d'une part, ils doivent correspondre à des noeuds logiques de l'expression reliés entre eux et, d'autre part, la relation entre ces deux noeuds solutions doit correspondre à la relation sémantique entre les noeuds logiques. Ainsi, dans l'exemple considéré en Figures 1 à 7, lorsque l'événement correspondant à l'élément b illustré en référence 430 de la Figure 4, associé au noeud logique 330 de la Figure 3, est traité, le noeud solution représentant cet événement est lié au noeud solution représentant le noeud logique 320 de la Figure 3 associé au noeud solution représentant l'élément a référencé en 425 de la Figure 4 associé au noeud logique 300 de la Figure 3. En effet, les noeuds logiques 300 et 330 de la Figure 3 sont reliés par une relation de filiation de type enfant ( child selon la spécification XPath), ce qui correspond effectivement à la relation entre les deux éléments b (430) et a (425). Par contre, le noeud solution représentant cet élément b (430) associé au noeud logique 330 de la Figure 3 n'est pas lié au noeud solution représentant l'élément a référencé en 435 de la Figure 4 associé au noeud logique 300 de la Figure 3. En effet, l'élément b (430) n'est pas le fils de l'élément a (435). L'étape 1105 décrite précédemment est suivie de l'étape 1110 consistant à tester s'il existe un noeud solution I lié à un noeud solution m parmi les nouveaux noeuds solutions créés lors de l'étape 1105. Dans la négative, il est mis fin à l'algorithme à l'étape 1190. Dans le cas contraire, l'algorithme se poursuit à l'étape 1115 consistant à relier le noeud solution I au noeud solution m . L'étape 1115 est suivie de l'étape 1120 consistant à propager l'évaluation. La propagation de l'évaluation consiste à vérifier si l'événement reçu permet d'avancer dans l'évaluation de l'expression XPath. Plusieurs cas se présentent pour la propagation de l'évaluation, en fonction du type du noeud logique correspondant au noeud solution m . Dans un premier cas, le noeud logique correspondant au noeud solution m est une étape de localisation. Dans un deuxième cas, le noeud logique correspondant au noeud solution m ne représente pas une étape de localisation. 28 Si le noeud logique correspondant au noeud solution m représente une étape de localisation, alors l'algorithme vérifie s'il existe une solution complète pour ce chemin de localisation. Pour ce faire, on vérifie s'il existe un ensemble de noeuds solutions 5 liés entre eux et correspondant aux différentes étapes du chemin de localisation. A chaque étape du chemin de localisation doit correspondre un et un seul noeud solution dans l'ensemble de noeuds solutions. Toutefois, plusieurs ensembles de noeuds solutions peuvent être testés pour couvrir l'ensemble des 10 noeuds solutions correspondant à chaque étape du chemin de localisation. En outre, pour chaque noeud solution de cet ensemble, il est vérifié que l'ensemble des prédicats associés à ce noeud solution sont évalués positivement. Pour chaque solution complète ainsi trouvée, il est généré un résultat 15 pour le chemin de localisation. Lors de la génération des résultats, il est vérifié que les résultats ne sont générés qu'une seule fois et qu'ils sont générés dans l'ordre approprié. Il est à noter qu'un résultat peut être généré par deux ensembles de noeuds solutions différents. 20 Ainsi, après la création du noeud solution associé au noeud logique 310 de la figure 3 représentant l'élément a référencé en 435 dans la Figure 4, il est vérifié s'il existe un noeud solution associé au noeud logique 300 lié à ce premier noeud solution. Dans l'exemple considéré, il existe un tel noeud solution, c'est le 25 noeud solutionreprésentant l'élément a référencé en 425 de la Figure 4. Ainsi, pour chacune des étapes du chemin de localisation, il existe un noeud solution correspondant à cette étape. En outre, il est vérifié si le prédicat de ce deuxième noeud solution est vérifié. Dans l'exemple considéré, un seul élément b fils de l'élément 30 a référencé en 425 de la Figure 4 a été trouvé à ce moment là, le prédicat n'est donc pas vérifié. Par conséquence, dans l'exemple considéré, il n'existe pas de solution complète pour le chemin de localisation. Aucun résultat pour ce chemin de localisation ne peut donc être retourné. Dans le cas où le résultat généré pour un chemin de localisation ne correspond pas à l'expression principale de l'expression XPath évaluée, alors ce résultat est propagé vers les noeuds solutions parents de la solution complète ayant généré le résultat. Il s'agit des noeuds solutions parent du noeud solution de la première étape du chemin de localisation appartenant à la solution complète. En outre, ce résultat est mémorisé au niveau de la première étape du chemin de localisation appartenant à la solution complète pour pouvoir être utilisé ultérieurement par de nouveaux noeuds solutions reliés à ce chemin de localisation. Chaque noeud solution parent est alors réévalué en prenant en compte ce nouveau résultat. Deux cas peuvent se présenter. Selon un premier cas, l'évaluation du noeud solution parent est 15 terminée. Le résultat de cette évaluation est alors retransmis de la même façon aux noeuds solutions parents de ce noeud solution parent. Selon un second cas, l'évaluation du noeud solution parent n'est pas terminée et aucune autre action n'est effectuée au niveau de ce noeud solution parent. 20 L'évaluation d'un noeud solution après la réception d'un résultat dépend du type d'élément de l'expression XPath représenté par ce noeud solution. S'il s'agit d'une étape de localisation, l'algorithme vérifie s'il existe une solution complète pour ce chemin de localisation comme décrit précédemment. Dans un tel cas, le résultat correspond à l'évaluation d'un prédicat de cette 25 étape de localisation et peut donc permettre de trouver une solution complète pour le chemin de localisation auquel appartient cette étape de localisation. S'il s'agit d'une fonction, l'algorithme tente d'évaluer la fonction. Pour ce faire, il est vérifié si l'ensemble des données nécessaires à l'évaluation de la fonction a été reçu. Dans ce but, le contexte de recherche lié à ce noeud 30 solution est utilisé pour déterminer si l'ensemble des données constituant les arguments de la fonction est connu ou non. II est à noter que certaines fonctions peuvent être évaluées même si certains de leurs arguments ne sont pas encore entièrement connus. Si l'ensemble des données nécessaires à l'évaluation de la fonction a été reçu, la fonction est évaluée. Dans le cas contraire, le résultat ou une partie du résultat est mémorisé afin de pouvoir évaluer ultérieurement la fonction. S'il s'agit d'un opérateur, l'algorithme tente d'évaluer l'opérateur. Cette évaluation est réalisée de manière similaire à l'évaluation d'une fonction. Dans ces deux derniers cas, si la fonction ou l'opérateur peut être évalué, le résultat de cette évaluation est transmis aux noeuds solutions parents du noeud solution correspondant à la fonction ou à l'opérateur. Ces noeuds solutions parents sont à leur tour évalués comme décrit précédemment. En outre, le résultat de l'évaluation est mémorisé au niveau du noeud solution correspondant à la fonction ou à l'opérateur pour pouvoir être utilisé ultérieurement. Le deuxième cas pour la propagation de l'évaluation est celui où le noeud logique correspondant au noeud solution m ne représente pas une étape de localisation. Le noeud logique peut ainsi représenter une fonction, ou bien un opérateur. Dans ce cas, l'algorithme tente d'évaluer la fonction ou l'opérateur, comme décrit précédemment. En outre, si la fonction ou l'opérateur peut être évalué, le résultat de cette évaluation est transmis à ses noeuds solutions parents pour propager l'évaluation. L'étape 1120 est suivie de l'étape 1125 consistant à tester si certains résultats générés au cours de l'étape 1120 correspondent à l'expression principale de l'expression XPath évaluée. Si tel est le cas, alors l'algorithme se poursuit à l'étape 1130 consistant à retourner ces résultats. L'étape suivante est l'étape 1135. Lors de l'étape 1125, si le test est négatif, alors l'étape suivante est l'étape 1135. Cette étape (étape 1135) consiste à réaliser une mise à jour des noeuds solutions. Pour ce faire, l'algorithme commence par considérer un ensemble de noeuds solutions. Cet ensemble de noeuds solutions comprend les noeuds solutions correspondant à une étape de localisation dont un prédicat a été évalué à faux et les noeuds solutions correspondant à la dernière étape du chemin de localisation du résultat et représentant un événement correspondant à un résultat généré lors de l'étape 1120. L'ensemble des noeuds solutions considérés est ensuite supprimé. Ensuite, sont également supprimés les noeuds solutions ne représentant pas une étape de localisation et descendant de l'un de ces noeuds solutions supprimés, soit directement, soit indirectement par l'intermédiaire d'autres noeuds solutions ne représentant pas une étape de localisation. Enfin, les descendants de l'un des noeuds solutions précédemment supprimés correspondant à des étapes de localisation sont examinés. Pour chacun de ces noeuds, deux critères sont vérifiés. D'une part, le noeud solution ne doit pas être enfant d'un autre noeud solution existant. D'autre part, le noeud solution ne doit pas pouvoir être enfant d'un futur noeud solution non encore créé. Ce second critère est vérifié, notamment en analysant la relation du noeud logique correspondant au noeud solution avec ses noeuds logique parents. Si ces deux critères sont vérifiés pour un noeud solution, alors ce noeud solution est supprimé et ses éventuels descendants sont à leur tour examinés de la même manière. L'algorithme se poursuit ensuite à l'étape 1140 afin de vérifier s'il reste d'autres noeuds liés aux noeuds précédemment créés. Si tel est le cas, alors l'algorithme se poursuit à l'étape 1115 précédemment décrite. Dans le cas contraire, il est mis fin à l'algorithme à l'étape 1190. De retour à l'étape 1100, dans le cas où l'événement e correspond à la fin d'un item XML, par exemple à une balise fermante pour un élément XML, l'algorithme se poursuit à l'étape 1150 au cours de laquelle il est recherché s'il existe un noeud solution n correspondant à l'événement e et au noeud logique r . Si tel n'est pas le cas, alors l'algorithme se termine à l'étape 1190. Si, au contraire, un noeud solution n est trouvé, alors l'algorithme se poursuit à l'étape 1155 consistant à propager l'événement de fin d'item. La propagation de l'événement de fin d'item consiste à terminer toutes les évaluations qui ne pouvaient l'être avant la fin de cet item. Pour ce faire, l'ensemble des noeuds solutions descendant du noeud solution n est parcouru, et pour chacun de ces noeuds solutions, il est vérifié si l'événement de fin d'item est utile pour l'évaluation de ce noeud solution. Durant cette vérification, le contexte de recherche correspondant à un noeud solution est utilisé pour vérifier si l'événement de fin d'item indique la fin du contexte de recherche et donc la fin de l'évaluation du noeud solution. Si tel est le cas alors l'évaluation est réalisée. Si cette évaluation est terminée, alors elle est propagée comme décrit précédemment. Par exemple, dans le cas d'une expression de type a/b[position() = last()] , l'événement de fin d'élément a permet de calculer la valeur de last() pour cet événement. L'étape 1155 est suivie de l'étape 1160 permettant de tester si des résultats on été générés par la propagation de fin d'item. Cette étape est similaire à l'étape 1125. Si tel est le cas, alors l'algorithme se poursuit à l'étape 1165 au cours de laquelle ces résultats sont retournés. Cette étape est similaire à l'étape 1130. L'étape suivante est l'étape 1170. Si le test de l'étape 1160 est négatif, alors l'algorithme se poursuit à l'étape 1170 de mise à jour des solutions. L'étape 1170 est similaire à l'étape 1135. Toutefois, elle en diffère par l'ensemble de noeuds solutions considérés. En effet, en plus des noeuds solutions correspondant à une étape de localisation dont un prédicat a été évalué à faux et des noeuds solutions correspondant à un résultat généré, dans certains cas le noeud solution n est ajouté à cet ensemble de noeuds solutions. Le noeud solution n est effectivement ajouté à cet ensemble de noeuds solutions s'il existe un noeud logique rp représentant une étape de localisation liée directement au noeud logique r ou indirectement par l'intermédiaire de noeuds logiques ne représentant pas une étape de localisation et vérifiant deux conditions. D'une part, aucun noeud solution correspondant à ce noeud logique rp n'a été associé au noeud solution n . D'autre part, il n'est plus possible de trouver un noeud solution correspondant à ce noeud logique rp et pouvant être associé au noeud solution n . Pour un noeud logique rp descendant du noeud logique r associé au noeud solution n , cette deuxième condition peut être évaluée à l'aide du contexte de recherche pour rp associé au noeud solution n . Ainsi dans le cas de l'expression /a/b , lors du traitement de l'événement représentant la balise fermante d'un élément a , Si aucun noeud solution représentant un élément b fils de cet élément a n'a été trouvé, alors le noeud solution représentant a est supprimé. La même situation se produit aussi lors de l'évaluation de l'expression /a[b] . L'étape 1170 est suivie de l'étape 1190 mettant fin à l'algorithme. Afin de mettre en oeuvre le procédé d'évaluation d'une expression sur des éléments d'un document structuré, un dispositif d'évaluation d'une expression sur des éléments d'un document structuré comprend notamment des moyens de génération, à partir de l'expression, d'un ensemble des noeuds cibles correspondant à des items à rechercher dans le document structuré ; des moyens de génération d'une représentation logique de l'expression, une représentation logique comprenant un ensemble de noeuds, représentant les sous-expressions élémentaires de l'expression, reliés en fonction des relations entre ces sous-expressions élémentaires ; et des moyens d'évaluation de l'expression sur des items du document structuré à partir de l'ensemble des noeuds cibles généré et de la représentation logique générée. Ce dispositif d'évaluation d'une expression sur des éléments d'un document structuré peut être incorporé dans un ordinateur 1200 tel qu'illustré à la Figure 12. En particulier, les différents moyens identifiés ci-dessus peuvent être incorporés dans une mémoire morte 1205 ("Read-Only Memory" ou ROM) adaptée à mémoriser un programme d'évaluation d'une expression sur des éléments d'un document structuré conforme à l'invention. La mémoire vive 1210 ("Random Access Memory" ou RAM) est adaptée à mémoriser dans des registres les valeurs modifiées lors de l'exécution du programme d'évaluation d'une expression sur des éléments d'un document structuré. Le microprocesseur 1220 est intégré à un ordinateur 1200 qui peut être connecté à différents périphériques et à d'autres ordinateurs d'un réseau de communication. Cet ordinateur comporte de manière connue une interface de communication 1230 reliée au réseau de communication 1235 pour recevoir ou transmettre des messages. L'ordinateur comporte en outre des moyens de stockage de documents, tel qu'un disque dur 1270, ou est adapté à coopérer au moyen d'un lecteur de disque 1280 (disquettes, disques compacts ou cartes informatiques) avec des moyens de stockage de documents amovibles, tels que des disques 1285. Ces moyens de stockage fixes ou amovibles peuvent comporter le code du procédé d'évaluation d'une expression sur des éléments d'un document structuré conforme à l'invention. Ils sont également adaptés à mémoriser un document électronique contenant des données hiérarchisées tel que défini par la présente invention. A titre de variante, le programme permettant au dispositif d'évaluation d'une expression de mettre en oeuvre l'invention peut être stocké dans la mémoire morte 1205. En seconde variante, le programme pourra être reçu pour être stocké comme décrit précédemment par l'intermédiaire du réseau de communication 1235. L'ordinateur 1200 possède également un écran 1240 permettant par exemple de servir d'interface avec un opérateur à l'aide du clavier 1250 ou de la souris 1260 ou de tout autre moyen. L'unité centrale 1220 (CPU) exécutera alors les instructions relatives à la mise en oeuvre de l'invention. Lors de la mise sous tension, les programmes et méthodes relatives à l'invention stockés dans une mémoire non volatile, par exemple la mémoire 1205, sont transférés dans la mémoire 1210 qui contiendra alors le code exécutable de l'invention ainsi que les variables nécessaires à la mise en oeuvre de l'invention. Le bus de communication 1290 permet la communication entre les différents sous-éléments de l'ordinateur ou liés à lui. La représentation de ce bus 1290 n'est pas limitative et notamment le microprocesseur 1220 est susceptible de communiquer des instructions à tout sous-élément directement ou par l'intermédiaire d'un autre sous-élément. Bien entendu, de nombreuses modifications peuvent être apportées aux exemples de réalisation décrits précédemment sans sortir du cadre de l'invention. REVENDICATIONS 1. Procédé d'évaluation d'une expression sur des items d'un document structuré, une expression comprenant un ensemble de sous- expressions élémentaires, caractérisé en ce qu'il comprend les étapes préalables suivantes : - génération, à partir de l'expression, d'un ensemble des noeuds cibles (920) correspondant à des items à rechercher dans le document structuré ; - génération d'une représentation logique (930) de l'expression, une représentation logique comprenant un ensemble de noeuds, représentant les sous-expressions élémentaires de l'expression, reliés en fonction des relations entre ces sous-expressions élémentaires ; et une étape de - évaluation de l'expression sur des items du document structuré à partir de l'ensemble des noeuds cibles généré et de la représentation logique générée. 2. Procédé selon la revendication 1, caractérisé en ce que l'étape de 20 génération d'un ensemble des noeuds cibles comprend, en outre, la génération d'une représentation des relations entre les noeuds cibles. 3. Procédé selon la revendication 1 ou la revendication 2, caractérisé en ce que l'étape d'évaluation de l'expression comprend : 25 - une étape de filtrage des items du document à partir de l'ensemble des noeuds cibles ; et - une étape d'évaluation des items filtrés à partir de la représentation logique. 30 4. Procédé selon la revendication 3, caractérisé en ce que l'étape de filtrage des items du document à partir de l'ensemble des noeuds cibles comprend une étape d'identification des items du document correspondant à des noeuds cibles de l'ensemble des noeuds cibles. 5. Procédé selon la revendication 3 ou la revendication 4, caractérisé en ce que l'étape d'évaluation des items filtrés comprend une étape de création d'un noeud solution associé à un noeud de la représentation logique, ce noeud solution représentant un résultat d'évaluation pour le noeud de la représentation logique. 6. Procédé selon la revendication 5, caractérisé en ce que l'étape de création d'un noeud solution associé à un noeud de la représentation logique comprend une étape d'association d'un item filtré avec ce noeud solution. 7. Procédé selon la revendication 6, caractérisé en ce que l'étape d'évaluation des items filtrés comprend en outre une étape de création d'une relation entre un premier noeud solution associé à un premier noeud de la représentation logique et au moins un deuxième noeud solution associé à un deuxième noeud de la représentation logique conformément à la relation entre le premier noeud de la représentation logique et le deuxième noeud de la représentation logique. 8. Procédé selon la revendication 7, caractérisé en ce que l'étape d'évaluation de l'expression comprend en outre une étape de vérification de la complétude d'une solution comprenant les sous-étapes suivantes : -vérification de l'existence pour chaque noeud de la représentation logique d'au moins un noeud solution associé ; - sélection pour chaque noeud de la représentation logique d'un noeud solution associé, l'ensemble des noeuds solutions sélectionnés formant une solution ; - pour chaque relation entre deux noeuds de la représentation logique, vérification qu'une relation similaire existe entre les noeuds solutions associés sélectionnés. 9. Procédé selon la revendication 8, caractérisé en ce que l'étape d'évaluation de l'expression comprend, si l'étape de vérification de la complétude d'une solution est positive, une étape de génération d'un résultat à partir de la solution. 10. Procédé selon l'une quelconque des revendications 3 à 9, caractérisé en ce qu'un contexte de recherche est associé à un item filtré correspondant à un noeud de la représentation logique et à un noeud de la représentation logique descendant du noeud correspondant à l'item filtré. 11. Procédé selon la revendication 10, caractérisé en ce qu'un contexte de recherche comprend une information d'identification d'une partie du document dans laquelle est recherché un item correspondant au noeud descendant. 12. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il comprend une étape de transmission d'un résultat dès la fin de l'évaluation de l'expression. 13. Procédé selon l'une quelconque des revendications 5 à 12 caractérisé en ce qu'il comprend une étape de suppression d'un noeud solution, la suppression d'un noeud solution étant réalisée en fonction d'un critère de validité du noeud solution. 14. Procédé selon la revendication 13, caractérisé en ce que le critère de validité d'un noeud solution dépend des relations existant entre ce noeud solution et d'autres noeuds solutions et des contextes de recherches associés au noeud de la représentation logique associé à ce noeud solution. 25 30 15. Dispositif d'évaluation d'une expression sur des items d'un document structuré, une expression comprenant un ensemble de sous-expressions élémentaires, caractérisé en ce qu'il comprend : - des moyens de génération, à partir de l'expression, d'un ensemble 5 des noeuds cibles correspondant à des items à rechercher dans le document structuré ; - des moyens de génération d'une représentation logique de l'expression, une représentation logique comprenant un ensemble de noeuds, représentant les sous-expressions élémentaires de l'expression, reliés en 10 fonction des relations entre ces sous-expressions élémentaires ; et - des moyens d'évaluation de l'expression sur des items du document structuré à partir de l'ensemble des noeuds cibles généré et de la représentation logique générée. 15 16. Dispositif selon la revendication 15, caractérisé en ce que les moyens de génération d'un ensemble des noeuds cibles comprennent, en outre, des moyens de génération d'une représentation des relations entre les noeuds cibles. 20 17. Dispositif selon la revendication 15 ou la revendication 16, caractérisé en ce que les moyens d'évaluation de l'expression comprennent : - des moyens de filtrage des items du document à partir de l'ensemble des noeuds cibles ; et - des moyens d'évaluation des items filtrés à partir de la 25 représentation logique. 18. Dispositif selon la revendication 17, caractérisé en ce que les moyens de filtrage des items du document à partir de l'ensemble des noeuds cibles comprennent des moyens d'identification des items du document 30 correspondant à des noeuds cibles de l'ensemble des noeuds cibles. 19. Dispositif selon la revendication 17 ou la revendication 18, caractérisé en ce que les moyens d'évaluation des items filtrés comprennent des moyens de création d'un noeud solution associé à un noeud de la représentation logique, ce noeud solution représentant un résultat d'évaluation pour le noeud de la représentation logique. 20. Dispositif selon la revendication 19, caractérisé en ce que les moyens de création d'un noeud solution associé à un noeud de la représentation logique comprennent des moyens d'association d'un item filtré avec ce noeud solution. 21. Dispositif selon la revendication 20, caractérisé en ce que les moyens d'évaluation des items filtrés comprennent en outre des moyens de création d'une relation entre un premier noeud solution associé à un premier noeud de la représentation logique et au moins un deuxième noeud solution associé à un deuxième noeud de la représentation logique conformément à la relation entre le premier noeud de la représentation logique et le deuxième noeud de la représentation logique. 22. Dispositif selon la revendication 21, caractérisé en ce que les moyens d'évaluation de l'expression comprennent en outre des moyens de vérification de la complétude d'une solution comprenant : - des moyens de vérification de l'existence pour chaque noeud de la représentation logique d'au moins un noeud solution associé ; - des moyens de sélection pour chaque noeud de la représentation logique d'un noeud solution associé, l'ensemble des noeuds solutions sélectionnés formant une solution ; - des moyens de vérification aptes à vérifier, pour chaque relation entre deux noeuds de la représentation logique, qu'une relation similaire existe entre les noeuds solutions associés sélectionnés. 23. Dispositif selon la revendication 22, caractérisé en ce que les moyens d'évaluation de l'expression comprennent des moyens de génération d'un résultat à partir de la solution. 24. Dispositif selon l'une quelconque des revendications 17 à 23, caractérisé en ce qu'il comprend des moyens d'association d'un contexte de recherche à un item filtré correspondant à un noeud de la représentation logique et à un noeud de la représentation logique descendant du noeud correspondant à l'item filtré. 25. Dispositif selon la revendication 24, caractérisé en ce qu'un contexte de recherche comprend une information d'identification d'une partie du document dans laquelle est recherché un item correspondant au noeud descendant. 26. Dispositif selon l'une quelconque des revendications 15 à 25, caractérisé en ce qu'il comprend des moyens de transmission d'un résultat dès la fin de l'évaluation de l'expression. 20 27. Dispositif selon l'une quelconque des revendications 19 à 26, caractérisé en ce qu'il comprend des moyens de suppression d'un noeud solution, la suppression d'un noeud solution étant réalisée en fonction d'un critère de validité du noeud solution. 25 28. Dispositif selon la revendication 27, caractérisé en ce que le critère de validité d'un noeud solution dépend des relations existant entre ce noeud solution et d'autres noeuds solutions et des contextes de recherches associés au noeud de la représentation logique associé à ce noeud solution. 30 29. Produit programme ordinateur pouvant être chargé dans un appareil programmable, caractérisé en ce qu'il comporte des séquences d'instructions pour mettre en oeuvre un procédé d'évaluation d'une expression15 sur des items d'un document structuré selon l'une quelconque des revendications 1 à 14, lorsque ce programme est chargé et exécuté par l'appareil programmable. 30. Moyen de stockage d'informations, lisible par un ordinateur ou un microprocesseur conservant des instructions d'un programme d'ordinateur, caractérisé en ce qu'il permet la mise en oeuvre d'un procédé d'évaluation d'une expression sur des items d'un document structuré selon l'une quelconque des revendications 1 à 14.10