FR2954983A1

FR2954983A1 - Procede et dispositif de codage d'un document structure memorise sous forme d'arbre dom

Info

Publication number: FR2954983A1
Application number: FR1050039A
Authority: FR
Inventors: Youenn Fablet; Franck Denoual; Herve Ruellan
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 2010-01-05
Filing date: 2010-01-05
Publication date: 2011-07-08
Anticipated expiration: 2030-01-05
Also published as: FR2954983B1

Abstract

La présente invention concerne un procédé et un dispositif correspondant de codage d'un document structuré en éléments, par exemple de type XML, ainsi qu'une structure de données arborescente pour un tel codage. Selon le procédé, on forme (E110, E120, E210, E255), dans une mémoire (53, 54, 58) d'un codeur (50), une arborescence (20, 30), type arbre DOM, représentative de la structure et des éléments d'au moins une partie du document, et on parcourt ladite arborescence pour coder (E160, E220, E270) au moins un dit élément en une valeur de codage binaire. Selon l'invention, ladite arborescence (20, 30) comprend des informations d'indexation (22, 34, e:ct, e:a, e:sd, e:ed) associées aux éléments et la valeur de codage binaire dudit élément est déterminée en fonction des informations d'indexation associées à l'élément dans l'arborescence.

Description

La présente invention concerne un procédé et un dispositif correspondant de codage d'un document structuré. Elle s'applique en particulier aux documents structurés de type XML (acronyme de "eXtensible Markup Language" pour langage de balisage extensible) pour un codage conformément à un format de codage binaire type EXI ("Efficient XML Interchange") ou Fast Infoset. L'invention concerne également une structure de données arborescente pour un tel codage. 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 ou des données textuelles, le document composant ainsi une structure hiérarchique d'éléments. 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">). De façon connue en soi, la syntaxe XML permet aussi de définir des commentaires, des instructions de traitement et des sections d'échappement.

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, une section d'échappement, etc.

Plusieurs langages différents basés sur le langage XML peuvent contenir des éléments 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. On dit alors que ces deux éléments ont le même nom qualifié ("qualified narre").

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, de façon connue en soi, par la définition d'un préfixe qui est un raccourci vers l'URI de cet espace de nommage. De façon générale, un nom qualifié regroupe ainsi le nom local de l'événement (par exemple "balise") et éventuellement une URI (et son possible préfixe associé). Il s'agit d'un nom identifiant de façon unique un type d'événement XML structurel.

Le langage 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. Le langage 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 voire un espace mémoire de stockage important. Pour remédier à ces inconvénients, des méthodes de compression et d'encodage d'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.

C'est notamment le cas des formats binaires tels que EXI (format utilisé comme base pour la standardisation d'un format XML binaire par le groupe de travail EXI du W3C - "World Wide Web Consortium", organisation produisant des standards pour le Web) ou Fast Infoset spécifié par la norme ITU-T Rec. X.891 1 ISO/IEC 24824-1. Ces formats ont pour caractéristique de prendre en compte un nombre important d'informations structurelles du document afin de compresser davantage les données. Par exemple, 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 "indexes de codage", 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é.

Ces valeurs sont généralement exprimées sur un octet (8 bits) et manipulées ainsi par l'encodeur. Toutefois, chaque niveau peut être codé sur le nombre de bits minimum pour pouvoir coder la plus grande valeur de ce niveau associée à une production de la grammaire. Aussi, pour un niveau prenant des valeurs de 0 à 6, on utilise trois bits de codage. Dans ce cas, le codage peut être réalisé en connaissant l'index de codage et le nombre de productions (ou de priorités) dans la grammaire. Ces deux informations constituent une information d'indexation pour l'événement correspondant. 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, connu de l'homme de l'art comme étant un "nom qualifié"), un ensemble de grammaires est utilisé pour coder les événements XML de ce type.

Un ensemble de dictionnaires de chaînes ou de valeurs est également utilisé pour encoder, à l'aide d'indexes également, les noms d'événements ou attributs, et autres contenus du document XML. Ces dictionnaires évoluent également par l'incorporation de nouvelles chaînes/valeurs rencontrées dans le document et codées.

Les règles de grammaire 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.

La norme EXI introduit, à cet effet, un mode dit "EXI Schéma" qui se base sur des fichiers de description structurelle de documents, connus sous la dénomination de Schémas XML. Ces derniers décrivent des modèles de données représentatifs de structures, et, à ce titre, il est possible de construire des grammaires représentant ce modèle.

Dans le mode EXI Schéma, on utilise un tel schéma afin de créer des grammaires avant codage, puis on utilise ces grammaires pour coder ou décoder un document. Le mode EXI Schéma permet d'obtenir une meilleure compression que lorsque les grammaires sont apprises depuis le document. En effet, considérons l'exemple simplifié suivant de données structurées, dans lequel un élément <element> comprend trois éléments successifs <enfant1>, <enfant2> et <enfant3> dans cet ordre : <element> <enfant1/> <enfant2/> <enfant3/> </element>. Selon la spécification EXI, si aucun schéma n'est utilisé, les éléments <enfant1>, <enfant2> et <enfant3> figurent dans la même grammaire, celle qui décrit le contenu de l'élément <element>.

En revanche, avec un schéma XML, il devient possible de savoir que les éléments <enfant1>, <enfant2> et <enfant3> se produisent toujours dans le même ordre. Cette information permet de créer davantage de grammaires pour ces éléments, chaque grammaire contenant une seule production: une grammaire pour le passage de <element> vers <enfant1>, une autre pour le passage de <enfant1> vers <enfant2>, etc. En réduisant le nombre de productions par grammaire, on réduit le nombre de bits nécessaires pour coder les priorités, et dans l'exemple ici, puisqu'une seule production demeure par grammaire, il n'y a même plus lieu de coder la production associée (qui est toujours prédictible).

La création des grammaires à partir d'un schéma XML est décrite dans la spécification EXI. Comme il arrive que les documents instanciant un Schéma XML ne respectent pas parfaitement le modèle défini, il est possible de choisir un sous-mode autorisant les déviations par rapport au schéma. Dans ce cas, on insère des productions supplémentaires dans les grammaires afin de pouvoir encoder les parties qui ne respectent pas strictement le schéma. De cette manière, on profite de la connaissance du schéma sans pour autant nécessiter des documents parfaitement conformes. Néanmoins, du fait des productions supplémentaires, la compression est moins importante que dans le cas où l'on n'autorise pas les déviations.

Lors du décodage, le processus inverse à celui décrit précédemment est utilisé : la valeur de codage est extraite du flux binaire, 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 de création et d'évolution des grammaires et des dictionnaires de chaînes sont utilisées, éventuellement à partir de Schémas XML, permettant d'avoir à tout moment un ensemble de règles de grammaires et de dictionnaires identique à celui qui était utilisé lors du codage. Pour lire un document XML en vue de son codage ou lors de son décodage, il existe deux méthodes assez répandues: SAX (ou StAX; pour "Simple API for XML" et "Streaming API for XML") et DOM (pour "Document Object Modef').

Les interfaces de programmation (API) type SAX ou StAX réalisent une lecture du document XML événement après événement pour effectuer les traitements sur ces événements lus. Les événements restent donc dans le document XML initial, ce qui permet de limiter l'espace mémoire occupé par les événements en cours de traitement, en fonction des besoins.

En revanche, le format DOM est un ensemble de spécifications du W3C décrivant un modèle de représentation de données XML sous la forme d'un arbre. L'arbre est généralement formé de noeuds auxquels correspondent des éléments du document, la hiérarchie des noeuds étant conforme à la hiérarchie des éléments au sein du document XML. Cette hiérarchie définit la notion de noeud/élément parent ù noeud/élément enfant, qui reste classique pour l'homme de l'art. Chaque noeud possède par ailleurs un ensemble de propriétés permettant de mémoriser par exemple les attributs relatifs à l'élément XML correspondant ou d'offrir des fonctionnalités propres à la spécification DOM via des bibliothèques de fonctions. Ainsi, plusieurs événements XML peuvent être regroupés en un même noeud DOM (par exemple l'événement début d'élément et les événements relatifs à tous les attributs de cet élément). Un exemple de structuration des noeuds est largement documenté dans la recommandation DOM.

Contrairement au modèle de traitement par flux (StAX ou SAX) où les données sont présentées évènement par évènement, les données XML du document sont, dans l'interface DOM, intégralement mises en mémoire dans l'arbre DOM. Les interfaces API de type DOM permettent ainsi d'accéder rapidement à n'importe quelle donnée XML du document. Conformément à la recommandation DOM, la représentation sous forme d'arbre DOM offre de nombreuses fonctionnalités de parcours ou de manipulation des noeuds de l'arbre, comme par exemple: - chaque élément peut accéder directement à l'ensemble de ses enfants directs et à l'ensemble de ses attributs; - une fonction dédiée à l'accès à l'ensemble des éléments ayant le même nom qualifié; - une fonction, connue sous la dénomination d"'événement mutation", notifiant les modifications d'un arbre DOM. On récupère ainsi aisément de telles modifications de noeuds de l'arbre. Ces événements mutation permettent d'appeler des fonctions lors d'une modification de l'arbre DOM, notamment : o l'insertion ou la suppression d'un élément, d'un attribut ou d'un noeud texte; o la modification de la valeur d'un attribut ou d'un noeud texte. Il s'avère que les technologies XML binaires sont indépendantes de l'API utilisée (SAX, StAX ou DOM), ce qui permet de les utiliser dans tous les cas.

Cependant, les encodeurs et décodeurs sont généralement mis en oeuvre pour des interfaces API de type flux, c'est-à-dire type SAX ou StAX par exemple. Une raison en est que, étant donné qu'il est aisé de construire un arbre DOM à partir d'une suite d'événements (lus par SAX) et inversement et que la lecture type SAX requiert une complexité moindre et un espace mémoire réduit, il est préférable de mettre en oeuvre l'interface SAX. Ainsi, le codage d'un document XML mémorisé sous forme d'arbre DOM consiste traditionnellement par le parcours de l'arbre DOM et le codage de chaque noeud ainsi parcouru. En d'autres termes, le codage se passe comme suit: - sélection d'un noeud DOM par une fonction dédiée; - récupération du premier événement correspondant à ce noeud DOM; - appel de l'interface API par flux (SAX ou StAX par exemple) pour encoder cet événement. Comme expliqué précédemment, cet encodage consiste à récupérer les informations d'indexation dans les tables de codage (grammaires et dictionnaires de valeurs) pour obtenir le code binaire correspondant; - itération sur l'ensemble des événements du noeud DOM; - itération sur l'ensemble des noeuds de l'arbre DOM, en passant notamment au noeud suivant DOM. L'avantage principal de l'utilisation d'API de type flux est de permettre la modification de l'encodeur/décodeur par flux sans modifier la couche d'implémentation DOM. Toutefois, ces technologies ne sont pas optimisées pour le modèle DOM. On observe, en effet, des temps d'encodage de documents XML qui sont relativement longs dès que le document structuré est mémorisé sous forme d'arbre. La présente invention vise ainsi à pallier cet inconvénient de l'état de la technique, pour notamment améliorer les performances lors de l'encodage, en flux binaire, d'un document XML mémorisé sous forme d'une structure arborescente type arbre DOM.

Dans ce dessein, l'invention concerne notamment un procédé de codage d'un document structuré comprenant des éléments, le procédé comprenant les étapes consistant à: - former, dans une mémoire d'un codeur, une arborescence représentative de la structure et des éléments d'au moins une partie du document, et - parcourir ladite arborescence pour coder au moins un dit élément en une valeur de codage binaire, caractérisé en ce que ladite arborescence comprend des informations d'indexation associées aux éléments et la valeur de codage binaire dudit élément est déterminée en fonction des informations d'indexation associées à l'élément dans l'arborescence. Ainsi, grâce à la présente invention, les informations d'indexation permettant d'obtenir les codes binaires de codage sont directement récupérées dans l'arborescence lors du parcours de celle-ci. Cela permet d'éviter de laborieuses recherches et récupérations dans les grammaires et dictionnaires, comme réalisées dans les méthodes connues. En effet, pour des documents standards (documents avec une proportion structure/contenu textuel moyenne), les codeurs EXI actuels passent environ la moitié du temps d'encodage à rechercher et récupérer les informations d'indexation de la structure du document dans les grammaires, l'autre moitié du temps étant passée à encoder les valeurs en codes binaires. La présente invention réduit ainsi le temps d'encodage des documents XML de presque la moitié, en permettant une récupération plus rapide des informations d'indexation. On voit ici qu'une partie de l'étape traditionnelle de codage (la recherche des informations d'indexation notamment) a été effectuée préalablement à cette étape de codage.

Dans un mode de réalisation de l'invention, ladite arborescence comprend des noeuds correspondants, chacun, à un élément dudit document structuré, et lesdites informations d'indexation d'un élément sont mémorisées au niveau du noeud correspondant. Cette disposition permet une récupération immédiate des informations d'indexation pour le codage, lors du parcours du noeud à encoder. Elle permet d'améliorer encore la vitesse d'encodage des documents XML mémorisés sous forme d'arbre DOM. En particulier, lesdites informations d'indexation d'un élément sont mémorisées à un emplacement prédéfini parmi les champs (également appelés attributs ou propriétés) définissant ledit noeud correspondant. Il peut notamment s'agir du dernier attribut des propriétés du noeud. On évite ainsi la recherche parmi l'ensemble des champs définissant le noeud. On accélère ainsi la récupération des informations d'indexation et donc l'encodage. Dans un mode de réalisation de l'invention, le procédé comprend, lors d'une modification d'un élément du document, une étape de mise à jour des informations d'indexation. De la sorte, on effectue une partie des tâches de l'encodage (la recherche notamment dans les grammaires) durant la phase d'édition/modification du document, simplifiant l'étape d'encodage effectif.

On observera d'ailleurs que l'identification des noeuds modifiés est aisée grâce aux événements mutation DOM décrits précédemment. L'invention s'applique donc de façon particulièrement efficace à l'édition de documents structurés suivie de leur encodage.

En particulier, la mise à jour des informations d'indexation est réalisée au niveau d'un noeud correspondant, dans l'arborescence, à l'élément modifié. Dans un mode de réalisation de l'invention, les informations d'indexation insérées dans l'arborescence sont déterminées à partir d'un fichier de description structurelle de documents, par exemple à partir d'un Schéma XML. Le mode EXI schéma permet des gains en termes de compression et permet aussi de déterminer facilement, au préalable ou à tout moment, les informations d'indexation de structure de la plupart des noeuds de l'arbre DOM. On notera que l'arborescence peut, elle-même, être formée sur la base de ce schéma XML. En variante, les informations d'indexation insérées dans l'arborescence sont récupérées d'un flux binaire encodant une version antérieure dudit document structuré, par exemple avant modification entraînant le codage selon l'invention. C'est notamment le cas lors d'un processus de réception-édition-transmission d'un document XML compressé. La réception conduit au décodage du document compressé au cours duquel on récupère les informations d'indexation et on les mémorise dans l'arbre DOM. Une modification (édition) du document est alors opérée avant qu'un codage de la version modifiée soit effectué selon l'invention pour permettre la transmission.

Selon une caractéristique de l'invention, l'étape de formation comprend la construction successive de noeuds composant ladite arborescence, chaque noeud correspondant à un élément dudit document, et les informations d'indexation d'un élément sont insérées, dans le noeud correspondant, au moment de la construction de ce noeud. On réalise ainsi une indexation de l'arbre DOM pendant sa construction. En variante, l'étape de formation comprend une étape préalable de construction d'une arborescence, et une étape postérieure d'indexation de ladite arborescence par ajout desdites informations d'indexation. On peut mettre en oeuvre cette disposition dans le cas où l'on ne contrôle pas la construction de l'arborescence (par exemple dans le cas d'un navigateur Internet actuel). L'arborescence est débord chargée en mémoire.

En particulier, ladite étape d'indexation est réalisée séquentiellement par nom qualifié, une occurrence d'indexation consistant à ajouter, à l'arborescence, les informations d'indexation pour l'ensemble des éléments ayant le même nom qualifié. Cette disposition permet une indexation de l'arbre DOM plus rapide grâce notamment aux fonctions DOM dédiées à l'accès simultané à l'ensemble des éléments ayant le même nom qualifié. Selon une caractéristique particulière, le procédé comprend, préalablement à l'étape d'indexation, une étape d'ordonnancement des noms qualifiés ayant une occurrence dans le document, en fonction d'au moins un paramètre, typiquement une fréquence d'occurrence ou un nombre d'occurrences, et ladite étape d'indexation est réalisée séquentiellement dans l'ordre des noms qualifiés. Ainsi, on favorise une indexation la plus complète possible de l'arbre DOM dans le cas où le temps alloué à cette indexation est limité. En effet, en se concentrant sur les noms qualifiés les plus fréquents, on indexe un plus grand nombre de noeuds de l'arbre en un temps fixe. Dans un mode de réalisation de l'invention, le procédé comprend, préalablement à l'étape de codage d'un élément du document, une étape de validation des informations d'indexation dudit élément, et les informations d'indexation non valides sont supprimées de ladite arborescence. Cette disposition permet, notamment lorsqu'une modification du document XML est opérée au niveau de l'arbre DOM, de ne conserver que les informations d'indexation qui seront finalement utilisées pour coder le document XML. On évite ainsi, lors de l'encodage, de récupérer des indexes de codage faux et donc de produire un flux binaire erroné. Notamment cette validation est effectuée après chaque modification. Selon une caractéristique particulière, l'étape de codage d'un élément du document comprend une étape de recherche d'une information d'indexation à partir d'une table de codage si l'arborescence ne contient aucune information d'indexation correspondant audit élément à coder, généralement au niveau du noeud de cet élément. Les tables de codage sont typiquement les grammaires EXI décrites précédemment. Il s'agit ici, en l'absence d'information d'indexation dans l'arbre DOM, de procéder à un codage effectif d'un événement XML en ayant recours aux techniques classiques. En particulier, la validation des informations d'indexation d'un élément et le codage de l'élément est réalisée séquentiellement pour chaque élément de la partie du document à encoder. Cette disposition permet de ne parcourir qu'une seule fois l'arborescence car validation et codage sont réalisés lors du même passage sur un noeud de l'arborescence. Dans un mode de réalisation, toutes les informations d'indexation d'un élément ne sont pas encodées lors du codage dudit élément. Dans un mode de réalisation, ladite arborescence comprend, associée aux informations d'indexation, une information de typage de donnée. Cela permet, notamment pour les événements XML de type attribut ou texte, de simplifier l'étape de codage effectif. L'invention concerne également une structure de données arborescente comprenant une pluralité de noeuds correspondants, chacun, à un élément d'un document structuré, caractérisé en ce que lesdits noeuds comprennent au moins une information représentative dudit élément, généralement au moins le nom de l'élément ou sa valeur, et au moins une information d'indexation conforme à un format de codage. Cette structure de données correspond notamment à un arbre DOM 25 mettant en oeuvre la présente invention, par l'insertion des informations d'indexation. En particulier, l'au moins une information d'indexation d'un noeud comprend une valeur de priorité correspondant à une production d'une grammaire et un nombre représentatif du nombre de priorités au sein de ladite 30 grammaire. Ces éléments permettent de calculer les valeurs binaires de codage pour former le flux binaire, et sont ainsi utilisées lors de l'étape de codage effectif selon l'invention.

Selon une caractéristique particulière, l'au moins une information d'indexation comprend, en outre, une information de typage. Comme cette information de typage est utilisée lors du codage, cette disposition permet, lors de l'étape de codage effectif, d'obtenir l'information plus rapidement. Il s'agit généralement du typage des attributs ou des noeuds texte d'un élément XML: par exemple booléen, entier, etc. Selon une caractéristique, le noeud correspondant à un élément comprend une pluralité d'informations d'indexation correspondant à une pluralité respective d'événements composant ledit élément. En effet, la structure DOM regroupe, au sein d'un même noeud, plusieurs événements d'un même élément, par exemple l'événement 'début d'élément' et les événements 'attributs' définissant cet élément. En particulier, lesdites informations d'indexation sont identifiées selon la nature dudit événement correspondant. Cela permet un accès plus rapide aux informations d'indexation lors du codage successif des événements. Corrélativement, l'invention concerne également un dispositif de codage d'un document structuré comprenant des éléments, le dispositif comprenant: - une mémoire de stockage apte à mémoriser des structures de données 20 arborescentes, - un moyen de formation pour former, dans ladite mémoire, une arborescence représentative de la structure et des éléments d'au moins une partie du document, et - un moyen de parcours de l'arborescence et de codage pour coder au moins 25 un dit élément en une valeur de codage binaire, caractérisé en ce que ladite arborescence comprend des informations d'indexation associées aux éléments et le dispositif est configuré pour que la valeur de codage binaire dudit au moins en élément soit déterminée en fonction des informations d'indexation associées à l'élément dans 30 l'arborescence. Le dispositif de codage présente des caractéristiques et avantages analogues au procédé de codage selon l'invention.

De façon optionnelle, le dispositif peut comprendre des moyens se rapportant aux caractéristiques du procédé de codage exposé précédemment. Selon une caractéristique, le dispositif de codage comprend, en mémoire, une structure de données comme décrite 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 codage 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 codage 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 réduit le temps d'encodage des documents XML mémorisés sous forme d'arbre DOM, permettant ainsi de transmettre plus rapidement ces documents compressés à des destinataires tels qu'un serveur, par exemple en vue d'un stockage. 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 SVG sous forme de représentation XML (gauche) et de représentation graphique (droite); - la figure 2 illustre un exemple de représentation XML du document de la figure 1, comprenant des informations d'indexation et de structure conformément aux enseignements de la présente invention; - la figure 3 représente, schématiquement, une autre représentation XML du document de la figure 1, sous forme d'arbre; - la figure 4 représente, sous forme d'ordinogramme, des étapes générales de codage selon la présente invention; - la figure 5 représente, sous forme d'ordinogramme, des étapes d'un mode de réalisation particulier de la présente invention; - la figure 5 bis représente un exemple de fichier de grammaires transmis entre un serveur et un client dans le mode de réalisation de la figure 5; - la figure 6 représente, sous forme d'ordinogramme, des étapes d'un autre mode de réalisation particulier de la présente invention; - la figure 7 représente, sous forme d'ordinogramme, des étapes pour la mise à jour des informations d'indexation et de structure, dans le cas d'une modification d'attribut XML; - la figure 8 représente, sous forme d'ordinogramme, des étapes pour la mise à jour des informations d'indexation et de structure, dans le cas d'une modification d'élément XML; - la figure 9 représente, sous forme d'ordinogramme, des étapes de l'encodage mis en oeuvre dans la présente invention; - la figure 10 représente, sous forme d'ordinogramme, des étapes de décodage d'un document XML codé lors d'une indexation simultanée de la représentation XML du document décodé; - la figure 11 représente, sous forme d'ordinogramme, des étapes d'indexation d'une représentation XML déjà existante, type arbre DOM; - la figure 12 représente, sous forme d'ordinogramme, des étapes pour la mise à jour d'informations d'indexation et de structure dites dynamiques, selon l'invention; et - la figure 13 montre une configuration matérielle particulière d'un dispositif apte à une mise en oeuvre du procédé selon l'invention. La présente invention repose sur la mémorisation, au sein d'une arborescence représentant un document structuré, d'informations d'indexation permettant de coder des événements, par exemple dans un format binaire tel que l'EXI ou Fast Infoset. Ce format binaire peut être prédéfini par exemple au travers de la source d'informations d'indexation utilisées pour remplir l'arborescence, par exemple un Schéma XML, des grammaires (EXI) ou encore des dictionnaires d'indexation (Fast Infoset).

Pour les besoins d'illustration, on utilisera une arborescence de type arbre DOM bien connue de l'homme de l'art, et sur laquelle des modifications peuvent être apportées comme il ressortira de la suite. A titre illustratif, on s'intéresse au cas d'une application web client- serveur mettant en oeuvre les étapes suivantes : - le client est un navigateur web, également nommé navigateur Internet par la suite; - le client récupère un document XML stocké sur le serveur sous forme binaire; - le client édite le document en lui apportant des modifications; - le client transmet, au serveur, le document modifié et recompressé en binaire. Dans ce cas, le client étant un navigateur web, le document est typiquement stocké et modifié sous la forme d'un arbre DOM, notamment pour profiter des nombreuses API DOM proposées pour interagir avec le document. Ces API sont notamment décrites dans les spécifications W3C HTML et SVG selon le cas d'usage. Pour optimiser le stockage du document coté serveur et/ou la transmission des données entre le client et le serveur, le serveur utilise une technologie XML binaire telle qu'EXI. Dans ce cadre, la transmission serveur vers client utilise le format XML binaire. De même, le serveur peut souhaiter récupérer les données au format XML binaire pour minimiser la bande passante et ne pas avoir besoin de ré-encoder les données émises par le client dans le format voulu par le serveur.

Dans cet exemple, l'invention permet d'améliorer les performances du processus réception-édition-transmission du côté du client. Ce cas est particulièrement intéressant lorsque le serveur souhaite utiliser des options d'encodage particulières (typiquement un ou plusieurs schémas XML et/ou des encodages de valeurs particuliers).

Durant la phase de réception du document, on crée un arbre DOM à partir d'un Schéma XML et on initialise l'ensemble des informations d'indexation de structure de l'arbre DOM, notamment à partir du même Schéma XML. Ces informations sont ajoutées aux noeuds de l'arbre DOM sous la forme d'attributs DOM de ces noeuds. Cette phase d'initialisation des informations d'indexation de l'arbre DOM peut être effectuée par l'application construisant l'arbre DOM ou par l'application qui transmet le document XML.

Durant la phase d'édition du document, chaque modification est récupérée via par exemple l'événement mutation de DOM. On met alors à jour les informations d'indexation du ou des noeuds modifiés. Puis durant la phase d'encodage, le codeur va, pour chaque élément du document XML, récupérer les informations d'indexation, les enlever de l'arbre DOM et les utiliser pour encoder rapidement le contenu de cet élément (attributs, noeuds texte, enfants éléments). Pour accélérer l'encodage, on peut prévoir d'ajouter, aux informations d'indexation, des informations de typage pour certains noeuds, type attribut et texte. On appelle "informations de structure" l'ensemble constitué des informations d'indexation et l'information de typage. En connaissant le typage d'une valeur, l'encodeur n'a pas besoin d'accéder, à chaque codage, ni même de connaître le schéma XML précisant ces typages (et utilisé par le serveur). Outre le gain en temps d'encodage résultant de l'accès direct aux informations d'indexation dans l'arbre DOM, la mise en oeuvre de l'invention dans le cadre d'une application web client/serveur permet, au serveur, de décider exactement du schéma qu'il souhaite avant de le communiquer éventuellement au client. Le schéma choisi peut notamment être un sous-ensemble d'un schéma "standard".

C'est particulièrement judicieux pour des serveurs embarqués dans des appareils légers (mobiles ou imprimantes par exemple) qui peuvent avoir des difficultés à embarquer un schéma complet et préfèrent n'embarquer qu'une sous-partie du schéma. Dans ce cas, la sous-partie du schéma effectivement utilisée est déterminée dynamiquement au niveau du client à l'aide d'une information communiquée par le serveur. L'invention peut s'appliquer à tout format XML, notamment les formats de documents, type Office ou PDF-like. Un autre exemple est le cas de documents ATOM stockés sur un disque dur. Ces documents sont chargés sous la forme d'arbre DOM pour être mis à jour (ajout ou suppression de noeuds XML typiquement). On peut appliquer le même principe pour permettre un temps de décodage-modification-encodage minimal.

On illustre maintenant l'invention à l'aide d'un exemple de document SVG, dont une représentation est fournie par la figure 1. Sur cette figure, la partie de gauche montre le document structuré SVG 10 qui correspond à la représentation graphique de la partie droite (via une visionneuse SVG). On note que les caractères de "Hello World!" ont des couleurs différentes, fonction de l'attribut "file' précisé au niveau d'éléments 12 du document 10. Dans ce cadre, la mise en oeuvre de l'invention peut s'inscrire dans le scénario suivant : - un utilisateur ouvre une application web sur un navigateur Internet; - l'utilisateur sélectionne une image SVG qui est alors ouverte dans l'application web (récupérée depuis un serveur web); - lors de cette ouverture, la représentation XML de l'image est indexée selon un format binaire souhaité au final (format binaire, typiquement EXI, récupéré via une page HTML contenant un script Javascript et envoyée à l'application web, par exemple au travers d'options de codage). Cette indexation consiste à déterminer les informations d'indexation (valeurs de codage/priorités et nombre de priorités dans les tables de codage, par exemple). Puis, le résultat de l'indexation est inséré dans une représentation hiérarchique en mémoire (arbre DOM) du document SVG; - l'utilisateur édite alors cette image pour obtenir une image SVG telle que souhaité, par exemple en opérant un changement de couleur, un ajout/déplacement d'éléments graphiques, etc.; - les informations d'indexation, dépendantes du format binaire choisi, sont alors mises à jour pour les éléments de l'arbre DOM correspondants aux éléments graphiques modifiés par l'utilisateur; - l'utilisateur décide de sauvegarder son résultat sur son appareil photo ou de l'imprimer, auquel cas la représentation en mémoire (arbre DOM) est encodée au format binaire de manière efficace en utilisant les informations d'indexation stockées dans la représentation en mémoire. Le format binaire souhaité peut notamment être déterminé en fonction de l'équipement (par exemple un appareil photo) qui recevra l'image modifiée compressée. Dans ce cas, le flux binaire ainsi produit correspond parfaitement aux besoins de cet équipement. Comme indiqué précédemment, l'arborescence utilisée pour stocker le document XML en mémoire peut être un arbre DOM. Toutefois, d'autres représentations peuvent être utilisées. La figure 2 montre une arborescence 20 plus facile à représenter, sous la forme du même document XML incorporant une sérialisation possible des informations d'indexation au sein même du document. Dans cet exemple, le document comprend de nouvelles informations d'indexation 22 sous la forme d'attributs (e:sd, e:ed, e:ct et e:a) d'un éventuel 15 noeud DOM. Ces informations contiennent les informations d'indexation des différents noeuds de l'arbre DOM permettant l'indexation (pour le codage) des éléments SVG 12 correspondants. Ainsi, l'attribut «e:sd» contient l'information d'indexation de structure 20 (index de production et nombre de productions/de priorités) de l'événement `début de document'. L'attribut «e:a» contient l'ensemble des informations de structure des attributs XML de l'élément XML auquel il est rattaché (l'index de production, le nombre de productions et le type de la valeur). Dans l'exemple de la figure, les 25 informations "9 67 0" entourées sont les informations de structure relatives au troisième attribut XML, ici "version". L'attribut «e:ct» contient les informations de structure des enfants du noeud auquel il est rattaché (index de production et nombre de productions/priorités pour l'ensemble des noeuds éléments qui sont représentés 30 dans le flux sous la forme d'événement `début de balise' ; index de production, nombre de productions/priorités et type de la valeur pour les noeuds textes).

L'attribut «e:sd» contient les informations de structure de l'événement "début de document", et l'attribut «e:ct» celles de l'événement "fin de document". On va maintenant décrire, en référence à la figure 4, les étapes d'un algorithme général selon l'invention mettant en oeuvre une modification d'un document XML. Pour la suite de la description et comme introduit précédemment, on définit tout d'abord les informations de structure et les informations d'indexation (également nommées informations d'indexation de structure). Ces informations comprennent un certain nombre d'indications particulières à l'élément XML ou à l'événement XML auxquelles elles sont rattachées, aux fins de permettre le codage de cet élément/événement selon un format binaire défini. Typiquement, l'information de structure d'un attribut ou d'un noeud texte du document XML correspond à l'information d'indexation de structure et le type de la valeur. L'information de structure d'un élément correspond à l'information d'indexation de structure de cet élément, typiquement les index utilisés pour encoder le début et la fin de l'élément. Dans le cadre d'EXI, l'information d'indexation correspond à l'index de la production associée et au nombre total de productions ou de priorités (dans la grammaire à laquelle appartient la production à coder). Ces informations permettent d'encoder les événements XML sur le plus petit nombre de bits possibles. Comme il ressortira de la description qui suit, l'invention prévoit d'ajouter ou de mettre à jour une information de structure ou une information d'indexation de structure d'un noeud dans l'arborescence représentant le document XML accédé. Il s'agit typiquement d'insérer cette information sous la forme d'un attribut au niveau du noeud considéré dans la représentation en arbre des données XML. Cette insertion peut être similaire à l'exemple de la figure 2. Par exemple, sur cette figure, l'attribut « e:a » correspond aux informations de structure des attributs de l'élément courant. L'attribut « e:ct » correspond aux informations de structure des noeuds enfant de l'élément courant. Pour supprimer ces informations, il suffit de retirer ces attributs des noeuds.

Pour permettre une mise en oeuvre plus efficace, on peut mettre ces différents attributs à une position précise parmi les attributs du noeud, par exemple à la fin des attributs. On peut ainsi très rapidement récupérer ces attributs. La figure 3 montre un exemple simplifié d'arbre DOM 30 dans lequel on a fait apparaître à chaque noeud 32 correspondant à un élément XML, les informations de structure et d'indexation 34 à la fin des attributs de ces noeuds. Comme il ressortira également de la description qui suit, l'invention fait une distinction entre les informations d'indexation statiques et celles non statiques.

Cette notion correspond au fait de savoir si l'édition d'une autre partie de l'arbre peut changer les informations d'indexation 34 d'un attribut DOM donné d'un noeud 32. Une information d'indexation est dite statique si cette information reste valide quelque soit les modifications d'une partie antérieure des données XML (antérieure au sens du parcours de l'arbre par un chemin profondeur d'abord), excepté les modifications d'un noeud enfant du même parent. Ce cas se présente typiquement lorsque les informations d'indexation résultent d'une grammaire prédéfinie par un schéma XML ou d'une partie antérieure du document qui n'est jamais modifiée. L'homme du métier, de part ses connaissances, est à même d'identifier ces informations statiques. Dans ce cas, l'ajout ou la suppression d'informations dans un autre élément que l'élément parent du noeud concerné n'aura pas d'impact sur ces informations d'indexation. L'information d'indexation est dite non statique (donc dynamique) dans les autres cas. On peut prévoir que chaque information d'indexation est pourvue d'une indication renseignant son caractère statique ou non statique, au sens défini ci-dessus. Dans la suite de la description, lorsque l'on cherche à savoir si une information d'indexation est statique ou non, il suffit de se référer à cette indication. Comme représenté sur la figure 4, un traitement général selon l'invention débute, à l'étape E100, par la récupération des données XML à encoder. Une fois les données récupérées, on met ces données en mémoire, typiquement sous la forme d'un arbre (DOM par exemple) à l'étape E110. La construction d'un arbre DOM est classique pour l'homme du métier.

On indexe ensuite, à l'étape E120, les informations de structure et d'indexation pour chaque événement XML composant les éléments XML. On stocke alors le résultat de cette indexation dans la représentation mémoire des données. Il s'agit par exemple de créer un nouvel attribut DOM au niveau des noeuds correspondants, comme montré sur les figures 2 et 3.

On peut noter que cette étape d'indexation peut aussi être effectuée durant l'étape E110 de mise en mémoire des données. L'utilisateur peut alors procéder à des modifications du document XML qui s'affiche à lui, ces modifications ayant pour effet de modifier les données (l'arbre DOM) en mémoire.

Pour chaque modification ou ensemble de modifications (test de l'étape E130), la modification (ou l'ensemble de modifications) est effectuée à l'étape E140 par l'utilisateur, et les informations de structure/indexation sont mises à jour à l'étape El 50. Cette mise à jour correspond typiquement à indexer les informations de structure des données modifiées. Durant cette étape, l'indexation ne s'applique pas sur l'ensemble des données en mémoire mais uniquement des données nécessitant une nouvelle indexation, en tenant notamment compte de la notion d'informations statiques/non statiques et en utilisant par exemple l'événement mutation DOM. Cette mise à jour sera explicitée ci-après en lien avec les figures 7, 8 et 12. Lorsque l'ensemble des modifications est effectué (réponse non à l'étape E130), l'encodage proprement dit des données est effectué à l'étape E160. Cet encodage, détaillé par la suite en référence à la figure 9, s'effectue de manière générale comme suit, pour chaque événement XML, : - on récupère les informations de structure 34 (comprenant les informations d'indexation) correspondant à l'événement courant (le noeud 32 courant dans le parcours de l'arbre DOM 30) et ces informations sont alors enlevées des données à encoder (les noeuds de l'arbre); - on encode la structure de l'événement XML selon ces informations d'indexation; - puis, on encode les valeurs de l'événement (s'il y en a) suivant le type obtenu dans les informations de structure 34. On présente maintenant deux cas particuliers de cet algorithme général, en référence aux figures 5 et 6. Le cas de la figure 5 s'applique à une communication client léger/serveur pour laquelle il est souhaité séparer la phase d'indexation de la structure arborescente 30 (par le serveur par exemple sur la base d'un Schéma XML) de la phase d'encodage (réalisée par le client, par exemple une plateforme de type navigateur Internet). Les indexes de codage étant fonction du Schéma XML choisi par le serveur web, la phase d'indexation varie en fonction des besoins du serveur, notamment du schéma employé. Il est alors particulièrement bénéfique d'effectuer cette indexation en utilisant un langage de type Javascript afin que le serveur puisse facilement communiquer les paramètres de la phase d'indexation. En revanche, la phase d'encodage par les clients est similaire pour l'ensemble des serveurs, car elle se base sur les informations d'indexation contenues dans l'arborescence. Cette phase peut alors être mise en oeuvre au travers d'un langage de programmation plus efficace, par exemple un langage compilé. L'algorithme débute par la demande, par le client, d'un document ou 30 de données XML (étape E200). Le serveur web identifie les données recherchées dans une mémoire de stockage et les convertit dans un format décodable par le client (par exemple en XML textuel) à l'étape E205. Il peut par exemple s'agir d'un décodage depuis un format binaire EXI vers le format classique XML. Le serveur envoie ensuite au client les données XML à l'étape E210. Ces données XML peuvent optionnellement être augmentées des données d'indexation. Notamment, le serveur peut envoyer les informations d'encodage de structure qu'il souhaite que le client utilise. Il peut s'agir typiquement d'un fichier XML ou JavaScript représentant les informations de grammaire à utiliser durant l'encodage des données. La figure 5bis illustre un exemple d'un tel fichier XML 40 transmis avec les données XML. Dans cet exemple, le serveur informe le client d'utiliser deux grammaires "desc" et "text" ayant chacune des attributs et contenus (qui correspondent à des productions). Le client reçoit ainsi les données XML qu'il mémorise au travers d'un arbre DOM 30, grâce à une API de type DOM équipant le navigateur web, et reçoit également les informations de grammaire à partir desquelles il peut compléter l'arbre DOM avec des informations de structure et d'indexation 34 selon les enseignements de l'invention. Ces étapes sont transparentes pour l'utilisateur du client. A l'aide de l'affichage sur son navigateur, l'utilisateur peut modifier les données XML à volonté à l'étape E215.

Durant cette étape, les données d'indexation de structure sont mises à jour, comme cela sera décrit dans la suite en référence aux figures 7, 8 et 12. Typiquement, dans le cas d'un client léger de type navigateur, l'API DOM permet de poser des fonctions de rappel sur les événements mutation DOM. Ces fonctions de rappel sont appelées à chaque modification de l'arbre DOM et permettent de synchroniser les informations d'indexation dans l'arbre DOM avec les modifications. Ces fonctions de rappel sont typiquement réalisées en JavaScript et sont transmises par le serveur au client. De ce fait, l'encodage est spécialisé selon les besoins du serveur, typiquement selon les informations de grammaire transmises par le serveur. Ces mises à jour étant faites durant l'édition des données, elles sont peu perceptibles par l'utilisateur.

Une fois l'ensemble des modifications apportées, le client va alors encoder (étape E220) les données suivant les informations d'indexation de structure présentes dans l'arbre DOM 30 à ce moment. Cette étape, décrite par la suite en référence à la figure 9, est effectuée de manière linéaire, par parcours de l'arbre de noeud en noeud. On note ici qu'un avantage de ce mode de réalisation de l'invention est d'effectuer l'ensemble des tâches d'encodage nécessitant les informations du schéma de codage souhaité par le serveur durant la phase d'édition des données, afin d'obtenir les informations d'indexation et de les mémoriser dans l'arbre DOM. Durant l'étape E220, l'encodage utilise uniquement les données de l'arbre DOM. Cela peut notamment permettre à cette partie de l'encodage d'être effectuée par le navigateur de manière native (ou via un plug-in, c'est-à-dire de façon similaire pour n'importe quel client) et ainsi de profiter de la vitesse d'exécution des langages de programmation tels que C, C++ ou Java. Une fois cette étape E220 terminée, le client transmet les données compressées au serveur à l'étape E225 et le serveur traite ensuite les données compressées (stockage, impression...) à l'étape E230. Le cas de la figure 6 s'applique lorsque le décodage et l'encodage sont contrôlés par la même application locale, auquel cas il n'est pas forcément nécessaire d'indexer l'ensemble des informations de structure, l'encodeur pouvant indexer selon le schéma de codage souhaité localement. Dans ce cas, on peut par exemple effectuer l'indexation avant le début des modifications. Puis, durant l'encodage proprement dit, la phase de mise à jour des informations de structure peut alors se limiter à enlever les informations d'indexation obsolètes. Comparativement au cas de la figure 5, l'étape de mise à jour est moins lourde, donc les traitements plus rapides. Cependant, il en résulte un arbre DOM dépourvu de certaines informations d'indexation, qui doivent, du coup, être re-déterminées de façon classique lors de l'encodage effectif des données. On obtient toutefois un encodage plus rapide que dans les solutions connues de l'état de l'art.

En détail, l'algorithme débute par la récupération des données à l'étape E250. Par exemple, il s'agit d'un flux EXI codant un document XML, ce flux étant stocké en mémoire locale. A l'étape E255, les données récupérées sont décodées et mises sous la forme d'un arbre DOM en mémoire vive. Durant le décodage, les données d'indexation sont ajoutées à l'arbre, soit depuis un schéma XML, soit grâce aux grammaires utilisées lors du décodage. Cette indexation s'avère peu coûteuse. En effet, le décodage du flux EXI nécessite la récupération, par exemple dans les grammaires, des informations d'indexation et de typage pour pouvoir décoder les indexes binaires. La mémorisation de ces informations au niveau des noeuds 32 de l'arbre DOM 30 en mémoire est donc immédiate pour les besoins de l'invention sans surcoût important. L'application modifie ensuite la représentation mémoire à l'étape E260, par édition par exemple des données XML par un utilisateur. A l'étape E265, l'application valide les informations d'indexation de l'arbre DOM, c'est-à-dire vérifie si les informations dans l'arbre DOM correspondent effectivement aux valeurs d'indexation qui seront utilisées lors du codage compte tenu des modifications apportées (ces modifications décalant par exemple les valeurs de priorité ou modifiant le nombre de priorités par grammaire). On note que les informations d'indexation statiques restent généralement valides, alors que les informations d'indexation non statiques sont susceptibles de changer si des modifications sont opérées dans les données XML en amont de la première occurrence de ces informations d'indexation non statiques. Lors de cette étape E265, si les informations ne sont pas valides, elles sont enlevées de l'arbre DOM. Il en résulte un nombre moindre d'informations d'indexation dans l'arbre DOM. En pratique, l'étape 265 nécessite, durant la phase d'édition, le stockage des éléments modifiés. Pour chaque élément modifié, on détermine si les informations d'indexation sont statiques ou dynamiques. Si ces informations sont statiques, on peut alors enlever l'ensemble des informations d'indexation de l'élément. Si ces informations sont dynamiques, on va alors enlever l'ensemble des informations d'indexation de l'élément et des éléments du même nom situés postérieurement à cet élément dans le document (informations non valides).

L'étape E270 consiste ensuite à encoder les données XML représentées par l'arbre DOM, selon les informations d'indexation. Pour le codage d'une donnée XML, lorsque les informations d'indexation sont présentes dans le noeud correspondant, l'encodage est réalisé simplement par la récupération de celles-ci et la génération des codes binaires correspondants. Si ces informations d'indexation ne sont pas présentes, par exemple dans le cas d'un élément ajouté ou d'informations qui ont été invalidées à l'étape E265, elles sont recalculées par l'encodeur selon les techniques classiques.

On peut noter que les étapes E265 et E270 peuvent être effectuées séquentiellement pour chaque noeud 32, ce qui permet de parcourir la représentation mémoire des données une seule fois. Dans ce mode de mise en oeuvre, un avantage réside dans le fait que l'application locale n'a pas à être modifiée pour bénéficier de l'avantage de l'invention (encodage plus rapide) car seule la couche d'encodage/décodage peut être modifiée. Toutefois, les éditions de données XML prises en charge par ce mode de réalisation sont limitées comparativement au cas de la figure 5. Le cas de la figure 6 prend typiquement en charge les éditions du type uniquement ajout ou uniquement suppression d'un ou plusieurs noeuds d'un même élément, résultant en un nombre d'enfants qui varie. Il s'agit toutefois d'un cas assez courant (uniquement des ajouts, ou uniquement des suppressions). La détection de ces modifications s'effectue par exemple en surveillant la variation du nombre d'attributs et/ou d'enfants, ce nombre n'étant alors plus équivalent aux nombres d'informations d'indexation dans le noeud correspondant à l'élément analysé et modifié.

D'autres méthodes de détection permettent d'accroître le nombre de cas supportés. On décrit maintenant la mise à jour des informations d'indexation par exemple lors de l'étape E150 ou E215, en référence aux figures 7 et 8.

La figure 7 concerne la mise à jour d'informations d'indexation résultant d'une modification d'attribut XML, alors que la figure 8 concerne la mise à jour d'informations d'indexation résultant d'une modification d'élément XML. L'homme du métier n'aura aucune difficulté à adapter ces étapes pour la mise à jour d'autres types d'événement XML.

Sur la figure 7, l'information de mise à jour, ici l'attribut XML modifié, est supposée connue en entrée de l'algorithme, typiquement via le mécanisme des événements mutation EXI. L'algorithme débute par récupérer la modification d'attribut XML effectuée sur l'arbre DOM à l'étape E300.

On teste ensuite à l'étape E305 si l'information de structure correspondant à cet attribut XML est statique ou pas. Si les informations de structure ne sont pas statiques, elles seront déterminées durant l'encodage proprement dit des données, et on supprime alors toute information de structure de l'attribut (étape E310) présente dans l'arbre DOM. L'algorithme se termine (étape 315). Si l'information de structure concernant l'attribut XML est dite statique, on peut alors déterminer cette information et la mettre à jour, comme suit. On teste tout d'abord si la modification résulte d'une insertion (test E320), auquel cas on récupère la position de l'attribut XML à l'étape E325, puis on calcule l'information de structure de l'attribut XML à l'étape E330. Pour réaliser ce calcul, on récupère la grammaire associée à l'encodage de cet attribut XML de laquelle on déduit la valeur de priorité, le nombre de priorités et éventuellement le typage de l'attribut.

On ajoute alors cette nouvelle information de structure à l'arbre DOM 30 au niveau du noeud correspondant à l'attribut XML modifié (ici ajouté), à l'étape E335.

On met ensuite à jour, à l'étape E355, l'information de structure de l'événement suivant cet attribut XML ajouté. En effet, l'insertion de l'attribut XML dans les données XML peut modifier l'encodage de l'événement suivant puisque l'état de la grammaire est potentiellement différent.

On récupère alors cet événement et on détermine son information d'indexation de structure de manière similaire à l'étape E330. On met alors à jour cette information dans l'arbre DOM 30. L'algorithme se termine ensuite à l'étape E315. Dans le cas où la modification résulte d'une suppression d'attribut XML (sortie "non" de l'étape E320 puis sortie « oui » du test E340), on récupère l'ancienne position de l'attribut XML supprimé (étape E345) pour éliminer les informations de structure de cet attribut XML dans l'arbre DOM (étape E350). On récupère également l'événement suivant l'attribut XML supprimé pour mettre à jour les informations d'indexation de structure de cet événement (étape E355). A noter que, dans le cas d'une simple mise à jour de la valeur d'un attribut (pas d'insertion, ni de suppression), l'algorithme se termine directement. A noter qu'une substitution d'attribut XML correspond à une suppression puis à une insertion d'attribut.

Sur la figure 8, l'information de mise à jour, ici l'élément XML modifié, est supposée connue en entrée de l'algorithme, typiquement via le mécanisme des événements mutation EXI. Le procédé de mise à jour débute par la récupération de la modification de l'élément à l'étape E400.

On peut alors déterminer si l'information de structure correspondant à cette modification est statique ou pas à l'étape E405 de manière similaire à l'étape E305. Dans le cas où cette information est dynamique, on supprime l'information de structure correspondant à l'élément si existante à l'étape E410 et l'algorithme se termine à l'étape E470.

Si l'information d'indexation de structure est dite statique, on détermine le type de modification (insertion ou suppression) via les tests E420 et E455. S'il s'agit de l'insertion d'un élément (un noeud DOM correspondant ayant alors été créé dans l'arbre 30), on indexe, à l'étape E425, le contenu de l'élément, c'est-à-dire que l'on détermine les informations d'indexation correspondant à cet élément. On indexe notamment les attributs éventuels (par exemple suivant la figure 8) et le contenu éventuel de cet élément. On récupère ensuite, à l'étape E430, la position de l'élément nouvellement inséré par rapport aux autres éléments ayant le même élément parent, ce qui permet de calculer, à l'étape E435, les informations de structure correspondant à l'insertion de l'élément dans le document. On ajoute cette information de structure dans l'arbre DOM, lors de l'étape E440. Une mise en oeuvre particulière de l'invention consiste par exemple à ajouter ces informations de structure au niveau du noeud DOM correspondant à l'élément parent de l'élément inséré (voir l'attribut "e:ct" par exemple qui comprend les informations de structure des éléments fils dans l'ordre de ces éléments fils, sur la figure 2). Suite à cette insertion, on met à jour les informations de structure/d'indexation du noeud suivant l'élément inséré, lors de l'étape E445, ces informations de structure ayant pu être modifiées. Suivant le type de la grammaire utilisée pour encoder l'élément parent, il peut s'avérer nécessaire de mettre à jour l'ensemble des informations d'indexation « e:ct » du noeud parent (étape E450). Ces informations correspondent aux noeuds fils du parent de l'élément inséré, qui sont situés après cet élément inséré (c'est-à-dire aux noeuds frères suivants). S'il s'agit d'une suppression d'un noeud ("oui" au test de l'étape E455), on récupère l'ancienne position de l'élément supprimé à l'étape E460, ce qui permet de supprimer l'information de structure de cet élément de l'attribut "e:ct" mémorisé au niveau du noeud parent, lors de l'étape E465. Cette suppression consiste à localiser cette information de structure, dans l'attribut "e:ct", à partir de la position de l'élément, puis à supprimer cette information. Dans le cas où cette information est contenue dans la valeur de l'attribut "e:ct", on enlève de cette valeur l'index de la production et le nombre de productions relative à l'élément supprimé. On met alors à jour les informations de structures du ou des noeuds suivants (étapes E445 et E450) avant que le traitement prenne fin (étape E470). On décrit maintenant, en référence à la figure 9, l'étape d'encodage des événements XML en utilisant, conformément à l'enseignement de l'invention, les informations de structure et d'indexation mémorisées dans l'arbre DOM. La présente invention permet notamment d'accélérer cette étape car ces informations permettant de générer les codes binaires du flux compressé peuvent être directement récupérées de l'arbre DOM sans effectuer de recherche dans les grammaires ou dictionnaires d'indexation. Ce codage correspond notamment aux étapes E160, E220 et E270.

L'algorithme débute, à l'étape E500, par la récupération d'un noeud DOM 32 à encoder. Pour le codage d'un document XML, on récupérera successivement tous les noeuds de l'arbre DOM en parcourant ce dernier dans le sens hiérarchique similaire à la structure du document XML. On récupère les informations d'indexation de structure du noeud à l'étape E505 ce qui permet d'encoder l'événement balise ouvrante de l'élément à l'étape E510. Cette récupération est faite dans l'arbre DOM lorsque ces informations sont disponibles, sinon via des mécanismes classiques si aucune information n'est disponible dans l'arbre (cas où aucune mise à jour n'est effectuée û voir figure 6 par exemple).

Si l'élément possède des attributs (test de l'étape E515), on effectue les étapes E520 à E535 pour chaque attribut. On récupère tout d'abord, à l'étape E520, l'information d'indexation de structure de l'attribut. Cette récupération est effectuée en récupérant les données stockées dans l'arbre DOM (via par exemple l'attribut "e:a" du noeud courant, celui de l'élément en train d'être codé). Si cette information n'est pas stockée dans l'arbre, l'encodeur doit alors la calculer lui-même.

Cette information est alors encodée lors de l'étape E525. On récupère ensuite l'information de type de l'attribut (étape E530 via l'attribut "e:a" ou directement calculée par l'encodeur). Il reste ensuite à encoder la valeur de l'attribut à l'étape E535 suivant le type d'encodage ainsi récupéré. Lorsque tous les attributs sont encodés, on procède à l'encodage des noeuds enfants de l'élément, s'il en a (test de l'étape E535). Pour chaque noeud enfant, on effectue les étapes E545 à E560. On détermine, tout d'abord, s'il s'agit d'un enfant de type "élément" ou d'un noeud "texte/commentaire". S'il s'agit d'un enfant "élément", on passe à l'étape E560 qui consiste à itérer le présent algorithme (en partant de l'étape E500) sur l'élément enfant et son contenu. S'il s'agit d'un noeud "texte", on récupère l'information d'indexation dans l'arbre DOM, et on encode cette information à l'étape E550 pour obtenir un code binaire. Puis, on récupère l'information de typage du noeud texte de la même façon, et on encode la valeur du noeud texte selon ce type, lors de l'étape E555, générant ainsi un code binaire correspondant à cette valeur. Le noeud "texte" est ainsi encodé.

Une fois l'ensemble des enfants de l'élément encodé, on encode la balise fermante de l'élément à l'étape E565. L'information d'indexation de la balise fermante peut notamment être stockée au niveau du noeud DOM correspondant à l'élément, puisque cette balise lui est étroitement liée. On peut noter que, dans de nombreux cas, l'algorithme d'encodage n'a pas besoin de connaître le schéma utilisé pour encoder le document XML, car l'ensemble des données nécessaires se retrouve dans l'arbre DOM On peut ainsi éviter de charger les informations du schéma au niveau de l'encodeur, ce qui correspond à un gain de temps et de mémoire. Par ailleurs, une stratégie de chargement en partie d'un schéma à la 30 demande peut être mise en oeuvre dans le cas où certaines parties du schéma sont effectivement nécessaires.

Comme déjà évoqué en lien avec la figure 5, l'algorithme d'encodage peut être mis en oeuvre dans un langage différent du langage de programmation utilisé durant l'édition du document ou même par un autre processeur plus adapté au traitement par flux, l'ensemble des informations spécifiques au format souhaité par le serveur étant incluses dans le document lors de sa transmission au client. Enfin, l'ensemble des informations de structure statiques est calculé durant le décodage du document stocké sous forme compressée et/ou l'édition de ce document une fois décodé (voir les tests E305 et E405), alors que les informations dynamiques sont calculées durant l'encodage (car supprimées dès qu'elles ne sont plus valides ù voir étapes E310 et E410) ce qui correspond généralement aux données XML non représentées par des schémas XML. On verra toutefois, en lien avec la figure 12, qu'il peut être envisagé de réaliser une mise à jour des informations dynamiques lors du décodage ou de l'édition.

Comme rappelé ici, les informations de structure/d'indexation sont parfois calculées lors du décodage ou de l'édition. La figure 10 illustre un exemple de décodage d'un document structuré compressé et l'indexation simultanée d'une représentation XML du document. Cette représentation peut par exemple être du type arbre DOM ou du type fichier XML similaire à celui représenté sur la figure 2. Il s'agit par exemple du décodage des étapes E205 et E255 produisant une représentation des données XML enrichies des informations de structure, par exemple comme représenté sur la figure 2. Cet algorithme débute, à l'étape E600, par la récupération des 25 données, par exemple un flux EXI, à décoder. On va ensuite décoder l'ensemble des données EXI jusqu'à ce que toutes les données soient décodées (test de l'étape E610) en décodant événement par événement. Pour ce faire, on effectue autant de fois que nécessaires les étapes E620 à E670 suivantes. 30 A l'étape E620, on décode les informations de structure concernant l'événement courant à ajouter à la représentation XML décompressée: le type d'événement notamment, le nom qualifié de l'attribut, etc.

On stocke par ailleurs ces informations décodées de structure de l'événement dans l'élément parent courant. Si l'événement nécessite de décoder une valeur (test de l'étape E630), on décode la valeur (étape E640) et on ajoute, à l'étape E650, l'événement à la représentation XML en cours d'élaboration. Si l'événement est de type fin d'élément (test de l'étape E660), on récupère les informations de structure stockées pour l'élément courant, on les convertit en une information XML sous la forme d'attribut qu'on ajoute, à l'étape E670, à l'élément courant dans la représentation XML en cours d'élaboration.

Dans le cas où l'événement n'est pas de type "fin de balise", on reboucle sur l'étape E610. Une fin de balise correspond à l'événement qui termine une série d'événements "balise ouvrante" et "attributs", et clôt la définition de l'élément courant. Une fois les données totalement décodées, le procédé se termine 15 par une étape de traitements sur ces données XML (étape E680), notamment une modification/édition du document XML. Cet algorithme de décodage peut être étendu au cas de construction d'un arbre DOM à partir de données XML textuelles. Dans ce cas, l'étape E620 contient une sous-étape supplémentaire de détermination des informations 20 d'indexation de structure relatives à l'événement courant. Dans ce cas, des informations de structure de type schéma sont nécessaires. Ces informations sont fournies par l'application au moment où on effectue le décodage. L'indexation de l'arbre DOM simultanément au décodage du flux EXI correspondant au document XML à éditer présente l'avantage principal 25 d'améliorer les vitesses d'édition et de ré-encodage du document. Il est des situations où il n'est pas possible d'effectuer cette indexation pendant la construction de la représentation XML, ici l'arbre DOM. C'est notamment le cas lorsque l'on ne peut pas modifier l'implémentation de l'arbre DOM, par exemple dans le cas du navigateur web. L'indexation est alors 30 effectuée par un script Javascript après la construction de l'arbre DOM.

La figure 11 illustre un exemple de traitement pour indexer totalement ou partiellement un arbre DOM, c'est-à-dire lui ajouter les informations de structure/d'indexation au sens de l'invention. L'algorithme débute, à l'étape E700, par la récupération d'un arbre 5 DOM 30 à indexer. Dans le cas où un élément est à indexer (test de l'étape E710), on commence par indexer ses attributs. Ainsi, pour chaque attribut de l'élément (test E730), on détermine (comme lors de l'encodage de cet attribut) les informations d'indexation 10 correspondantes et on les stocke dans une mémoire temporaire, lors de l'étape E740. Une fois l'ensemble des attributs indexés, on ajoute, lors de l'étape E750, ces informations de structure correspondant à l'ensemble des attributs de l'élément, au niveau du noeud correspondant à l'élément courant, typiquement 15 en ajoutant un ou plusieurs attributs (un attribut "e:a" dans notre exemple précédent) contentant les informations de structures stockées à l'étape E740. L'algorithme continue par indexer les enfants de l'élément courant. Pour chaque enfant direct (test de l'étape E760), on détermine et on stocke les informations de structure correspondantes (index et nombre de productions 20 pour les enfants éléments, index et nombre de productions et type de valeur pour les noeuds textes). Une fois l'ensemble des enfants directs indexés, on ajoute ces informations à l'arbre DOM, typiquement au niveau du noeud correspondant à l'élément courant (sous la forme de l'attribut "e:ct" par exemple). 25 Lorsque l'indexation d'un élément est terminée, on passe au suivant (E710) jusqu'à avoir indexé l'ensemble des noeuds à indexer. L'algorithme se termine alors par le traitement de l'arbre DOM indexé à l'étape E720, par exemple une édition/modification avant ré-encodage. L'indexation n'est effectuée que pour les éléments indexables, 30 typiquement les éléments décrits dans une grammaire, et peut par ailleurs être partielle. En effet, cette indexation étant effectuée relativement en amont du traitement du document, on peut souhaiter arrêter cette indexation selon un critère de temps, notamment dans le cas où un utilisateur doit attendre la fin de l'indexation pour pouvoir utiliser ces données. Dans ce cas, l'arbre DOM est seulement partiellement indexé et il reviendra à une partie du processus de terminer cette indexation, soit au moment de l'encodage, soit juste avant l'encodage en effectuant un algorithme tel que celui décrit ci-dessus en lien avec la figure 11. On peut noter que l'ordre des éléments à indexer n'est pas défini dans l'algorithme. Diverses approches peuvent être envisagées. Notamment, cet ordre peut naturellement suivre l'ordre du document XML, par exemple en utilisant un algorithme profondeur d'abord. Cet ordre peut aussi suivre un ordre différent de celui du document XML. Il est notamment parfois judicieux (notamment dans le cas d'une indexation limitée dans le temps) de regrouper les éléments suivant leur nom qualifié. Dans ce cas, on peut utiliser l'API DOM pour récupérer l'ensemble des éléments ayant un nom particulier. Ainsi, dans un mode de réalisation, on envisage de sélectionner une grammaire, de récupérer l'ensemble des éléments dont le nom correspond à la grammaire et d'effectuer l'indexation de l'ensemble de ces éléments récupérés. On a ainsi indexé les éléments ayant le même nom qualifié, et cette approche permet de garder en mémoire uniquement la grammaire relative à ce nom qualifié. On peut itérer ce procédé sur l'ensemble des grammaires. L'ordre suivi est alors l'ordre des grammaires. Cet ordre peut être défini en triant les grammaires selon une probabilité d'occurrence décroissante. Ainsi, dans un temps d'indexation donné, on indexe un plus grand nombre d'éléments/nœuds de l'arbre DOM. Par exemple, le procédé effectue une indexation partielle à partir d'un petit nombre de grammaires qui recouvreront la plus grande partie de l'arbre. Cette approche permet ainsi une indexation optimisée eu égard au temps d'indexation disponible. Comme évoqué précédemment, la mise à jour des informations de structure dites non statiques (ou dynamiques) peut, dans un mode de réalisation particulier, être menée lors du décodage ou de l'édition d'un document, par exemple durant ou à la place des étapes E310 ou E410 précitées. La figure 12 illustre des étapes de mise à jour d'informations de structure dites dynamiques. L'avantage de cette mise à jour est de permettre d'indexer une plus grande partie de l'arbre DOM 30, ce qui permet un encodage plus rapide des informations. L'algorithme débute, à l'étape E800, par la récupération de la modification de l'arbre DOM 30.

On détermine l'impact de la modification sur les dictionnaires d'indexation ou grammaires, lors de l'étape E810. Typiquement, dans le cadre du format EXI, un ajout ou une suppression d'un attribut ou d'un élément modifie la grammaire de l'élément parent. A l'étape E820, on détermine les noeuds DOM 32 qui sont impactés par le modification. Dans le cadre du format EXI, on peut récupérer efficacement l'ensemble des noeuds 32 dont le nom qualifié est égal au nom de l'élément parent impacté par la modification. On sélectionne alors les noeuds de cet ensemble, qui sont situés après l'élément parent dans le document.

Une fois ces noeuds sélectionnés, on met à jour les informations d'indexation de noeuds DOM à l'étape E830. Cette mise à jour consiste à modifier les indexes des enfants directs des noeuds sélectionnés à l'étape E820. Typiquement, une partie de ces indexes sont incrémentés dans le cas d'une édition de type insertion et décrémentés dans le cas d'une édition de type suppression. En référence maintenant à la figure 13, il est décrit à titre d'exemple une configuration matérielle particulière d'un dispositif de codage d'un document structuré 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 50, 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 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 selon l'invention comprennent par exemple une caméra numérique 64, ou un scanner ou tout autre moyen d'acquisition ou de stockage d'images, relié à une carte d'entrée/sortie (non représentée) et fournissant au dispositif des données multimédia, éventuellement sous forme de documents XML ou de flux binaire. Le dispositif 50 comporte un bus de communication 51 auquel sont reliés : - une unité centrale de traitement CPU 52 se présentant par exemple sous la forme d'un microprocesseur ; - une mémoire morte 53 dans laquelle peuvent être contenus les programmes dont l'exécution permet la mise en oeuvre du procédé selon l'invention. Il peut s'agir d'une mémoire flash ou EEPROM; - une mémoire vive 54 qui, après la mise sous tension du dispositif 50, contient le code exécutable des programmes de l'invention nécessaires à la mise en oeuvre de l'invention. Cette mémoire vive 54 est de type RAM (à accès aléatoire), ce qui offre des accès rapide comparés à la mémoire morte 53 ; - un écran 55 permettant de visualiser des données notamment vidéo 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 56 ou de tout autre moyen tel qu'un dispositif de pointage, comme par exemple une souris 57 ou un crayon optique ; - un disque dur 58 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 disquettes 59 optionnel, ou un autre lecteur de support de données amovible, adapté à recevoir une disquette 63 et à y lire / écrire des données traitées ou à traiter conformément à l'invention ; et - une interface de communication 60 reliée au réseau de télécommunications 61, l'interface 60 étant apte à transmettre et à recevoir des données. Le bus de communication 51 autorise une communication et une interopérabilité entre les différents éléments inclus dans le dispositif 50 ou reliés à celui-ci. La représentation du bus 51 n'est pas limitative et, notamment, l'unité centrale 52 est susceptible de communiquer des instructions à tout élément du dispositif 50 directement ou par l'intermédiaire d'un autre élément du dispositif 50.

Les disquettes 63 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 ou une carte mémoire. 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, é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, la mise en oeuvre de l'invention peut être indifféremment stocké en mémoire morte 53, sur le disque dur 58 ou sur un support numérique amovible tel que par exemple une disquette 63 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 61, via l'interface 60, pour être stocké dans un des moyens de stockage du dispositif 50 (tel que le disque dur 58 par exemple) avant d'être exécuté.

L'unité centrale 52 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 50, le ou les programmes qui sont stockés dans une mémoire non volatile, par exemple le disque dur 58 ou la mémoire morte 53, sont transférés dans la mémoire vive 54 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 le dispositif mettant en oeuvre l'invention ou incorporant celle-ci est réalisable aussi sous la forme d'un appareil programmé. Par exemple, un tel dispositif peut 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 52, sont susceptibles de mettre en oeuvre tout ou partie des traitements décrits en lien avec les figures 1 à 12, pour mettre en oeuvre les procédés objets de la présente invention et constituer les dispositifs objets 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.

Claims

REVENDICATIONS1. Procédé de codage d'un document structuré (10) comprenant des éléments, le procédé comprenant les étapes consistant à: - former (E110, E120, E210, E255), dans une mémoire (53, 54, 58) d'un codeur (50), une arborescence (20, 30) représentative de la structure et des éléments d'au moins une partie du document, et - parcourir ladite arborescence pour coder (E160, E220, E270) au moins un dit élément en une valeur de codage binaire, caractérisé en ce que ladite arborescence (20, 30) comprend des informations d'indexation (22, 34, e:ct, e:a, e:sd, e:ed) associées aux éléments et la valeur de codage binaire dudit élément est déterminée en fonction des informations d'indexation associées à l'élément dans l'arborescence.
2. Procédé selon la revendication 1, dans lequel ladite arborescence (20, 30) comprend des noeuds (32) correspondants, chacun, à un élément dudit document structuré, et lesdites informations d'indexation (22, 34, e:ct, e:a, e:sd, e:ed) d'un élément sont mémorisées au niveau du noeud correspondant.
3. Procédé selon la revendication précédente, dans lequel lesdites informations d'indexation (22, 34, e:ct, e:a, e:sd, e:ed) d'un élément sont mémorisées à un emplacement prédéfini parmi les champs définissant ledit noeud correspondant.
4. Procédé selon l'une des revendications précédentes, comprenant, lors d'une modification (E140, E260) d'un élément du document (10), une étape de mise à jour (E150, E265, E830) des informations d'indexation (22, 34, e:ct, e:a, e:sd, e:ed).
5. Procédé selon la revendication précédente, dans lequel la mise à jour (E150, E265, E830) des informations d'indexation (22, 34, e:ct, e:a, e:sd, e:ed) est réalisée au niveau d'un noeud (32) correspondant, dans l'arborescence (20, 30), à l'élément modifié.
6. Procédé selon l'une des revendications 1 à 5, dans lequel les informations d'indexation (22, 34, e:ct, e:a, e:sd, e:ed) insérées dansl'arborescence (20, 30) sont déterminées à partir d'un fichier de description structurelle de documents (40).
7. Procédé selon l'une des revendications 1 à 5, dans lequel les informations d'indexation (22, 34, e:ct, e:a, e:sd, e:ed) insérées dans l'arborescence (20, 30) sont récupérées d'un flux binaire encodant une version antérieure dudit document structuré.
8. Procédé selon l'une des revendications 1 à 7, dans lequel l'étape de formation (E110, E120, E210, E255) comprend la construction successive (E650) de noeuds (32) composant ladite arborescence (20, 30), chaque noeud correspondant à un élément dudit document, et les informations d'indexation (22, 34, e:ct, e:a, e:sd, e:ed) d'un élément sont insérées (E670), dans le noeud correspondant, au moment de la construction de ce noeud.
9. Procédé selon l'une des revendications 1 à 7, dans lequel l'étape de formation (E110, E120, E210, E255) comprend une étape préalable de construction d'une arborescence (20, 30), et une étape postérieure d'indexation (E750, E780) de ladite arborescence par ajout desdites informations d'indexation (22, 34, e:ct, e:a, e:sd, e:ed).
10. Procédé selon la revendication précédente, dans lequel ladite étape d'indexation (E750, E780) est réalisée séquentiellement par nom qualifié (qname), une occurrence d'indexation consistant à ajouter, à l'arborescence (20, 30), les informations d'indexation (22, 34, e:ct, e:a, e:sd, e:ed) pour l'ensemble des éléments ayant le même nom qualifié.
11. Procédé selon la revendication précédente, comprenant, préalablement à l'étape d'indexation (E750, E780), une étape d'ordonnancement des noms qualifiés (qname) ayant une occurrence dans le document (10), en fonction d'au moins un paramètre, et ladite étape d'indexation (E750, E780) est réalisée séquentiellement dans l'ordre des noms qualifiés.
12. Procédé selon l'une des revendications précédentes, comprenant, préalablement à l'étape de codage (E160, E220, E270) d'unélément du document (10), une étape de validation (E265) des informations d'indexation (22, 34, e:ct, e:a, e:sd, e:ed) dudit élément, et les informations d'indexation non valides sont supprimées de ladite arborescence (20, 30).
13. Procédé selon la revendication précédente, dans lequel l'étape de codage (E160, E220, E270) d'un élément du document (10) comprend une étape de recherche d'une information d'indexation à partir d'une table de codage si l'arborescence ne contient aucune information d'indexation correspondant audit élément à coder.
14. Procédé selon l'une des revendications précédentes, dans lequel toutes les informations d'indexation (22, 34, e:ct, e:a, e:sd, e:ed) d'un élément ne sont pas encodées lors du codage (E160, E220, E270) dudit élément.
15. Procédé selon lune des revendications précédentes, dans lequel ladite arborescence (20, 30) comprend, associée aux informations d'indexation (22, 34, e:ct, e:a, e:sd, e:ed), une information de typage de donnée.
16. Structure de données arborescente (20, 30) comprenant une pluralité de noeuds (32) correspondants, chacun, à un élément d'un document structuré (10), caractérisé en ce que lesdits noeuds (32) comprennent au moins une information représentative (<g>, <svg>) dudit élément et au moins une information d'indexation (22, 34, e:ct, e:a, e:sd, e:ed) conforme à un format de codage pour permettre un encodage dudit élément.
17. Structure (20, 30) selon la revendication précédente, dans laquelle l'au moins une information d'indexation (22, 34, e:ct, e:a, e:sd, e:ed) d'un noeud comprend une valeur de priorité correspondant à une production d'une grammaire et un nombre représentatif du nombre de priorités au sein de ladite grammaire.
18. Structure (20, 30) selon la revendication précédente, dans laquelle l'au moins une information d'indexation (22, 34, e:ct, e:a, e:sd, e:ed) comprend, en outre, une information de typage.
19. Dispositif de codage (50) d'un document structuré (10) comprenant des éléments, le dispositif comprenant: - une mémoire de stockage (53, 54, 58) apte à mémoriser des structures de données arborescentes (20, 30), - un moyen de formation pour former (E110, E120, E210, E255), dans ladite mémoire, une arborescence (20, 30) représentative de la structure et des éléments d'au moins une partie du document, et - un moyen de parcours de l'arborescence et de codage pour coder (E160, E220, E270) au moins un dit élément en une valeur de codage binaire, caractérisé en ce que ladite arborescence (20, 30) comprend des informations d'indexation (22, 34, e:ct, e:a, e:sd, e:ed) associées aux éléments et le dispositif est configuré pour que la valeur de codage binaire dudit au moins en élément soit déterminée en fonction des informations d'indexation associées à l'élément dans l'arborescence.
20. Dispositif de codage (50) selon la revendication précédente, comprenant, en mémoire, une structure de données selon l'une des revendications 16 à 18.
21. Moyen de stockage d'informations, 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 à 15 lorsque le programme est chargé et exécuté par le système informatique.
22. 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 à 15, lorsqu'il est chargé et exécuté par le microprocesseur.