FR2907567A1 - Procede et dispositif de generation de motifs de reference a partir d'un document ecrit en langage de balisage et procedes et dispositifs de codage et de decodage associes. - Google Patents

Abstract

L'invention concerne un procédé de génération de motifs de référence aptes à représenter des données hiérarchisées, les données hiérarchisées étant structurées conformément à un schéma, les données hiérarchisées étant organisées en une pluralité d'items. Il comprend les étapes suivantes : extraction de motifs structurels primaires à partir du schéma, chacun des motifs structurels primaires représentant un ensemble d'informations structurelles ; association d'items de la pluralité d'items à au moins un motif structurel primaire extrait ; groupement des items associés en fonction d'un critère prédéterminé; et détermination d'un motif de référence par groupe d'items à partir des motifs structurels primaires associés ; ledit motif de référence comprenant au moins une information structurelle apte à représenter au moins une information structurelle de chaque item du groupe qui lui est associé.

Description

La présente invention concerne un procédé, un dispositif et un programme

d'ordinateur pour la génération de motifs de référence aptes à représenter des données hiérarchisées. L'invention concerne également un procédé, un dispositif et un programme d'ordinateur pour le codage de données hiérarchisées, notamment, mémorisées dans un document écrit dans un langage de balisage à partir de motifs de référence. L'invention concerne en outre, un procédé, un dispositif et un programme d'ordinateur pour le décodage de données hiérarchisées codées. De nombreuses applications manipulent des données structurées de façon hiérarchique également appelées données hiérarchisées . Un document de données hiérarchisées renferme deux types d'information : un premier type d'information qui renseigne sur la structure du document et un second type d'information qui renseigne sur le contenu même des données. Les informations du premier type, appelées informations structurelles , sont toutes les informations qui servent à hiérarchiser les données, ainsi que les informations servant à décrire le type des valeurs ou des instances prises par les données du document. Les informations du second type, appelées informations de contenu , représentent les valeurs ou les instances prises par les données du document.

Le lien entre les informations structurelles et les informations de contenu dépend du langage utilisé pour hiérarchiser les données. II existe plusieurs façons de décrire une structure de données hiérarchisées. La plus usuelle utilise le langage de balisage XML, acronyme de eXtensible Markup Language , c'est-à-dire un langage à balise extensible. Ce langage est standardisé par le comité de standardisation W3C (une description du langage peut être trouvée à l'adresse http://www.w3.org/TRIREC-xml). XML est 1 2907567 2 de plus en plus utilisé pour le stockage et la transmission de données numériques. En pratique, XML est un format de description de données, et non un format de représentation ou d'affichage de données. 5 Le langage XML définit une syntaxe particulière pour mélanger les informations structurelles et les informations de contenu. Le langage XML définit plusieurs types d'items pour décrire les informations structurelles et les informations de contenu. Selon cette syntaxe, un noeud, appelé élément , est défini par une balise ouvrante, une balise fermante et un identifiant. Chaque 10 élément peut contenir d'autres éléments ou des données textuelles. Un item feuille, c'est-à-dire un item autre qu'un élément, représente le plus souvent du contenu et peut être, par exemple, du texte, un commentaire (par exemple : <!--Commentaire--> ), une instruction de traitement (par exemple : <?mon traitement?> ) ou un attribut. L'attribut est un item localisé 15 dans la balise ouvrante d'un élément et contient, outre le contenu même de l'attribut, un identifiant pour le définir (par exemple : <balise attribut="valeur">). XML est une syntaxe permettant de définir de nouveaux langages. Ainsi, il est rendu possible de définir une pluralité de langages XML qui peuvent être traités en utilisant des outils génériques. 20 En outre, la syntaxe XML permet de structurer des données, ce qui permet d'élaborer des documents contenant les descriptions structurelles des données. Enfin, la syntaxe XML est textuelle et peut être lue ou écrite aisément par un utilisateur. 25 Plusieurs langages XML différents peuvent contenir des éléments de même nom. Ainsi, pour pouvoir mélanger plusieurs langages XML différents, la syntaxe XML permet de définir des espaces de nommage ( Namespace selon la terminologie anglo-saxonne). De cette manière, deux éléments sont identiques s'ils ont le même nom et se trouvent dans le même espace de 30 nommage. 2907567 3 Un espace de nommage est défini par un identifiant uniforme de ressource aussi appelé URI ( Uniform Resource Identifier en terminologie anglo-saxonne), par exemple : http://canon.crf.fr/xml/monlangage . L'utilisation d'un espace de nommage dans un document XML est 5 réalisée par la définition d'un préfixe qui est un raccourci vers l'identifiant uniforme de ressource de cet espace de nommage. Ce préfixe est défini au moyen d'un attribut spécifique. Par exemple, l'expression xmins:ml="http://canon.crf.fr/xml/monlangage" associe le préfixe ml à l'identifiant uniforme de ressource 10 http://canon.crf.fr/xml/monlangage . Ensuite, l'espace de nommage d'un élément ou d'un attribut est précisé en faisant précéder le nom par le préfixe associé à l'espace de nommage suivi de deux-points : tel qu'illustré dans l'exemple suivant : <ml:balise ml:attribut="valeur"> . 15 Un langage de description de format de document XML permettant de définir la structure d'un document XML est, par exemple le langage appelé schéma XML ( XML Schema en terminologie anglo-saxonne). Un schéma XML est lui-même un langage utilisant la syntaxe XML permettant de définir des langages XML. Il permet ainsi de définir, pour un 20 langage XML, les éléments utilisés par le langage, les attributs que ces éléments contiennent, leur agencement, etc. Un schéma XML définit donc la syntaxe d'un langage XML ou d'une partie d'un langage. Le schéma définit la structure des données hiérarchisées contenues dans des documents écrits en langage XML. En particulier, pour 25 chaque élément du langage XML, le schéma XML définit le nom, l'espace de nommage, le contenu de l'élément et la liste des attributs de l'élément en précisant notamment si un attribut est obligatoire ou non, et si d'autres attributs peuvent être ajoutés ainsi que le type du contenu de chaque attribut. Le contenu d'un élément peut être, par exemple, des données, des sous-éléments 30 ou une combinaison des deux. Ainsi, un schéma XML est un ensemble de définitions, chaque définition correspondant à un item XML. Ces définitions sont reliées entre elles 2907567 4 soient en étant inclues les unes dans les autres, soit en utilisant des références. Chaque définition précise non seulement le contenu d'un item XML, mais aussi ses relations avec les autres items XML proches (par exemple le nombre d'instances possibles pour cet item XML, la possibilité de cooccurrence d'une 5 instance de cette définition avec une instance d'une autre définition...). Le schéma peut définir plus précisément le contenu d'un élément en précisant un type pour le contenu. Dans le cas de données, le type de l'élément correspond au type des données, par exemple chaîne de caractère, entier, etc. Dans le cas de sous-éléments, le type de l'élément définit les sous-éléments 10 présents, leur nombre et leur ordre. Un schéma XML peut non seulement être utilisé pour définir la syntaxe d'un langage XML, mais permet en outre de vérifier qu'un document écrit en langage XML respecte la syntaxe du langage XML auquel il appartient. Ce processus de vérification s'appelle validation. II permet d'éviter à une 15 application de traiter un document erroné. Les langages à balise, notamment le langage XML, sont utilisés pour stocker des données dans un fichier ou pour échanger des données. Il permet en particulier de disposer de nombreux outils pour traiter les fichiers générés. En outre, un document écrit par exemple en XML peut être édité manuellement 20 avec un simple éditeur de texte. De plus, étant donné qu'un document écrit en langage à balise, par exemple XML, contient sa structure intégrée aux données, ce document est rendu lisible sans même en connaître la spécification. Toutefois la syntaxe XML est très prolixe. Ainsi, la taille d'un document XML peut être plusieurs fois supérieure à la taille intrinsèque des 25 données. Cette taille importante des documents XML induit donc un temps de traitement important lors de la génération de tels documents et surtout de la lecture de documents XML. On connaît différentes méthodes pour compresser un document sans perdre de données. 30 Ainsi, les méthodes de compressions zip ou gzip permettent de coder un document sous une forme compressée qui utilise moins d'espace mémoire que le document original. Ces méthodes de compressions sont 2907567 5 réversibles et l'on peut donc retrouver le document original. Ces méthodes se basent sur l'algorithme appelé DEFLATE définit par le document RFC 1951 et accessible à l'adresse Internet suivante : http://www.ietf.org/rfc/rfc1951.txt. L'algorithme DEFLATE est basé sur la détection des répétitions 5 pour diminuer la taille des données codées. Ainsi lorsque l'algorithme détecte qu'une séquence de données est déjà apparue dans le document, l'algorithme mémorise une référence à cette séquence de données au lieu de mémoriser la séquence de données. De cette manière, le codage de plusieurs répétitions d'une même séquence de données est efficace. 10 Les méthodes de compressions zip ou gzip présentent cependant un certain nombre de désavantages pour compresser des fichiers XML. En effet, ces méthodes n'ont pas connaissance de la syntaxe XML et ne peuvent nullement exploiter les spécificités de ce langage pour coder efficacement un document XML. En outre, ces méthodes ne permettent de 15 coder efficacement que les répétitions identiques d'une même séquence de données. Pour pallier à ces inconvénients, d'autres méthodes de compression on été adaptées à la syntaxe XML. Ainsi, une solution est de coder les informations structurelles dans un format binaire au lieu d'utiliser un format 20 textuel. Plusieurs méthodes existent pour cela, un exemple étant la norme ISO Fastlnfoset définie par la spécification ITU-T Rec. X.891. En outre, la redondance des informations structurelles dans le format XML est supprimée ou au moins diminuée, par exemple, par la suppression du nom de l'élément dans la balise ouvrante et la balise fermante. 25 Selon une autre méthode, on utilise le schéma XML associé à un document XML pour coder le document. En effet, le schéma XML décrivant la structure des données mémorisées dans le document XML, l'utilisation du schéma permet de ne pas coder une partie de l'information structurelle des données du document XML, cette dernière pouvant être reconstruite par le 30 décodeur à l'aide de ce même schéma XML. En effet, il est connu, notamment dans le standard Fastlnfoset, d'utiliser un schéma XML afin de générer une table d'index pour les noms des 2907567 6 éléments et des attributs. En outre, le schéma peut permettre de générer une table d'index pour les contenus prédéfinis ou dont les options sont spécifiées dans le schéma XML. Ces tables étant construites à partir du schéma XML, elles ne sont pas insérées lors du codage du document XML. 5 En outre, il est connu, d'utiliser un schéma XML afin de prendre en compte le type d'une valeur pour la coder. En effet, la syntaxe XML ne supporte pas directement de données typées, et code l'ensemble des données sous forme textuelle. Le format Xebu, décrit dans l'article intitulé Xebu: A Binary Format with Schema-Based Optimizations for XML Data de Jaakko 10 Kangasharju, Sasu Tarkoma et Tancred Lindholm publié lors de la conférence WISE 2005, permet par exemple de prendre en compte le type d'une valeur pour la coder. Toutefois, un schéma XML permet de préciser les types des données. Avec une telle méthode, un entier ou un réel ne sera donc plus codé 15 sous une forme textuelle peu efficace, mais sous une forme optimisée, aussi bien en termes de taille que de temps de codage et décodage. Ces méthodes permettent de coder de manière plus efficace les données contenues dans un document XML, tout en permettant la reconstruction du document XML. 20 Ainsi, il est possible d'utiliser une méthode comme Xebu ou Fastlnfoset pour générer une représentation compacte d'un document XML, en utilisant certaines propriétés de la syntaxe XML, puis d'utiliser une méthode de compression générique comme zip ou gzip pour compresser cette représentation compacte. 25 Une telle combinaison est permet de réduire la taille du document généré, mais elle est réalisée en deux étapes, aussi bien au niveau du codage que du décodage, ce qui demande une puissance de calcul importante et nécessite de mémoriser des données intermédiaires. En outre, une méthode de compression générique comme zip ou 30 gzip ne peut prendre en compte les propriétés de la syntaxe XML ou de la représentation compacte utilisée pour améliorer le taux de compression et/ou le temps de compression ou de décompression. 2907567 7 La présente invention vise en premier lieu à fournir un procédé de génération de motifs de référence aptes à représenter des données hiérarchisées, les données hiérarchisées étant structurées conformément à un schéma, les données hiérarchisées étant organisées en une pluralité d'items, 5 caractérisé en ce qu'il comprend les étapes suivantes : extraction de motifs structurels primaires à partir du schéma, chacun des motifs structurels primaires représentant un ensemble d'informations structurelles ; association d'items de la pluralité d'items à au moins un motif structurel 10 primaire extrait ; groupement des items associés en fonction d'un critère prédéterminé; et - détermination d'un motif de référence par groupe d'items à partir des motifs structurels primaires associés ; ledit motif de référence comprenant au moins une information structurelle apte à représenter au 15 moins une information structurelle de chaque item du groupe qui lui est associé. L'invention prévoit d'analyser le schéma des données hiérarchisées pour en extraire des motifs structurels ( patterns en terminologie anglo- saxonne) appelés motifs structurels primaires. Un motif structurel est la 20 description d'une partie de la structure des données hiérarchisées. Un schéma est une définition de la structure de l'ensemble des données hiérarchisées. Les données hiérarchisées sont, notamment, décrites dans un langage de balisage structurant les données, par exemple, en utilisant le langage XML. 25 L'objectif de l'invention est de trouver des motifs contenant des informations structurelles qui se reproduisent dans les données hiérarchisées. Pour ce faire, le procédé selon l'invention prévoit de déterminer à partir des motifs structurels primaires extraits du schéma et des items associés à ces motifs structurels primaires, des motifs structurels de référence aptes à 30 représenter des données hiérarchisées. En outre, il est à noter que, conformément à l'invention, si le motif de référence comprend une pluralité d'informations structurelles, au moins une 2907567 8 information structurelle de chaque item du groupe est représentée par au moins une information structurelle du motif de référence, ladite au moins une information pouvant être différente selon les items du groupe. Ultérieurement, les motifs de référence permettront, notamment, de 5 coder ces données de sorte à réduire la taille de ces données. Le procédé se fonde, notamment, sur une étape de regroupement des items associés aux motifs structurels primaires en fonction d'un critère prédéterminé. Selon un mode de réalisation particulier, le groupement des items en 10 groupes d'items est réalisé en regroupant les items associés à un même motif structurel primaire. Selon cette caractéristique, on regroupe les items qui sont associés à un même motif structurel primaire, c'est-à-dire qui ont les informations structurelles présentes dans le motif structurel primaire. Ces items pourront 15 ainsi être codés par rapport à leur motif structurel primaire commun. Selon une caractéristique particulière, le groupement des items en groupes d'items est réalisé en regroupant des items ayant des informations de contenu identiques. Selon cette caractéristique, on regroupe les items qui ont des 20 informations de contenu identiques, c'est-à-dire qui ont les mêmes données. Ainsi, lors du codage de ces items, les informations de contenu identiques ne seront codées qu'une seule fois. Selon une autre caractéristique particulière, le groupement des items en groupes d'items est réalisé en regroupant des items ayant des informations 25 structurelles identiques. Selon cette caractéristique, on regroupe les items qui ont des informations structurelles identiques, ces informations structurelles étant complémentaires à celles présentes dans les motifs structurels primaires. Ainsi, lors du codage de ces items, un plus grand nombre d'informations structurelles 30 seront codées une seule fois. 2907567 9 Selon une autre caractéristique particulière, le motif de référence comprend en outre au moins une information structurelle commune à un nombre élevé d'items du groupe. Selon cette caractéristique, le motif de référence est augmenté 5 d'informations structurelles qui sont présentes dans un grand nombre d'items du groupe. Ainsi, les informations structurelles fréquentes pour les items du groupe ne sont codées qu'une seule fois. Selon un mode de réalisation, le motif de référence comprend en outre au moins une information de contenu présente dans un nombre élevé 10 d'items du groupe. Selon une caractéristique particulière, l'étape de détermination d'un motif de référence comprend les sous-étapes suivantes pour au moins un groupe d'items : extraction des informations structurelles et des informations de contenu 15 communes à un nombre élevé d'items dudit groupe ; et détermination d'un motif de référence contenant lesdites informations structurelles et lesdites informations de contenu communes extraites ; ledit motif de référence étant apte à représenter une partie des informations structurelles et des informations de contenu d'items dudit 20 groupe. Ainsi, si les items d'un groupe présentent une partie similaire, mais que le reste de ces items varie beaucoup, il est cependant possible de coder une seule fois les informations communes présentes dans cette partie similaire. En outre, il reste possible de trouver des similarités pour les parties restantes 25 des items de ce groupe et ainsi de les regrouper avec d'autres items. Selon un mode de réalisation, si le nombre d'items d'un groupe d'items est inférieur à un seuil prédéterminé, ledit groupe d'items est assemblé à un autre groupe d'items. Selon une caractéristique particulière, ledit groupe d'items est 30 assemblé au groupe d'items le plus proche dudit groupe d'items par rapport à une mesure de distance. 2907567 10 Selon cette caractéristique, le groupe est assemblé à un autre groupe de faible distance afin de déterminer un motif de référence commun apte à représenter les items de l'ensemble du groupe ainsi formé. Selon une caractéristique, la mesure de distance entre deux groupes 5 d'items est fonction du nombre de différences entre les motifs structurels primaires associés aux items. Selon une caractéristique particulière, la mesure de distance entre deux groupes d'items est fonction du nombre de différences entre les informations structurelles et les informations de contenu des items. 10 Selon une autre caractéristique particulière, en l'absence de groupe d'items situé à une distance inférieure à un seuil prédéterminé, pour des items du groupe, le motif de référence est le motif structurel primaire associé à cet item. Ceci permet d'obtenir un motif de référence pour le codage d'un item 15 dans tous les cas de figure. L'invention concerne également un procédé de codage de données hiérarchisées, les données hiérarchisées étant structurées conformément à un schéma, caractérisé en ce qu'il comprend les étapes suivantes : - obtention de motifs de référence aptes à représenter des données 20 hiérarchisées structurées conformément audit schéma, lesdits motifs de référence étant générés selon le procédé de génération de motifs de référence conforme à l'invention ; - détermination d'informations de différence entre les motifs de référence et les données hiérarchisées associées ; et 25 - codage des données hiérarchisées en fonction des motifs de référence et des informations de différence. Conformément à ce procédé, on génère des motifs structurels de référence selon le procédé de l'invention précédemment décrit de sorte à recoder les données hiérarchisées en vue de réduire la taille de codage de ces 30 données hiérarchisées. En effet, après avoir déterminé les structures des données hiérarchisées à partir du schéma de ces données (au moyen des motifs 2907567 11 structurels de référence), on recode ces données à partir des motifs structurels de référence. De la sorte, on évite un codage des informations structurelles pour chaque donnée et on réduit ainsi de manière significative la taille de codage des données hiérarchisées. 5 Selon une caractéristique, le procédé comprend en outre une étape de codage d'au moins un motif de référence utilisé pour le codage de données hiérarchisées. Selon une autre caractéristique, l'étape de codage d'au moins un motif de référence comprend, pour chaque motif de référence, les étapes 10 suivantes : - codage d'une information d'identification du motif structurel primaire associé audit motif de référence ; et - codage d'informations structurelles dudit motif de référence. Selon cette caractéristique, le codage d'un motif de référence 15 consiste à mémoriser une information d'identification d'un motif structurel primaire apte à être extrait du schéma des données et de coder des informations structurelles du motif de référence. Selon une caractéristique particulière, l'étape de codage d'au moins un motif de référence comprend, en outre, pour au moins un motif de référence, 20 une étape de codage d'au moins une information de contenu dudit motif de référence. L'invention concerne également un procédé de décodage de données hiérarchisées codées, les données hiérarchisées étant structurées conformément à un schéma, caractérisé en ce que lesdites données 25 hiérarchisées étant codées en fonction de motifs de référence et d'informations de différence, les motifs de référence étant déterminés à partir d'au moins un motif structurel primaire extrait du schéma, le procédé comprend une étape de décodage des données hiérarchisées codées en fonction des motifs de référence et des informations de différence. 30 Selon une caractéristique particulière, le procédé comprend une étape de décodage d'au moins un motif de référence codé. 2907567 12 Selon une autre caractéristique, l'étape de décodage d'au moins un motif de référence codé comprend les étapes suivantes : extraction de motifs structurels primaires à partir du schéma, chacun des motifs structurels primaires représentant un ensemble d'informations 5 structurelles ; et pour chaque motif de référence codé, décodage d'une information d'identification du motif structurel primaire associé audit motif de référence codé ; - obtention des motifs de référence à partir du motif structurel primaire 10 extrait correspondant à l'information d'identification décodée et d'informations structurelles dudit motif de référence codé. Selon un mode de réalisation particulier, l'étape de décodage d'au moins un motif de référence codé comprend, en outre, pour au moins un motif de référence codé, une étape de décodage d'au moins une information de 15 contenu dudit motif de référence. L'invention vise également un dispositif de génération de motifs de référence aptes à représenter des données hiérarchisées, les données hiérarchisées étant structurées conformément à un schéma, les données hiérarchisées étant organisées en une pluralité d'items, caractérisé en ce qu'il 20 comprend les moyens suivants : des moyens d'extraction de motifs structurels primaires à partir du schéma, chacun des motifs structurels primaires représentant un ensemble d'informations structurelles ; des moyens d'association d'items de la pluralité d'items à au moins un 25 motif structurel primaire extrait ; des moyens de groupement des items associés en fonction d'un critère prédéterminé; et des moyens de détermination d'un motif de référence par groupe d'items à partir des motifs structurels primaires associés ; ledit motif de référence 30 comprenant au moins une information structurelle apte à représenter au moins une information structurelle de chaque item du groupe qui lui est associé. 2907567 13 De même, l'invention propose un dispositif de codage de données hiérarchisées, les données hiérarchisées étant structurée conformément à un schéma, caractérisé en ce qu'il comprend les moyens suivants : - un dispositif de génération de motifs de référence aptes à 5 représenter des données hiérarchisées structurées conformément audit schéma, conforme à l'invention ; - des moyens de détermination d'informations de différence entre les motifs de référence et les données hiérarchisées associées ; et - des moyens de codage des données hiérarchisées en fonction des 10 motifs de référence et des informations de différence. En outre, l'invention propose un dispositif de décodage données hiérarchisées codées, les données hiérarchisées étant structurées conformément à un schéma, caractérisé en ce que lesdites données hiérarchisées sont codées en fonction de motifs de référence et de données 15 hiérarchisées, les motifs de référence étant déterminés à partir d'au moins un motif structurel primaire extrait du schéma, le dispositif comprend des moyens de décodage des données hiérarchisées en fonction des motifs de référence et des informations de différence. Ces dispositifs présentent les mêmes avantages que les procédés 20 brièvement décrit ci-dessus et ils ne seront donc pas rappelés ici. La présente invention vise aussi un moyen de stockage, éventuellement amovible partiellement ou totalement, lisible par un ordinateur ou un microprocesseur conservant des instructions d'un programme d'ordinateur, permettant la mise en oeuvre des procédés tels qu'exposés ci- 25 dessus. La présente invention vise enfin un produit programme d'ordinateur pouvant être chargé dans un appareil programmable, comportant des séquences d'instructions pour mettre en oeuvre les procédés tels qu'exposés ci-dessus, lorsque ce programme est chargé et exécuté par l'appareil 30 programmable. D'autres aspects et avantages de la présente invention apparaîtront plus clairement à la lecture de la description qui va suivre, cette description 2907567 14 étant donnée uniquement à titre d'exemple non limitatif et faite en référence aux dessins annexés, dans lesquels : - la Figure 1 illustre un schéma XML ; - la Figure 2 illustre un document XML contenant des données 5 hiérarchisées correspondant au schéma XML en référence à la Figure 1 ; -la Figure 3 représente un algorithme général de génération de motifs de référence et de codage conformément à l'invention ; - la Figure 4 représente un algorithme général d'extraction des motifs structurels primaires depuis un schéma XML conformément à l'invention ; 10 - la Figure 5 représente un algorithme de création d'un motif structurel primaire pour un élément principal d'un schéma XML conformément à l'invention ; - la Figure 6 représente un algorithme de génération des motifs de référence conformément à l'invention ; 15 - la Figure 7 représente un algorithme de codage des données hiérarchisées conformément à l'invention ; - la Figure 8 représente un algorithme de codage d'un élément en fonction d'un motif de référence conformément à l'invention ; - la Figure 9 représente un algorithme général de décodage d'un 20 document codé selon les algorithmes des Figures 3 à 8 ; et - la Figure 10 représente un schéma bloc illustrant un dispositif adapté à mettre en oeuvre la présente invention.L'invention a pour objectif d'obtenir un codage compact des données 25 hiérarchisées notamment mémorisées dans des documents écrits en langage de balisage tel que XML. L'invention est décrite relativement au standard XML Schema . Cependant, d'autres schémas existent pour définir la structure d'un ensemble de données hiérarchisées notamment mémorisées dans des documents XML. 30 Ainsi, l'invention s'applique aussi à ces autres langages. Des exemples de schémas sont les Documents Type Définition (DTD) et le langage de description de document XML appelé Relax NG. 2907567 15 Pour obtenir un codage compact d'un document XML, l'invention extrait des motifs structurels primaires du document schéma XML associé à ce document XML. Les motifs structurels primaires contiennent des informations structurelles pour ce document XML décrites dans le schéma XML. Ensuite, à 5 partir du contenu du document XML, l'invention construit des motifs de référence représentant plus précisément les informations structurelles de ce document XML et éventuellement certaines informations de contenu de ce document XML. Il est maintenant décrit en référence à la Figure 1 un exemple de 10 schéma XML, décrivant une syntaxe XML pour des données hiérarchisées contenant une liste de personnes. Il est à noter que cet exemple a été légèrement simplifié par rapport au standard XML Schema afin de faciliter sa lecture. Cette liste est contenue dans un élément appelé liste . Cet 15 élément liste peut contenir un nombre indéfini d'éléments personne . En effet, le nombre d'occurrences ( maxOccurs selon la spécification XML) prend la valeur non limitée. Chaque élément personne décrit une personne et est de type personne . Un élément personne est composé d'un élément intitulé prénom , d'un élément intitulé nom et d'un élément 20 optionnel intitulé ville . L'élément ville définit également le nombre d'occurrences minimum de cet élément. Selon l'exemple, l'occurrence définie par l'attribut minOccurs selon la spécification XML prend la valeur 0 indiquant de cette manière, que cet élément est optionnel. Ces trois éléments contiennent une valeur qui est une chaîne de caractères (la définition du type 25 de cette valeur a été omise dans la Figure 1 pour des raisons de lisibilité). A partir de ce schéma XML, conformément à l'invention, des motifs structurels primaires vont être créés. Pour cela, on considère dans un premier temps l'élément principal, à savoir l'élément liste selon l'exemple. Pour cet élément, un motif structurel primaire est créé. Tel que définit par le type 30 liste , ce motif structurel primaire comprend un ensemble d'éléments personne . 2907567 16 Comme le nombre d'éléments personne contenus dans un élément liste n'est pas défini, un motif structurel primaire est créé pour l'élément personne P, et il est indiqué dans le motif structurel primaire de l'élément liste que l'élément liste comprend un nombre inconnu 5 d'éléments de type personne . Lors de la création du motif structurel primaire pour l'élément personne , ce motif comprend l'information selon laquelle un élément personne comprend un élément prénom , un élément nom et un élément optionnel ville . Ainsi, lors du codage d'un élément personne à 10 l'aide de ce motif structurel primaire, il suffit d'indiquer si ce motif structurel primaire contient l'élément optionnel ville , ainsi que le contenu des sous-éléments de cet élément personne . On décrit maintenant en référence à la Figure 2 un exemple de document XML contenant des données hiérarchisées correspondant au 15 schéma XML précédemment décrit en référence à la Figure 1. A partir de ce document XML et à partir des motifs structurels primaires créés précédemment, des motifs de référence sont créés conformément à l'invention. Selon l'exemple de la Figure 2, les deux premiers éléments 20 personne ne possèdent pas de sous-élément ville . Pour cette raison, un motif de référence P1, défini à partir du motif structurel primaire créé pour l'élément personne P et n'incluant pas le sous-élément ville est créé. Concernant le troisième élément personne , celui-ci possède un sous-élément ville alors un motif de référence P2, défini à partir du motif 25 structurel primaire créé pour l'élément personne P et incluant le sous-élément ville est créé. Ainsi, lors du codage des données hiérarchisées du document XML de la Figure 2, le motif de référence P1 étant apte à représenter plusieurs éléments du document, sera effectivement utilisé pour le codage des données, 30 notamment pour le codage des deux premiers éléments personne . Toutefois, le motif de référence P2 n'étant apte à représenter qu'un seul élément du document XML, ce motif n'est pas utilisé lors du codage du 2907567 17 document et notamment pour le codage du troisième élément. Ce dernier sera codé à partir du motif structurel primaire P qui sera considéré comme un motif de référence. En référence à la Figure 3, on décrit maintenant un algorithme 5 général de génération de motifs de référence et de codage conformément à l'invention. L'algorithme débute à l'étape 300 par l'obtention d'un document mémorisant un schéma XML. Puis, lors de l'étape suivante (étape 310), ce schéma XML est analysé afin d'extraire des motifs structurels primaires. Cette 10 analyse est décrite ci-après en référence aux Figures 4 et 5. L'étape 310 est suivie de l'étape 320, consistant à obtenir un document XML mémorisant des données hiérarchisées correspondant à ce schéma XML. Lors de l'étape suivante (étape 330), des motifs de référence pour ce 15 document XML sont générés. Cette génération est décrite ci-après en référence à la Figure 6. Enfin, lors de l'étape 340 qui suit l'étape 330, les données hiérarchisées du document XML sont codés à l'aide de ces motifs de référence. Le codage des données hiérarchisées du document XML est décrit ci-après en 20 référence aux Figures 7 et 8. II est à noter que les étapes 320 à 340 peuvent être répétées plusieurs fois sur des ensembles de données hiérarchisées dès lors que ces données sont décrites par rapport à un même schéma XML, l'étape 310 d'extraction de motifs structurels primaires ayant été effectuée préalablement. 25 Selon un mode de réalisation particulier, des motifs structurels primaires générés pour un schéma XML sont mémorisés. Ainsi, lorsqu'un document XML est obtenu, le schéma XML correspondant est recherché. Si ce schéma XML a déjà été traité tel que décrit en référence à l'étape 310, les motifs structurels primaires associés sont rechargés depuis la mémoire où ils 30 sont mémorisés. Selon un mode de réalisation particulier, si les motifs structurels primaires contiennent peu de choix, ou si le document XML est petit, ou si le 2907567 18 document XML doit être traité rapidement, les motifs de référence ne sont pas générés, et seuls les motifs structurels primaires sont utilisés lors du codage des données. En effet, si les motifs structurels primaires contiennent peu de choix, 5 il est probable que la création de motifs de référence n'apporte qu'un gain faible par rapport à l'utilisation directe des motifs structurels primaires. De même, si le document XML est petit, ce dernier ne contiendra probablement que peu de répétitions et il est donc peu probable de trouver des motifs de référence apte à représenter plusieurs éléments du document XML. 10 L'évaluation de la taille du document XML peut être réalisée en fonction de la taille du schéma XML (voire du contenu de celui-ci). En effet, il est possible d'effectuer une corrélation entre la taille du schéma XML et la taille minimale du document XML. Enfin, si le document XML doit être traité rapidement, même si 15 l'utilisation de motifs de référence peut être utile, il est parfois préférable de choisir un gain en temps de calcul plutôt qu'un gain en taille du document. Bien entendu, ces trois conditions peuvent être combinées entre elles. Selon un autre mode de réalisation, on crée des motifs de référence 20 à partir d'un ensemble de documents XML mémorisant des données hiérarchiques, ces données étant écrites par rapport à un même schéma XML. Ces motifs de référence sont construits à partir de l'ensemble de ces données hiérarchiques mémorisées dans l'ensemble des documents XML, et non pas en considérant les données d'un seul document. Ensuite, ces motifs de référence 25 sont mémorisés et les motifs structurels primaires sont mémorisés en association avec le schéma XML. Ainsi, lors du codage des données d'un document XML structurées conformément à ce schéma, au lieu d'extraire les motifs de référence de ce nouveau document XML, les motifs de référence prédéfinis sont utilisés. Ce mode de réalisation permet d'obtenir un gain en 30 temps de calcul, avec en contrepartie une légère perte au niveau de la taille de codage des documents XML. 2907567 19 En outre, il est possible d'échanger à l'avance des motifs de référence figés, qui ne devront plus être codés pour chaque document XML. Il est maintenant décrit, en référence à la Figure 4, un algorithme général d'extraction des motifs structurels primaires depuis un schéma XML 5 notamment mémorisé dans un document. L'algorithme débute à l'étape 400 par l'obtention d'un premier élément principal D défini dans le schéma XML. L'étape 400 est suivie de l'étape 410 au cours de laquelle on génère un motif structurel primaire pour cet élément D tel que décrit ci-après en 10 référence à la Figure 5. Ensuite, l'algorithme se poursuit à l'étape 420 au cours de laquelle on vérifie s'il existe un autre élément principal D non traité. S'il n'y a plus d'élément principal à traiter, alors il est mis fin a l'algorithme à l'étape 430. 15 Si, au contraire, il reste un élément principal D à traiter, alors on obtient sa définition et l'algorithme se poursuit à l'étape 410 précédemment décrite. Si le schéma XML utilise d'autres schémas XML pour définir le langage XML auquel il correspond, alors conformément au standard XML 20 Schema , on traite les autres schémas XML comme s'ils étaient inclus dans le schéma XML principal. II est maintenant décrit en référence à la Figure 5, un algorithme de création d'un motif structurel primaire pour une définition D d'un item d'un schéma XML. Cette définition peut être une définition globale dans le schéma 25 XML, aussi appelée définition de plus haut niveau ou peut être une définition locale contenue dans une autre définition. L'algorithme débute à l'étape 500 par la création d'un motif structurel primaire M pour la définition D. Initialement, ce motif structurel primaire M comprend les informations 30 correspondant à l'item principal de la définition D. Ce motif structurel primaire M va être complété par la suite de l'algorithme. 2907567 20 Toutefois, si la définition D ne comprend aucune définition de sous-item, alors il est mis fin à l'algorithme. Dans le cas général, l'algorithme se poursuit à l'étape 510 au cours de laquelle on obtient la première définition du sous-item S contenue dans 5 définition D. L'étape 510 est suivie de l'étape 520 au cours de laquelle on vérifie si cette définition S est indépendante de la définition D. Ce test consiste à vérifier notamment si une instance de la définition D et une instance de la définition S sont fortement liées ou non. 10 Ainsi, dans l'exemple du schéma XML illustré en référence à la Figure 1, un élément liste et un sous-élément personne ne sont pas fortement liés, car un élément liste peut contenir un nombre indéterminé de sous-éléments personne . Par contre, l'élément personne et son sous-élément prénom sont fortement lié, car un sous-élément personne 15 contient systématiquement un unique sous-élément prénom . Selon un mode de réalisation, cette vérification consiste à vérifier la multiplicité d'occurrences du sous-item correspondant à la définition S. En effet, si le sous-item correspondant à la définition S a un nombre d'occurrences indéterminé ou avec une variance supérieure à une valeur prédéterminée, alors 20 la définition S n'est pas considérée comme fortement liée à la définition D. En outre, si la définition de sous-item S est utilisé dans plusieurs définitions, alors la définition S n'est pas considérée comme fortement liée à la définition D. De plus, si la définition S n'est pas clairement identifié, par exemple 25 dans le cas où elle correspond à un contenu libre ( xs:any selon la spécification XML Schema) ou si cette définition est un choix parmi un nombre important de variantes, alors elle n'est pas considérée comme fortement liée à la définition D. Selon un autre mode de réalisation particulier, le lien entre la 30 définition de sous-item S et la définition D est dépendante du type du sous-item défini par S. Par exemple, la définition d'un attribut sera considérée comme plus liée que la définition d'un élément enfant. 2907567 21 Selon un mode de réalisation particulier, les critères décrits ci-dessus déterminant si la définition de sous-item S est fortement liée à la définition D sont tolérants. En effet, la décomposition des motifs est effectuée de préférence lors de la création des motifs de référence tel que décrit en référence à la 5 Figure 6 et non lors de la création des motifs structurels primaires. Si la définition S n'est pas indépendante de la définition D, alors l'algorithme se poursuit à l'étape 530 au cours de laquelle on crée un motif structurel primaire pour représenter la définition S, en appelant de manière récursive l'algorithme pour la définition S. 10 Cette étape est suivie de l'étape 535 au cours de laquelle on inclut le motif structurel primaire pour la définition S dans le motif structurel primaire M de la définition D de l'élément considéré. L'algorithme se poursuit à l'étape 540 au cours

de laquelle on vérifie s'il existe une autre définition de sous-item S non encore traitée.

15 Si tel est le cas, la définition est traitée. Pour ce faire, l'algorithme se poursuit à l'étape 510 précédemment décrite. Sinon l'algorithme se termine lors de l'étape 550, et la création du motif structurel primaire M décrivant la définition D est terminée. De retour à l'étape 520, si la définition de sous-item S est 20 indépendante alors l'algorithme se poursuit à l'étape 560 au cours de laquelle on crée un motif structurel primaire pour cette définition, en appelant de manière récursive l'algorithme pour cette définition S. Dans ce cas, le motif structurel primaire M de la définition D est complété par l'indication d'un contenu libre.

25 L'étape 560 est suivie de l'étape 540 précédemment décrite. Selon un mode de réalisation particulier, un motif structurel primaire correspond à la définition d'un élément et de son contenu ou d'une partie du contenu. Cependant, un motif structurel primaire peut correspondre à toute définition contenue dans un schéma XML, par exemple, un groupe d'attributs, 30 une séquence d'éléments, etc. Il est maintenant décrit en référence à la Figure 6 un algorithme de génération des motifs de référence. Cette génération est réalisée à partir des 2907567 22 motifs structurels primaires créés à partir du schéma et du contenu d'un document XML associé à ce schéma. L'algorithme débute à l'étape 600 consistant à créer une liste des éléments du document XML, appelés instances, pour les motifs structurels 5 primaires précédemment créés. Pour ce faire, on parcourt le document XML et le schéma, puis on associe à l'aide du schéma chaque item du document XML au motif structurel primaire correspondant (si ce motif structurel primaire existe). II est à noter que pour un item de type élément XML, généralement, 10 lors de l'association de cet élément à un motif structurel primaire, une partie du contenu de cet élément est associé au même motif structurel primaire. L'ensemble de ces items forme alors une instance du motif structurel primaire. L'algorithme se poursuit à l'étape 605 en regroupant les instances similaires entre elles.

15 Selon un mode de réalisation, deux instances sont considérées similaires si elles correspondent au même motif structurel primaire, et comprennent les mêmes choix structurels par rapport à ce motif structurel primaire. Selon un autre mode de réalisation, la similarité implique également 20 que les contenus des instances, par exemple au niveau des valeurs des attributs et des valeurs du contenu textuel, sont identiques. La suite de l'algorithme a pour but de créer, pour chaque groupe d'instances similaires, le motif de référence le plus adapté. Pour cela, L'étape 605 est suivie de l'étape 610 au cours de laquelle 25 on considère dans un premier temps le groupe G d'instances similaires ayant le moins d'éléments. L'algorithme se poursuit à l'étape 620 au cours de laquelle on teste si le nombre d'instances du groupe G représenté par la variable n(G) est supérieur ou égal à un seuil prédéterminé.

30 Si tel n'est pas le cas, l'algorithme se poursuit à l'étape 630 au cours de laquelle ce groupe d'instances G est réuni au groupe d'instances le plus 2907567 23 proche. Pour cela, l'algorithme calcule une distance entre ce groupe d'instances G et les autres groupes d'instances. Selon un mode de réalisation, la distance entre deux instances dépend, d'une part, du nombre de différences entre les motifs structurels 5 primaires correspondant à ces instances, une différence étant par exemple l'ajout, la suppression ou la modification d'un élément ou d'une option entre ces motifs structurels primaires et, d'autre part, du nombre de différences entre les instances, par exemple au niveau des choix structurels et du contenu. Ces différences peuvent être pondérées en fonction de leurs importances relatives.

10 Selon un mode de réalisation particulier, la distance entre deux groupes d'instances est fonction de la distance entre les instances de ces deux groupes et du nombre d'instances dans chaque groupe. II est à noter que, si aucun groupe d'instances n'est suffisamment proche du groupe d'instances G, alors celui-ci est supprimé et le motif de 15 référence utilisé par chacune de ses instances est le motif structurel primaire associé à l'instance. Ce motif structurel primaire est alors considéré comme un motif de référence. L'algorithme se poursuit à l'étape 680 au cours de laquelle on vérifie s'il reste un autre groupe à traiter.

20 Si tel est le cas, l'algorithme se poursuit à l'étape 610 précédemment décrite. Dans le cas contraire, il est mis fin à l'algorithme à l'étape 690. De retour à l'étape 620, si le nombre d'instances du groupe d'instances G est supérieur ou égal au seuil prédéterminé, alors l'algorithme se 25 poursuit à l'étape 640 au cours de laquelle on tente de créer un motif de référence pour le groupe d'instances G. Pour cela, on détermine la partie commune C de toutes les instances du groupe d'instances G. Cette détermination revient à rechercher une structure commune à toutes les instances du groupe d'instances G.

30 Selon un mode de réalisation, cette étape de détermination peut être réalisée comme une recherche de motifs structurels pour toutes les instances du groupe G.

2907567 24 Selon un autre mode de réalisation, l'étape de détermination peut être réalisée en recherchant, dans un premier temps, l'item XML le plus fréquent au sein des instances du groupe G. Cet item est de préférence un élément, mais peut être du texte, un attribut ou tout autre item XML. Cet item 5 forme le noyau de la structure commune. Cette structure commune est alors étendue aux items voisins, en vérifiant pour chaque item voisin s'il est présent dans une proportion importante, notamment dans une proportion prédéterminée d'instances du groupe G et, si tel est le cas, en incluant cet item voisin dans la structure commune. Ainsi, à 10 partir d'un noyau, la structure commune est étendue de proche en proche. II est à noter que dans cette recherche de structure commune, les contenus des items peuvent ou non être pris en compte en fonction du nombre d'instances ayant les mêmes valeurs. Ainsi, si pour un élément, un de ses contenus a la même valeur pour la plupart des instances comportant cet 15 élément, la valeur de ce contenu est alors intégrée à la structure commune. L'algorithme se poursuit ensuite à l'étape 650 au cours de laquelle on vérifie si la partie commune déterminée lors de l'étape 640 est importante. Cette vérification s'effectue en comparant la taille de la partie commune à la taille, notamment à la taille moyenne, des instances du groupe G et dépend 20 aussi du nombre d'instances du groupe G contenant cette partie commune. Ainsi, dans l'exemple de la figure 2, si l'on considère le groupe d'items constitué par les trois éléments personnes , la partie commune des éléments de ce groupe est constituée par les éléments personne , prénom et nom . Elle peut donc être considérée comme importante, 25 puisque, d'une part, elle correspond à l'ensemble des informations structurelles de deux des items du groupe et à la majeure partie du troisième item du groupe et, d'autre part, elle est commune aux trois éléments du groupe. Si la partie commune est déterminée comme importante selon les critères décrits ci-dessus, alors l'algorithme se poursuit à l'étape 660 au cours 30 de laquelle il crée un motif de référence R pour représenter cette partie commune C.

2907567 25 Ce motif de référence R est créé à partir d'un des motifs structurels primaires associé à une instance comportant la partie commune C, et en fonction des choix structurels réalisés dans la partie commune ainsi que des valeurs intégrées dans la partie commune.

5 Le motif structurel primaire choisi est celui le plus proche de la partie commune, c'est à dire le motif structurel primaire comportant le moins d'options non choisies par la partie commune. Les instances comportant cette partie commune sont alors décomposées. Dans ce but, pour chaque instance, la partie correspondant à la 10 partie commune C est isolée et associée au motif de référence R, tandis que la ou les partie(s) restante(s) sont conservées. Les parties restantes conservées sont alors réparties dans des nouveaux groupes d'instances similaires, tandis que les instances ne comportant pas la partie commune sont toutes regroupées dans un autre nouveau groupe.

15 L'étape 660 est suivie de l'étape 680 précédemment décrite. Si, lors de l'étape 650, la partie commune n'est pas importante au sens du critère d'importance défini ci-dessus par rapport à l'étape 650, alors l'algorithme se poursuit à l'étape 670 au cours de laquelle on tente de créer un motif de référence pour le groupe d'instances G. Si les instances contenues 20 dans le groupe G ne correspondent pas au même motif structurel primaire, alors aucun motif de référence n'est créé et le motif de référence pour ces instances est leur motif structurel primaire associé. Si les instances du groupe G correspondent au même motif structurel primaire, alors leurs choix structurels et leurs contenus sont 25 comparés. Si le nombre de choix structurels commun et de valeurs de contenu identiques est supérieur à un seuil prédéterminé, alors un nouveau motif de référence est créé à partir du motif structurel primaire pour représenter ces choix structurels et ces valeurs de contenu. Ce motif de référence est associé 30 aux instances comprises dans le groupe G. Sinon, aucun motif de référence n'est créé et le motif de référence pour ces instances est leur motif structurel primaire associé.

2907567 26 Selon une variante de réalisation, chaque choix structurel et chaque valeur de contenu est pondéré par son importance lors du comptage de ces éléments. Par exemple, un choix entre dix possibilités est plus important qu'un choix entre deux possibilités.

5 Il est à noter, en outre, qu'un motif de référence peut conserver plusieurs possibilités structurelles. Ceci permet soit de réduire le nombre de possibilités présentes dans le motif de référence par rapport à celles présentes dans le motif structurel primaire, soit de préciser un nombre important de valeurs de contenu dans le motif de référence.

10 Il est à noter également que pour un même contenu, plusieurs valeurs peuvent être définies dans un motif de référence. Ceci correspond, par exemple, aux énumérations définies dans les schémas XML. Il est aussi à noter qu'un choix structurel peut correspondre à la réduction des possibilités pour les valeurs d'un contenu, par exemple, en 15 réduisant le nombre de valeurs possibles pour une énumération, ou en précisant le type d'une valeur. II est aussi à noter que la définition d'une valeur dans un motif de référence peut utiliser le type de cette valeur si celui-ci est précisé dans le schéma XML.

20 Après l'étape 670, l'algorithme se poursuit à l'étape 680 précédemment décrite. II est maintenant décrit, en référence à la Figure 7, un algorithme de codage des données hiérarchisées contenues dans un document XML à l'aide de motifs de références. Cet algorithme est utilisé pour l'ensemble des items du 25 document XML non codés comme sous-item d'un autre item. L'algorithme débute à l'étape 700, consistant à obtenir un premier item E non traité du document XML. Ensuite, l'algorithme se poursuit à l'étape 705 au cours de laquelle on vérifie si l'item E a un motif de référence associé.

30 Si tel n'est pas le cas, alors l'algorithme se poursuit à l'étape 730 décrite ci-après.

2907567 27 Au contraire, si l'item E a un motif de référence associé, alors l'algorithme se poursuit à l'étape 710 au cours de laquelle le motif de référence R associé à ce premier item E est obtenu. L'étape suivante (étape 715) vérifie si le motif de référence R est 5 codé. Si tel est le cas, l'algorithme se poursuit à l'étape 730 décrite ci-après. Dans le cas contraire, l'algorithme se poursuit à l'étape 720 au cours de laquelle le motif de référence R est codé. Pour cela, l'identification du motif 10 structurel primaire dont dépend le motif de référence R est codée, avec si nécessaire l'indication de la partie du motif structurel primaire correspondant au motif de référence R. Ensuite, l'ensemble des choix structurels du motif de référence R est codé, ainsi que l'ensemble des valeurs de contenus du motif de référence R.

15 Ensuite, l'algorithme se poursuit à l'étape 730 au cours de laquelle l'item E est codé. Cette étape est décrite ci-après en référence à la Figure 8. Si des items contenus directement ou indirectement dans l'item E ne sont pas décrits par le motif de référence R, ces items sont codés en utilisant ce même algorithme.

20 Si le motif de référence R n'existe pas, alors l'item E est codé en utilisant une méthode classique puis l'ensemble des items enfants de l'item E est codé en utilisant de manière récursive l'algorithme décrit ici. L'algorithme se poursuit à l'étape 740 au cours de laquelle on vérifie s'il reste d'autres items à coder. Si tel est le cas, l'algorithme se poursuit à 25 l'étape 700 décrite précédemment. Quand tous les items sont codés, alors l'algorithme se termine à l'étape 750. Il est maintenant décrit, en référence à la Figure 8, un algorithme de codage d'un élément E en fonction d'un motif de référence R.

30 Selon cet algorithme, pour coder un item E qui n'est pas associé à un motif de référence, l'ensemble de la structure de l'item E et de son contenu 2907567 28 sont codés directement en utilisant une méthode connue (par exemple Fastl nfoset). L'algorithmedébute à l'étape 800 consistant à coder l'identification du motif de référence R. Ceci permet de conserver l'association entre le motif 5 de référence R et l'item E. Puis l'algorithme se poursuit à l'étape 810 au cours de laquelle on code les choix structurels réalisés pour l'item E par rapport à son motif de référence R. Enfin, l'algorithme code le contenu de l'item E lors de l'étape suivante 10 (étape 820). Au cours de cette étape, on code le contenu de l'item E correspondant à la partie de l'item E décrite par le motif de référence R et non spécifiée dans la définition du motif de référence R (ou bien spécifiée dans la définition du motif de référence R avec une valeur différente). Il est maintenant décrit, en référence à la Figure 9, un algorithme 15 général de décodage d'un document codé selon les algorithmes décrits précédemment. Les deux premières étapes de l'algorithme (étapes 900 et 910) sont similaires aux étapes 300 et 310 de l'algorithme de codage décrit en référence à la Figure 3. Ces étapes permettent de recréer les motifs structurels primaires 20 utilisés par le traitement du décodage. Pour ce faire, l'étape 900 consiste à obtenir un document mémorisant un schéma XML et au cours de l'étape 910, on extrait de ce schéma XML des motifs structurels primaires. Ensuite, l'algorithme se poursuit à l'étape 920 au cours de laquelle on obtient un document codé.

25 Lors de l'étape suivante, (étape 930), à partir du document codé, on décode les motifs de référence. Pour chaque motif de référence, on décode l'identification du motif structurel primaire et on peut donc obtenir le motif structurel primaire. A partir du motif structurel primaire, des éventuelles indications 30 concernant la partie du motif structurel primaire correspondant à ce motif de référence, des choix structurels et des valeurs de contenus décodés à partir du document, le motif de référence est reconstruit.

2907567 29 L'étape 930 est suivie de l'étape 940 aux cours de laquelle on décode les items constituant le document XML. Pour chaque item, on décode l'identification du motif de référence utilisé et on obtient le motif de référence. Puis, à partir de ce motif de référence, des choix structurels et du 5 contenu décodé depuis le document, l'élément est reconstruit. II est à noter que les étapes 930 et 940 peuvent être confondues pour être réalisées pour chaque motif de référence et chaque élément au fur et à mesure de leur lecture dans le document codé. Afin de mettre en oeuvre les procédés de génération de motifs 10 référence aptes à représenter des données hiérarchisées et de codage de ces données utilisant ces motifs de référence, un dispositif de génération de motifs de référence comprend des moyens d'extraction de motifs structurels primaires à partir du schéma, des moyens d'association d'items de la pluralité d'items à au moins un motif structurel primaire extrait, des moyens de groupement des 15 items associés en fonction d'un critère prédéterminé et des moyens de détermination d'un motif de référence par groupe d'items à partir des motifs structurels primaires associés, un dispositif de codage de données hiérarchisées, les données hiérarchisées étant structurée conformément à un schéma, comprend des moyens d'obtention de motifs de référence, des 20 moyens de détermination d'informations de différence entre les motifs de référence et les données hiérarchisées associées, et des moyens de codage des données hiérarchisées en fonction des motifs de référence et des informations de différence et un dispositif de décodage comprenant notamment des moyens de décodage des données hiérarchisées en fonction des motifs de 25 référence et des informations de différence. Ces dispositifs de génération de motifs de référence et de codage peuvent être incorporés dans un ordinateur 1000 tel qu'illustré à la Figure 10. En particulier, les différents moyens identifiés ci-dessus peuvent être incorporés dans une mémoire morte 1005 ("Read- only memory" ou ROM) 30 adaptée à mémoriser un programme de génération de motifs et/ou de codage conforme à l'invention.

2907567 30 La mémoire vive 1010 ("Random access memory" ou RAM) est adaptée à mémoriser dans des registres les valeurs modifiées lors de l'exécution du programme de génération et de codage. Le microprocesseur 1020 est intégré à un ordinateur 1000 qui peut 5 être connecté à différents périphériques et à d'autres ordinateurs d'un réseau de communication. Cet ordinateur comporte de manière connue une interface de communication 1030 reliée au réseau de communication 1035 pour recevoir ou transmettre des messages. L'ordinateur comporte en outre des moyens de 10 stockage de documents, tel qu'un disque dur 1070, ou est adapté à coopérer au moyen d'un lecteur de disque 1080 (disquettes, disques compacts ou cartes informatiques) avec des moyens de stockage de documents amovibles, tels que des disques 1085. Ces moyens de stockage fixes ou amovibles peuvent comporter le code du procédé de génération de motifs ou de codage conforme 15 à l'invention. Ils sont également adaptés à mémoriser un document électronique contenant des données hiérarchisées tel que défini par la présente invention. A titre de variante, le programme permettant au dispositif de génération de motifs ou de codage de mettre en oeuvre l'invention peut être 20 stocké dans la mémoire morte 1005. En seconde variante, le programme pourra être reçu pour être stocké comme décrit précédemment par l'intermédiaire du réseau de communication 1035. L'ordinateur 1000 possède également un écran 1040 permettant par exemple de servir d'interface avec un opérateur à l'aide du clavier 1050 ou de la 25 souris 1060 ou de tout autre moyen. L'unité centrale 1020 (CPU) exécutera alors les instructions relatives à la mise en oeuvre de l'invention. Lors de la mise sous tension, les programmes et méthodes relatives à l'invention stockés dans une mémoire non volatile, par exemple la mémoire 1005, sont transférés dans la mémoire 1010 30 qui contiendra alors le code exécutable de l'invention ainsi que les variables nécessaires à la mise en oeuvre de l'invention.

2907567 31 Le bus de communication 1090 permet la communication entre les différents sous-éléments de l'ordinateur ou liés à lui. La représentation de ce bus 1090 n'est pas limitative et notamment le microprocesseur 1020 est susceptible de communiquer des instructions à 5 tout sous-élément directement ou par l'intermédiaire d'un autre sous-élément. Bien entendu, de nombreuses modifications peuvent être apportées aux exemples de réalisation décrits précédemment sans sortir du cadre de l'invention.

Claims (38)

REVENDICATIONS

1. Procédé de génération de motifs de référence aptes à représenter des données hiérarchisées, les données hiérarchisées étant structurées conformément à un schéma, les données hiérarchisées étant organisées en une pluralité d'items, caractérisé en ce qu'il comprend les étapes suivantes : extraction de motifs structurels primaires à partir du schéma, chacun des motifs structurels primaires représentant un ensemble d'informations structurelles ; - association d'items de la pluralité d'items à au moins un motif structurel primaire extrait ; groupement des items associés en fonction d'un critère prédéterminé; et détermination d'un motif de référence par groupe d'items à partir des motifs structurels primaires associés ; ledit motif de référence comprenant au moins une information structurelle apte à représenter au moins une information structurelle de chaque item du groupe qui lui est associé.

2. Procédé de génération selon la revendication 1, caractérisé en ce 20 que le groupement des items en groupes d'items est réalisé en regroupant les items associés à un même motif structurel primaire.

3. Procédé de génération selon la revendication 1 ou la revendication 2, caractérisé en ce que le groupement des items en groupes d'items est 25 réalisé en regroupant des items ayant des informations de contenu identiques.

4. Procédé de génération selon l'une quelconque des revendications précédentes, caractérisé en ce que le groupement des items en groupes d'items est réalisé en regroupant des items ayant des informations structurelles 30 identiques. 2907567 33

5. Procédé de génération selon l'une quelconque des revendications précédentes, caractérisé en ce que le motif de référence comprend en outre au moins une information structurelle commune à un nombre élevé d'items du groupe.

6. Procédé de génération selon l'une quelconque des revendications précédentes caractérisé en ce que le motif de référence comprend en outre au moins une information de contenu présente dans un nombre élevé d'items du groupe. 10

7. Procédé de génération selon l'une quelconque des revendications précédentes, caractérisé en ce que l'étape de détermination d'un motif de référence comprend les sous-étapes suivantes pour au moins un groupe d'items : 15 extraction des informations structurelles et des informations de contenu communes à un nombre élevé d'items dudit groupe ; et détermination d'un motif de référence contenant lesdites informations structurelles et lesdites informations de contenu communes extraites ; ledit motif de référence étant apte à représenter une partie des informations structurelles et des informations de contenu d'items dudit groupe.

8. Procédé de génération selon l'une quelconque des revendications précédentes, caractérisé en ce que si le nombre d'items d'un groupe d'items est 25 inférieur à un seuil prédéterminé, ledit groupe d'items est assemblé à un autre groupe d'items.

9. Procédé de génération selon la revendication 8, caractérisé en ce que ledit groupe d'items est assemblé au groupe d'items le plus proche dudit 30 groupe d'items par rapport à une mesure de distance. 5 2907567 34

10. Procédé de génération selon la revendication 9, caractérisé en ce que la mesure de distance entre deux groupes d'items est fonction du nombre de différences entre les motifs structurels primaires associés aux items. 5

11. Procédé de génération selon l'une quelconque des revendications 9 ou 10, caractérisé en ce que la mesure de distance entre deux groupes d'items est fonction du nombre de différences entre les informations structurelles et les informations de contenu des items. 10

12. Procédé de génération selon l'une quelconque des revendications 9 à 11, caractérisé en ce que, en l'absence de groupe d'items situé à une distance inférieure à un seuil prédéterminé, pour des items du groupe, le motif de référence est le motif structurel primaire associé à cet item. 15

13. Procédé de génération selon l'une quelconque des revendications précédentes, caractérisé en ce que les données hiérarchisées sont définies à l'aide d'un langage de balisage.

14. Procédé de génération selon la revendication 13, caractérisé en 20 ce que le langage de balisage utilisé est XML.

15. Procédé de codage de données hiérarchisées, les données hiérarchisées étant structurées conformément à un schéma, caractérisé en ce qu'il comprend les étapes suivantes : - obtention de motifs de référence aptes à représenter des données hiérarchisées structurées conformément audit schéma, lesdits motifs de référence étant générés selon le procédé de génération de motifs de référence conforme à l'une quelconque des revendications 1 à 14 ; - détermination d'informations de différence entre les motifs de référence et les données hiérarchisées associées ; et -codage des données hiérarchisées en fonction des motifs de référence et des informations de différence. 2907567

16. Procédé de codage selon la revendication 15, caractérisé en ce que le procédé comprend en outre une étape de codage d'au moins un motif de référence utilisé pour le codage de données hiérarchisées. 5

17. Procédé de codage selon la revendication 16, caractérisé en ce que l'étape de codage d'au moins un motif de référence comprend, pour chaque motif de référence, les étapes suivantes : codage d'une information d'identification du motif structurel primaire 10 associé audit motif de référence ; et codage d'informations structurelles dudit motif de référence.

18. Procédé de codage selon la revendication 17, caractérisé en ce que l'étape de codage d'au moins un motif de référence comprend, en outre, 15 pour au moins un motif de référence, une étape de codage d'au moins une information de contenu dudit motif de référence.

19. Procédé de décodage de données hiérarchisées codées, les données hiérarchisées étant structurées conformément à un schéma, 20 caractérisé en ce que lesdites données hiérarchisées étant codées en fonction de motifs de référence et d'informations de différence, les motifs de référence étant déterminés à partir d'au moins un motif structurel primaire extrait du schéma, le procédé comprend une étape de décodage des données hiérarchisées codées en fonction des motifs de référence et des informations 25 de différence.

20. Procédé de décodage selon la revendication 19, caractérisé en ce que le procédé comprend une étape de décodage d'au moins un motif de référence codé. 30 2907567 36

21. Procédé de décodage selon la revendication 20, caractérisé en ce que l'étape de décodage d'au moins un motif de référence codé comprend les étapes suivantes : extraction de motifs structurels primaires à partir du schéma, chacun des 5 motifs structurels primaires représentant un ensemble d'informations structurelles ; et pour chaque motif de référence codé, -décodage d'une information d'identification du motif structurel primaire associé audit motif de référence codé ; 10 obtention des motifs de référence à partir du motif structurel primaire extrait correspondant à l'information d'identification décodée et d'informations structurelles dudit motif de référence codé.

22. Procédé de décodage selon la revendication 21, caractérisé en 15 ce que l'étape de décodage d'au moins un motif de référence codé comprend, en outre, pour au moins un motif de référence codé, une étape de décodage d'au moins une information de contenu dudit motif de référence.

23. Dispositif de génération de motifs de référence aptes à 20 représenter des données hiérarchisées, les données hiérarchisées étant structurées conformément à un schéma, les données hiérarchisées étant organisées en une pluralité d'items, caractérisé en ce qu'il comprend les moyens suivants : des moyens d'extraction de motifs structurels primaires à partir du 25 schéma, chacun des motifs structurels primaires représentant un ensemble d'informations structurelles ; des moyens d'association d'items de la pluralité d'items à au moins un motif structurel primaire extrait ; des moyens de groupement des items associés en fonction d'un critère 30 prédéterminé; et des moyens de détermination d'un motif de référence par groupe d'items à partir des motifs structurels primaires associés ; ledit motif de référence 2907567 37 comprenant au moins une information structurelle apte à représenter au moins une information structurelle de chaque item du groupe qui lui est associé. 5

24. Dispositif de génération selon la revendication 23, caractérisé en ce que les moyens de détermination d'un motif de référence pour au moins un groupe d'items comprennent les moyens suivants: des moyens d'extraction des informations structurelles et des informations de contenu communes à un nombre élevé d'items dudit 10 groupe ; et des moyens de détermination d'un motif de référence contenant lesdites informations structurelles et lesdites informations de contenu communes extraites ; ledit motif de référence étant apte à représenter une partie des informations structurelles et des informations de contenu d'items dudit 15 groupe.

25. Dispositif de codage de données hiérarchisées, les données hiérarchisées étant structurées conformément à un schéma, caractérisé en ce qu'il comprend les moyens suivants : 20 - un dispositif de génération de motifs de référence aptes à représenter des données hiérarchisées structurées conformément audit schéma, conforme à la revendication 23 ou à la revendication 24 ; - des moyens de détermination d'informations de différence entre les motifs de référence et les données hiérarchisées associées ; et 25 - des moyens de codage des données hiérarchisées en fonction des motifs de référence et des informations de différence.

26. Dispositif de codage selon la revendication 25, caractérisé en ce que le dispositif comprend en outre des moyens de codage d'au moins un motif 30 de référence utilisé pour le codage de données hiérarchisées. 2907567 38

27. Dispositif de codage selon la revendication 26, caractérisé en ce que les moyens de codage d'au moins un motif de référence comprennent les moyens suivants appliqués sur chaque motif de référence : des moyens de codage d'une information d'identification du motif 5 structurel primaire associé audit motif de référence ; et des moyens de codage d'informations structurelles dudit motif de référence.

28. Dispositif de codage selon la revendication 27, caractérisé en ce 10 que les moyens de codage d'au moins un motif de référence comprennent, en outre, des moyens de codage d'au moins une information de contenu dudit motif de référence.

29. Dispositif de décodage de données hiérarchisées codées, les 15 données hiérarchisées étant structurées conformément à un schéma, caractérisé en ce que lesdites données hiérarchisées sont codées en fonction de motifs de référence et de données hiérarchisées, les motifs de référence étant déterminés à partir d'au moins un motif structurel primaire extrait du schéma, le dispositif comprend des moyens de décodage des données 20 hiérarchisées en fonction des motifs de référence et des informations de différence.

30. Dispositif de décodage selon la revendication 29, caractérisé en ce que le dispositif comprend des moyens de décodage d'au moins un motif de 25 référence codé.

31. Dispositif de décodage selon la revendication 30, caractérisé en ce que les moyens de décodage d'au moins un motif de référence codé comprennent les moyens suivants : 30 - des moyens d'extraction de motifs structurels primaires à partir du schéma, chacun des motifs structurels primaires représentant un ensemble d'informations structurelles ; 2907567 39 des moyens de décodage d'une information d'identification du motif structurel primaire associé audit motif de référence codé ; des moyens d'obtention des motifs de référence à partir du motif structurel primaire extrait correspondant à l'information d'identification 5 décodée et d'informations structurelles dudit motif de référence codé.

32. Dispositif de décodage selon la revendication 31, caractérisé en ce que les moyens de décodage d'au moins un motif de référence codé comprennent, en outre, pour au moins un motif de référence codé, des moyens 10 de décodage d'au moins une information de contenu dudit motif de référence.

33. Produit programme ordinateur pouvant être chargé dans un appareil programmable, caractérisé en ce qu'il comporte des séquences d'instructions pour mettre en oeuvre un procédé de génération de motifs de 15 référence selon l'une quelconque des revendications 1 à 14, lorsque ce programme est chargé et exécuté par l'appareil programmable.

34. Produit programme ordinateur pouvant être chargé dans un appareil programmable, caractérisé en ce qu'il comporte des séquences d'instructions 20 pour mettre en oeuvre un procédé de codage de données hiérarchisées selon l'une quelconque des revendications 15 à 18, lorsque ce programme est chargé et exécuté par l'appareil programmable.

35. Produit programme ordinateur pouvant être chargé dans un appareil 25 programmable, caractérisé en ce qu'il comporte des séquences d'instructions pour mettre en oeuvre un procédé de décodage de données hiérarchisées codées selon l'une quelconque des revendications 19 à 22, lorsque ce programme est chargé et exécuté par l'appareil programmable. 30

36. Moyen de stockage d'informations, lisible par un ordinateur ou un microprocesseur conservant des instructions d'un programme d'ordinateur, 2907567 caractérisé en ce qu'il permet la mise en oeuvre d'un procédé de génération de motifs de référence selon l'une quelconque des revendications 1 à 14.

37. Moyen de stockage d'informations, lisible par un ordinateur ou un 5 microprocesseur conservant des instructions d'un programme d'ordinateur, caractérisé en ce qu'il permet la mise en oeuvre d'un procédé de codage de données hiérarchisées selon l'une quelconque des revendications 15 ou 18.

38. Moyen de stockage d'informations, lisible par un ordinateur ou un 10 microprocesseur conservant des instructions d'un programme d'ordinateur, caractérisé en ce qu'il permet la mise en oeuvre d'un procédé de décodage de données hiérarchisées codées selon l'une quelconque des revendications 19 à 22. 15