Brevet FR2907568A1 — publié le 20080425

La présente invention concerne un procédé et 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 ce type de données d'un document écrit dans un langage de balisage à partir de motifs de référence. En outre, l'invention concerne un procédé, un dispositif et un programme d'ordinateur pour le décodage de données hiérarchisées codées. L'invention concerne également un procédé, un dispositif et un programme d'ordinateur pour la génération de méta-motifs de référence et un procédé, un dispositif et un programme d'ordinateur de codage de méta-motifs de référence. 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. Cependant, et de façon générale, un document contenant des données hiérarchisées peut être vu comme un ensemble d' items organisés en arbre . Un item représente un noeud s'il contient au moins un autre item et représente une feuille s'il n'en contient aucun. Le noeud situé au niveau 1 2907568 2 hiérarchique le plus élevé est le noeud racine. Le noeud racine peut donc contenir des sous-noeuds, appelés aussi noeuds-enfants , qui eux-mêmes peuvent contenir d'autres sous-noeuds et ainsi de suite. Un noeud est identifié dans la structure de données à l'aide d'une 5 balise ouvrante et, le plus souvent, d'une balise fermante. Toutes les données situées entre la balise ouvrante et la balise fermante font parties du noeud et représentent le ou les items situés au niveau hiérarchique inférieur par rapport à ce noeud. Ainsi, si un des items est un noeud-enfant, les balises définissant ce noeud-enfant et les données qui lui sont associées sont contenues entre les deux 10 balises du noeud parent. II existe plusieurs façons de décrire une structure de données hiérarchisées. La plus usuelle utilise le langage 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 15 peut être trouvée à l'adresse http://www.w3.org/TR/REC-xml). XML est 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. Le langage XML définit une syntaxe particulière pour mélanger les 20 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. 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, une instruction de traitement ou un attribut. L'attribut est un item 25 localisé dans la balise ouvrante d'un élément et contient, outre le contenu même de l'attribut, un identifiant pour le définir. 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. 30 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. 2907568 3 Enfin, la syntaxe XML est textuelle et peut être lue ou écrite aisément par un utilisateur. Toutefois, le langage XML présente un certains nombre d'inconvénients. 5 Tout d'abord, un document décrit en langage XML est de taille importante puisque la taille du document est bien supérieure à la taille effective des données qu'il contient. Ainsi, la manipulation d'un tel document est rendue difficile, aussi bien en termes de stockage qu'en termes d'échange, ou de traitement. 10 On connaît différentes méthodes pour compresser un document sans perdre de données. 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 15 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 pour diminuer la taille des données codées. Ainsi lorsque l'algorithme détecte 20 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. Les méthodes de compressions zip ou gzip présentent 25 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 coder efficacement que les répétitions identiques d'une même séquence de 30 données. Il est connu du document US 2005/0256893 de la société Hewlett Packard, intitulée : Method and system for updating hierarchical data 2907568 4 structures une méthode permettant de transmettre de façon optimisée un document XML en utilisant un modèle de document appelé template en terminologie anglo-saxonne. Selon cette méthode, le document à transmettre est comparé avec le modèle et il n'est transmis que l'identification du modèle et 5 les différences identifiées par rapport au modèle. Toutefois, selon cette méthode, les modèles sont fixés par avance. Ainsi, cette méthode ne s'applique qu'aux documents ayant un modèle préalablement identifié. De plus, cette méthode impose qu'un modèle soit disponible au niveau de la compression et au niveau de la décompression. 10 Une autre méthode connue du document US 2005/0278616, intitulée : Extensible binary mark-up language for efficient XML-based data communications and related systems and methods permet de coder un document XML sous une forme plus compacte. Le principe de cette méthode repose sur l'utilisation d'une définition de document type appelée DTD 15 ( Document Type Definition en terminologie anglo-saxonne) qui définit le document XML à coder. Une définition de document type, dont la spécification fait partie de la spécification du langage XML, permet de décrire la structure d'un ensemble de documents XML. Toutefois, cette méthode ne peut être appliquée qu'à un document 20 XML pour lequel une définition de document type ou une description similaire comme un schéma XML existe. En outre, la définition de document type doit être disponible pour le codage et pour le décodage. Il serait par conséquent intéressant de pouvoir coder de manière efficace un document XML en tirant parti de la structure particulière du 25 document mais sans avoir besoin d'un document annexe décrivant cette structure. 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, caractérisé en ce qu'il comprend les étapes suivantes : 30 - détermination de motifs structurels primaires associés aux données hiérarchisées, chacun des motifs structurels primaires représentant un ensemble d'informations structurelles ; 2907568 5 - extraction d'informations de contenu à partir des données hiérarchisées associées à au moins un motif structurel primaire déterminé ; - génération d'au moins un motif structurel mixte, un motif structurel mixte comprenant les informations structurelles représentées par un motif 5 structurel primaire déterminé et au moins une information de contenu parmi les informations de contenu extraites à partir des données hiérarchisées associées à ce motif structurel primaire ; et - détermination d'au moins un motif de référence au moins à partir d'au moins un motif structurel mixte, ledit motif de référence étant apte à 10 représenter ledit au moins un motif structurel mixte L'invention prévoit d'analyser 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 description d'une partie de la structure des données hiérarchisées. 15 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. A ces motifs structurels, sont ajoutées des informations de contenu extraites des données hiérarchisées afin de générer des motifs structurels 20 mixtes. L'objectif de l'invention est de trouver des motifs contenant des informations structurelles et des informations de contenu 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 25 des motifs structurels mixtes extraits des données, des motifs de référence aptes à représenter des données hiérarchisées. Ultérieurement, les motifs de référence permettront, notamment, de coder ces données de sorte à réduire la taille de ces données. Selon une caractéristique, la détermination dudit au moins un motif 30 de référence est réalisée, en outre, à partir d'au moins un motif structurel primaire. 2907568 6 Selon cette caractéristique, les motifs de référence sont déterminés à partir de motifs structurels mixtes et de motifs structurels primaires si à ces derniers, il n'a pas été créé de motifs structurels mixtes. Selon une caractéristique particulière, l'étape de génération dudit au 5 moins un motif structurel mixte comprend pour chaque motif structurel mixte à générer à partir d'un motif structurel primaire, les étapes suivantes : - détermination du degré d'utilisation des informations de contenu extraites en fonction du nombre de données hiérarchisées contenant ces informations de contenu associées audit motif structurel primaire ; 10 - sélection parmi les informations de contenu extraites, d'au moins une information de contenu en fonction de son degré d'utilisation déterminé ; et - génération dudit motif structurel mixte comprenant ladite au moins une information de contenu sélectionnée et les informations structurelles du motif structurel primaire auquel est associée ladite au moins une information de 15 contenu. Selon cette caractéristique, les motifs structurels mixtes comprennent des informations de contenu utilisées dans les données hiérarchisées. Selon une autre caractéristique, l'étape de détermination d'au moins 20 un motif de référence comprend les étapes suivantes : - groupement dudit au moins un motif structurel mixte avec au moins un motif structurel mixte similaire et / ou au moins un motif structurel primaire similaire en groupe de motifs ; et - détermination d'un motif de référence par groupe de motifs; ledit 25 motif de référence étant apte à représenter les motifs structurels du groupe qui lui est associé. Selon cette caractéristique, le procédé de génération de motifs de référence se fonde, notamment, sur une étape de regroupement de motifs structurels mixtes et / ou de motifs structurels primaires qui présentent une 30 similitude. Les motifs ainsi regroupés sont appelés motifs structurels. Selon un mode de réalisation, l'étape de groupement est effectuée en fonction d'une mesure de distance entre des motifs structurels. 2907568 7 Selon un autre mode de réalisation, l'étape de groupement est effectué en fonction du nombre de données hiérarchisées aptes à être représentées par ledit au moins un motif structurel. Selon une caractéristique particulière, le nombre de données 5 hiérarchisées aptes à être représentées par ledit au moins un motif structurel est déterminé en fonction du nombre de données hiérarchisées dont les informations structurelles et ladite au moins une information de contenu correspondent aux informations structurelles et à au moins une information de contenu de ce motif structurel mixte. 10 Selon une autre caractéristique, le motif de référence associé à un groupe de motifs est construit par la réunion des informations structurelles et des informations de contenu de tous les motifs du groupe. Selon cette caractéristique, le motif de référence comprend l'ensemble des informations structurelles et de contenu des motifs structurels 15 mixtes du groupe de sorte à créer un sur-ensemble des motifs. Selon une autre caractéristique particulière, les données hiérarchisées étant organisées en une pluralité d'items, un item représentant un noeud s'il contient au moins un autre item dit item enfant, les informations structurelles d'un motif structurel primaire ou d'un motif structurel mixte sont 20 relatives à une pluralité de noeuds ayant une relation hiérarchique entre eux. Selon cette caractéristique, l'information structurelle d'un motif structurel primaire ou l'information structurelle et de contenu d'un motif structurel mixte est déterminée par rapport à l'information structurelle contenue dans une pluralité de noeuds telle que ces noeuds présentent entre eux une 25 relation hiérarchique. En outre, selon une caractéristique particulière, les données hiérarchisées étant organisées en une pluralité d'items, les informations de contenu sont relatives aux données comprises dans au moins un item. L'invention vise, en outre, un procédé de génération de méta-motifs 30 de référence aptes à représenter des motifs de référence, caractérisé en ce qu'il comprend les étapes suivantes : 2907568 8 - génération de motifs de référence aptes à représenter des données hiérarchisées selon le procédé de génération de motifs de référence conforme à l'invention ; - groupement des motifs de référence générés à l'étape de 5 génération ; ledit groupement étant effectué en fonction du degré d'utilisation d'au moins un motif de référence ; et -détermination d'un méta-motif de référence par groupe de motifs de référence, ledit méta-motif de référence étant apte à représenter les motifs de référence du groupe qui lui est associé. 10 L'invention vise également un procédé de codage de données hiérarchisées, caractérisé en ce qu'il comprend les étapes suivantes : - génération de motifs de référence aptes à représenter les données hiérarchisées selon le procédé de génération de motifs de référence conforme à l'invention ; 15 -détermination des 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. Conformément à ce procédé, on génère des motifs de référence selon 20 le procédé de l'invention précédemment décrite de sorte à recoder les données hiérarchisées en vue de réduire la taille de codage de ces données hiérarchisées. En effet, après avoir déterminé des informations structurelles des données hiérarchisées et des informations de contenu (au moyen des motifs de 25 référence), on recode ces données à partir des motifs de référence. De la sorte, on évite un codage des informations structurelles et de contenu pour chaque donnée et on réduit ainsi de manière significative la taille de codage des données hiérarchisées. Selon une caractéristique particulière, les informations de différence 30 entre les motifs de référence et les données hiérarchisées associées comprennent des informations structurelles et des informations de contenu'. 2907568 9 L'invention vise également un procédé de codage de motifs de référence, caractérisé en ce qu'il comprend les étapes suivantes : - génération de méta-motifs de référence aptes à représenter des motifs de référence selon le procédé de génération de méta-motifs de référence 5 conformément à l'invention ; - détermination des informations de différence entre les méta-motifs de référence et les motifs de référence associés ; et - codage des motifs de référence en fonction des motifs de référence et des informations de différence. 10 L'invention vise également un procédé de décodage de données hiérarchisées codées, caractérisé en ce que les 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 comprenant des informations structurelles et au moins une information de contenu, le procédé comprend une étape de décodage des 15 données hiérarchisées codées en fonction des motifs de référence et des informations de diffé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, caractérisé en ce qu'il comprend les moyens suivants : 20 des moyens de détermination de motifs structurels primaires associés aux données hiérarchisées, chacun des motifs structurels primaires représentant un ensemble d'informations structurelles ; - des moyens d'extraction aptes à extraire des informations de contenu à partir des données hiérarchisées associées à au moins un motif 25 structurel primaire déterminé ; - des moyens de génération d'au moins un motif structurel mixte, un motif structurel mixte comprenant les informations structurelles représentées par un motif structurel primaire déterminé et au moins une information de contenu parmi les informations de contenu extraites à partir des données 30 hiérarchisées associées à ce motif structurel primaire ; et 2907568 10 -des moyens de détermination d'au moins un motif de référence au moins à partir d'au moins un motif structurel mixte, ledit motif de référence étant apte à représenter ledit au moins un motif structurel mixte. L'invention vise également un dispositif de génération de méta-motifs 5 de référence aptes à représenter des motifs de référence, caractérisé en ce qu'il comprend les moyens suivants : un dispositif de génération de motifs de référence aptes à représenter des données hiérarchisées conformément à l'invention ; - des moyens de groupement des motifs de référence générés par lesdits 10 moyens de génération; ledit groupement étant effectué en fonction du degré d'utilisation d'au moins un motif de référence ; et des moyens de détermination d'un méta-motif de référence par groupe de motifs de référence, ledit méta-motif de référence étant apte à représenter les motifs de référence du groupe qui lui est associé. 15 De même, l'invention propose un dispositif de codage de données hiérarchisées, caractérisé en ce qu'il comprend les moyens suivants : - un dispositif de génération de motifs de référence aptes à représenter les données hiérarchisées conforme à l'invention ; - des moyens de détermination des informations de différence entre 20 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. En outre, l'invention vise un dispositif de codage de motifs de référence, caractérisé en ce qu'il comprend les moyens suivants : 25 - un dispositif de génération de méta-motifs de référence aptes à représenter des motifs de référence conformément à l'invention ; - des moyens de détermination des informations de différence entre les méta-motifs de référence et les motifs de référence associés ; et - des moyens de codage des motifs de référence en fonction des 30 motifs de référence et des informations de différence. En outre, l'invention propose un dispositif de décodage de données hiérarchisées codées, caractérisé en ce que les données hiérarchisées étant 2907568 11 codées en fonction de motifs de référence et d'informations de différence, les motifs de référence comprenant des informations structurelles et au moins une information de contenu, le dispositif comprend des moyens de décodage des données hiérarchisées codées en fonction des motifs de référence et des 5 informations de différence. Ces dispositifs présentent les mêmes avantages que les procédés brièvement décrits 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 10 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-dessus. La présente invention vise enfin un produit programme d'ordinateur pouvant être chargé dans un appareil programmable, comportant des 15 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 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 20 étant donnée uniquement à titre d'exemple non limitatif et faite en référence aux dessins annexés, dans lesquels : - la Figure 1 montre la structure d'un motif structurel conformément à l'invention ; - la Figure 2 montre la structure d'un item enfant conformément à 25 l'invention ; - la Figure 3 montre un exemple de document écrit en langage de balisage XML pouvant être traité par l'invention ; - la Figure 4 représente un algorithme général génération de motifs mixte de référence et de codage d'un document XML conformément à 30 l'invention ; - la Figure 5 représente un algorithme général de décodage d'un document XML conformément à l'invention ; 2907568 12 - la Figure 6 représente un algorithme d'extraction de motifs structurels primaires à partir d'un document XML ; - la Figure 7 représente un algorithme d'extraction des valeurs liées aux motifs structurels primaires extraits conformément à l'invention ; 5 - la Figure 8 représente un algorithme de création de motifs mixtes contenant des valeurs d'attributs fixées ; - la Figure 9 représente un algorithme d'association des motifs mixtes conforme à l'invention ; - la Figure 10 représente un algorithme de calcul de distance entre 10 deux motifs mixtes conforme à l'invention ; - la Figure 11 représente un algorithme de génération des motifs mixtes de référence conforme à l'invention ; - la Figure 12 représente un algorithme d'écriture d'un motif mixte de référence conforme à l'invention ; 15 - la Figure 13 représente un algorithme d'écriture d'un noeud XML associé à un motif mixte de référence conforme à l'invention ; - la Figure 14 représente un algorithme de lecture d'un motif mixte de référence conforme à l'invention ; - la Figure 15 représente un algorithme de lecture d'un noeud XML 20 associé à un motif mixte de référence conforme à l'invention ; et - la Figure 16 représente un schéma bloc illustrant un dispositif adapté à mettre en oeuvre la présente invention. L'invention consiste à analyser un document écrit en langage de 25 balisage, notamment, en langage XML pour en extraire des motifs structurels mixtes ( patterns en terminologie anglo-saxonne). Un motif structurel mixte est la description d'une partie de la structure du document XML appelé motif structurel et d'une partie des informations de contenu du document XML correspondant à cette structure. L'objectif de l'invention est de trouver des 30 motifs mixtes qui se reproduisent dans le document. Un motif structurel comporte un ensemble d'informations structurelles portant sur une partie du document XML. Ces informations 2907568 13 structurelles peuvent être le type d'un item, par exemple un élément XML, du texte, etc., l'identifiant d'un item, la relation d'ordre entre des items, la relation hiérarchique entre des items, etc. Un motif structurel mixte, aussi appelé motif mixte, est une extension 5 d'un motif structurel qui comporte en outre un ensemble d'informations de contenu portant sur la même partie du document XML ou sur une sous-partie de cette partie du document XML. Ces informations de contenu peuvent être la valeur d'un attribut, la valeur d'un contenu textuel, la valeur d'un commentaire, etc. 10 Enfin, un motif structurel (mixte ou non) est appelé motif de référence lorsqu'il est sélectionné pour être utilisé dans le codage d'un document XML ou pour une autre application des motifs structurels. En référence à la Figure 1 et désignée par la référence générale notée 100, la structure d'un motif structurel est représentée. 15 Le motif structurel peut prendre, notamment, deux formes différentes illustrées en 110 et 120. La première forme de motif structurel 110 est constituée par l'identifiant de l'élément XML qu'il représente 111, le nombre d'items enfants qu'il contient 112 et par la description de ces items enfants 113. L'identifiant 20 d'un élément XML est par exemple le nom de l'élément ou le nom qualifié ( QName est terminologie anglo-saxonne) si les espaces de nommage XML sont utilisés. La seconde forme de motif structurel 120 est constituée de manière similaire, mais l'identifiant de l'élément XML représenté sous la référence 121 25 n'est pas précisé, mais laissé libre. En référence à la Figure 2, il est maintenant décrit différentes formes de description d'un item enfant 150 présentes dans un motif structurel. Chaque description d'un item 150 illustrée en Figure 2 dépend de son type. La description de l'item représente les informations structurelles 30 associées à cet item. Elle comprend une indication de son type. Ainsi, si le type de l'item est de type attribut 151, alors sa description comprend en outre l'identifiant de cet attribut. Il est à noter que l'identifiant de 2907568 14 l'attribut peut ne pas être précisé. En outre, si le motif structurel est un motif structurel mixte, il peut aussi comprendre la valeur de cet attribut. Si le type de l'item est de type commentaire 152, de type instruction de traitement ( processing-instruction ou pi en terminologie anglo- 5 saxonne) 153 ou de type texte 154, alors la description de l'item ne comprend aucune information additionnelle. Cependant, si le motif structurel est un motif structurel mixte, il peut aussi comprendre la valeur de l'item. Si le type de l'item est de type description d'un autre motif structurel 155, alors sa description comprend la structure de cet autre motif structurel telle 10 que représentée par la référence 100. Si le type de l'item est une référence à un motif structurel 156, alors sa description comprend la référence de ce motif structurel. Toutefois, cette référence peut ne pas être précisée comme pour le type d'item 157. Une répétition de type d'items 158 peut également être décrite. Dans 15 ce cas, la description comprend le nombre de répétitions, éventuellement le nombre d'items répétés et la liste des items répétés. Enfin, l'item peut ne pas être précisé, comme représenté enréférence 159. La Figure 2 est donnée à titre d'exemple non limitatif. La structure 20 peut, en effet, être modifiée en vue d'être adaptée à des cas particuliers de réalisation ou de façon à la rendre plus générale. Comme indiqué précédemment, le langage de balisage permet de structurer des données de façon hiérarchique. Ainsi, la Figure 3 présentant un exemple simple d'un document 25 contenant des données hiérarchisées écrit en langage XML comprend une pluralité d'éléments XML appelés aussi noeuds, par exemple , , qui comprennent chacun au moins un item enfant, l'item enfant étant soit un noeud soit une donnée d'information. Ces données d'information peuvent être du texte, comme dans l'exemple, mais aussi des commentaires, des instructions de 30 traitement ou d'autres composants XML. Ce document contient 17 éléments. L'élément racine, possédant l'identifiant liste , est délimité par la balise ouvrante et la balise 2907568 15 fermante , et comprend quatre items enfants de type élément XML et ayant pour nom employé qui sont eux-mêmes des noeuds. Les éléments employé contiennent eux-mêmes d'autres éléments comme prénom , nom et ville . 5 Il est à noter que l'on appelle élément XML l'ensemble constitué d'une balise ouvrante, du contenu de la balise et de la balise fermante. Par ailleurs, les balises XML et leur hiérarchie constituent la description structurelle des données du document XML. Dans cet exemple, un motif structurel dont la référence est `liste' peut 10 être associé à l'élément principal correspondant au noeud . Ce motif structurel a pour identifiant liste et comprend le nombre d'items dans ce noeud, à savoir la valeur 4. Il comprend également la description des éléments contenus dans le noeud , sous la forme de quatre références à d'autres motifs structurels. 15 Les quatre éléments employés possèdent la même structure, à savoir un attribut département et trois éléments , et . Ils peuvent être associés à un même motif structurel `employé'. Ce motif structurel a pour identifiant employé et comprend le nombre d'items dans les noeuds employés, à savoir la valeur 4. II comprend également la description 20 des éléments contenus dans le noeud , à savoir un attribut de nom département et trois motifs structurels. Le premier de ces motifs structurels a pour identifiant prénom et comprend un enfant de type texte. Le deuxième de ces motifs structurels a pour identifiant nom et comprend un enfant de type texte. Le troisième de ces motifs structurels a pour identifiant ville et 25 comprend un enfant de type texte. Cependant, on peut remarquer que les trois premiers employés ont tous la même valeur pour l'attribut département , à savoir Image . II est donc possible d'associer à ces trois premiers employés un motif structurel mixte 'employél', qui a la même structure que le motif structurel 'employé', mais qui 30 comprend en outre la valeur Image pour l'attribut département . De même, on peut aussi remarquer que les employés 1, 3 et 4 ont tous la même valeur textuelle pour l'élément , à savoir la valeur 2907568 16 Rennes . II est donc possible d'associer à ces trois employés un motif structurel mixte 'employé2', qui a la même structure que le motif structurel 'employé', mais qui comprend en outre la valeur Rennes pour l'item de type texte compris dans le motif structurel identifié par nom . 5 Enfin, il est possible de combiner ces deux valeurs et d'associer aux employés 1 et 3 un motif structurel mixte 'employé3', qui a la même structure que le motif structurel 'employé', mais qui comprend en outre la valeur Image pour l'attribut département et la valeur Rennes pour l'item de type texte compris dans le motif structurel identifié par nom . 10 Le choix du motif de référence pour chacun des éléments employés dépend de l'application pour laquelle on utilise l'invention. Dans le cas du codage d'un document XML, un motif structurel n'est utilisé comme motif de référence que s'il est associé à un nombre minimum d'éléments XML. Ainsi, dans l'exemple précédent qui ne comporte que peu d'éléments XML, il est 15 avantageux de n'utiliser qu'un seul motif de référence pour les éléments employés, à savoir le motif structurel 'employé'. Par contre, si l'exemple contenait le double d'éléments XML, il serait avantageux d'utiliser deux motifs de référence, l'un correspondant au motif structurel 'employé', l'autre correspondant au motif structurel mixte 'employé3'. 20 La Figure 4 illustre l'algorithme général de génération de motifs de référence et de codage d'un document XML en utilisant des motifs de référence générés. Les motifs de référence servent à représenter les données hiérarchisées de manière optimisée. Ainsi, il n'est pas nécessaire de maintenir 25 des motifs mixtes représentant exactement les différentes structures présentes parmi les données hiérarchisées, mais seulement quelques motifs de référence qui permettent de représenter toutes les structures et les informations de contenu avec un coût réduit. Les données hiérarchisées peuvent être localisées dans un ou 30 plusieurs documents selon les applications. En appliquant les étapes du procédé selon l'invention aux données hiérarchisées de plusieurs documents, les motifs de référence seront optimisés pour représenter les données de tous ces documents. 2907568 17 Cela n'empêche évidemment pas d'utiliser les motifs de référence générés à partir des données d'un document pour représenter les données appartenant à d'autres documents. L'algorithme débute par l'extraction des motifs structurels primaires à 5 partir des données hiérarchisées du document XML (étape 410). Ces motifs sont appelés primaires car ils reprennent les différentes structures des données hiérarchisées. Cette étape consiste en outre à analyser la structure de chaque noeud XML composant le document XML. Le motif structurel primaire ainsi 10 extrait reflète la structure du noeud XML duquel il est extrait. Elle sera décrite ultérieurement en référence à la Figure 6. Un motif structurel primaire représente un ensemble d'informations structurelles relatives à une partie de l'arbre des données. Les informations structurelles peuvent par exemple être : la nature d'un item (noeud ou feuille), le 15 nombre d'items enfants contenus dans un noeud, l'ordre de ces items enfants, le type d'un item, etc. Par analogie avec la représentation en arbre des données hiérarchisées, un motif structurel primaire peut également être représenté sous forme d'une structure arborescente d'informations, notamment d'informations 20 structurelles. Après l'étape 410, l'étape 420 consiste à extraire des données hiérarchisées des informations de contenu, notamment, les valeurs des instances correspondant à chacun des motifs structurels primaires. Cette étape est décrite ci-après en référence à la Figure 7. 25 Puis, l'étape 430 permet de sélectionner les informations de contenu ayant un degré d'utilisation parmi les plus élevés parmi les informations de contenu extraites. A partir de ces informations de contenu sélectionnées, sont générés des motifs mixtes représentant à la fois la structure des noeuds et les informations de contenu les plus utilisées de ces noeuds. Cette étape est 30 décrite ci-après en référence à la Figure 8. L'algorithme se poursuit en associant les motifs mixtes ainsi créés (étape 440). Cette étape permet de détecter les motifs mixtes similaires et de 2907568 18 les associer entre eux. Cette étape sera décrite ultérieurement en référence à la Figure 9. Après l'étape 440, l'étape 450 consiste en la génération des motifs de référence. Cette étape consiste à déterminer à partir des motifs mixtes 5 obtenus, les motifs qui ont un degré d'utilisation élevé. Les motifs mixtes déterminés sont appelés motifs de référence et seront utilisés dans le codage du document XML. Cette étape est décrite ci-après en référence à la Figure 11. Selon un mode de réalisation particulier, lors des étapes 440 et 450, les motifs structurels primaires sont considérés avec les motifs mixtes. Ainsi les 10 motifs de références sont construits à partir de l'ensemble des motifs, aussi bien les motifs structurels primaires que les motifs mixtes, déterminés à partir du document XML. Selon ce mode de réalisation, les motifs structurels primaires sont traités comme des motifs mixtes ne comprenant aucune information de contenu. 15 L'étape suivante (étape 460) consiste à écrire les motifs de référence déterminés dans le fichier dans lequel est codé le document XML. Cette étape est décrite ci-après en référence à la Figure 12. Ensuite, le document XML est codé dans le fichier (étape 470). Pour cela, chaque noeud du document XML est écrit dans le fichier, à l'aide du motif 20 de référence qui lui est associé. Cette étape est décrite ci-après en référence à la Figure 13. Selon un mode de réalisation particulier, les étapes 460 et 470 peuvent former une même étape. En effet, au lieu d'écrire d'une part, l'ensemble des motifs de référence puis d'autre part, l'ensemble des noeuds du 25 document XML, il est possible d'écrire les motifs de référence au fur et à mesure de leur utilisation. Ainsi, avant d'écrire un noeud XML, on vérifie si le motif de référence qui lui est associé a déjà été écrit dans le fichier. Si tel n'est pas le cas, alors le motif de référence est écrit dans le fichier. Selon une autre variante de réalisation additionnelle, les étapes 410 30 et 420 forment une même étape. Dans ce cas, l'extraction des données structurelles et des informations de contenu sont réalisées en parallèle, ce qui permet de ne parcourir qu'une seule fois le document XML. 2907568 19 Après l'étape 470, il est mis fin à l'algorithme. II est maintenant décrit, en référence à la Figure 5, un algorithme général de décodage d'un document XML à partir d'un fichier généré par exemple au moyen de l'algorithme décrit en référence à la Figure 4. 5 L'algorithme débute à l'étape 510 par la lecture des motifs de référence. Cette étape permet d'obtenir l'ensemble des motifs de référence utilisés pour coder les noeuds du document XML. Cette étape est décrite ci-après en référence à la Figure 14. L'étape 510 est suivie de l'étape 520 au cours de laquelle on lit les 10 noeuds du document XML. Pour ce faire, on utilise les motifs de référence lus à l'étape 510. Cette étape permet de reconstruire les noeuds du document XML et donc l'ensemble du document XML. Cette étape est décrite ci-après en référence à la Figure 15. Selon une variante de réalisation, les étapes 510 et 520 forment une 15 seule étape dans laquelle l'algorithme lit les motifs de référence et les noeuds du document XML au fur et à mesure de leur apparence dans le fichier. II est à noter que les motifs de référence lus à l'étape 510 peuvent comprendre ou non des informations de contenu. Après cette étape, il est mis fin à l'algorithme. 20 II est maintenant décrit en référence à la Figure 6 un d'algorithme permettant la création d'un motif structurel primaire m à partir d'un élément XML e d'un document XML (étape 600). Un motif structurel primaire est un ensemble de données reflétant la structure d'un noeud, la structure étant décrite au moyen des informations 25 structurelles comprises dans le document XML. En particulier, cette structure détermine les types des items enfants de ce noeud. Selon un mode de réalisation, un motif structurel primaire est décrit selon le format de motif décrit précédemment en référence aux Figures 1 et 2. L'algorithme de la Figure 6 est exécuté de manière récursive en 30 partant de l'élément racine du document XML. Ainsi, la procédure débute à l'étape 600 avec l'élément racine. 2907568 20 Lors de l'étape 605, un item enfant s de l'élément XML e est sélectionné. Il est à noter que les attributs d'un élément XML sont considérés comme des items enfants de celui-ci. L'étape 605 est suivie d'un test effectué à l'étape 610 afin de 5 déterminer si l'item enfant s est lui-même un élément XML ou pas. Dans le cas d'un résultat négatif pour le test de l'étape 610, c'est-à-dire si l'item enfant s sélectionné n'est pas un élément, alors l'algorithme se poursuit à l'étape 640 au cours de laquelle on considère que l'item enfant est alors une donnée d'information. Dans ce cas, le type de l'item enfant s est 10 ajouté au motif structurel primaire m. Cette étape est suivie de l'étape 650 au cours de laquelle on vérifie s'il existe un autre item enfant s à traiter ou non. De retour à l'étape 610, dans le cas d'un résultat positif, c'est-à-dire si l'item est lui-même un élément XML, la procédure d'extraction de motif pour cet 15 item enfant est une nouvelle fois appelée (étape 615). L'étape 615 est suivie de l'étape 620 consistant à vérifier au moyen d'un test si l'item enfant s contient des éléments XML. Si l'item enfant s ne contient pas d'élément XML, alors l'étape 620 est suivie de l'étape 625 au cours de laquelle le contenu du motif structurel 20 primaire ms est ajouté au motif structurel primaire m. Ainsi, la description de l'item enfant s se retrouve dans le motif structurel primaire m. L'algorithme se poursuit alors à l'étape 650. Dans le cas contraire, l'étape 620 est suivie de l'étape 630 consistant à ajouter au motif structurel primaire m une référence au motif structurel 25 primaire ms ainsi extrait. L'étape 630 est suivie de l'étape 650. L'étape 650 consiste à vérifier s'il existe un autre item enfant s à traiter ou non. S'il reste au moins un autre item enfant à traiter, alors l'algorithme se 30 poursuit à l'étape 605 précédemment décrite, de manière à traiter l'item enfant suivant. 2907568 21 Dans le cas contraire, l'algorithme se termine à l'étape 660 et retourne le motif structurel primaire associé à l'élément XML e. Selon un mode de réalisation, avant de retourner le motif structurel primaire ainsi créé, on vérifie si ce motif structurel primaire existe déjà. 5 Si tel est le cas, le motif structurel primaire existant est associé à l'élément XML e et est retourné, tandis que le motif structurel primaire nouvellement créé est supprimé. Si tel n'est pas le cas, le motif structurel primaire nouvellement créé est associé à l'élément XML e et est retourné. 10 Ceci permet d'avoir un même motif structurel primaire pour deux éléments XML ayant la même structure. Selon un autre mode de réalisation, avant de créer un motif structurel primaire associé à un élément XML e, on vérifie si un motif structurel primaire existant peut être associé à l'élément XML e. 15 Si tel est le case, le motif structurel primaire existant est associé à l'élément XML e et est retourné. Si tel n'est pas le cas, un motif structurel primaire est créé et est associé à l'élément XML e. L'algorithme de la Figure 6 permet d'inclure un motif structurel 20 primaire directement dans la description d'un autre motif structurel primaire ou permet de l'inclure par référence. On notera avec intérêt l'exemple illustrant l'inclusion d'un motif structurel primaire dans un autre motif structurel primaire, à savoir le motif structurel primaire décrivant un employé . En effet, les motifs structurels 25 primaires correspondant aux noeuds , et peuvent être insérés dans le motif structurel primaire de l'item employé , les noeuds , et représentant les données d'informations qui sont des feuilles de la hiérarchie. Dans l'exemple considéré, le motif structurel primaire 'employé' 30 inclus un motif structurel primaire décrivant les noeuds , et . 2907568 22 La Figure 7 illustre un algorithme d'extraction des valeurs liées aux motifs structurels primaires correspondant à l'étape 420 de la Figure 4. Pour ce faire, la Figure 7 décrit l'obtention des listes de valeurs des instances associées à chacun des motifs structurels primaires extraits 5 conformément à l'invention. Une liste de valeurs est une liste ordonnée contenant l'ensemble des valeurs contenues dans un noeud du document XML et dans certains de ses enfants, dans leur ordre d'apparition. Ainsi pour le premier employé de l'exemple illustré en Figure 3, la liste des valeurs est : [Image, Jean, Dupont, Rennes]. 10 L'algorithme de la Figure 7 commence à l'étape 700 par la sélection d'un noeud N du document. L'étape 710 est suivie de l'étape 720 au cours de laquelle à partir de ce noeud N, on extrait la liste L des valeurs contenues dans ce noeud. Cette liste comprend la valeur des attributs, le contenu textuel, le contenu des 15 commentaires ou des instructions de traitement ( Processing Instructions en terminologie anglo-saxonne). L'étape suivante 720 permet d'obtenir le motif structurel primaire M associé au noeud N. Ensuite, lors de l'étape suivante (étape 730), on vérifie si la liste L est 20 déjà associée à ce motif structurel primaire M. Si tel est le cas, alors l'algorithme se poursuit à l'étape 740 au cours de laquelle il augmente le nombre d'occurrences de la liste L pour le motif structurel primaire M de la valeur 1. Si la liste L n'est pas associée au motif structurel primaire M, alors 25 l'algorithme se poursuit à l'étape 750 au cours de laquelle il ajoute la liste L à l'ensemble des valeurs associées au motif structurel primaire M, avec un nombre d'occurrences égal à la valeur 1. Les étapes 740 et 750 sont suivies de l'étape 760 au cours de laquelle on vérifie s'il reste d'autres noeuds à traiter. 30 Si tel est le cas, l'algorithme se poursuit en effectuant de nouveau les étapes 700 à 750. Sinon, il est mis fin à l'algorithme à l'étape 770. 2907568 23 A la fin de cet algorithme, à chaque motif structurel primaire M est associé un ensemble de liste de valeurs avec le nombre d'occurrences pour chacune de ces listes. Dans certains documents XML, la valeur d'un attribut ou le contenu 5 textuel d'un élément varie peu ou pas du tout pour l'ensemble du document. Par exemple, pour une liste de personnes comprenant le titre de chaque personne dans un attribut titre , par exemple mademoiselle, monsieur ou madame, cet attribut ne peut prendre que trois valeurs. Selon un mode de réalisation, la valeur de cet attribut ou le contenu 10 textuel de l'élément pour chaque instance n'est pas codée séparément. Cette valeur ou ce contenu est codé directement au niveau d'un motif. Dans l'exemple précédent, il est codé trois motifs pour représenter les personnes, correspondant respectivement aux trois valeurs de l'attribut 15 titre . La Figure 8 décrit un algorithme conforme à l'invention pour déterminer les valeurs ayant le degré d'utilisation parmi les plus élevés dans les instances de chaque motif structurel primaire afin de créer des motifs mixtes représentant à la fois la structure d'un noeud et une partie de son contenu. 20 Cet algorithme permet de déterminer les valeurs des degrés d'utilisation les plus élevées pour un motif structurel primaire m donné (étape 800). L'algorithme débute à l'étape 830 par la sélection de la liste de valeur L ayant le plus grand nombre d'occurrences. 25 L'étape 830 est suivie de l'étape 840 au cours de laquelle on teste si la liste L a un nombre d'occurrences supérieur à une valeur limite prédéfinie. Dans le cas positif, l'algorithme se poursuit à l'étape 850 au cours de laquelle on crée un motif mixte pour lequel certaines valeurs sont fixées. Pour ce faire, l'algorithme crée un nouveau motif identique au motif 30 structurel primaire m. Puis, pour chaque valeur de la liste L, on ajoute au motif structurel les valeurs de contenu définies par la liste L. Ce motif nouvellement créé est un motif structurel mixte qui décrit à la fois la structure de noeuds du 2907568 24 document XML et une partie de leur contenu. En outre, la liste L est supprimée de l'ensemble des listes du motif structurel primaire m. Ensuite, l'algorithme se poursuit à l'étape 830, en sélectionnant une nouvelle liste L. 5 Si lors de l'étape 840, le test est négatif, c'est-à-dire si la liste L n'a pas un nombre d'occurrences supérieur à une valeur limite prédéfinie, alors l'algorithme se poursuit à l'étape 860 au cours de laquelle on compte le nombre de listes restantes et on teste si ce nombre est ou non supérieur à un seuil prédéterminé. 10 Si le nombre de listes n'est pas supérieur à un seuil prédéterminé alors il est mis fin à l'algorithme à l'étape 895. Dans le cas contraire, l'algorithme se poursuit à l'étape 870 au cours de laquelle pour chaque valeur, on compte le nombre d'occurrences de cette valeur à la même position dans l'ensemble des listes. 15 L'étape 870 est suivie de l'étape 880 au cours de laquelle l'algorithme sélectionne la valeur la moins fréquente à une position donnée. L'ensemble des listes est alors modifié en supprimant cette valeur de toutes les listes où cette valeur apparaît à cette position. A l'issue de cette étape, une liste contient pour chaque position soit une valeur, soit un contenu 20 vide. Ainsi, la liste pour le premier élément de l'exemple considéré illustré en Figure 3, est pour commencer : [Image, Jean, Dupont, Rennes]. Etant donné que la valeur Jean n'apparaît qu'une seule fois en deuxième position, cette valeur est l'une des valeurs les moins fréquentes et va être supprimée. Après 25 cette suppression, la liste pour le premier élément devient : [Image, ", Dupont, Rennes]. L'étape 880 se poursuit à l'étape 890 au cours de laquelle on regroupe les listes identiques. Ensuite, l'algorithme se poursuit à l'étape 830 précédemment décrite. 30 Il est à noter que si aucune valeur n'a une fréquence supérieure à la valeur limite, aucun motif mixte ne sera créé à partir du motif structurel primaire m. 2907568 25 Selon un mode de réalisation particulier, on détermine, avant d'appliquer l'algorithme décrit en référence à la Figure 8 les valeurs constantes pour l'ensemble des noeuds associées au motif structurel primaire m. Si de telles valeurs existent, le motif structurel primaire m est remplacé par un motif 5 structurel mixte créé à partir de ce motif structurel primaire m en ajoutant ces valeurs constantes. En outre, ces valeurs ne seront pas reprises dans les listes obtenues à l'étape 810 de la Figure 8. La Figure 9 présente un exemple de mise en oeuvre de l'étape 440 du procédé de la Figure 4 pour grouper les motifs mixtes similaires entre eux. 10 L'algorithme débute à l'étape 900. Après cette étape, un motif mixte quelconque M est sélectionné (étape 910) parmi l'ensemble des motifs mixtes déterminés précédemment, selon les étapes 410, 420 et 430 de l'algorithme de la Figure 4 par exemple. Ce motif mixte M va être comparé à l'ensemble des motifs mixtes 15 pour déterminer s'il est proche d'autres motifs mixtes. Pour cela, une notion de distance est utilisée. Cette notion de distance est liée au système de codage des motifs : le motif mixte M est proche d'un autre motif mixte, si cet autre motif mixte peut être codé efficacement en fonction de ce motif mixte M. Selon un mode de réalisation, une notion de distance intéressante 20 est le cas où le motif mixte M englobe un autre motif mixte. Ainsi cet autre motif mixte peut être codé uniquement en décrivant les éléments du motif mixte M qu'il ne reprend pas. Cet exemple de distance est décrit en référence à la Figure 10. Selon un autre mode de réalisation, la notion de distance n'impose 25 pas que l'un des motifs mixtes englobe l'autre. Dans un tel cas, l'algorithme de calcul de la distance prend en compte aussi bien les suppressions que les ajouts d'informations structurelles entre les motifs mixtes pour évaluer la distance entre ces motifs mixtes. Selon une variante de réalisation de ce mode de réalisation, si deux 30 motifs mixtes sont proches, mais qu'aucun des deux n'englobe l'autre, un troisième motif mixte englobant ces deux motifs mixtes est créé et les deux 2907568 26 motifs mixtes sont codés (s'ils sont conservés comme motif de référence) en fonction de ce motif mixte englobant. Pour réaliser ces comparaisons, lors de l'étape 920, on sélectionne un motif structurel mixte N, différent du motif mixte M. 5 L'étape suivante (étape 940) consiste à calculer la distance d entre les motifs mixtes M et N. Un exemple de calcul de distance est décrit ultérieurement en référence à la Figure 10. Le résultat de ce calcul est affecté à la variable d. Cette distance d est ensuite comparée à la valeur d'une variable d(N) 10 représentant la distance entre le motif mixte N et le motif mixte le plus proche, lors de l'étape 950. Cette variable d(N) est initialisée au départ à une valeur très grande. Si les motifs mixtes M et N sont suffisamment proches, c'est-à-dire si la distance d est inférieure à la valeur de la variable d(N), alors l'algorithme se 15 poursuit à l'étape 960, sinon il se poursuit directement à l'étape 970. Dans l'étape 960, le motif mixte M qui a été identifié comme suffisamment proche du motif mixte N par le calcul de la distance, est affecté à la variable ref(N) qui représente le motif mixte le plus proche du motif mixte N. De plus, la variable d(N) prend la valeur de la variable d. 20 L'algorithme se poursuit à l'étape 970. L'étape 970 consiste à vérifier au moyen d'un test s'il existe un autre motif mixte qui n'a pas été comparé au motif mixte M. Si le test est positif, l'algorithme retourne à l'étape 920 pour la sélection d'un nouveau motif mixte N. Sinon, l'algorithme continue à l'étape 980. 25 L'étape 980 consiste à vérifier au moyen d'un test s'il existe encore un autre motif mixte M qui n'a pas été traité. Si le test est positif, l'algorithme continue à l'étape 910 pour la sélection d'un nouveau motif mixte M. Sinon, l'algorithme se termine à l'étape 990. A l'issue de cet algorithme, chaque motif mixte est associé au motif 30 mixte le plus proche de lui. Selon un mode de réalisation particulier, lors de l'étape 910, l'algorithme sélectionne aussi les motifs structurels primaires. Ainsi, lors de la 2907568 27 création des motifs de référence, si aucun motif mixte n'est choisi pour être un motif de référence, le motif structurel primaire peut être choisi comme motif de référence. Ainsi, dans l'exemple, cette étape permet d'associer au motif mixte 5 `employé3', le motif mixte 'employé2', d'associer au motif mixte `employé2' le motif structurel 'employé', et d'associer au motif mixte 'employél' le motif structurel 'employé'. La Figure 10 représente un algorithme permettant de calculer la distance entre deux motifs mixtes M et N (étape 1000). Selon cet algorithme, on 10 considère que le motif mixte M englobe le motif mixte N, c'est-à-dire que le motif mixte M comprend l'ensemble des items enfant du motif mixte N. Si ce n'est pas le cas, la distance entre les motifs mixtes M et N est considérée comme infinie. Par contre, aucune condition n'est imposée sur les valeurs de contenu comprises dans les motifs mixtes M et N. 15 II est à noter que cet algorithme de calcul de distance entre deux motifs mixtes M et N n'est pas symétrique : généralement, il ne retourne pas le même résultat si l'ordre des deux motifs mixtes M et N est inversé. Le résultat de cet algorithme est mémorisé dans une variable distance, initialisée à la valeur 0. 20 Il est à noter que la distance permet de mesurer, de manière quantitative, la similarité entre deux descriptions structurelles. Lorsque deux motifs mixtes sont proches, cela veut dire qu'un motif mixte peut être remplacé par l'autre dans la description des données qui leur sont associées. La distance entre deux motifs mixtes est très grande, voire infinie, si les25 deux motifs mixtes ne correspondent pas à des éléments XML ayant une structure similaire. On notera que la distance utilisée dépend de l'application envisagée. De même, la limite utilisée pour comparer cette distance dépend de l'application envisagée et de la distance utilisée. 30 L'algorithme débute par une étape 1005 au cours de laquelle on teste s'il reste un item A du motif mixte M à traiter. 2907568 28 Dans la négative, l'algorithme se termine à l'étape 1010 et retourne la valeur de la variable distance. Dans l'alternative positive du test, l'algorithme se poursuit à l'étape 1015 au cours de laquelle on teste s'il reste un item B du motif mixte N à traiter. 5 S'il ne reste aucun item à traiter, alors l'algorithme se poursuit à l'étape 1020 au cours de laquelle la valeur de la variable distance est incrémentée de la valeur 1. Ensuite, l'étape 1020 est suivie de l'étape 1005 précédemment décrite. Si, au contraire il reste un item à traiter, alors l'étape 1015 est suivie 10 de l'étape 1025 au cours de laquelle on teste si l'item A du motif mixte M et l'item B du motif mixte N sont tous deux des motifs, c'est-à-dire correspondant notamment à la forme précédemment décrite à l'appui de la Figure 2, référence 155. Si tel est le cas, l'algorithme se poursuit à l'étape 1050 décrite ci- 15 après. Si ce n'est pas le cas, alors l'algorithme se poursuit à l'étape 1030 qui vérifie si les items A et B sont similaires. Selon un mode de réalisation, cette vérification consiste à vérifier, d'une part, que les items A et B sont de même type et, si les items A et B 20 correspondent à des attributs, c'est-à-dire sont de la forme précédemment décrite à l'appui de la Figure 2, référence 151, que les identifiants des items A et B sont identiques. Si la vérification est négative, alors l'algorithme se poursuit à l'étape 1035 au cours de laquelle la valeur de la variable distance est incrémentée de 25 la valeur 1. Ensuite, l'algorithme se poursuit à l'étape 1005 précédemment décrite. En outre dans ce cas, l'item B du motif mixte N reste à traiter. Si la vérification est positive, alors l'algorithme se poursuit à l'étape 1040 au cours de laquelle on vérifie si les items A et B ont des valeurs fixées similaires. Si seul l'un des items A ou B a une valeur fixée, ils sont considérés 30 comme ayant des valeurs différentes. Dans le cas positif, l'algorithme se poursuit à l'étape 1005 précédemment décrite. 2907568 29 Si la vérification est négative, l'algorithme se poursuit à l'étape 1045 au cours de laquelle la valeur de la variable distance est incrémentée de la valeur 1. Puis, l'algorithme se poursuit à l'étape 1005 précédemment décrite. De retour à l'étape 1050, l'algorithme vérifie si les identifiants des 5 deux motifs mixtes A et B sont similaires. Dans le cas positif, l'algorithme se poursuit à l'étape 1060 au cours de laquelle l'algorithme calcule la distance entre les motifs mixtes des items A et B. Pour ce faire, cette étape appelle récursivement l'algorithme de 10 calcul de distance sur ces deux motifs mixtes. Le résultat de cet appel est ajouté à la valeur de la variable distance. L'algorithme se poursuit alors à l'étape 1005 précédemment décrite. Si lors de l'étape 1050 les deux motifs mixtes des items A et B ne sont pas similaires, alors l'algorithme se poursuit à l'étape 1055 au cours de 15 laquelle la valeur de la variable distance est incrémentée de la valeur de la taille du motif mixte de l'item A. Selon un mode de réalisation, la taille du motif mixte de l'item A est le nombre d'items contenus dans le motif de l'item A incrémenté de la valeur 1. En outre, l'item B reste à traiter. L'algorithme se poursuit à l'étape 1005 20 précédemment décrite. Dans une variante de réalisation, les poids des divers types de différences peuvent être modifiés, en particulier aux étapes 1020, 1035, 1045 et 1055, pour modifier l'importance relative de ces types de différences. Dans une autre variante de réalisation, dans le cas d'une différence 25 portant sur une valeur de contenu, la modification de la distance réalisée à l'étape 1045 dépend du type de cette différence, à savoir s'il s'agit d'une suppression de valeur de contenu, de son ajout ou de sa modification. La Figure 11 décrit un algorithme de sélection des motifs de référence (étape 1100) conforme à l'invention. Cet algorithme correspond à 30 l'étape 450 de l'algorithme décrit en référence à la Figure 4. Cet algorithme, permet de sélectionner, parmi l'ensemble des motifs mixtes extraits du document XML, ceux qui serviront pour le codage du document XML. 2907568 30 L'algorithme commence à l'étape 1110 par initialiser, pour chaque motif mixte, le nombre de noeuds associés à ce motif mixte. Pour un motif mixte M, le nombre de noeuds qui lui sont associés est représenté par la variable i(M). Dans la pratique, le nombre de noeuds associés à un motif mixte est 5 calculé lors de la création des motifs mixtes tel qu'illustré notamment à l'étape 430 de la Figure 4 et décrit en référence à la Figure 8, et lors de leur groupement tel qu'illustré notamment à l'étape 440 de la Figure 4 et décrit en référence à la Figure 9. L'algorithme se poursuit à l'étape 1120 par l'obtention du motif mixte 10 M le moins utilisé, c'est-à-dire ayant un degré d'utilisation parmi les moins élevés. Selon un mode de réalisation, cette étape consiste à parcourir l'ensemble des motifs mixtes pour trouver celui dont la valeur i(M) est la plus petite. 15 Ensuite, l'algorithme se poursuit à l'étape 1130 au cours de laquelle on compare le nombre de noeuds associés au motif mixte M, c'est-à-dire la valeur de la variable i(M) à une valeur limite prédéterminée. Si la valeur de la variable i(M) est supérieure ou égale à cette valeur limite, alors, l'algorithme se termine à l'étape 1170. 20 Si ce n'est pas le cas, on considère que le motif mixte M est trop peu utilisé pour être intéressant et permettre un codage efficace des noeuds XML qui lui sont associés. Le motif mixte M n'est donc pas utilisé comme motif de référence. Pour cela, l'algorithme vérifie lors de l'étape 1140 s'il existe un motif 25 mixte englobant M, c'est-à-dire si la variable ref(M) contient une référence à un autre motif. Si tel n'est pas le cas, l'algorithme se poursuit à l'étape 1150 au cours de laquelle on supprime le motif mixte M. Cette suppression consiste en particulier à supprimer les associations entre les noeuds du document XML et 30 ce motif mixte M. L'algorithme se poursuit alors à l'étape 1120 précédemment décrite. 2907568 31 Dans le cas contraire, c'est-à-dire s'il existe un motif mixte englobant, alors l'algorithme se poursuit à l'étape 1160 au cours de laquelle le motif mixte M est remplacé par ce motif mixte englobant, c'est-à-dire le motif mixte ref(M). Pour ce faire, l'algorithme associe au motif mixte ref(M) tous les 5 noeuds associés au motif mixte M. En outre, pour tenir compte de cette modification, la valeur de la variable i(ref(M)) est augmentée de la valeur de la variable i(M). Enfin, s'il existe d'autres motifs mixtes dont le motif mixte englobant associé est le motif mixte M, pour ces autres motifs mixtes, le motif englobant associé est modifié pour 10 devenir la valeur de la variable ref(M). L'algorithme se poursuit ensuite à l'étape 1120 décrite précédemment. A l'issue de cet algorithme, tous les motifs mixtes qui n'ont pas été supprimés forment les motifs de référence qui vont être utilisés pour encoder le 15 document XML. La Figure 12 décrit un algorithme d'écriture d'un motif de référence M (étape 1200). Cet algorithme permet d'écrire la définition d'un motif de référence dans le fichier où est codé le document XML. L'algorithme commence à l'étape 1205 par vérifier si le motif de 20 référence M possède un motif de mixte englobant associé. Selon un mode de réalisation, on teste si la variable ref(M) est définie. Dans le cas positif, l'algorithme se poursuit à l'étape 1270 consistant à écrire le motif de référence M par référence à la variable ref(M). Cette étape 25 sera décrite ci-après. Si, au contraire, le motif de référence M ne possède pas de motif de référence englobant, alors l'algorithme se poursuit à l'étape 1210 pour écrire le motif de référence M intégralement. Pour cela, l'algorithme commence, à l'étape 1210, par écrire la 30 définition du motif mixte de référence M. En premier lieu, un index est généré pour le motif de référence et est écrit. 2907568 32 Ensuite, le nom du motif tel que précédemment décrit à l'appui de la Figure 2, référence 111, est écrit, ainsi que le nombre d'items qu'il comporte (voir figure 2, référence 112). La suite de l'algorithme permet d'écrire l'ensemble des items 5 contenus dans le motif de référence. Pour cela, l'algorithme se poursuit à l'étape 1220 au cours de laquelle on vérifie s'il reste un item K du motif de référence qui n'a pas encore été traité. S'il n'y a plus d'item à traiter, alors l'algorithme se termine à l'étape 10 1230. Si au contraire, il reste encore un item à traiter, alors l'algorithme se poursuit à l'étape 1240 consistant à écrire le type de l'item K. En outre, si l'item K est un attribut, alors l'identifiant de l'attribut est aussi écrit. Ensuite, l'étape 1240 est suivie de l'étape 1250 au cours de laquelle 15 on vérifie si l'item K est un motif, c'est-à-dire notamment de la forme précédemment décrite à l'appuie de la Figure 2, référence 155. Si l'item K est un motif alors l'algorithme se poursuit à l'étape 1255 au cours de laquelle l'item K est écrit comme un motif en appelant récursivement l'algorithme. 20 La seule différence est que le motif mixte correspondant à l'item K étant inclus dans un autre motif, il n'a pas d'index associé et ne peut être défini par référence. L'algorithme se poursuit ensuite à l'étape 1220 précédemment décrite. 25 Si lors de l'étape 1250, l'item K n'a pas été identifié comme un motif, alors l'étape 1250 est suivie de l'étape 1260, au cours de laquelle on vérifie si l'item K a une valeur fixée. Dans la négative, l'algorithme se poursuit à l'étape 1220 précédemment décrite. 30 Si l'item K a une valeur fixée, alors l'algorithme se poursuit à l'étape 1265 au cours de laquelle on écrit la valeur de l'item K. L'algorithme se poursuit ensuite à l'étape 1220 précédemment décrite. 2907568 33 De retour à l'étape 1270, l'algorithme écrit la définition de motif de référence M en fonction de son motif englobant ref(M). Pour ce faire, il est nécessaire que le motif mixte ref(M) ait déjà été écrit. 5 Si tel n'est pas le cas, alors ce motif mixte est écrit préalablement à l'écriture du motif de référence M. Pour écrire la définition du motif de référence M, en premier lieu, un index est généré pour ce motif et est écrit. Ensuite, l'index du motif de référence ref(M) est écrit. 10 Enfin, le nombre de différences entre le motif de référence M et le motif mixte ref(M) est écrit. L'algorithme se poursuit ensuite à l'étape 1280 au cours de laquelle on vérifie s'il reste une différence D non traitée. Si ce n'est pas le cas, l'algorithme se termine à l'étape 1230. 15 Sinon, l'algorithme se poursuit à l'étape 1290 par l'écriture de cette différence D. Selon un mode de réalisation, cette différence D est la suppression de l'un des items du motif mixte ref(M) ou l'ajout, la suppression ou la modification d'une valeur fixée. Pour la suppression d'un item, l'écriture de cette 20 différence se réduit à l'écriture de la position dans le motif mixte ref(M) de l'item supprimé. Pour la suppression d'un item du motif mixte, l'écriture de cette différence consiste à écrire la position de l'item supprimé. Pour la suppression d'une valeur fixée, l'écriture de cette différence 25 consiste à écrire la position de la valeur supprimée. Pour l'ajout ou la modification d'une valeur fixée, l'écriture consiste à écrire la position de la valeur ajoutée ou modifiée, ainsi que cette valeur. L'algorithme se poursuit ensuite à l'étape 1280 précédemment décrite. 30 Selon une variante de réalisation, il est possible d'écrire un motif de référence M par différence par rapport à un motif de référence englobé E. Dans 2907568 34 ce cas, l'écriture d'une différence consiste à écrire un item ajouté au motif de référence E. Pour cela, on écrit la position d'ajout dans le motif de référence E de l'item, ainsi que la définition de l'item tel que décrit en référence aux étapes 5 1240 à 1260 de la Figure 12. Pour écrire l'ensemble des motifs de référence générés à l'étape 430 de la Figure 4, l'algorithme décrit en référence à la Figure 12 est utilisé pour chacun de ces motifs de référence. Selon un autre mode de réalisation, le codage des motifs de 10 référence est réalisé en utilisant des méta-motifs. Dans la pratique, l'algorithme de détermination des motifs de référence est appliqué aux données hiérarchisées constituées par les motifs de référence. Dans ces données hiérarchisées, les informations structurelles correspondent aux items décrivant les motifs de référence, à leurs types et à leur organisation hiérarchique, tandis 15 que les informations de contenu correspondent aux noms et identifiants des items ainsi qu'à leurs éventuelles valeurs de contenu. Cet autre mode de réalisation permet de coder deux motifs représentant des structures similaires de par l'organisation hiérarchique des noeuds qu'elles représentent, mais différentes au niveau des identifiants 20 associés à ces noeuds en réduisant la taille de ce codage. Dans cet autre mode de réalisation, le codage des méta-motifs est réalisé selon l'algorithme décrit en référence à la Figure 12, tandis que le codage des motifs de référence est réalisé selon l'algorithme décrit en référence à la Figure 13, à l'aide de ces méta-motifs. 25 La Figure 13 décrit un algorithme conforme à l'invention d'écriture d'un noeud N du document XML (étape 1300). Cet algorithme n'est utilisé que pour les noeuds associés à un motif de référence. Pour écrire un noeud qui n'est pas associé à un motif de référence, on utilise une méthode connue. Par exemple un tel noeud est écrit directement 30 en utilisant la syntaxe XML ou en utilisant la syntaxe Fastlnfoset (définit dans la spécification ITU-T Rec. X.891). Ces méthodes connues sont modifiées pour pouvoir intégrer l'écriture de noeuds XML conformément à l'invention. Puis, pour 2907568 chaque item enfant du noeud, si cet item enfant n'est pas un noeud XML, il est écrit en utilisant la même méthode connue. Par contre, si cet item enfant est un noeud XML, on vérifie s'il est associé à un motif de référence. Si tel est le cas, ce noeud est écrit en utilisant 5 l'algorithme décrit en référence à la Figure 13. Sinon, ce noeud est lui-même écrit en utilisant la même méthode connue. En pratique, pour écrire l'ensemble des noeuds du document XML, on commence par écrire le noeud racine du document. Dans le cas d'un noeud associé à un motif de référence, l'algorithme 10 commence à l'étape 1305 par obtenir le motif de référence associé M. Puis l'algorithme écrit l'index de ce motif de référence M lors de l'étape suivante (étape 1310). L'algorithme se poursuite par l'étape 1315 au cours de laquelle on vérifie s'il reste une différence D entre la structure de ce noeud et le motif de 15 référence M. S'il reste une différence, l'algorithme se poursuit à l'étape 1320 consistant à écrire cette différence D. Selon un mode de réalisation, l'écriture de cette différence est réalisée comme décrit en référence à la Figure 12. 20 L"algorithme se poursuit ensuite à l'étape 1315 précédemment décrite. Si au contraire, il ne reste plus de différence, alors l'algorithme se poursuit à l'étape 1325 au cours de laquelle on vérifie s'il reste un item K non traité du motif mixte associé au motif mixte N. 25 Si tel n'est pas le cas, il est mis fin à l'algorithme à l'étape 1350. Dans le cas contraire, l'algorithme se poursuit à l'étape 1330 au cours de laquelle on vérifie si le type de l'item K correspond à un type ayant une valeur c'est-à-dire notamment si le type de l'item K correspond à un attribut, une valeur textuelle, un commentaire ou une instruction de traitement. 30 En outre, l'algorithme vérifie si le motif de référence M fixe cette valeur, et, si tel est le cas alors l'algorithme vérifie si la valeur de l'item K est identique à la valeur fixée. 2907568 36 Si tel n'est pas le cas, l'algorithme se poursuit à l'étape 1335 et obtient cette valeur à partir du noeud N et l'écrit. Ainsi, la valeur d'un item K d'un noeud N n'est écrite que si cette valeur n'est pas définie par le motif de référence du noeud N ou si cette valeur 5 est définie par le motif de référence du noeud N mais avec une valeur différente. L'étape 1335 est suivie de l'étape 1340 au cours de laquelle on vérifie si l'item K correspond à une référence à un motif de référence. De même à l'étape 1330, lors d'un test négatif, l'algorithme se poursuit à l'étape 1340. 10 Si le test de l'étape 1340 est négatif alors l'algorithme se poursuit à l'étape 1325 précédemment décrite. Si le test est positif, l'algorithme se poursuit à l'étape 1345 au cours de laquelle on obtient le noeud correspondant à l'item K à partir du noeud N et celui-ci est écrit. 15 Si ce noeud est associé à un motif de référence, il est écrit en utilisant l'algorithme de la Figure 13, sinon, il est écrit en utilisant une méthode connue tel que décrit précédemment. La Figure 14 décrit un algorithme conforme à l'invention pour lire un motif de référence M écrit en utilisant l'algorithme décrit en référence à la Figure 20 12. Cet algorithme commence à l'étape 1405 par déterminer si le motif de référence M est décrit par référence ou intégralement. Si le motif de référence M est décrit par référence, l'algorithme se poursuit à l'étape 1450 décrite ci-après. 25 Sinon, l'algorithme se poursuit à l'étape 1410 par la lecture de la définition du motif mixte. Cette définition comprend l'index associé au motif mixte, le nom du motif tel que précédemment décrit à l'appui de la Figure 2, référence 111, et le nombre d'éléments qu'il comporte tel que précédemment décrit à l'appui de la Figure 2, référence 112. 30 L'algorithme se poursuit à l'étape 1415, au cours de laquelle l'algorithme crée une structure pour représenter le motif mixte. 2907568 37 Selon un mode de réalisation, cette structure est celle décrite en référence aux Figures 1 et 2. Le nom du motif mixte et le nombre d'items que comporte ce motif sont mémorisés dans cette structure. L'algorithme se poursuit à l'étape 1420 au cours de laquelle on 5 détermine s'il reste un item K du motif structurel mixte à lire. Dans la négative, l'algorithme se termine à l'étape 1480. S'il reste un item à lire, alors l'algorithme se poursuit à l'étape 1425 au cours de laquelle on lit le type de l'item K. Si cet item est un attribut, alors l'algorithme lit aussi l'identifiant de 10 cet attribut. En outre, l'algorithme vérifie si cet item a une valeur fixée. Si tel est le cas, l'algorithme lit cette valeur. Ensuite, l'algorithme se poursuit à l'étape 1430 au cours de laquelle on ajoute l'item K et son éventuelle valeur à la structure représentant le motif 15 mixte. Puis, l'étape 1430 est suivie de l'étape 1435 au cours de laquelle on vérifie si l'item K est un motif tel que précédemment décrit à l'appui de la Figure 2, référence 155. Si le test est négatif, alors l'algorithme se poursuit à l'étape 1420 20 précédemment décrite. Dans le cas contraire, c'est-à-dire si l'item K est un motif, alors l'algorithme se poursuit à l'étape 1440 au cours de laquelle on lit le motif de l'item K. Cette lecture s'effectue en appelant récursivement cet algorithme. La seule différence est que le motif correspondant à l'item K n'a pas d'index 25 associé et ne peut être défini par référence. L'algorithme se poursuit à l'étape 1445 au cours de laquelle on ajoute la structure créée lors de la lecture du motif mixte K à la structure représentant le motif de référence M. Puis l'algorithme se poursuit à l'étape 1420 précédemment décrite. 30 De retour à l'étape 1450, l'algorithme lit la définition du motif de référence M. Ce motif mixte étant défini par référence, la définition comporte l'index associé au motif de référence M, l'index du motif mixte servant de 2907568 38 référentiel pour le codage et le nombre de différences entre le motif de référence M et le motif mixte servant de référentiel. L'algorithme se poursuit à l'étape 1455 par l'obtention du motif mixte servant de référentiel. 5 Puis, l'algorithme à l'étape 1460 crée une structure pour représenter le motif de référence M. Selon un mode de réalisation, cette structure est créée en dupliquant la structure représentant le motif mixte servant de référentiel. L'algorithme se poursuit à l'étape 1465 au cours de laquelle on 10 vérifie s'il reste une différence D non lue. Dans la négative, il est mis fin à l'algorithme à l'étape 1480. Dans le cas contraire, c'est-à-dire s'il reste une différence D non lue, alors l'algorithme se poursuit à l'étape 1470 consistant à lire la différence D. L'étape 1470 est suivie de l'étape 1475, au cours de laquelle on 15 modifie la structure représentant le motif de référence M en fonction de cette différence D. Ensuite, l'algorithme se poursuit à l'étape 1465 précédemment décrite. Il est maintenant décrit en référence à la Figure 15 un algorithme de 20 lecture d'un noeud N écrit selon l'algorithme décrit en référence à la Figure 13, conformément à l'invention. Cet algorithme est utilisé pour les noeuds écrits à partir d'un motif de référence. Pour lire un noeud qui n'est pas associé à un motif de référence, on utilise une méthode connue. Par exemple, si un tel noeud a été écrit 25 directement en utilisant la syntaxe XML, il est lu à partir de cette syntaxe. De même, si un tel noeud a été écrit directement en utilisant la syntaxe Fastlnfoset, il est lu à partir de cette syntaxe. Puis, pour chaque item enfant du noeud, si cet item enfant n'est pas un noeud XML, il est lu en utilisant la même méthode connue. Par contre, si cet item enfant est un noeud XML, on vérifie comment il a 30 été écrit. 2907568 39 S'il a été écrit en utilisant un motif de référence, l'algorithme décrit en référence à la Figure 15 est utilisé pour le lire. Sinon, le noeud est lu en utilisant la méthode connue. Dans le cas d'un noeud associé à un motif de référence M, 5 l'algorithme commence à l'étape 1505 par la lecture de l'index associé au motif de référence M. Puis, l'algorithme se poursuit à l'étape 1510 en obtenant le motif de référence M à partir de son index. A partir de ce motif de référence M, l'algorithme va construire un autre motif mixte Ms, dont la structure correspond 10 exactement à cette du noeud N. Le motif mixte Ms correspond au motif structurel primaire associé au noeud N et peut comporter en outre des valeurs de contenu. Initialement, le motif mixte Ms est créé identique au motif de référence M. 15 L'algorithme se poursuit par l'étape 1515 au cours de laquelle on vérifie s'il reste une différence D entre la structure du noeud N et le motif de référence associé M. Si tel est le cas, l'algorithme se poursuit à l'étape 1520 en lisant cette différence D. Cette différence D est ensuite utilisée pour modifier le motif mixte 20 Ms associé au noeud N. L'algorithme se poursuit ensuite à l'étape 1515. Si le test de l'étape 1515 est négatif, alors l'algorithme se poursuit à l'étape 1525 au cours de laquelle on vérifie s'il reste un item K du motif mixte Ms associé au noeud N non traité. 25 Si tel n'est pas le cas, alors l'algorithme se termine à l'étape 1555. Si, au contraire, il reste un item K non traité, alors l'algorithme crée à l'étape 1530 un item enfant du noeud N correspondant à cet item K. Puis, l'algorithme vérifie à l'étape 1535 si le type de l'item K correspond à un type ayant une valeur c'est-à-dire notamment si le type de 30 l'item K correspond à un attribut, une valeur textuelle, un commentaire ou une instruction de traitement. 2907568 En outre l'algorithme vérifie si la valeur de l'item K est fixée, et dans ce cas, l'algorithme vérifie si la valeur est égale à la définition contenue dans le motif de référence M. Si tel n'est pas le cas, l'algorithme se poursuit à l'étape 1540 au 5 cours de laquelle on lit cette valeur et on l'ajoute à l'item enfant du noeud N correspondant à l'item K. Sinon, l'algorithme utilise la valeur définie par le motif de référence M pour l'ajouter à l'item enfant du noeud N correspondant à l'item K. L'étape 1540 se poursuit à l'étape 1545 au cours de laquelle on 10 vérifie si l'item K correspond à une référence à un motif de référence. De même, à l'étape 1535, si le test est négatif, l'étape 1535 est suivie de l'étape 1545. Si l'item K ne correspond pas à une référence à un motif de référence, alors l'algorithme se poursuit à l'étape 1525 précédemment décrite. 15 Dans le cas contraire, l'algorithme se poursuit à l'étape 1550 en lisant le noeud correspondant à l'item K. Si ce noeud est associé à un motif de référence, il est lu en utilisant ce même algorithme. Sinon, il est lu en utilisant une méthode connue comme décrit précédemment. 20 Les algorithmes décrits en référence aux figures 6, 7, 8, 9 et 11 pour permettre la détermination des motifs de référence utilisent une méthode qui est basée sur les différences des motifs structurels primaires en fonction des valeurs les plus fréquentes pour leurs instances. Une autre méthode consiste à créer en premier lieu des motifs 25 mixtes décrivant pour chaque noeud du document sa structure et ses valeurs. Cette première opération est réalisée à la place des étapes 410, 420 et 430 de la Figure 4. Ensuite, les motifs mixtes sont regroupés et pour chaque groupe, un motif de référence est déterminé. Ainsi seul un petit nombre de motifs mixtes 30 est conservé. Pour réaliser ces regroupements, une méthode de calcul de distance prenant en compte de manière spécifique les valeurs fixées est nécessaire. 2907568 41 Selon un mode de réalisation, on associe un motif mixte à d'autres motifs représentant la même structure mais avec des valeurs différentes. En outre, l'algorithme de regroupement prend en compte le nombre d'instances d'un motif mixte : deux motifs mixtes fréquents, même très proches, 5 sont conservés dans des groupes différents pour permettre de les utiliser tous les deux. Afin de mettre en oeuvre les procédés de génération de motifs de 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 10 de référence comprend des moyens d'extraction de motifs structurels primaires associés aux données hiérarchisées, des moyens d'extraction aptes à extraire des informations de contenu, des moyens de génération d'au moins un motif structurel mixte, et des moyens de détermination d'au moins un motif de référence, un dispositif de codage comprenant notamment les moyens du 15 dispositif de génération de motifs de référence, des moyens de détermination des 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 20 données hiérarchisées codées en fonction des motifs de référence et des informations de différence. Ces dispositifs de génération de motifs de référence, de codage et de décodage peuvent être incorporés dans un ordinateur 1600 tel qu'illustré à laFigure 16. 25 En particulier, les différents moyens identifiés ci-dessus peuvent être incorporés dans une mémoire morte 1605 ("Read- only memory" ou ROM) adaptée à mémoriser un programme de génération de motifs et/ou de codage conforme à l'invention. La mémoire vive 1610 ("Random access memory" ou RAM) est 30 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. 2907568 42 Le microprocesseur 1620 est intégré à un ordinateur 1600 qui peut être connecté à différents périphériques et à d'autres ordinateurs d'un réseau de communication. Cet ordinateur comporte de manière connue une interface de 5 communication 1630 reliée au réseau de communication 1635 pour recevoir ou transmettre des messages. L'ordinateur comporte en outre des moyens de stockage de documents, tel qu'un disque dur 1670, ou est adapté à coopérer au moyen d'un lecteur de disque 1680 (disquettes, disques compacts ou cartes informatiques) avec des moyens de stockage de documents amovibles, tels 10 que des disques 1685. Ces moyens de stockage fixes ou amovibles peuvent comporter le code du procédé de génération motifs de référence, de codage ou de décodage conforme à l'invention. Ils sont également adaptés à mémoriser un document électronique contenant des données hiérarchisées tel que défini par la présente invention. 15 A titre de variante, le programme permettant au dispositif de génération de motifs de référence, de codage ou de décodage de mettre en oeuvre l'invention peut être stocké dans la mémoire morte 1605. 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 20 1635. L'ordinateur 1600 possède également un écran 1640 permettant par exemple de servir d'interface avec un opérateur à l'aide du clavier 1650 ou de la souris 1660 ou de tout autre moyen. L'unité centrale 1620 (CPU) exécutera alors les instructions relatives à la mise en oeuvre de l'invention. Lors de la mise sous tension, les 25 programmes et méthodes relatives à l'invention stockés dans une mémoire non volatile, par exemple la mémoire 1605, sont transférés dans la mémoire 1610 qui contiendra alors le code exécutable de l'invention ainsi que les variables nécessaires à la mise en oeuvre de l'invention. Le bus de communication 1690 permet la communication entre les 30 différents sous-éléments de l'ordinateur ou liés à lui. 2907568 43 La représentation de ce bus 1690 n'est pas limitative et notamment le microprocesseur 1620 est susceptible de communiquer des instructions à tout sous-élément directement ou par l'intermédiaire d'un autre sous-élément. Bien entendu, de nombreuses modifications peuvent être apportées 5 aux exemples de réalisation décrits précédemment sans sortir du cadre de l'invention. REVENDICATIONS 1. Procédé de génération de motifs de référence aptes à représenter des données hiérarchisées, caractérisé en ce qu'il comprend les étapes suivantes : - détermination de motifs structurels primaires associés aux données hiérarchisées, chacun des motifs structurels primaires représentant un ensemble d'informations structurelles ; - extraction d'informations de contenu à partir des données hiérarchisées associées à au moins un motif structurel primaire déterminé ; - génération d'au moins un motif structurel mixte, un motif structurel mixte comprenant les informations structurelles représentées par un motif structurel primaire déterminé et au moins une information de contenu parmi les informations de contenu extraites à partir des données hiérarchisées associées à ce motif structurel primaire ; et - détermination d'au moins un motif de référence au moins à partir d'au moins un motif structurel mixte, ledit motif de référence étant apte à représenter ledit au moins un motif structurel mixte. 2. Procédé de génération selon la revendication 1, caractérisé en ce que la détermination dudit au moins un motif de référence est réalisée, en outre, à partir d'au moins un motif structurel primaire. 3. Procédé de génération selon l'une quelconque des revendications précédentes, caractérisé en ce que l'étape de génération dudit au moins un motif structurel mixte comprend pour chaque motif structurel mixte à générer à partir d'un motif structurel primaire, les étapes suivantes : -détermination du degré d'utilisation des informations de contenu extraites en fonction du nombre de données hiérarchisées contenant ces informations de contenu associées audit motif structurel primaire ; sélection parmi les informations de contenu extraites, d'au moins une information de contenu en fonction de son degré d'utilisation déterminé ; et 2907568 45 -génération dudit motif structurel mixte comprenant ladite au moins une information de contenu sélectionnée et les informations structurelles du motif structurel primaire auquel est associée ladite au moins une information de contenu. 5 4. 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'au moins un motif de référence comprend les étapes suivantes : - groupement dudit au moins un motif structurel mixte avec au 10 moins un motif structurel mixte similaire et / ou au moins un motif structurel primaire similaire en groupe de motifs ; et - détermination d'un motif de référence par groupe de motifs; ledit motif de référence étant apte à représenter les motifs structurels du groupe qui lui est associé. 15 5. Procédé de génération selon la revendication 4, caractérisé en ce que l'étape de groupement est effectuée en fonction d'une mesure de distance entre des motifs structurels. 20 6. Procédé de génération selon la revendication 4 ou la revendication 5, caractérisé en ce que l'étape de groupement est effectuée en fonction du nombre de données hiérarchisées aptes à être représentées par ledit au moins un motif structurel. 25 7. Procédé de génération selon la revendication 6, caractérisé en ce que le nombre de données hiérarchisées aptes à être représentées par ledit au moins un motif structurel est déterminé en fonction du nombre de données hiérarchisées dont les informations structurelles et ladite au moins une information de contenu correspondent aux informations structurelles et à au 30 moins une information de contenu de ce motif structurel mixte. 2907568 46 8. Procédé selon l'une quelconque des revendications 4 à 7, caractérisé en ce que le motif de référence associé à un groupe de motifs est construit par la réunion des informations structurelles et des informations de contenu de tous les motifs du groupe. 5 9. Procédé de génération selon l'une des revendications précédentes, caractérisé en ce que les données hiérarchisées étant organisées en une pluralité d'items, un item représentant un noeud s'il contient au moins un autre item dit item enfant, les informations structurelles d'un motif structurel 10 primaire ou d'un motif structurel mixte sont relatives à une pluralité de noeuds ayant une relation hiérarchique entre eux. 10. Procédé de génération selon l'une des revendications précédentes, caractérisé en ce que les données hiérarchisées étant organisées 15 en une pluralité d'items, les informations de contenu sont relatives aux données comprises dans au moins un item. 11. 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 20 sont décrites dans un langage de balisage structurant les données. 12. Procédé de génération de méta-motifs de référence aptes à représenter des motifs de référence, caractérisé en ce qu'il comprend les étapes suivantes : 25 - génération de motifs de référence aptes à représenter des données hiérarchisées selon le procédé de génération de motifs de référence conforme à l'une quelconque des revendications 1 à 11 ; groupement des motifs de référence générés à l'étape de génération ; ledit groupement étant effectué en fonction du degré d'utilisation 30 d'au moins un motif de référence ; et 2907568 47 - détermination d'un méta-motif de référence par groupe de motifs de référence, ledit méta-motif de référence étant apte à représenter les motifs de référence du groupe qui lui est associé. 5 13. Procédé de codage de données hiérarchisées, caractérisé en ce qu'il comprend les étapes suivantes : - génération de motifs de référence aptes à représenter les données hiérarchisées selon le procédé de génération de motifs de référence conforme à l'une quelconque des revendications 1 à 11 ; 10 - détermination des 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. 15 14. Procédé de codage selon la revendication 13, caractérisé en ce que les informations de différence entre les motifs de référence et les données hiérarchisées associées comprennent des informations structurelles et des informations de contenu. 20 15. Procédé de codage de motifs de référence, caractérisé en ce qu'il comprend les étapes suivantes : - génération de méta-motifs de référence aptes à représenter des motifs de référence selon le procédé de génération de méta-motifs de référence conformément à la revendication 12 ; 25 -détermination des informations de différence entre les méta-motifs de référence et les motifs de référence associés ; et - codage des motifs de référence en fonction des motifs de référence et des informations de différence. 30 16. Procédé de décodage de données hiérarchisées codées, caractérisé en ce que les 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 2907568 48 comprenant des informations structurelles et au moins une information de contenu, 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. 5 17. Dispositif de génération de motifs de référence aptes à représenter des données hiérarchisées, caractérisé en ce qu'il comprend les moyens suivants : - des moyens de détermination de motifs structurels primaires 10 associés aux données hiérarchisées, chacun des motifs structurels primaires représentant un ensemble d'informations structurelles ; - des moyens d'extraction aptes à extraire des informations de contenu à partir des données hiérarchisées associées à au moins un motif structurel primaire déterminé ; 15 - des moyens de génération d'au moins un motif structurel mixte, un motif structurel mixte comprenant les informations structurelles représentées par un motif structurel primaire déterminé et au moins une information de contenu parmi les informations de contenu extraites à partir des données hiérarchisées associées à ce motif structurel primaire ; et 20 - des moyens de détermination d'au moins un motif de référence au moins à partir d'au moins un motif structurel mixte, ledit motif de référence étant apte à représenter ledit au moins un motif structurel mixte. 18. Dispositif de génération selon la revendication 17, caractérisé en 25 ce que les moyens de détermination sont aptes à déterminer ledit au moins un motif de référence, en outre, à partir d'au moins un motif structurel primaire. 19. Dispositif de génération selon la revendication 17 ou la revendication 18, caractérisé en ce que les moyens de génération dudit au 30 moins un motif structurel mixte comprennent pour chaque motif structurel mixte à générer à partir d'un motif structurel primaire, les moyens suivants : 2907568 49 - des moyens de détermination du degré d'utilisation des informations de contenu extraites en fonction du nombre de données hiérarchisées contenant ces informations de contenu associées audit motif structurel primaire ; 5 - des moyens de sélection parmi les informations de contenu extraites, d'au moins une information de contenu en fonction de son degré d'utilisation déterminé ; et - des moyens de génération dudit motif structurel mixte comprenant ladite au moins une information de contenu sélectionnée et les informations 10 structurelles du motif structurel primaire auquel est associée ladite au moins une information de contenu. 20. Dispositif de génération selon l'une quelconque des revendications 17 à 19 caractérisé en ce que les moyens de détermination d'au 15 moins un motif de référence comprennent les moyens suivants : - des moyens de groupement aptes à grouper ledit au moins un motif structurel mixte avec au moins un motif structurel mixte similaire et / ou au moins un motif structurel primaire similaire en groupe de motifs ; et - des moyens de détermination d'un motif de référence par groupe 20 de motifs; ledit motif de référence étant apte à représenter les motifs structurels du groupe qui lui est associé. 21. Dispositif de génération selon la revendication 20, caractérisé en ce que les moyens de groupement sont aptes est à grouper les motifs 25 structurels en fonction d'une mesure de distance entre des motifs structurels. 22. Dispositif de génération selon la revendication 20 ou la revendication 21, caractérisé en ce que les moyens de groupement sont aptes à grouper les motifs structurels en fonction du nombre de données 30 hiérarchisées aptes à être représentées par ledit au moins un motif structurel. 2907568 50 23. Dispositif de génération selon la revendication 22, caractérisé en ce que le nombre de données hiérarchisées aptes à être représentées par ledit au moins un motif structurel est déterminé en fonction du nombre de données hiérarchisées dont les informations structurelles et ladite au moins une 5 information de contenu correspondent aux informations structurelles et à au moins une information de contenu de ce motif structurel mixte. 24. Dispositif de génération selon l'une quelconque des revendications 20 à 23, caractérisé en ce que le motif de référence associé à 10 un groupe de motifs est construit par la réunion des informations structurelles et des informations de contenu de tous les motifs du groupe. 25. Dispositif de génération selon l'une des revendications 17 à 24, caractérisé en ce que les données hiérarchisées étant organisées en une 15 pluralité d'items, un item représentant un noeud s'il contient au moins un autre item dit item enfant, les informations structurelles d'un motif structurel primaire ou d'un motif structurel mixte sont relatives à une pluralité de noeuds ayant une relation hiérarchique entre eux. 20 26. Dispositif de génération selon l'une des revendications 17 à 25, caractérisé en ce que les données hiérarchisées étant organisées en une pluralité d'items, les informations de contenu sont relatives aux données comprises dans au moins un item. 25 27. Dispositif de génération selon l'une quelconque des revendications 17 à 26, caractérisé en ce que les données hiérarchisées sont décrites dans un langage de balisage structurant les données. 28. Dispositif de génération de méta-motifs de référence aptes à 30 représenter des motifs de référence, caractérisé en ce qu'il comprend les moyens suivants : 2907568 51 - un dispositif de génération de motifs de référence aptes à représenter des données hiérarchisées conforme à l'une quelconque des revendications 17 à 27; - des moyens de groupement des motifs de référence générés par 5 lesdits moyens de génération; ledit groupement étant effectué en fonction du degré d'utilisation d'au moins un motif de référence ; et - des moyens de détermination d'un méta-motif de référence par groupe de motifs de référence, ledit méta-motif de référence étant apte à représenter les motifs de référence du groupe qui lui est associé. 10 29. Dispositif de codage de données hiérarchisées, caractérisé en ce qu'il comprend les moyens suivants : - un dispositif de génération de motifs de référence aptes à représenter les données hiérarchisées conforme à l'une quelconque des 15 revendications 17 à 27 ; - des moyens de détermination des 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. 20 30. Dispositif de codage selon la revendication 29, caractérisé en ce que les informations de différence entre les motifs de référence et les données hiérarchisées associées comprennent des informations structurelles et des informations de contenu. 25 31. Dispositif de codage de motifs de référence, caractérisé en ce qu'il comprend les moyens suivants : - un dispositif de génération de méta-motifs de référence aptes à représenter des motifs de référence conformément à la revendication 28 ; 30 - des moyens de détermination des informations de différence entre les méta-motifs de référence et les motifs de référence associés ; et 2907568 52 - des moyens de codage des motifs de référence en fonction des motifs de référence et des informations de différence. 32. Dispositif de décodage de données hiérarchisées codées, 5 caractérisé en ce que les 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 comprenant des informations structurelles et au moins une information de contenu, le dispositif comprend des moyens de décodage des données hiérarchisées codées en fonction des motifs de référence et des informations 10 de diffé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 à 11, 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 20 d'instructions pour mettre en oeuvre un procédé de génération de méta-motifs de référence selon la revendication 12, lorsque ce programme est chargé et exécuté par l'appareil programmable. 35. Produit programme ordinateur pouvant être chargé dans un 25 appareil programmable, caractérisé en ce qu'il comporte des séquences d'instructions pour mettre en oeuvre un procédé de codage de données hiérarchisées selon la revendication 13 ou 14, lorsque ce programme est chargé et exécuté par l'appareil programmable. 30 36. 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 codage de motifs de 2907568 53 référence selon la revendication 15, lorsque ce programme est chargé et exécuté par l'appareil programmable. 37. Produit programme ordinateur pouvant être chargé dans un 5 appareil 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 la revendication 16, lorsque ce programme est chargé et exécuté par l'appareil programmable. 10 38. Moyen de stockage d'informations, lisible par un ordinateur ou un microprocesseur conservant des instructions d'un programme d'ordinateur, caractérisé en ce qu'il permet la mise en oeuvre d'un procédé de génération de motifs de référence selon l'une quelconque des revendications 1 à 11. 15 39. Moyen de stockage d'informations, lisible par un ordinateur ou un microprocesseur conservant des instructions d'un programme d'ordinateur, caractérisé en ce qu'il permet la mise en oeuvre d'un procédé de génération de méta-motifs de référence selon la revendication 12. 20 40. Moyen de stockage d'informations, lisible par un ordinateur ou un microprocesseur conservant des instructions d'un programme d'ordinateur, caractérisé en ce qu'il permet la mise en oeuvre d'un procédé de codage de données hiérarchisées selon la revendication 13 ou 14. 25 41. Moyen de stockage d'informations, lisible par un ordinateur ou un microprocesseur conservant des instructions d'un programme d'ordinateur, caractérisé en ce qu'il permet la mise en oeuvre d'un procédé de codage de motifs de référence selon la revendication 15. 30 42. Moyen de stockage d'informations, lisible par un ordinateur ou un microprocesseur conservant des instructions d'un programme d'ordinateur, 2907568 54 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 la revendication 16.