FR2936623A1 - Procede de codage d'un document structure et de decodage, dispositifs correspondants - Google Patents

Abstract

La présente invention concerne le codage d'un document structuré (100) en un flux binaire (108), le décodage d'un tel document codé (108), notamment pour accéder à une sous-partie du document. En particulier, un procédé de codage comprend le codage (E414, E420, E426) d'événements hiérarchisés (102) composant le document structuré (100) en des événements correspondants (110) codés à l'aide d'au moins une table d'encodage (208, 214), ladite au moins une table d'encodage (208, 214) étant mise à jour lors du codage (E414, E450, E426) de certains événements hiérarchisés, et les étapes suivantes : - la détermination des événements hiérarchisés (102) impliqués dans la mise à jour de l'au moins une table d'encodage (208, 214); - l'association (E416, E422, E428) d'une information de marquage (106) aux événements codés (110) correspondant auxdits événements hiérarchisés (102) déterminés. L'invention s'applique en particulier aux documents structurés de type XML.

Description

La présente invention concerne un procédé et un dispositif correspondant de codage d'un document structuré, un procédé et un dispositif de décodage d'un tel document codé, notamment pour accéder à une sous-partie du document, et une structure de données d'un tel document codé.

Elle s'applique en particulier aux documents structurés de type XML (acronyme de "eXtensible Markup Language" pour langage de balisage extensible). Un document XML est composé d'éléments, chaque élément commençant par une balise ouvrante comportant le nom de l'élément (par exemple: <balise>) et se terminant par une balise fermante comportant, elle aussi, le nom de l'élément (par exemple: </balise>). Chaque élément peut contenir d'autres éléments, appelés éléments enfants (une terminologie de filiation, parent , enfant , étant utilisée pour décrire les relations entre les éléments imbriqués) ou des données textuelles. Chaque élément peut également contenir des données textuelles, par exemple sous forme de chaîne de caractères. D'autre part, un élément peut être précisé par des attributs, chaque attribut étant défini par un nom et ayant une valeur. Les attributs sont placés dans la balise ouvrante de l'élément qu'ils précisent (par exemple: <balise attribut="valeur">). La syntaxe XML permet aussi de définir des commentaires (par exemple: <!-- Commentaire-->) et des instructions de traitement, qui peuvent préciser à une application informatique les traitements à appliquer au document XML (par exemple: <?montraitement?> ), ainsi que des sections d'échappement qui permettent d'éviter qu'une section de texte soit interprétée comme une balise lorsqu'elle en a la forme (par exemple: <![CDATA[<texte>Echappement</texte>]]> où <texte> est reconnu comme une chaîne de caractère et non pas comme une balise). On considère dans la suite que des données XML sont décrites en terme d"'items" ou "événements", chaque item ou événement pouvant être un début d'élément (par exemple <balise>), une fin d'élément (par exemple </balise>), un attribut (par exemple attribut="valeur"), un contenu textuel, un commentaire, une instruction de traitement ou une section d'échappement. Plusieurs langages différents basés sur la syntaxe XML peuvent contenir des éléments ou attributs de même nom. Pour pouvoir mélanger plusieurs langages différents, un ajout a été effectué à la syntaxe XML permettant de définir des espaces de nommage ("Namespace" selon la terminologie anglo-saxonne). Deux éléments sont identiques seulement 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 une URI (acronyme de "Uniform Resource Identifier', pour Identifiant uniforme de ressource), par exemple http://canon.crf.fr/xml/monlangage . L'utilisation d'un espace de nommage dans un document XML passe par la définition d'un préfixe qui est un raccourci vers l'URI de cet espace de nommage. Ce préfixe est défini à l'aide d'un attribut spécifique (par exemple: xmins:ml="http://canon.crf.fr/xml/monlangage" associe le préfixe ml à l'URI 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 son nom par le préfixe associé à l'espace de nommage suivi de : (par exemple: <ml:balise ml:attribut="valeur"> indique que l'élément balise découle de l'espace de nommage ml et qu'il en est de même pour l'attribut attribut). Pour la suite, on entend par "nom" d'un élément ou d'un attribut le nom muni ou non de ce préfixe d'espace de nommage. XML présente de nombreux avantages et est devenu un langage de référence pour stocker des données dans un fichier ou pour échanger des données. XML permet en particulier de disposer de nombreux outils pour traiter les fichiers générés. En particulier, un document XML peut être édité manuellement avec un simple éditeur de texte. En outre, comme un document XML contient sa structure intégrée aux données, ce document est très lisible même sans en connaître la spécification.

Le principal inconvénient de la syntaxe XML est d'être très prolixe. Ainsi la taille d'un document XML peut être plusieurs fois supérieure à la taille intrinsèque des données. Cette taille importante des documents XML induit aussi un temps de traitement important lors de la génération et de la lecture de documents XML. Elle induit aussi un temps de transmission important. Pour remédier à ces inconvénients, d'autres méthodes pour encoder un document XML ont été recherchées. Le but de ces méthodes est de coder le contenu du document XML sous une forme plus efficace, tout en permettant de reconstruire facilement le document XML. Cependant, la plupart de ces méthodes ne conservent pas l'ensemble des avantages du format XML. Parmi ces méthodes, la plus simple consiste à coder les données de structure dans un format binaire au lieu d'utiliser un format textuel. En outre, la redondance des informations structurelles dans le format XML peut être supprimée ou au moins diminuée (par exemple, il n'est pas forcément utile de préciser le nom de l'élément dans la balise ouvrante et la balise fermante). Une autre méthode est d'utiliser une table d'index, en particulier pour les noms d'éléments et d'attributs qui sont généralement répétés dans un document XML. Ainsi, lors de la première occurrence d'un nom d'élément, celui-ci est codé normalement dans le fichier et un index lui est associé. Puis, pour les occurrences suivantes de ce nom d'élément, l'index est utilisé à la place de la chaîne complète, réduisant la taille du document généré, mais facilitant aussi la lecture (il n'y a plus besoin de lire la chaîne complète dans le fichier, et en outre, la détermination de l'élément lu peut être réalisée par une comparaison d'entiers au lieu d'une comparaison de chaînes de caractères). Enfin, au-delà de ces méthodes élémentaires, il existe des méthodes plus évoluées consistant notamment à prendre en compte un nombre plus important d'informations structurelles du document afin de compresser davantage les données. On peut citer le cas de la recommandation EXI (pour Efficient XML), format utilisé comme base pour la standardisation d'un format XML binaire par le groupe de travail EXI (acronyme de "Efficient XML Interchange") du W3C (acronyme de World Wide Web Consortium , organisation produisant des standards pour le Web), ou encore le format XML binaire "Fast Infoset", spécifié par la norme ITU-T Rec. X.891 1 ISO/IEC 24824- Ces méthodes évoluées de compression binaire XML (Fast Infoset, EXI) sont de plus en plus utilisées pour stocker et échanger des données XML de façon plus efficace aussi bien en termes de tailles de données qu'en termes de rapidité de lecture.

La recommandation EXI, disponible au travers du document "Efficient XML Interchange (EXI) Format 1.0 - W3C Working Draft 28 July 2008", prend en compte l'ordre d'apparition des différents événements au sein d'un document structuré pour construire une ou plusieurs grammaires qui permettent d'encoder les événements les plus fréquents sur un faible nombre de bits. Une grammaire est composée d'un ensemble de productions, chaque production comprenant une description d'événement XML, une valeur de codage associée et l'indication de la grammaire suivante à utiliser. Pour coder un événement XML à l'aide d'une grammaire, la production contenant la description la plus précise de l'événement XML est utilisée. La valeur de codage contenue dans cette production est utilisée pour représenter l'événement dans le flux binaire codé, et les informations contenues dans l'événement et non décrites dans la production sont codées à la suite. Une grammaire selon Efficient XML est évolutive. Dans un certain nombre de cas, après l'occurrence d'un événement XML déjà décrit par une production de la grammaire (s'il n'est pas décrit par une production, il ne peut être encodé par la grammaire), la grammaire est modifiée pour inclure une nouvelle production plus efficace correspondant à cet événement XML. Cette production peut soit contenir une description plus précise de l'événement, diminuant le nombre d'informations à coder pour représenter l'événement, soit avoir une valeur de codage plus compacte. Les valeurs de codage, ou codes , sont exprimées sous forme de priorités ayant, généralement, entre 1 et 3 niveaux. Coder une valeur de codage revient à coder les valeurs de sa priorité. Chaque niveau est codé sur le nombre de bits minimum pour pouvoir coder la plus grande valeur de ce niveau associée à une production de la grammaire. Ainsi, pour un niveau prenant des valeurs de 0 à 6, on utilise 3 bits de codage.

Pour coder un document XML, un ensemble de grammaires est utilisé. Quelques grammaires servent à coder la structure propre au document XML. En outre, pour chaque type d'événement XML présent dans le document (un type d'élément XML étant un ensemble d'événements ayant le même nom), un ensemble de grammaires est utilisé pour coder les événements XML de ce type. Un ensemble de dictionnaires de chaînes est également utilisé pour encoder les noms d'événements et contenus du document XML. Ces dictionnaires évoluent également par l'incorporation de nouvelles chaînes rencontrées dans le document et codées. Les règles de grammaires utilisées peuvent soit être des règles génériques, communes à tous les documents XML et construites à partir de la syntaxe XML, soit être des règles spécifiques à un type de document, construites à partir d'un Schéma XML décrivant la structure de ce type de document. Lors du décodage, le processus inverse est utilisé : la valeur de codage est extraite et permet d'identifier l'événement XML codé, ainsi que les informations complémentaires à décoder. En outre, lors du décodage, les mêmes règles d'évolution des grammaires et des dictionnaires de chaînes sont utilisées, permettant d'avoir à tout moment un ensemble de règles de grammaires et de dictionnaires identique à celui qui était utilisé lors du codage. A titre d'exemple, le fragment XML suivant est utilisé pour décrire le codage d'un document XML à l'aide de la spécification EXI : <person> <firstname>John</firstname> <lastname>Smith</lastname> </person> L'encodeur n'ayant pas encore rencontré d'événement person , ici un début d'élément <person>, une grammaire par défaut est créée pour cet événement. Il s'agit d'une grammaire ne contenant que des productions génériques. Durant l'encodage de l'élément person , de nouvelles productions sont créées et insérées pour rendre la grammaire liée à l'élément person plus efficace. La grammaire par défaut utilisée pour coder le contenu de l'élément person est la suivante (de manière simplifiée par rapport à la spécification Efficient XML) : ElementContent : EE 0 SE (*) ElementContent 1.0 CH ElementContent 1.1 EE correspond à l'événement de fin d'élément, SE (*) correspond un événement de début d'élément quelconque (générique, le nom n'est donc pas précisé), et CH correspond à un événement de contenu textuel. La grammaire ainsi créée est stockée dans une table, par exemple en mémoire volatile de l'encodeur.

Lors de l'encodage, après avoir reçu l'événement correspondant au début d'élément person (SE (person)), et l'avoir codé par exemple de façon littérale (ou à l'aide d'une grammaire appropriée de plus haut niveau), l'encodeur sélectionne la grammaire de codage du contenu de l'élément person , décrite ci-dessus.

Ensuite, l'encodeur reçoit l'événement correspondant au début d'élément firstname (SE (firstname)). La production qui correspond à cet événement dans la grammaire ci-dessus est la deuxième : SE (*) ElementContent 1.0 L'encodeur va donc coder la priorité 1.0 . Comme le premier niveau de priorité comprend deux valeurs distinctes ( 0 et 1 ) parmi les productions de la grammaire, ce niveau peut être codé sur un bit, avec la valeur 1 . De même, le deuxième niveau de priorité comprend deux valeurs distinctes et peut être codé sur un bit, avec la valeur 0 . La priorité 1.0 est donc codée ici avec les deux bits 10 .

Ensuite, comme la production ne précise pas le nom de l'élément, firstname est codé, par exemple de façon littérale (et/ou en utilisant un dictionnaire de chaînes référençant toutes ou partie des chaînes de caractères), en utilisant la production CH ElementContent 1.1 On poursuit ensuite l'encodage du contenu de firstname . Dans ce dessein, on recherche la règle associée à cet élément. Comme aucun élément firstname n'a été rencontré, on crée une grammaire firstname à partir de la grammaire par défaut. L'élément firstname contient un noeud texte pour unique enfant. On encode ce noeud texte, par exemple à l'aide d'un dictionnaire de chaînes dans lequel on associe la valeur textuelle à un premier index. Une fois ce noeud texte encodé, on met à jour la grammaire de firstname en insérant une production texte CH. Grammaire firstname ElementContent : Characters 0 EE 1 SE (*) ElementContent 2.0 CH ElementContent 2.1 Une fois le contenu de firstname codé, l'encodeur modifie la grammaire associée à l'élément person pour adapter la grammaire aux 20 données XML rencontrées. Pour cela, une nouvelle production est ajoutée à la grammaire, cette production correspondant au début d'élément firstname . A cette production est associée la priorité 0 , et les autres priorités sont décalées pour conserver l'unicité des priorités. On rappelle ici que le décodeur agissant de façon symétrique sera en mesure de réaliser des décalages de 25 priorités (ou index) similaires au fur et à mesure du décodage des données reçues. Ainsi la grammaire devient : 30 Grammaire person ElementContent : SE (firstname) ElementContent 0 EE 1 SE (*) ElementContent 2.0 CH ElementContent 2.1 L'événement suivant du fragment XML à coder est le début de l'élément lastname . Comme pour firstname , cet élément est codé à l'aide de la production : SE (*) ElementContent 2.0 puisque aucune production correspondant à l'élément lastname n'est trouvée. Le premier niveau de priorité ayant maintenant trois valeurs possibles, il est codé sur 2 bits, avec la valeur 2 . Le deuxième niveau de priorité est toujours codé sur un seul bit. La priorité 2.0 est donc codée ici avec les trois bits 100 . Le nom de l'élément, lastname , est ensuite codé par exemple littéralement en binaire. Puis le contenu de lastname est codé à l'aide de la grammaire associée à l'élément lastname , à créer si nécessaire lors de la première itération, de façon similaire à celle décrite ci-dessus pour firstname . Ensuite, la grammaire person est modifiée pour y ajouter une production correspondant au début de l'élément lastname et elle devient alors : Grammaire person ElementContent : SE (lastname) ElementContent 0 SE (firstname) ElementContent 1 EE 2 SE (*) ElementContent 3.0 CH ElementContent 3.1 Ensuite, l'événement de fin d'élément, correspondant à la fin de l'élément person est codé, en utilisant la production : EE 2 Il est à noter que toutes les productions de la grammaire à 30 l'exception de cette dernière production comprennent la description d'un événement, le code associé et la grammaire suivante à utiliser. Cette 25 grammaire suivante est celle utilisée pour continuer le codage après le codage de l'événement compris dans la production. Cependant, dans le cas d'un événement décrivant un début d'élément, les grammaires spécifiques à cet élément sont utilisées pour coder le contenu de l'élément. La grammaire suivante indiquée dans la production comprenant l'événement de début d'élément est utilisée pour le codage après la fin de cet élément. Aussi, la production comprenant l'événement de fin d'élément ne contient pas de grammaire suivante : la grammaire à utiliser pour coder la suite du document est celle qui avait été indiquée par la grammaire de l'élément parent dans la production utilisée pour coder l'événement de début de cet élément. Si, par la suite, dans le document XML, le codeur rencontre un autre élément person similaire, cet élément va être codé à partir de cette grammaire. Ainsi le premier événement correspondant au contenu de l'élément person est l'événement de début de l'élément firstname . Cet élément est codé avec la production:

correspond aussi à cet événement, mais est moins précise (elle ne précise pas le nom firstname de l'élément. C'est donc la première production qui est utilisée pour une efficacité de codage accrue. L'encodeur code donc la priorité de cette production, à savoir la valeur "1", qui est codée sur deux bits (car prenant des valeurs de 0 à 3), soit "01". Il n'y a pas besoin de coder le nom de l'élément, puisque celui-ci est précisé par la production et ressort du codage littéral initial lorsque l'élément firstname a été rencontré pour la première fois. L'encodeur code ensuite le contenu de l'élément firstname .

Comme une production spécifique à l'événement de début de l'élément firstname existe déjà dans la grammaire, il n'est pas nécessaire d'ajouter une nouvelle production à la grammaire. SE (firstname) ElementContent 1 On note que la production 3.0 SE (*) ElementContent L'encodeur code ensuite, de manière similaire, l'événement de début de l'élément lastname , en codant uniquement la priorité 0 avec les deux bits 00 . Ainsi, pour le codage du deuxième élément person similaire au premier, le code généré est plus compact, puisqu'il n'est plus nécessaire de coder le nom des éléments contenus dans person , ni littéralement (en codant l'intégralité de la chaîne de caractères), ni même à l'aide d'un index. D'autres productions, par exemple celles relatives aux attributs: AT (*) ElementContent, sont également utilisées lorsque des événements correspondants sont présents dans le document XML. Des dictionnaires de chaînes regroupant les différentes valeurs de chaînes rencontrées et leurs codes binaires associés sont également prévus, parfois spécialisés en dictionnaire d'éléments (regroupant les noms des éléments de structure), dictionnaire d'attributs (regroupant les noms des attributs), dictionnaire de contenu (regroupant les données textuelles), etc. Pour la suite, on regroupe, sous le terme de tables ou dictionnaires d'encodage (ou de décodage le cas échéant), les grammaires, productions, dictionnaires de chaînes prévus par EXI, les tables d'index prévues par Fast Infoset et toute autre structure d'encodage équivalente utilisée par des algorithmes de codage XML binaire. Ces méthodes évoluées de compression binaire XML (Fast Infoset, EXI) ne permettent cependant pas aisément de décoder uniquement des sous-parties d'un document XML binaire ainsi généré. Pourtant, le décodage partiel peut s'avérer très utile lorsque seulement une sous-partie d'un document est utile à l'application qui le manipule. De tels accès partiels sont généralement nombreux pour un même document binaire XML. C'est le cas par exemple des traitements de requêtes XPath ou XQuery sur des documents XML binaires. En effet, si l'on considère par exemple l'algorithme d'encodage EXI comme vu ci-dessus, le codeur maintient, durant l'encodage, diverses tables d'encodage (dictionnaires et grammaires) : certaines pour les chaînes de valeurs (valeur de noeuds texte, valeurs d'attributs, noms d'éléments et d'attributs, définition des URI des espaces de nommage...) et d'autres pour les informations décrivant la structure du document (grammaires de productions). Afin de fournir un fort taux de compression, ces tables d'encodage ne sont pas transmises au décodeur qui doit, sur le même schéma que le codeur, les reconstruire (lors du décodage, ces tables peuvent également être appelées tables de décodage) au fur et à mesure du décodage. Ceci implique que lorsque l'on veut commencer à reconstruire le document à partir d'une position donnée, le décodeur doit tout de même parcourir tout le début du document jusqu'à la position voulue afin que ses tables de décodage se trouvent dans l'état correspondant à cette position (c'est-à-dire comprenant toutes les grammaires/productions requises et chaînes de caractères codées) pour permettre la reconstruction de la portion du document commençant à cette position. On cherche donc à améliorer la récupération de sous-parties de 15 document binaire XML, et notamment d'améliorer le codage d'un document structuré pour faciliter une telle récupération. On connaît déjà des mécanismes pour la récupération de sous-parties dans un document XML non codé, par exemple par le document US 7 133 857. Ces mécanismes reposent sur l'utilisation d'une indexation des 20 informations de structure du document XML réalisée sous la forme d'un fichier binaire. Chaque entrée de l'index (fichier binaire) stocke notamment une position dans le document XML, la profondeur du bloc de données correspondant, un indicateur de modification, un indicateur d'insertion (pour décrire des noeuds fils) et un indicateur de fin de document. 25 Ainsi, lorsqu'un logiciel souhaite accéder à une sous-partie du document XML, il s'appuie sur le fichier binaire d'indexation afin de notamment déterminer la profondeur des éléments à récupérer. Cela permet de pallier les inconvénients des analyseurs de bits ("parsec" selon la terminologie anglo-saxonne) type DOM gourmand en ressources pour représenter la structure du 30 document XML sous forme d'arbre hiérarchique et les inconvénients des analyseurs de bits type SAX ne s'appuyant pas sur la hiérarchisation des données dans le document.

Néanmoins, cette solution a été développée pour des documents structurés non compressés et ne tient donc pas compte des contraintes liées à la compression (quantité de données, valeurs compressées à décoder lors de l'accès).

On connaît également, dans la recommandation EXI susmentionnée, l'option "self-contained" mise en oeuvre au travers d'un type d'événement EXI particulier (nommé SC) pour coder les événements d'un document XML. En utilisant ce type d'événement EXI, on peut réaliser un encodage indépendant de un ou plusieurs événements XML, c'est-à-dire que chaque événement ainsi codé est auto-descriptif. Ainsi, il n'est plus nécessaire, pour l'encodeur recevant le flux encodé, de lire le début du flux binaire pour accéder à un événement XML encodé par l'événement EXI de type "SC". Néanmoins, cette solution peut poser des problèmes d'interopérabilité entre codeurs et décodeurs, puisque l'option "self-contained" est une extension du standard EXI qui n'est pas toujours acceptée par les décodeurs. En outre, un grand nombre d'informations est statistiquement nécessaire pour le codage de tels événements auto-descriptifs, en particulier des informations pour chacun des événements du document XML. Il en résulte une baisse notable de l'efficacité de compression. L'invention vise à pallier au moins un des inconvénients précités en complétant le flux binaire codé d'indications permettant au décodeur de se configurer rapidement et à moindre coût dans un état adapté, étant donnée une position à partir de laquelle il doit reconstruire le document XML.

A cet effet, l'invention concerne notamment un procédé de codage d'un document structuré en un flux binaire, comprenant le codage d'événements hiérarchisés composant le document structuré en des événements correspondants codés à l'aide d'au moins une table d'encodage, ladite au moins une table d'encodage étant mise à jour lors du codage de certains événements hiérarchisés, le procédé étant caractérisé en ce qu'il comprend les étapes suivantes : - la détermination des événements hiérarchisés impliqués dans la mise à jour de l'au moins une table d'encodage ; - l'association d'une information de marquage aux événements codés correspondant auxdits événements hiérarchisés déterminés.

On note que généralement les tables d'encodage ou les dictionnaires sont mis à jour lors de la première occurrence d'un nouvel événement hiérarchisé ou d'une nouvelle valeur d'événement que l'on souhaite indexer dans un dictionnaire. Néanmoins, certaines valeurs peuvent ne jamais être indexées car leur indexation serait peu profitable à la compression.

Selon l'invention, le décodeur recevant le flux binaire ainsi codé avec les informations de marquage dispose rapidement d'une représentation haut niveau du document structuré, à partir de ces informations de marquage, permettant notamment de choisir une position d'accès dans celui-ci. En outre, à partir des informations de marquage, le décodeur souhaitant accéder à une sous-partie recense rapidement les différents événements utiles à la formation des tables de décodage nécessaires, principalement ceux contribuant à la mise à jour des tables d'encodage et situés en amont de la position d'accès dans le flux binaire. Il s'en suit un accès, dans le flux binaire, uniquement à ces 20 événements marqués et non à tout le début du document codé. La présente invention permet de conserver une bonne compression des documents structurés tout en facilitant les accès, éventuellement nombreux, à des sous-parties du document codé. Dans un mode de réalisation, le procédé comprend les étapes 25 suivantes : - la construction d'une table d'indexation desdits événements codés, ladite table d'indexation comprenant, pour une pluralité d'événements codés, une information représentative de la position dudit événement codé dans le flux binaire et une information représentative de l'implication ou non, à 30 une mise à jour de l'au moins une table d'encodage, de l'événement hiérarchisé correspondant, et - l'ajout de ladite table d'indexation audit flux binaire.

Dans cette configuration, l'ensemble des informations permettant au décodeur d'accélérer l'accès au document structuré est regroupé dans un même index, indifféremment appelé "table d'indexation" par la suite. Le traitement de ces informations par le décodeur en est ainsi encore facilité.

Le mécanisme d'indexation selon l'invention fournit ainsi des points d'entrée dans le flux binaire moyennant l'inclusion d'une table d'indexation dans ce flux. Selon une caractéristique particulière, ladite pluralité d'événements codés comprend une pluralité d'événements hiérarchisés relatifs à la structure dudit document, et ladite table d'indexation comprend en outre, pour des événements codés relatifs à du contenu dudit document, uniquement une information représentative de leur position dans le flux binaire. Les événements de contenu, généralement les données textuelles du document XML, sont ici uniquement indexés par la mention relative à leur position dans le flux. En effet, les données textuelles étant rarement identiques, il est apparu plus efficace de toutes les considérer comme contribuant à une mise à jour des tables (le décodeur détectant les exceptions) plutôt que d'augmenter la taille de l'index par l'indication de cette contribution. Dans un mode de réalisation, ladite table d'indexation comprend en outre, pour la pluralité d'événements codés, une donnée d'identification du nom de l'événement hiérarchisé correspondant. Grâce à cette donnée d'identification, la table d'indexation reconstituée par le décodeur pour accéder à un point d'entrée du document peut être optimisée, au niveau du décodeur, par la suppression des événements similaires à l'événement directement parent du point d'accès et ne contribuant pas à la mise à jour des tables d'encodage, tout en conservant la hiérarchie des événements jusqu'au point d'accès pour assurer, par exemple dans le cas EXI, un bon empilement des grammaires. Selon une caractéristique, ladite table d'indexation renseigne, pour chaque événement codé de ladite pluralité, le type d'événement correspondant et la profondeur dudit événement correspondant dans la structure hiérarchique dudit document.

Dans un mode de réalisation s'appliquant également au marquage au sens large selon l'invention, ladite au moins une table d'encodage comprend une table d'encodage d'événements de structure et une table d'encodage de chaînes de caractères, et ladite information représentative de l'implication prend une valeur différente pour représenter l'implication d'une mise à jour d'au moins une table d'encodage incluant ladite table d'encodage d'événements de structure et pour représenter l'implication d'une mise à jour d'uniquement une table d'encodage de chaînes de caractères. Une table d'encodage d'événements de structure peut consister en une grammaire au sens EXI, alors qu'une table d'encodage de chaînes peut être un dictionnaire d'indexation de valeurs. Dans cette configuration, on distingue ainsi les contributions/implications relatives à la structure du document (par exemple création d'une nouvelle production au sens EXI) et les contributions relatives uniquement à une nouvelle valeur (chaîne de caractères). La construction des tables de décodage par le décodeur est ainsi plus simple. En particulier, ladite information représentative de l'implication est codée, en cas de mise à jour de la table d'encodage d'événements de structure, sur un nombre de bits plus petit qu'en l'absence de mise à jour d'une telle table d'encodage. Cette configuration convient particulièrement bien aux documents structurés irréguliers car les événements modifiant les tables d'encodage relatives à la structure du document, création de nouvelles productions EXI par exemple, sont ainsi favorisés pour une compression minimum. En variante, ladite information représentative de l'absence d'implication est codée sur un nombre de bits plus petit que l'information représentative de l'implication d'une mise à jour de tables d'encodage d'événements de structure. Cette variante convient particulièrement bien aux documents structurés réguliers car elle favorise, pour la compression du document XML, les événements n'apportant pas de modification/mise à jour des tables d'encodage (et donc de décodage).

Dans un mode de réalisation améliorant la compression du flux binaire total (incluant la table d'indexation), le procédé comprend une étape de compression de ladite table d'indexation avant son ajout audit flux binaire. En particulier, lors de ladite compression, on groupe les entrées de la table d'indexation selon le type d'événement correspondant et la profondeur dudit événement correspondant dans la structure hiérarchique dudit document, et on code chaque groupe indépendamment. Ici, on utilise la redondance des informations de type d'événement et de profondeur pour réduire les informations codées, améliorant de la sorte l'efficacité de la compression de l'index. A noter qu'un groupage seul par type d'événement ou par profondeur peut être envisagé pour une compression de l'index moindre. Selon une caractéristique particulière, dans chaque groupe, on code les informations représentatives de la position des événements codés par différence par rapport à la première position dans le groupe. Ainsi, on réduit le nombre de bits nécessaires au codage des informations de position. La compression de la table d'indexation en est améliorée. De façon similaire, on prévoit que ladite donnée d'identification du nom est une valeur, et, dans chaque groupe, on code les données d'identification des noms des événements codés par différence par rapport à la donnée d'identification du nom la plus fréquente dans le groupe. Ainsi, le taux de compression de la table d'indexation est augmenté, car la valeur sera à coder de nombreuses fois puisque obtenue pour chaque occurrence de la donnée d'identification la plus fréquente. Dans un mode de réalisation particulier prévoyant de limiter la taille de la table d'indexation, on code : - les entrées de la table d'indexation dont la profondeur de l'événement correspondant dans la structure hiérarchique du document est inférieur à une profondeur seuil, et - les entrées de la table d'indexation de profondeur supérieure ou égale à la profondeur seuil et dont l'information représentative de l'implication correspond à une mise à jour de l'au moins une table d'encodage.

Ainsi, on n'indexe pas les événements de niveau hiérarchique trop profond, généralement nombreux. En revanche, pour conserver toute l'efficacité du décodeur, on transmet les informations "nécessaires" à la reconstruction des tables de décodage, c'est-à-dire les événements contribuant à une mise à jour des tables d'encodage. Dans un mode de réalisation, ladite table d'indexation éventuellement compressée est insérée dans l'entête dudit flux binaire. Cette configuration assure que le flux binaire reste conforme à, par exemple, la recommandation EXI et donc compatible avec des décodeurs ne mettant pas en oeuvre l'invention. En outre, le décodeur dispose ainsi rapidement de la représentation haut niveau du document structuré pour effectuer des décodages efficaces à la volée, même si le reste du flux binaire n'a pas encore été chargé. Selon différents modes de réalisation, on peut prévoir que : - ladite information représentative de la position indique la position du premier bit du code représentant l'événement codé ; - ladite information représentative de la position indique la position du premier bit d'un code de priorité utilisé pour encoder l'événement. L'invention vise également un procédé de décodage d'une portion d'un flux binaire comprenant des événements codés codant un document structuré, le procédé comprenant les étapes suivantes : - la détermination, dans ledit flux binaire, d'événements codés associés à une information de marquage ; - la construction d'au moins une table de décodage en décodant uniquement, dans ledit flux binaire, des événements codés déterminés ; et - le décodage de ladite portion à l'aide de l'au moins une table de décodage construite. Ainsi, selon l'invention, on reconstruit les tables de décodage en accédant uniquement à des événements codés marqués, et non à tous les événements du début de document précédent le point d'accès. La détection du marquage est une opération moins coûteuse que le parcours de l'ensemble du début du document jusqu'à la position d'accès.

On peut notamment filtrer les événements déterminés en fonction de leurs positions respectives dans le flux binaire, de leur information de marquage et d'une position représentative de la portion de flux à accéder, et utiliser ces événements filtrés pour l'étape de construction. Grâce à ce filtrage, on réduit le nombre d'événements à décoder pour fournir les tables de décodage dans l'état correspondant à la position d'accès souhaitée. La construction des tables de décodage peut notamment comprendre le décodage des événements marqués auxdites positions dans le flux binaire et l'ajout, dans les tables de décodage, de données de décodage correspondant auxdits événements ainsi décodés. Cela correspond au décodage classique appliqué uniquement aux événements marqués. De façon optionnelle, le procédé peut comprendre des étapes symétriques de celles se rapportant aux caractéristiques du procédé de codage exposé précédemment.

En particulier, ladite détermination comprend le décodage d'une table d'indexation comprise dans ledit flux binaire, ladite table d'indexation comprenant, pour une pluralité d'événements codés, une information représentative de la position dudit événement codé dans le flux binaire et ladite information de marquage dudit événement codé. Comme expliqué précédemment, l'utilisation d'une table d'indexation simplifie les traitements effectués par le décodeur. Selon une caractéristique particulière, on filtre ladite table d'indexation de sorte à ne conserver, pour l'étape de construction, que les événements codés dont la position correspondante précède celle du premier événement de la portion de flux binaire à accéder. De la sorte, on limite le nombre d'accès aux événements codés (et donc les opérations de décodage associées) à ceux qui sont prima facie utiles puisque précédant le point d'accès. Selon une caractéristique en variante, on filtre ladite table d'indexation de sorte à ne conserver, pour l'étape de construction, que les événements codés dont la position correspondante précède celle du dernier événement de la portion de flux binaire à accéder. Dans cette réalisation, on permet l'obtention de tables de décodage contenant déjà toutes les informations de codage relatives à la sous-partie à accéder. Ainsi, une fois les tables construites, le décodage à proprement parler de la sous-partie à accéder est plus rapide.

Dans un mode de réalisation particulier, les événements codés de ladite table d'indexation sont associés à une information de profondeur représentative de la profondeur de l'événement dans la structure du document structuré, et, dans le procédé, on filtre, en outre, ladite table d'indexation de sorte à ne conserver que les événements codés dont l'information de marquage est au moins d'un premier type et les événements codés qui sont ancêtres, dans ladite structure, dudit premier événement à accéder dont l'information de marquage est d'un second type. Généralement, le premier type correspond à une indication que l'événement associé contribue à une mise à jour des tables d'encodage/de décodage, alors que le second type correspond à des événements ne mettant pas à jour ces mêmes tables. Ainsi, dans cette réalisation, on minimise les événements traités par le décodeur à ceux qui sont uniquement nécessaires pour mettre à jour les tables de décodage (les événements du premier type) et à ceux qui sont nécessaires pour conserver l'ordonnancement dans les données de structure du document (les événements du second type). Ces derniers événements permettent, par exemple dans le cadre d'EXI, de changer de grammaires au fur et à mesure du parcours de la structure, afin de mettre à jour les bonnes tables de décodage avec les autres événements. Dans un mode de réalisation de l'invention, ladite construction comprend la mise à jour d'une pluralité de tables de décodage par l'ajout de données de décodage associées aux événements décodés, et, préalablement au décodage d'un événement codé filtré, on détermine, à partir du type de l'information de marquage, au moins une table de décodage à mettre à jour. Dans cette configuration, on accélère le traitement au niveau du décodeur car, pour chaque événement codé traité, les tables de décodage à mettre à jour sont déterminées, à l'aide de l'information de marquage, préalablement à l'accès à l'événement codé. Cette détermination peut notamment être menée en parallèle du décodage de l'événement filtré. Selon une caractéristique de l'invention, les événements codés de ladite table d'indexation sont associés à une information de profondeur hiérarchique, et le procédé comprend la construction et l'affichage d'une structure hiérarchique à partir desdites informations de profondeur de sorte qu'un utilisateur peut désigner, dans ladite structure affichée, ladite portion du flux binaire à décoder. L'invention permet ainsi d'obtenir une "première" représentation succincte du document structuré codé, permettant de désigner efficacement la sous-partie à accéder. En cas d'accès successifs à plusieurs sous-parties du document, cet affichage peut notamment s'enrichir des accès précédents pour fournir une représentation plus complète. Corrélativement, l'invention vise également un dispositif de codage d'un document structuré en un flux binaire, comprenant le codage d'événements hiérarchisés composant le document structuré en des événements correspondants codés à l'aide d'au moins une table d'encodage, ladite au moins une table d'encodage étant mise à jour lors du codage de certains événements hiérarchisés, le dispositif étant caractérisé en ce qu'il comprend : - des moyens pour déterminer des événements hiérarchisés impliqués dans la mise à jour de l'au moins une table d'encodage ; - des moyens pour associer une information de marquage aux événements codés correspondant auxdits événements hiérarchisés déterminés. De façon optionnelle, le dispositif de codage peut comprendre des moyens se rapportant aux caractéristiques du procédé de codage exposé précédemment, et présentant les mêmes avantages. De façon similaire, l'invention vise également un dispositif de décodage d'une portion d'un flux binaire comprenant des événements codés codant un document structuré, le dispositif comprenant : - des moyens pour déterminer, dans ledit flux binaire, des événements codés associés à une information de marquage ; - des moyens pour construire au moins une table de décodage en décodant uniquement, dans ledit flux binaire, des événements codés déterminés ; et - des moyens de décodage de ladite portion à l'aide de l'au moins une table de décodage construite. De façon optionnelle, le dispositif de décodage peut comprendre des moyens se rapportant aux caractéristiques du procédé de décodage exposé précédemment, et présentant les mêmes avantages. L'invention a également trait à une structure de données binaires comprenant des codes binaires correspondant à des événements hiérarchisés d'un document structuré codés à l'aide d'au moins une table d'encodage, caractérisé en ce qu'elle comprend, associée à chaque événement d'une pluralité des événements codés, une information de marquage représentative de l'implication de l'événement hiérarchisé correspondant dans une mise à jour de l'au moins une table d'encodage lors du codage de cet événement. Une telle structure simplifie, au même titre que le procédé de codage ci-dessus, notamment grâce aux informations de marquage permettant d'identifier rapidement les événements codés à traiter, les traitements de décodage en permettant la construction des tables de décodage préalablement à l'accès et au décodage, à proprement parler, de la sous-partie d'intérêt. Vue sous l'angle du décodage, cette structure de données vise une structure de données binaires comprenant des codes binaires correspondant à des événements hiérarchisés codés d'un document structuré, et comprenant, associée à chaque événement d'une pluralité des événements codés, une information de marquage représentative de la nécessité de mettre à jour au moins une table de décodage, lors du décodage de l'événement codé correspondant. De façon optionnelle, ces structures peuvent contenir des caractéristiques techniques se rapportant aux étapes de procédé décrites ci- dessus. Notamment, dans un mode de réalisation, la structure comprend une première partie formée de codes binaires correspondant aux événements codés et une deuxième partie comprenant une table d'indexation desdits événements codés, ladite table d'indexation comprenant, pour les événements de ladite pluralité d'événements codés, une information représentative de la position de l'événement codé dans ladite structure de données et ladite information de marquage.

Selon une caractéristique, la structure de données comprend un en-tête incluant ladite deuxième partie et une charge utile incluant ladite première partie. Comme déjà indiqué précédemment, la présence des informations de marquage dans l'en-tête accélère le traitement pour la construction des tables de décodage et le décodage de sous-parties du document.

De façon intrinsèque, la structure de données concerne une structure de données binaires comprenant des codes binaires correspondant à des événements hiérarchisés codés d'un document structuré, et des informations de marquage associées, chacune, à un événement codé correspondant à une première occurrence d'un événement hiérarchisé dans le document structuré.

L'invention concerne également un support d'enregistrement comprenant une des structures de données ci-dessus. Un moyen de stockage d'informations, éventuellement totalement ou partiellement amovible, lisible par un système informatique, comprend des instructions pour un programme informatique adapté à mettre en oeuvre le procédé de traitement conforme à l'invention lorsque ce programme est chargé et exécuté par le système informatique. Un programme d'ordinateur lisible par un microprocesseur, comprend des portions de code logiciel adaptées à mettre en oeuvre le procédé de traitement conforme à l'invention, lorsqu'il est chargé et exécuté par le microprocesseur. Les moyens de stockage d'information et programme d'ordinateur présentent des caractéristiques et avantages analogues aux procédés qu'ils mettent en oeuvre. Grâce à l'invention, on peut reconstruire un fragment XML à partir de n'importe quelle position dans un flux XML binaire de type EXI ou similaire. Cette reconstruction efficace est obtenue par la création, lors du codage EXI, d'un document structuré, et par le stockage d'un ensemble d'informations (index ou table d'indexation) relatif aux événements qui contribuent à la mise à jour des tables d'encodage EXI, et leur position dans le flux binaire. L'index est de préférence stocké dans le flux binaire contenant le document structuré codé en format EXI.

Les différents modes de réalisation de l'invention permettent : - un décodage plus simple et plus rapide des fragments XML, permettant le décodage à la volée ; - différents modes de décodage : à partir de l'index, de l'index et du flux, ou du flux uniquement ; - le flux binaire reste compatible au format EXI ; - des données d'indexation sont non mixées avec les données du document, ce qui permet : o au décodeur ne mettant pas en oeuvre l'invention de pouvoir tout de même traiter le flux ; o aux décodeurs mettant en oeuvre l'invention de pouvoir ne décoder efficacement qu'une sous-partie du flux binaire ; - un compromis entre compression et granularité des accès en contrôlant la profondeur d'indexation ; - d'adapter le marquage des événements contributeurs en fonction 20 de la nature du document XML ; - d'avoir un marquage plus précis pour savoir sur quel dictionnaire de valeurs, défini par EXI, un événement indexé intervient (par exemple celui des noms locaux, des valeurs globales, des valeurs locales, des préfixes, des URIs). 25 D'autres particularités et avantages de l'invention apparaîtront encore dans la description ci-après, illustrée par les dessins ci-joints, dans lesquels : - la figure 1 représente un exemple de document structuré et une table d'indexation établie selon la présente invention ; 30 - la figure 2 illustre le décodage selon l'invention d'une sous-partie du document de la figure 1 ; - la figure 3 est une représentation fonctionnelle d'un codeur selon l'invention ; - la figure 4 est un ordinogramme représentant un exemple d'étapes de codage selon l'invention ; - la figure 5 représente, sous forme d'ordinogramme, des étapes d'indexation d'un événement EXI lors du codage de la figure 4 ; - la figure 6 illustre la compression d'une table d'indexation selon l'invention, lors du codage de la figure 4 ; - la figure 7 représente un exemple de structure de table d'indexation compressée ; - la figure 8 est une représentation fonctionnelle d'un décodeur selon l'invention ; - la figure 9 est un ordinogramme représentant un exemple d'étapes de décodage selon l'invention ; - la figure 10 représente, sous forme d'ordinogramme, des étapes de filtrage de la table d'indexation reçue et de décodage rapide lors du processus global de décodage de la figure 9 ; et - la figure 11 montre une configuration matérielle particulière d'un dispositif de traitement d'information apte à une mise en oeuvre du procédé selon l'invention. On illustre maintenant l'invention à l'aide d'un premier exemple de document structuré 100, ici un document XML, tel que représenté en figure 1. Pour simplifier les explications qui suivent, cet exemple ne regroupe que des événements 102 de type début d'élément (type SE au format EXI), fin d'élément (type EE), attribut (type AT) et chaîne de caractère (type CH). Néanmoins, l'invention s'applique à tout événement d'un document structuré. On a représenté en 104 une numérotation des positions des événements XML du document 100, ici la numérotation étant incrémentée d'événements en événements. Par exemple <book> constitue l'événement début d'événement d'indice 2 et <price="17.99"> constitue l'événement attribut d'indice 3.

Bien entendu, l'invention s'applique à d'autres numérotations, par exemple bit par bit, ou ligne par ligne et mot par mot à l'intérieur de chaque ligne. L'invention concerne notamment le codage d'un tel document 100, 5 par exemple selon la recommandation EXI décrite précédemment par l'utilisation de grammaires et dictionnaires. Comme nous le verrons par la suite, grâce à l'invention, on obtient un index 106 répertoriant des événements 102 du document 100, ici l'ensemble de ces événements, identifiables par leur position posi correspondant à la position 10 de l'évènement indexé numéro i en 104 dans le flux EXI encodé. Ces informations sont organisées par profondeur (Profi, correspondant à la profondeur i dans la structure hiérarchique des éléments du document 100, appréciée depuis le premier élément de profondeur moindre jusqu'aux détails du document de profondeur maximale) et par type 15 d'événement (SE, AT, CH), et contiennent : - soit, un identifiant avec une position posi et un marqueur indiquant la contribution à la mise à jour d'au moins un dictionnaire ou grammaire EXI. C'est notamment le cas des événements 102 de type attributs AT et début d'éléments SE, 20 - soit, une position uniquement dans le cas des noeuds texte (CH). Cet index 106 peut être utilisé pour accéder au flux binaire correspondant au document XML 100 une fois codé, par exemple un flux EXI. Selon l'invention, cet index 106, qui est communiqué dans le flux binaire même, permet d'accélérer la reconstruction par décodage d'une sous-25 partie du document initial 100. Par exemple, si l'on veut reconstruire la sous-partie commençant à la position pos23 qui correspond au début d'élément editor , le décodeur filtre cet index 106 reçu pour obtenir un index 150 spécifique à la position pos23, tel qu'illustré sur la figure 2. 30 Comme on le verra par la suite, cet index 150, dit "index position", ne contient globalement que les évènements contribuant à la mise à jour des dictionnaires et grammaires EXI et précédant celui (pos23) par lequel on accède à la sous-partie qui nous intéresse. A l'aide de cet index 150, le décodeur parcourt rapidement (uniquement en accédant aux événements de l'index 150) le flux binaire EXI reçu afin de mettre à jour les dictionnaires et grammaires pour pouvoir ensuite décoder correctement l'élément editor 152 en position 23, par les mécanismes classiques de décodage. L'index 150 contient notamment les événements correspondant aux changements de grammaire EXI, généralement les événements directement parents de celui auquel on souhaite accéder, même s'ils ne contribuent pas à la mise à jour des tables d'encodage. Ici, l'événement SE(booklD, pos16, 00) qui, comme on l'observe du document 100, n'est pas un événement modifiant les dictionnaires et grammaires. Ainsi à la place des trente et un événements indexés, seule la moitié a besoin d'être traitée pour reconstruire le fragment correspondant à l'élément editor . On décrit maintenant les opérations de codage du document XML 100 et de décodage du flux binaire ainsi généré. On illustre notamment ces opérations à l'aide du codage conforme à la recommandation EXI.

On a représenté sur la figure 3 un dispositif de codage 200 pour la mise en oeuvre du procédé de codage selon l'invention. De façon classique, le codeur 200 reçoit en entrée un document XML 100 au niveau d'un analyseur XML 202 extrayant les événements XML 102 un par un.

Un module 204 récupère les types d'événements extraits et alimente un module 206 de gestion des grammaires 208 et d'encodage des priorités dans ces grammaires. En parallèle, un module 210 récupère le nom de l'événement, par exemple dans le cas d'un attribut ("price" dans l'exemple de l'événement d'indice 3 du document 100), qu'il fournit à un module 212 d'encodage des noms d'événement. Ce module 212 réalise cet encodage à l'aide d'un ou plusieurs dictionnaires 214 de chaînes de caractères.

En parallèle toujours, un module 216 récupère les valeurs des événements (par exemple "17.99" dans l'exemple de l'événement d'indice 3 du document 100), qu'il passe à un module d'encodage 218 des valeurs s'appuyant également sur des dictionnaires 214.

Toutes ces informations d'encodage (priorités, codes de nom, codes de valeurs) sont transmises au générateur 220 de flux binaire, qui génère alors le flux binaire EXI 108 correspondant au document XML 100. Pour la suite de la description, on note événement EXI 110, l'ensemble des données binaires de codage (dans le flux 108) correspondant à un événement XML 102.

Le codeur 200 comprend également un module d'indexation 222 des événements codés EXI, alimenté par le module 204 de récupération des types, le module d'encodage des noms 212 et le module d'encodage des valeurs 218. Le module d'indexation 222 génère l'index EXI 106 qui est compressé par un module de compression 224, avant d'être fourni au générateur de flux binaire 220 pour son intégration dans le flux binaire 108. Le processus d'encodage est maintenant décrit en référence à la figure 4. Lorsqu'un document XML 100 est fourni au codeur EXI 200, ce dernier le parcourt selon un mode bien connu (modèle SAX ou pull) qui consiste à extraire un à un les différents items d'information représentés par des événements XML 102. C'est l'analyseur XML 202, ou "parsec", qui se charge de cette extraction lors de l'étape E400. Chaque événement XML 102 extrait à l'étape E400 porte des informations dépendant de sa nature. La première de ces informations est son type récupéré à l'étape E402 par le module de récupération des types 204. Pour les événements "début d'élément" et "fin d'élément" ainsi que pour les attributs, des informations de préfixe d'espace de nommage ainsi qu'un nom local peuvent être présentes et sont alors récupérées, lors de l'étape E404, par le module de récupération des noms 210.

Pour les attributs et les noeuds texte, une information de valeur est présente sous forme d'une chaîne de caractères. Celle-ci est récupérée le cas échéant, lors de l'étape E406, par le module de récupération des valeurs 216.

Pour chaque nouvel événement 102 à coder, le codeur 202 vérifie, à l'étape E408, s'il dispose d'une production spécifique correspondant dans sa grammaire courante 208. Si ce test indique qu'une production spécifique existe déjà, alors celle-ci est utilisée, de façon classique à l'étape E410, pour déterminer le code de priorité à encoder dans le flux binaire 108. Si une telle production n'existe pas déjà, celle-ci est créée et insérée dans la grammaire courante 208 lors de l'étape E412. De plus, au cours de cette même étape, s'il s'agit d'un "début d'élément", une nouvelle grammaire est créée pour représenter cet élément et insérée dans la table des grammaires 208. Dans ce cas, on poursuit à l'étape E414 où le codeur de priorités 206 utilise la production générique de la grammaire courante pour déterminer directement le code binaire représentant l'information de type de l'événement XML courant. Le codeur de priorités 206 se charge de le transmettre ensuite au générateur de bits 220 pour insertion dans le flux EXI 108. Ensuite, à l'étape E416, l'événement EXI courant 110 est marqué comme contributeur à la mise à jour des grammaires. On détaille ci-après un exemple de marquage.

Suite au marquage, on teste, à l'étape E418, si un nom (récupéré à l'étape E404) est associé à l'événement 102. En cas de test positif, ce nom est encodé lors de l'étape E420 et écrit dans le flux binaire 108. Puis, l'événement EXI courant 110 est marqué, à l'étape E422, comme contributeur à la mise à jour des dictionnaires de valeurs 214 si une nouvelle entrée est ajoutée, à cette occasion, aux dictionnaires 214 (cas si le nom n'a pas déjà été encodé). L'étape suivante E424 se produit suite aux étapes E410, E418 (si test négatif) ou E422 et consiste à vérifier si une valeur (récupérée à l'étape E406) est à coder. C'est le cas pour les événements de type AT ou CH. Si c'est le cas, le codeur de valeurs 218 code, à l'étape E426, la valeur récupérée et l'écrit dans le flux binaire 108, puis marque, à l'étape E428, l'événement EXI courant 110 comme contributeur à la mise à jour des dictionnaires de valeurs 214 si une nouvelle entrée est ajoutée, à cette occasion, aux dictionnaires 214 (cas si la valeur n'a pas déjà été encodée). L'événement EXI ainsi produit est ensuite indexé dans l'index 106 à l'étape E430, sauf s'il s'agit d'un événement de type EE. Cette indexation est décrite ci-après en référence à la figure 5. Suite à l'indexation de l'événement EXI courant, on poursuit, à l'étape E432, par la mise à jour de la grammaire courante 208 du codeur 200 afin de préparer le codage de l'événement XML 102 suivant (par exemple changement de grammaire si on vient de traiter un événement "début d'élément"). Si plus aucun événement XML 102 ne reste à lire (test E400 faux), l'index 106 produit tout au long de l'encodage est compressé à l'étape E434. On décrit ci-après cette compression en référence à la figure 6. Enfin, le flux binaire EXI 108 est généré à l'étape E436 avec, notamment, l'index 106 et sa taille en nombre de bits insérés en début de flux binaire EXI 106 dans des parties optionnelles (en-tête) du flux afin de ne pas compromettre le décodage de ce flux binaire EXI 108 par un décodeur ne mettant pas en oeuvre l'invention. On notera que, le fait de placer l'index 106 en début de flux EXI 108 permet un décodage à la volée du document codé. La contrepartie réside dans un encodage qui, lui, ne peut se faire à la volée. Cette configuration est faiblement pénalisante dans la mesure où bon nombre de scénarios consistent à encoder le document XML 100 une seule fois, et à parcourir et décoder le flux binaire correspondant 108 un grand nombre de fois, éventuellement via des requêtes de type XPath ou XQuery. On décrit maintenant le marquage des événements EXI 110 évoqué dans les étapes E416, E422 et E428. Chaque événement XML 102 rencontré par le codeur 200 est encodé en un événement EXI 110 tel que décrit dans la recommandation du même nom. Parmi ces événements, seuls les événements EXI de type SE, AT et CH sont indexés. Les événements EE correspondant à des fins d'élément peuvent être déduits par le décodeur (par exemple, dernier événement avant l'ouverture d'un nouvel événement de même ou moindre profondeur). Chaque événement indexé par le module 222 du codeur EXI 200 est marqué d'un code de 1 à 2 bits qui représente la contribution de cet événement quant à la mise à jour des tables d'encodages, c'est-à-dire des différents dictionnaires 214 et grammaires 208, selon la configuration suivante : - le code binaire "1" signifie que l'événement courant contribue à la mise à jour des grammaires 208 et éventuellement des dictionnaires de chaînes 214. C'est par exemple le cas d'un événement EXI de type SE correspondant à un "début d'élément" pour lequel n'existe encore ni grammaire associée, ni production associée dans la grammaire courante. C'est également le cas pour un événement EXI de type AT ou de type CH pour lequel il n'existe encore aucune production associée dans la grammaire courante ; - le code binaire "01" signifie que l'événement ne contribue qu'à la mise à jour des dictionnaires de chaînes 214. Dans le cas d'un événement EXI de type "début d'élément" SE, cela n'est pas possible car un nouvel élément va engendrer la création d'une grammaire associée ainsi que d'une production correspondante dans la grammaire courante. Dans le cas d'un événement EXI de type attribut AT nommé pref:nom, cela signifie qu'une production AT(pref :nom) existe déjà dans la grammaire courante mais que la valeur de cet attribut n'est pas encore indexée. Idem dans le cas d'un événement EXI CH correspondant à un noeud texte ; - le code binaire "00" signifie que l'événement ne contribue à la mise à jour d'aucun des dictionnaires 214 et grammaires 208. Par exemple, dans le cas d'un événement EXI de type début d'élément SE, cela signifie que son nom (nom local + espace de nommage) a déjà été rencontré et indexé et qu'une grammaire StartTagContent nom décrivant son contenu existe déjà ainsi qu'une production SE(nom) dans la grammaire courante. Dans le cas d'un événement EXI de type attribut AT, ce code 00 signifie que son nom (nom local + espace de nommage) et sa valeur ont déjà été rencontrés et indexés et qu'une production AT(nom) existe déjà dans la grammaire courante. Pour un événement EXI correspondant à un noeud texte CH, cela signifie qu'une production CH existe déjà dans la grammaire courante et que la valeur correspondant à ce noeud texte est déjà indexée dans un dictionnaire de chaînes 214. Au cours des étapes E416, E422 et E428, le marquage peut consister à mettre à jour un indicateur courant avec l'un des codes ci-dessus. L'indexation de l'événement lors de l'étape E430 reprend alors cet indicateur pour insérer l'information correspondante dans l'index 106 comme on le verra par la suite. On décrit maintenant, en référence à la figure 5, l'indexation des événements EXI 100 par ajout dans l'index 106, réalisée notamment lors de l'étape E430. A l'étape E500, l'entité en charge de l'indexation au sein du codeur 200, l'indexeur 222, commence par récupérer la profondeur courante dans le document XML 100. Cette profondeur est maintenue par l'indexeur 222 tout au long du parcours du document XML 100, à l'aide d'un compteur qui est incrémenté ou décrémenté en fonction des événements rencontrés. L'étape suivante consiste, pour l'indexeur 222, à vérifier le type de l'événement EXI courant 110 au moyen des tests E502, E504 et E506, permettant ici de filtrer les événements de type SE, AT et CH.

Si l'événement EXI courant 110 est de type SE ou AT, le test E502 est vrai. L'indexeur 222 incrémente alors la profondeur courante à l'étape E508. Puis pour cette nouvelle profondeur, il sélectionne, à l'étape E510, la liste dans l'index 106 où insérer l'événement EXI courant 110. En effet, pour une profondeur donnée dans la structure hiérarchique correspondante du document XML 100, les événements EXI 110 sont organisés par type tel qu'illustré en figure 1. Sur cette figure, on distingue six listes 1121 à 1126. On sélectionne donc la liste 112; correspondant à la profondeur courante et au type (SE ou AT) de l'événement EXI courant 110 (on la crée si nécessaire).

Une fois cette liste 112; récupérée, l'indexeur 222 récupère, à l'étape E512, l'identifiant permettant de représenter le nom associé à l'événement EXI courant 110. Cette identifiant peut notamment correspondre à la valeur de 32 codage du nom ou à une clé unique associée utilisée dans les dictionnaires 214. A l'étape E514, l'indexeur 222 récupère, depuis le générateur de bits 220, la position posi définissant le début du contenu de l'événement EXI courant 110 dans le flux binaire. On poursuit à l'étape E516 où l'indexeur 222 insère, dans la liste 112; récupérée à l'étape E510, ce nouvel événement EXI 110 avec sa position posi, l'identifiant récupéré en E512 (par exemple l'identifiant booklD pour la liste 1122) et son code de contribution tel que défini précédemment et déterminé lors des étapes de marquage E416, E422 et E428. Enfin, si l'événement EXI courant 110 est de type AT (test E518 vrai), la profondeur courante est décrémentée de "un" à l'étape E520. Sinon, sa valeur reste inchangée et l'indexation de l'événement EXI courant 110 se termine.

Si l'événement EXI courant 110 est de type CH, le test E502 est faux et le test E504 est vrai. L'indexeur 222 incrémente alors la profondeur courante de 1 lors de l'étape E522. Il sélectionne ensuite, à l'étape E524, la liste 112; d'événements EXI de type CH à cette nouvelle profondeur (il la crée si nécessaire).

De façon optionnelle, l'indexeur 222 peut récupérer l'identifiant de la valeur de cet événement EXI 110 lors d'une étape E526 en vue de l'associer à l'événement EXI indexé. Par défaut, cette valeur n'est pas récupérée et seule la position posi dans le flux binaire 108 correspondant au début de cet événement EXI 110 est récupérée à l'étape E528.

On poursuit à l'étape E530 par l'insertion de l'événement EXI courant 110 dans la liste 112;. On insère ici uniquement sa position posi dans la liste (voir liste 1126 de la figure 1 par exemple). Selon une variante, l'indexeur 222 peut associer à cet événement EXI 110 de type CH, l'identifiant récupéré en E526 (ID, posi) et éventuellement son code de contribution (ID, posi, code) déterminé lors des étapes E416, E422 et E428. Cependant la probabilité de contribution des événements EXI 110 de type CH à la mise à jour des dictionnaires de valeurs 214 étant très élevée, celle-ci n'est pas indexée pour ne pas augmenter inutilement la taille de l'index 106. De même la probabilité d'avoir deux valeurs identiques pour deux événements EXI de type CH étant faible, l'identifiant n'est donc pas associé à l'événement EXI indexé pour les mêmes raisons.

Si l'événement EXI courant 110 est de type EE, les tests E502 et E504 sont faux, le test E506 est vrai. On passe directement à l'étape E520 de décrémentation de la profondeur courante. Cette étape d'indexation E430 décrite par la figure 5 est réalisée pour chaque événement EXI 110 de type SE, AT ou CH rencontré lors du parcours du document XML 100 par l'analyseur XML 202 et conduit à la construction de l'index 106. Avant d'être intégré au flux binaire EXI 108 par le générateur de bits 220, cet index 106 est compressé (étape E434) comme illustré ci-après en référence à la figure 6. Comme évoqué précédemment, les techniques de codage binaire visent à fournir une représentation compacte du document XML 100. Le fort taux de compression du codeur EXI 200 est obtenu au détriment de l'accessibilité dans ce flux binaire EXI 108. L'inclusion de l'index 106 dans le flux binaire 108 augmente la taille de ce dernier. Par l'étape de compression de l'index, on cherche ainsi à fournir une représentation compacte de l'index 106 afin de conserver un taux de compression satisfaisant. Cette opération est menée par le module 224 de compression d'index. On remarque, notamment sur l'exemple de la figure 1, que les informations contenues dans l'index 106 sont redondantes et que ces redondances peuvent être exploitées pour représenter l'index de façon plus compacte. L'index 106 est notamment organisé, comme évoqué ci-dessus, en fonction de la profondeur dans la structure du document, puis par type d'événements EXI (entre une et trois listes par niveau de profondeur, correspondant aux types SE, AT et CH). Le compresseur d'index 224 s'appuie sur ces deux niveaux d'organisation pour compresser l'index 106. De nouveau en référence à la figure 6, à l'étape E600, on initialise un paramètre taille index qui va contenir la taille de l'index 106 exprimée en nombre de bits, au fur et à mesure que cet index est construit. La valeur de départ est O. A l'étape E602, on initialise de même, à 0, un paramètre nb profs représentant le nombre de niveaux de profondeurs.

Comme on le verra par la suite, ces deux paramètres sont incrémentés tout au long du parcours de l'index 106 puis insérés au tout début de l'index 106 compressé afin de permettre ultérieurement son décodage. De façon générale, le paramètre taille index est incrémenté, à chaque encodage d'une valeur, du nombre de bits nécessaires à la représentation de la valeur ainsi codée. L'étape suivante E604 consiste, pour le compresseur d'index 224, à vérifier si des données de l'index sont disponibles à la prochaine profondeur nb_profs + 1. Si ce n'est pas le cas (sortie NON), l'index 106 a été entièrement parcouru, et sa taille taille index ainsi que son nombre de niveaux de profondeurs nb profs sont encodés à l'étape E606. Cet encodage correspond notamment à l'encodage d'entier non-signé tel que décrit dans la spécification EXI. A l'étape E608, on insère ces deux valeurs en début de l'index compressé, par le générateur de bits 220, ce qui clôt l'étape 516 de compression de l'index 106. La taille taille index encodée prend en compte, en plus du nombre de bits du contenu à proprement parler de l'index compressé, le nombre de bits nécessaire à la représentation de cette taille taille index elle-même et du nombre de niveaux de profondeur nb profs. Ceci permet au décodeur, utilisé après, de déduire les positions indexées des positions globales dans le flux binaire EXI 108 reçu par simple différence entre ces positions absolues et la taille de l'index. La figure 7 représente la structure de l'index compressé à l'issue de l'étape E608. La taille 650 taille index constitue les premiers bits de l'index compressé, suivie du nombre de profondeurs 652 nb profs, et enfin du contenu 654 de l'index 106 compressé comme décrit ci-après.

Dans le cas où il reste des données pour la profondeur suivante (OUI au test E604), le compresseur d'index 224 récupère, à l'étape E610, les listes 112; d'événements EXI non vides pour cette profondeur. Le compresseur 224 définit alors, à l'étape E612, un motif 656 sur trois bits, chaque bit indiquant respectivement la présence d'événements EXI 110 indexés dans les listes 112; d'événements EXI récupérées en E610. Les trois bits sont associés respectivement aux événements EXI de type SE, AT et CH, un bit mis à "1" indiquant qu'une liste 112; du type associé est non vide. En raison de ces trois bits, on incrémente d'autant la taille de l'index taille_index.

Ensuite à partir de l'étape E614, le compresseur d'index 224 itère sur les listes 112; non vides récupérées à l'étape E610, et commence par encoder, à l'étape E616, le nombre 658 d'événements EXI 110 encodés dans la liste courante. Le codage utilisé est le codage d'un entier non-signé tel que défini par la spécification EXI. Le nombre de bits nécessaire à cet encodage du nombre 658 est ajouté à la taille de l'index taille_index. A l'étape E618, le compresseur 224 récupère les identifiants de nom (par exemple "booklD", sauf dans le cas de la liste correspondant aux événements de type CH lorsqu'elle ne contient pas de tels identifiants) et détermine l'identifiant le plus présent comme identifiant de référence. Dans l'exemple 106 de la figure 1, à la profondeur 2, l'identifiant "booklD" est le plus fréquent. Cet identifiant est ensuite codé comme un entier non-signé 660. La taille de l'index taille_index est incrémentée d'autant de bits. A l'étape E620, la première position dans la liste 112; courante est codée comme un entier non-signé 662. Dans l'exemple ci-dessus, on encode "pos2". Ensuite lors d'une étape E622, chaque événement EXI 110 de la liste 112; courante est codé en un mot binaire 664 comprenant l'identifiant, la position et le marqueur pour les événements EXI de type SE et AT et la position uniquement pour les événements EXI de type CH (éventuellement avec identifiant et/ou marqueur selon le mode de réalisation choisi). Chaque identifiant et chaque position d'un événement EXI 110 sont codés par différence avec les valeurs de référence déterminées aux étapes E618 et E620. On utilise alors un nombre de bits fixe permettant de représenter les différences maximales entre une valeur et sa valeur de référence. Ce nombre de bits est indiqué en 661 pour les identifiants et en 663 pour les positions. Chaque marqueur de contribution est codé également lors de cette étape E622. On incrémente également taille index d'autant de bits utilisés pour coder l'ensemble des événements EXI 110 de la liste 112; courante. Le compresseur d'index 224 passe ensuite à une liste suivante lors de l'étape E614 et itère de nouveau les étapes E616 à E622 pour cette liste. Si plus aucune liste n'est à traiter pour cette profondeur courante (teste E614 faux), le nombre de niveaux de profondeur nb profs est incrémenté de 1 et le compresseur 224 revérifie, à l'étape E604, si des données sont à encoder pour la profondeur suivante. Lorsque ce n'est plus le cas, la compression de l'index se termine. Dans un mode de réalisation particulier, le test de l'étape E604 peut contenir une profondeur maximale au-delà de laquelle on ne souhaite pas indexer afin de contrôler la taille de l'index compressé. Toutefois, dans ce cas, les événements EXI 110 marqués comme contributeurs (marquage "1" ou "01") au-delà de cette profondeur maximum devront être indexés, seuls les non contributeurs (marquage "00") se trouvant au-delà de cette profondeur maximum pourront être écartés de l'indexation. Sur la figure 7, on retrouve la structure de l'index compressé, où le contenu 654 est composé de portions 666 correspondant chacune à un niveau de profondeur (itérations lors de l'étape E604). Chaque portion 666 est composée du motif 656 de trois bits précisant les listes 112; présentes, et de plusieurs sous-parties 668 associées chacune au codage d'une liste 112;. Ainsi chaque sous-partie 668 est composée successivement du nombre 658 d'événements de la liste, de l'identifiant de référence 660, de la position de référence 662 et des mots binaires 664 relatifs au codage de chacun des événements EXI 110 de la liste.

On décrit maintenant le décodage d'une partie du flux binaire 108 généré en fin d'étape E436. Le décodage aboutit à un fragment XML.

Sur la figure 8, on a représenté un décodeur 700 selon l'invention recevant en entrée le flux binaire EXI indexé 108 et fournissant en sortir le fragment XML 114. Le décodeur 700 est symétrique du codeur 200 avec, dans une partie classique, un analyseur de bits 702 fournissant les événements EXI 110 compressés à un décodeur de priorités 706 lui-même couplé à un reconstructeur de type 704 capables, à l'aide des grammaires de décodage 708, de déterminer le type d'événement XML décodé; à un décodeur de noms 712 couplé à un reconstructeur de noms 710 capables à l'aide des dictionnaires de chaînes 714 de rétablir le nom de l'événement XML décodé; et un décodeur de valeurs 718 couplé à un reconstructeur de valeurs qui, ensemble et à l'aide des dictionnaires 714, rétablissent les valeurs des événements XML décodés. Ces différents modules mettent à jour les tables de décodage lors d'un décodage classique.

Toutes ces informations de type, nom et valeur sont fournies au générateur XML 720 qui reconstruit le fragment XML 114. L'analyseur de bits 702 est capable de récupérer des mots de différentes longueurs dans le flux 108 et d'avancer dans celui-ci en ignorant un nombre donné de bits. L'analyseur de bits est alors piloté par les différents modules 706, 712, 718, 724 et 728 en fonction de leurs besoins respectifs comme décrit ci-après. Le décodeur 700 comprend également un décodeur d'index 724 apte à fournir un index 106', a priori identique à l'index 106 encodé, un convertisseur d'index 726 qui, à partir de cet index 106', va générer un index 150 spécifique à un position posi dans le document, et un décodeur rapide 728 qui va accéder au flux 108 uniquement pour les événements de l'index 150 de sorte à reconstituer les grammaires 708 et dictionnaires 714 qui serviront à la reconstruction du fragment XML 114 de façon classique. Les étapes de décodage sont illustrées en référence à la figure 9.

Comme il ressort de ce qui précède, le flux EXI binaire 108 est organisé de telle sorte que l'index construit et compressé se trouve dans les parties optionnelles au début du flux (en-tête).

Après réception du flux binaire 108 par le décodeur à l'étape E800, l'en-tête EXI est décodé à l'étape E802 selon des mécanismes classiques. A l'étape E804, le décodeur 700 détecte si, dans cet en-tête, se trouvent des données correspondant à un index.

En cas de réponse négative, il procède à un décodage classique (E814) des données codées, mettant notamment en oeuvre la construction classique des tables d'encodage au fur et à mesure du décodage. En cas de réponse positive, le décodeur d'index 724 décode l'index EXI compressé à l'étape E806 de sorte à obtenir un index 106' qui, sauf erreur de transmission ou de décodage (normalement), est similaire, en contenu, à l'index 106. Pour cela, le décodeur d'index 724 applique l'algorithme inverse de celui de compression décrit ci-dessus en lien avec la figure 6. Il décode les données de taille 650 et de nombre de profondeurs 652 puis itère sur ces profondeurs (test E604). Pour chaque niveau de profondeur, le motif 656 de trois bits calculé en E612 indique les listes 112; non vides. Pour chaque liste non vide, le décodeur d'index 724 récupère le nombre 658 d'événements codé lors de l'étape E616, les valeurs de référence 660, 662 codées aux étapes E618 et E620, puis itère sur les événements EXI 110 présents dans la liste 112; afin de récupérer leur position et le cas échéant leur identifiant de nom et leur marqueur de contribution (décodage des mots binaires 664). Le résultat ainsi obtenu est l'index global 106'. Grâce à l'invention, le décodeur EXI 700 est maintenant prêt à reconstruire une portion du document XML 100 à partir de n'importe quelle 25 position posi correspondant à un événement EXI indexé. A l'issue de cette étape E806, le décodeur EXI 700 est en mesure d'offrir une prévisualisation (sur un écran d'ordinateur par exemple) de la structure du document XML 100 à l'aide des informations de niveaux de profondeur récupérées, plus éventuellement le nom du premier élément et de 30 son premier fils en commençant, par exemple, le décodage des premiers événements EXI 110 du flux 108. Seuls les noeuds disposant d'événements EXI 110 dans l'index 106' sont affichés.

Les éléments fils non encore décodés sont visualisés par exemple avec un symbole ?? à la place de leur nom. Un clic sur un des noeuds nommés ou inconnus, via l'interface graphique représentant la prévisualisation du document, permet de récupérer un noeud indexé et donc sa position dans le flux 108 EXI indexé et d'indiquer au décodeur 700 une position de démarrage lors de l'étape E808. Une fois la position de début de fragment à décoder, on filtre l'index 106' lors de l'étape E810 pour obtenir un index 150 réduit ou filtré spécifique à cette position de début. Cet index 150 correspond, de préférence, au sous- ensemble minimum d'événements EXI 110 à traiter pour atteindre la position de début avec les différents dictionnaires 714 et grammaires 708 configurés dans l'état adéquat. Pour cela, le convertisseur 726 parcourt l'index global 106' selon les positions croissantes des événements EXI indexés.

En référence à la figure 10, le convertisseur initialise, lors de l'étape E900, sa position cible (position de l'événement EXI indexé à atteindre) avec la valeur récupérée en E808. A l'étape E902, il positionne également l'événement courant sur le dernier événement traité (le premier de la liste 1121 d'événements EXI de type SE à la profondeur 1 lors du démarrage) et conserve, comme profondeur courante, la profondeur de l'événement courant. A l'étape E904, il teste s'il s'agit d'un événement EXI de type SE. Dans l'affirmative, le convertisseur 726 initialise, à l'étape E906, une valeur posMax avec la position du frère (prochain SE dans la liste) de l'événement courant s'il existe, sinon avec le frère de son parent et ce jusqu'à trouver un événement SE ou jusqu'à la fin de l'index. posMax définit ainsi une position maximum au-delà de laquelle tout événement EXI indexé ne pourra être considéré comme fils de l'événement EXI courant. Cette position est utilisée à l'étape E908 afin de trouver le prochain fils de l'événement EXI de type SE courant: le convertisseur 726 parcourt les listes 112; de profondeur +1 par rapport à la profondeur courante, à partir du dernier événement EXI (événement courant) dans chacune de ces listes. Il garde parmi les prétendants AT, SE, CH celui dont la position est la plus faible tout en restant inférieure à posMax. Il peut également limiter son parcours jusqu'à posMax. Dans la négative (test E904 faux), il s'agit d'un événement EXI de type AT ou CH. Le convertisseur 726 récupère alors, lors de l'étape E910 l'événement EXI de type SE parent de l'événement courant dans la liste des événements de type SE à la profondeur précédente. Puis, à l'étape E912, il récupère son frère s'il en existe un, sinon le frère de son parent et ce jusqu'à trouver un événement SE ou jusqu'à la fin de 10 l'index. On obtient ainsi posMax. A l'étape E914, il recherche alors le prochain événement EXI qui peut être de type SE, AT ou CH. Pour un événement EXI de type AT, le prochain événement EXI indexé peut être soit un autre événement EXI de type AT, soit un événement de 15 type EXI de type CH, soit un événement EXI de type SE à la même profondeur ou encore un événement EXI de type SE à la profondeur précédente. L'événement EXI indexé retenu est comme pour l'étape E908 celui ayant la position la plus faible comprise entre la position de l'événement courant et posMax. 20 Pour un événement EXI de type CH, la recherche est moins complexe car on ne peut avoir d'événement EXI de type AT. Le convertisseur 726 se limite donc à la recherche d'un événement de type SE à la même profondeur ou à la profondeur précédente, et garde, s'il existe, celui dont la position est comprise entre la position de l'événement courant et posMax. 25 A l'étape E916, on vérifie si un événement fils a été trouvé lors de l'étape E908 ou si un événement prochain a été trouvé lors de l'étape E914, selon le cas de figure. Dans la négative, le convertisseur 726 choisit, à l'étape E918, comme prochain événement, le prochain frère trouvé respectivement aux 30 étapes E906 et E912. Dans l'affirmative du test E916, le prochain événement devient, à l'étape E920, l'événement trouvé lors des étapes E908 ou E914.

Suite aux étapes E918 et E920, la position du prochain événement est comparée à la position cible à l'étape E922. Si cette position est strictement inférieure à la position cible, alors le prochain événement est inséré dans l'index filtré 150 lors de l'étape E924. Puis ce prochain événement devient l'événement courant à l'étape E902. Le convertisseur 726 répète alors les traitements précédents jusqu'à atteindre la position cible ou la fin de l'index global 106'. On note ici que l'invention est compatible à l'accès au document XML 100 dans son intégralité, la position cible étant fixée au début du document.

Une fois que tous les événements EXI précédant la position cible ont été ainsi traités, une deuxième passe intervient, à l'étape E926, afin de sortir de l'index filtré 150 les événements EXI dont le marqueur de contribution indique qu'ils n'interviennent pas dans la mise à jour (marqueur = "00") des dictionnaires 714 et grammaires 708. Toutefois, les événements EXI 110 de type SE ancêtres de l'événement EXI à reconstruire sont conservés même s'ils ne contribuent pas à ces mises à jour, afin d'assurer le bon empilement des grammaires 708. En effet, la détection d'un événement de type SE amène généralement au chargement d'une nouvelle grammaire. L'index 150 représenté en figure 2 illustre notamment l'application de cet algorithme à l'index 106 de la figure 1, avec une position de départ égale à pos23. Cette seconde passe E926 permet d'éliminer les éléments book et leur contenu, excepté le parent direct de l'élément editor que l'on veut reconstruire (SE(booklD, pos16, 00)). De retour à la figure 9, une fois que l'index 150 basé sur la position cible est obtenu, le décodeur 700 est prêt à démarrer sa phase de décodage rapide, lors de l'étape E812, qui va le configurer (donc construire les tables de décodage type grammaires 708 et dictionnaires 714) en vue de la reconstruction du fragment XML 114 lors de l'étape E814. Ce décodage rapide E812 est notamment illustré par le bas de la 30 figure 10 et est mené par le décodeur rapide 728. Ce dernier parcourt la liste d'événements EXI de l'index 150 et si besoin navigue dans le flux binaire 108 via l'analyseur de bits 702 pour récupérer d'éventuelles informations manquantes. Le but du décodeur rapide est de traiter les événements EXI contributeurs (marquage à "1" ou "01") et de mettre à jour les grammaires 708 et dictionnaires 714 jusqu'à la position de reconstruction souhaitée (position cible) et récupérée lors de l'étape E808.

La lecture des événements EXI indexés selon leur position est effectuée à l'étape E950. Si plus aucun événement n'est disponible, c'est la fin du décodage rapide et on passe à l'étape E814 de reconstruction. Pour tout événement EXI lu depuis l'index 150 lors de l'étape E950 (sortie OUI de cette dernière), le décodeur rapide 728 indique, lors de l'étape E952, à l'analyseur de bits 702 de sauter jusqu'à la position donnée par la position de l'événement EXI courant. A l'étape E954, le décodeur rapide utilise le marqueur de contribution associé à l'événement EXI courant pour se configurer dans le mode le plus 15 adapté à un traitement rapide des événements EXI suivants. Si le marquage rencontré vaut "1", indiquant une contribution de l'événement courant à la mise à jour des différents dictionnaires 714 et grammaires 708, le décodeur rapide se prépare à mettre à jour ces différentes tables de décodage (par l'insertion d'une nouvelle valeur dans le dictionnaire 20 et/ou d'une nouvelle production dans une grammaire, voire de modifier les priorités des productions) et à éventuellement changer de grammaire. Si le marqueur indique une mise à jour des dictionnaires de valeurs uniquement (marquage vaut "01"), le décodeur rapide ne se soucie pas de la mise à jour des grammaires 708, mais uniquement des dictionnaires de valeurs. 25 Enfin, s'il s'agit d'un marquage valant "00", c'est-à-dire indiquant une non-contribution, nul besoin pour le décodeur rapide à mettre à jour les grammaires 708 et dictionnaires de valeurs 714. Dans ce dernier cas, correspondant systématiquement à un événement EXI de type SE, il doit juste considérer, comme grammaire courante, la grammaire associée à cet 30 événement EXI de type SE (c'est-à-dire changer de grammaire). On poursuit à l'étape E956, où le décodeur rapide 728 traite l'événement EXI courant en décodant depuis le flux binaire EXI 108 : - les données relatives à son nom (cas AT ou SE) si celui-ci n'a pas déjà été rencontré ; et - les données relatives à une valeur (cas AT ou CH). Les données ainsi décodées sont ensuite utilisées, lors de l'étape 958, pour mettre à jour les dictionnaires ou grammaires concernés ( pertinents ) par le mode de décodage en cours (issu de l'étape E954). Puis, le décodeur rapide 728 traite le prochain événement EXI indexé dans l'index filtré 150 et ce jusqu'au dernier (test E950 faux). Le décodeur EXI se trouve ensuite prêt à reconstruire le fragment XML 114 voulu (étape E807) par un décodage classique à partir de la position d'accès fournie à l'étape E808. Toutefois, il conserve la profondeur initiale (la profondeur correspondant à l'événement EXI ou XML depuis lequel l'accès est effectué) avant ce décodage classique pour savoir quand il doit s'arrêter. Cette fin de décodage correspond au décodage d'un événement EXI de type EE avec une profondeur inférieure ou égale à la profondeur initiale. En référence à la figure 11, il est maintenant décrit à titre d'exemple une configuration matérielle particulière d'un dispositif de traitement d'information apte à une mise en oeuvre du procédé selon l'invention.

Un dispositif de traitement d'information mettant en oeuvre l'invention est par exemple un micro-ordinateur 1000, une station de travail, un assistant personnel, ou un téléphone mobile connecté à différents périphériques. Selon encore un autre mode de réalisation de l'invention, le dispositif de traitement d'information se présente sous la forme d'un appareil photographique muni d'une interface de communication pour autoriser une connexion à un réseau. Les périphériques reliés au dispositif de traitement d'information comprennent par exemple une caméra numérique, ou un scanner ou tout autre moyen d'acquisition ou de stockage d'images ou de document XML, reliée à une carte d'entrée/sortie (non représentée) et fournissant au dispositif de traitement d'information des données multimédia. Le dispositif 1000 comporte un bus de communication 1005 auquel sont reliés : - une unité centrale de traitement CPU 1010 se présentant par exemple sous la forme d'un microprocesseur ; - une mémoire morte 1015 dans laquelle peuvent être contenus les programmes dont l'exécution permet la mise en oeuvre du procédé selon l'invention ; - une mémoire vive 1020 qui, après la mise sous tension du dispositif 1000, contient le code exécutable des programmes de l'invention ainsi que des registres adaptés à enregistrer des variables et paramètres nécessaires à la mise en oeuvre de l'invention ; - un écran 1025 permettant de visualiser des données et/ou de servir d'interface graphique avec l'utilisateur qui peut ainsi interagir avec les programmes de l'invention, à l'aide d'un clavier 1030 ou de tout autre moyen tel qu'un dispositif de pointage, comme par exemple une souris ou un crayon optique ; - un disque dur 1035 ou une mémoire de stockage, telle qu'une mémoire de type compact flash, pouvant comporter les programmes de l'invention ainsi que des données utilisées ou produites lors de la mise en oeuvre de l'invention ; - un lecteur de cartes 1040, ou un autre lecteur de support de données amovible, adapté à recevoir une carte mémoire 1045 et à y lire / écrire des données traitées ou à traiter conformément à l'invention ; et - une interface de communication 1050 reliée à un réseau de télécommunications, l'interface 1050 étant apte à transmettre et à recevoir des données.

Le bus de communication 1005 autorise une communication et une interopérabilité entre les différents éléments inclus dans le dispositif 1000 ou reliés à celui-ci. La représentation du bus 1005 n'est pas limitative et, notamment, l'unité centrale 1010 est susceptible de communiquer des instructions à tout élément du dispositif 1000 directement ou par l'intermédiaire d'un autre élément du dispositif 1000. Les cartes mémoires 1045 peuvent être remplacées par tout support d'information tel que, par exemple, un disque compact (CD-ROM) réinscriptible ou non, un disque ZIP, une clé USB ou une disquette. D'une manière générale, un moyen de stockage d'information, lisible par un micro-ordinateur ou par un microprocesseur, intégré ou non au dispositif de traitement d'information, éventuellement amovible, est adapté à mémoriser un ou plusieurs programmes dont l'exécution permet la mise en oeuvre du procédé selon l'invention. Le code exécutable permettant au dispositif de traitement d'information la mise en oeuvre de l'invention peut être indifféremment stocké en mémoire morte 1015, sur le disque dur 1035 ou sur un support numérique amovible tel que par exemple une carte mémoire 1045 comme décrite précédemment. Selon une variante, le code exécutable des programmes est reçu par l'intermédiaire du réseau de télécommunications, via l'interface 1050, pour être stocké dans un des moyens de stockage du dispositif 1000 (tel que le disque dur 1035 par exemple) avant d'être exécuté. L'unité centrale 1010 commande et dirige l'exécution des instructions ou portions de code logiciel du ou des programmes de l'invention, les instructions ou portions de code logiciel étant stockées dans l'un des moyens de stockage précités. Lors de la mise sous tension du dispositif 1000, le ou les programmes qui sont stockés dans une mémoire non volatile, par exemple le disque dur 1035 ou la mémoire morte 1015, sont transférés dans la mémoire vive 1020 qui contient alors le code exécutable du ou des programmes de l'invention, ainsi que des registres pour mémoriser les variables et paramètres nécessaires à la mise en oeuvre de l'invention. On notera également que les dispositifs de codage et de décodage mettant en oeuvre l'invention ou incorporant celle-ci sont aussi réalisables sous la forme d'appareils programmés. Par exemple, de tels dispositifs peuvent alors contenir le code du ou des programmes informatiques sous une forme figée dans un circuit intégré à application spécifique (ASIC). Le dispositif décrit ici et, particulièrement, l'unité centrale 1010, sont susceptibles de mettre en oeuvre tout ou partie des traitements décrits en lien avec les figures 1 à 10, pour mettre en oeuvre chaque procédé objet de la présente invention et constituer chaque dispositif objet de la présente invention.

Les exemples qui précèdent ne sont que des modes de réalisation de l'invention qui ne s'y limite pas. En particulier, les codes de marquage sur 1 ou 2 bits définis ci-dessus sont bien adaptés au traitement de documents XML 100 plutôt irréguliers. En effet, on considère que les événements 102 vont le plus fréquemment définir de nouvelles grammaires et/ou prédictions (du fait de l'irrégularité). Dans le cas de documents XML 100 possédant une structure régulière avec beaucoup de répétitions, il conviendrait plutôt de définir des codes de marquage courts en cas de non-contribution à des mises à jour: par exemple les codes 11 (au lieu de 1), 10 (au lieu de 01) et 0 (au lieu de 00) afin de favoriser les événements ne modifiant ni les grammaires 208 ni les dictionnaires de valeurs 214. Bien que, dans les exemples ci-dessus, la position des événements EXI 110 dans l'index 106 est calculée par pas d'événement (c'est-à-dire on incrémente la position de 1 pour chaque nouvel événement), on peut envisager de renseigner cette position en indiquant, par exemple lors de l'étape E514, le nombre de bits déjà écrit par le générateur de bits 220. Dans cette configuration, le décodeur 700 n'aura plus besoin de délimiter chaque événement EXI 110 dans le flux binaire 108, mais uniquement compter les bits dans la charge utile du flux. Egalement, cette position posi indexée lors de l'étape E430 peut correspondre à la position du code de priorité de l'événement EXI indexé plutôt qu'au premier bit correspondant à son contenu. Ce mode permet la vérification de la synchronisation des grammaires 208 du décodeur 700 avec la position dans le flux binaire 108. Par ailleurs, le décodage de l'index 106 et son filtrage (étape E810 et figure 10) peuvent être combinés en une seule étape pour plus d'efficacité. Ceci permet d'éviter le décodage d'événements EXI indexés avec une position supérieure ou égale à la position de début de reconstruction.

Dans un mode de réalisation, le décodage classique E814 permettant la reconstruction du fragment XML 114 peut s'effectuer à partir de l'index filtré 150 basé sur la position de fin de fragment à reconstruire, c'est-à- dire si l'index a été construit en considérant comme position cible, lors de l'étape E900, non plus la position correspondant au début du fragment à reconstruire mais à la position correspondant à l'événement EXI suivant le dernier événement correspondant au fragment XML à reconstruire, et sous réserve d'assigner aux événements correspondant au fragment un marquage spécifique indiquant un mode reconstruction au décodeur rapide.

Claims (11)

1. REVENDICATIONS1. Procédé de codage d'un document structuré (100) en un flux binaire (108), comprenant le codage (E410, E414, E420, E426) d'événements hiérarchisés (102) composant le document structuré (100) en des événements correspondants (110) codés à l'aide d'au moins une table d'encodage (208, 214), ladite au moins une table d'encodage (208, 214) étant mise à jour lors du codage (E410, E414, E450, E426) de certains événements hiérarchisés, le procédé étant caractérisé en ce qu'il comprend les étapes suivantes : - la détermination des événements hiérarchisés (102) impliqués dans la mise à jour de l'au moins une table d'encodage (208, 214) ; - l'association (E416, E422, E428) d'une information de marquage (106) aux événements codés (110) correspondant auxdits événements hiérarchisés (102) déterminés.
2. 2. Procédé selon la revendication 1, comprenant les étapes suivantes : - la construction (E430) d'une table d'indexation (106) desdits événements codés (110), ladite table d'indexation (106) comprenant, pour une pluralité d'événements codés, une information représentative de la position (posi) dudit événement codé dans le flux binaire (108) et une information représentative de l'implication ou non, à une mise à jour de l'au moins une table d'encodage (208, 214), de l'événement hiérarchisé correspondant (102), et - l'ajout (E436) de ladite table d'indexation (106) audit flux binaire (108).
3. 3. Procédé selon la revendication précédente, dans lequel ladite pluralité d'événements codés comprend une pluralité d'événements hiérarchisés (102) relatifs à la structure dudit document (100), et ladite table d'indexation (106) comprend en outre, pour des événements codés relatifs à du contenu dudit document, uniquement une information représentative de leur position dans le flux binaire.
4. 4. Procédé selon la revendication 2 ou 3, dans lequel ladite table d'indexation (106) comprend en outre, pour la pluralité d'événements codés, une donnée d'identification du nom de l'événement hiérarchisé correspondant.
5. 5. Procédé selon l'une des revendications 2 à 4, dans lequel ladite table d'indexation (106) renseigne, pour chaque événement codé (110) de ladite pluralité, le type d'événement (AT, SE, CH) correspondant et la profondeur (Profi) dudit événement correspondant dans la structure hiérarchique dudit document (100).
6. 6. Procédé selon l'une des revendications 2 à 5, dans lequel ladite au moins une table d'encodage comprend une table d'encodage d'événements de structure (208) et une table d'encodage de chaînes de caractères (214), et ladite information représentative de l'implication prend une valeur différente pour représenter l'implication d'une mise à jour d'au moins une table d'encodage incluant ladite table d'encodage d'événements de structure (208) et pour représenter l'implication d'une mise à jour d'uniquement une table d'encodage de chaînes de caractères (214).
7. 7. Procédé selon l'une des revendications 2 à 6, comprenant une étape de compression (E434) de ladite table d'indexation (106) avant son ajout (E436) audit flux binaire (108).
8. 8. Procédé selon la revendication précédente et la revendication 5, dans lequel, lors de ladite compression (E434), on groupe les entrées de la table d'indexation (106) selon le type d'événement (AT, CH, SE) correspondant et la profondeur (Profi) dudit événement correspondant (102) dans la structure hiérarchique dudit document (100), et on code chaque groupe (112;) indépendamment.
9. 9. Procédé selon l'une des revendications 7 et 8, dans lequel on code : - les entrées de la table d'indexation (106) dont la profondeur de l'événement correspondant dans la structure hiérarchique du document (100) est inférieur à une profondeur seuil, et - les entrées de la table d'indexation (106) de profondeur supérieure ou égale à la profondeur seuil et dont l'information représentative del'implication correspond à une mise à jour de l'au moins une table d'encodage (208, 214).
10. 10. Procédé selon l'une des revendications 2 à 9, dans lequel ladite table d'indexation (106) éventuellement compressée est insérée dans l'entête dudit flux binaire (108).
11. 11. Procédé de décodage d'une portion d'un flux binaire (108) comprenant des événements codés (110) codant un document structuré (100), le procédé comprenant les étapes suivantes : - la détermination, dans ledit flux binaire (108), d'événements codés (110) associés à une information de marquage (106') ; - la construction (E812) d'au moins une table de décodage (708, 714) en décodant uniquement, dans ledit flux binaire (108), des événements codés déterminés ; et - le décodage (E814) de ladite portion à l'aide de l'au moins une table de décodage construite (708, 714). 15. Procédé selon la revendication précédente, dans lequel ladite détermination comprend le décodage (E806) d'une table d'indexation (106') comprise dans ledit flux binaire (108), ladite table d'indexation (106') comprenant, pour une pluralité d'événements codés (110), une information représentative de la position (posi) dudit événement codé (110) dans le flux binaire (108) et ladite information de marquage dudit événement codé. 16. Procédé selon la revendication 12, dans lequel on filtre (E810) ladite table d'indexation (106') de sorte à ne conserver, pour l'étape de construction (E812), que les événements codés (110) dont la position correspondante précède celle du premier événement de la portion de flux binaire à accéder. 17. Procédé selon la revendication 12, dans lequel on filtre (E810) ladite table d'indexation (106') de sorte à ne conserver, pour l'étape de construction (E812), que les événements codés (110) dont la position correspondante précède celle du dernier événement de la portion de flux binaire à accéder.15. Procédé selon la revendication 13 ou 14, dans lequel les événements codés (110) de ladite table d'indexation (106') sont associés à une information de profondeur (Profi) représentative de la profondeur de l'événement dans la structure du document structuré (100), et dans lequel on filtre (E926), en outre, ladite table d'indexation (106') de sorte à ne conserver que : - les événements codés dont l'information de marquage est au moins d'un premier type, et - les événements codés qui sont ancêtres, dans ladite structure, 10 dudit premier événement à accéder dont l'information de marquage est d'un second type. 16. Procédé selon l'une des revendications 12 à 15, dans lequel ladite construction (E812) comprend la mise à jour (E958) d'une pluralité de tables de décodage (708, 714) par l'ajout de données de décodage associées 15 aux événements décodés, et dans lequel, préalablement au décodage (E956) d'un événement codé filtré, on détermine (E954), à partir du type de l'information de marquage, au moins une table de décodage (708, 714) à mettre à jour. 17. Procédé selon l'une des revendications 11 à 13, dans lequel les 20 événements codés (110) de ladite table d'indexation (106') sont associés à une information de profondeur hiérarchique, et le procédé comprenant la construction et l'affichage (E808) d'une structure hiérarchique à partir desdites informations de profondeur de sorte qu'un utilisateur peut désigner, dans ladite structure affichée, ladite portion du 25 flux binaire à décoder. 18. Dispositif de codage (200) d'un document structuré (100) en un flux binaire (108), comprenant le codage d'événements hiérarchisés (102) composant le document structuré en des événements correspondants (110) codés à l'aide d'au moins une table d'encodage (208, 214), ladite au moins une 30 table d'encodage étant mise à jour lors du codage (E414, E450, E426) de certains événements hiérarchisés, le dispositif étant caractérisé en ce qu'il comprend :- des moyens pour déterminer des événements hiérarchisés (102) impliqués dans la mise à jour de l'au moins une table d'encodage (208, 214); - des moyens pour associer (222) une information de marquage (106) aux événements codés (110) correspondant auxdits événements hiérarchisés (102) déterminés. 19. Dispositif de décodage (700) d'une portion d'un flux binaire (108) comprenant des événements codés (110) codant un document structuré (100), le dispositif comprenant : - des moyens (724) pour déterminer, dans ledit flux binaire (108), 10 des événements codés associés à une information de marquage; - des moyens (728) pour construire au moins une table de décodage (708, 714) en décodant uniquement, dans ledit flux binaire (108), des événements codés déterminés; et - des moyens de décodage (704, 706, 710, 712, 716, 718) de ladite 15 portion à l'aide de l'au moins une table de décodage construite (708, 714). 20. Structure de données binaires comprenant des codes binaires correspondant à des événements hiérarchisés (102) d'un document structuré (100) codés à l'aide d'au moins une table d'encodage (208, 214), caractérisé en ce qu'elle comprend, associée à chaque événement d'une pluralité des 20 événements codés (110), une information de marquage (106) représentative de l'implication de l'événement hiérarchisé (102) correspondant dans une mise à jour de l'au moins une table d'encodage lors du codage de cet événement. 21. Structure de données binaires selon la revendication précédente, comprenant une première partie formée de codes binaires 25 correspondant aux événements codés (110) et une deuxième partie comprenant une table d'indexation (106) desdits événements codés (110), ladite table d'indexation (106) comprenant, pour les événements de ladite pluralité d'événements codés (110), une information représentative de la position (posi) de l'événement codé dans ladite structure de données et ladite 30 information de marquage. 22. Support d'enregistrement comprenant une structure de données selon l'une des revendications 20 et 21.23. Moyen de stockage d'informations, éventuellement totalement ou partiellement amovible, lisible par un système informatique, comprenant des instructions pour un programme informatique adapté à mettre en oeuvre le procédé conforme à l'une quelconque des revendications 1 à 19 lorsque le programme est chargé et exécuté par le système informatique. 24. Produit programme d'ordinateur lisible par un microprocesseur, comprenant des portions de code logiciel adaptées à mettre en oeuvre le procédé selon l'une quelconque des revendications 1 à 19, lorsqu'il est chargé et exécuté par le microprocesseur.