Brevet FR2901036A1 — publié le 20071116

La présente invention concerne un procédé, un dispositif et un programme d'ordinateur pour la génération de motifs structurels 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 en utilisant les motifs structurels de référence ainsi générés. 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. 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 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 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 partie 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 balises du noeud parent. Il 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 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. Le langage XML définit une syntaxe particulière pour mélanger les informations structurelles et les informations de contenu. Selon cette syntaxe, un noeud, appelé élément , est défini par une balise ouvrante, une balise fermante et un identifiant. 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 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. La figure 1 présente un exemple simple d'un document contenant des données hiérarchisées écrit en langage XML. Ce document contient onze éléments. L'élément racine, possédant l'identifiant liste , est délimité par la balise ouvrante et la balise fermante , et comprend trois éléments employé . Les éléments employé contiennent en eux-mêmes d'autres éléments comme prénom , nom ou ville . Le langage XML présente de nombreux avantages. La syntaxe XML est textuelle, elle peut donc être lue ou écrite aisément par un utilisateur. Elle est également générique. Elle peut alors servir de base pour la construction de nouveaux langages plus complexes. Toutefois, la description en langage XML présente un certain nombre d'inconvénients. Tout d'abord, un document écrit en langage XML est de taille importante puisque le document inclut non seulement des informations de contenu qui correspondent à l'information effective, mais également des informations structurelles. Ainsi, la manipulation d'un tel document est rendue difficile, aussi bien en termes de stockage qu'en termes d'échange ou de traitement. En outre, les informations structurelles dont le rôle initial est de hiérarchiser les données du document ne sont pas optimisées pour les divers traitements susceptibles d'être appliqués à ces données, tel que la recherche d'un item particulier dans le document ou la compression du document pour son stockage ou sa transmission. Une première approche pour résoudre ces problèmes est d'utiliser comme base de traitement non pas les informations structurelles du document XML lui-même, mais celles d'un document qui lui est associé ou duquel il dérive. C'est typiquement le cas d'un schéma XML ( XML Schema en terminologie anglo-saxonne, dont une description peut être trouvée aux adresses: http://www.w3.orgfTR/xmlschema-l/ et http://www.w3.org/TR/xmischema-2/). Le schéma XML est un langage qui définit les types de données présents dans un document XML. Un document écrit en schéma XML constitue en quelque sorte un répertoire des types de données autorisés et un modèle structurel pour tous les documents XML conformes à ce schéma. Ces types concernent aussi bien les types des items feuilles qui sont le plus souvent des types simples (entier, texte, etc.) que les types des éléments XML. Selon la syntaxe des schémas XML, le type d'un élément est défini par son identifiant. Par conséquent, il existe autant de type d'élément qu'il existe d'identifiants d'éléments différents. Dans l'exemple, de la figure 1, il existe cinq types d'éléments qui sont : liste, employé, nom, prénom et ville. Le type employé comprend deux sous-éléments de type nom et prénom et, optionnellement, un élément de type ville. Il est par exemple connu du document US 2004/172591 de la société Microsoft, intitulé Method and system for inferring a schema from a hierarchical data structure for use in a spreadsheet , une méthode de génération d'un schéma XML à partir d'un document XML. Cette génération du schéma XML est réalisée à partir des identifiants des éléments XML. Pour cela, lors du parcours du document, si un identifiant est rencontré plusieurs fois, alors une même structure est utilisée pour définir le type de cet élément dans le sens des schémas XML. L'utilisation d'un schéma permet d'améliorer la performance de certains traitements car le schéma renseigne sur les structures d'éléments qui doivent êtres nécessairement satisfaites par le document XML. Par exemple, il est connu d'utiliser le document de schéma XML associé à un document XML à compresser afin de ne coder que les valeurs d'instances. La décompression ne consistant 4 ainsi qu'à appliquer les valeurs d'instances au document de schéma XML pour retrouver le document XML d'origine. L'utilisation d'un schéma XML n'est toutefois pas optimale pour l'application de traitements au document XML. En effet, la syntaxe des schémas XML sert en premier lieu à vérifier si les types des différents items d'un document XML sont corrects et si ce dernier vérifie bien les contraintes imposées par le modèle du schéma XML. Il serait par conséquent intéressant de pouvoir réaliser une nouvelle décomposition d'un document structuré, qui fournisse plus d'informations sur la structure du document, de manière à permettre à de nombreuses applications d'être plus perforrnantes lorsqu'elles traitent un document. A cet effet, l'invention a pour objet en premier lieu un procédé de génération de motifs structurels de référence aptes à représenter des données hiérarchisées. Le procédé comprend les étapes suivantes : extraction de motifs structurels primaires associés aux données hiérarchisées, chacun des motifs structurels primaires représentant un ensemble d'informations structurelles ; groupement des motifs structurels primaires situés, par rapport à l'un d'entre eux au moins, à une distance inférieure ou égale à une valeur 20 prédéterminée; et détermination d'un motif structurel de référence par groupe de motifs structurels, ledit motif structurel de référence étant apte à représenter les motifs structurels primaires du groupe qui lui est associé. L'invention prévoit d'analyser des données hiérarchisées pour en extraire 25 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. L'objectif de l'invention est de trouver des motifs structurels qui se reproduisent dans les données hiérarchisées. 30 Pour ce faire, le procédé selon l'invention prévoit de déterminer à partir des motifs structurels primaires extraits des données, des motifs structurels de référence aptes à représenter des données hiérarchisées. Ultérieurement, les motifs structurels de référence permettront, notamment, de coder ces données de sorte à réduire la taille de ces données. Le procédé se fonde, notamment, sur une étape de regroupement de motifs structurels primaires qui présentent une similitude déterminée au moyen du calcul d'une distance entre les motifs structurels primaires. Selon une caractéristique, 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 sont relatives à un noeud et à ses items enfants directs uniquement. Selon cette caractéristique, l'information structurelle d'un motif structurel primaire est déterminée par rapport à l'information structurelle contenue dans un noeud et dans les items enfants de ce noeud. Selon une variante de réalisation, les informations structurelles d'un motif structurel primaire sont relatives à une pluralité de noeuds ayant une relation hiérarchique entre eux. Selon cette caractéristique, l'information structurelle d'un motif structurel primaire est déterminée par rapport à l'information structurelle contenue dans une pluralité de noeuds telle que ces noeuds présentent entre eux une relation hiérarchique. Selon une autre caractéristique, les données hiérarchisées sont décrites dans un langage de balisage structurant les données, notamment en utilisant le langage XML. Selon encore une autre caractéristique, les groupes résultant de l'étape de groupement comprennent des motifs structurels primaires qui sont situés, deux à deux, à une distance inférieure ou égale à la valeur prédéterminée. Selon cette caractéristique, on détermine un groupe tel que les membres de ce groupe présentent entre chacun d'eux une similitude, cette similitude étant déterminée au moyen du calcul d'une distance entre motifs structurels primaires, deux à deux. Selon un mode de réalisation particulier, la distance entre un premier et un second motif structurel primaire est définie par le nombre d'informations 6 structurelles à ajouter et / ou à supprimer et / ou à modifier par rapport au premier motif structurel primaire pour obtenir le second motif structurel primaire. Selon ce mode de réalisation, le calcul de la distance est effectué par la détermination des items à ajouter, à supprimer et / ou à modifier pour passer d'un premier motif structurel primaire à un second motif structurel primaire. II est bien entendu que toutes les combinaisons entre l'ajout et / ou la suppression et / ou la modification peuvent être envisagées afin de déterminer le résultat du calcul de la distance entre ces deux motifs structurels primaires. Selon un mode de réalisation, le motif structurel de référence est le motif structurel primaire d'un groupe par rapport auquel tous les motifs structurels primaires du groupe sont situés à une distance inférieure ou égale à la valeur prédéterminée. Selon ce mode de réalisation, le motif structurel de référence déterminé est un motif structurel primaire appartenant au groupe. Selon un autre mode de réalisation, le motif structurel de référence associé à un groupe est construit par la réunion des informations structurelles de tous les motifs structurels primaires du groupe, le motif structurel de référence ainsi construit étant dit motif structurel de référence englobant. Selon ce mode de réalisation, le motif structurel de référence déterminé comprend l'ensemble des informations structurelles de tous les motifs structurels primaires du groupe. 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 structurels de référence aptes à représenter les données hiérarchisées selon le procédé de génération de motifs structurels de référence brièvement exposé ci-dessus ; détermination des informations de différence entre les motifs structurels 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 structurels de référence et des informations de différence. Conformément à ce procédé, on génère des motifs structurels de référence selon le procédé de l'invention précédemment décrit de sorte à recoder les données hiérarchisées en vue de réduire la taille de codage de ces données hiérarchisées. En effet, après avoir déterminé les structures des données hiérarchisées (au moyen des motifs structurels de référence), on recode ces données à partir des motifs structurels de référence. De la sorte, on évite un codage des informations structurelles pour chaque donnée et on réduit ainsi de manière significative la taille de codage des données hiérarchisées. Selon une caractéristique, les informations de différence entre les motifs structurels de référence et les données hiérarchisées associées comprennent des informations structurelles et des informations de contenu. L'invention vise également un dispositif de génération de motifs structurels de référence aptes à représenter des données hiérarchisées, caractérisé en ce qu'il comprend : des moyens d'extraction pour extraire des 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 de groupement pour grouper des motifs structurels primaires situés, par rapport à l'un d'entre eux au moins, à une distance inférieure ou égale à une valeur prédéterminée ; et des moyens de détermination pour déterminer un motif structurel de référence par groupe de motifs structurels primaires déterminé, ledit motif structurel de référence étant apte à représenter les motifs structurels primaires du groupe qui lui est associé. De même, l'invention propose un dispositif de codage de données 25 hiérarchisées, caractérisé en ce qu'il comprend : - un dispositif de génération de motifs structurels de référence aptes à représenter les données hiérarchisées conforme au dispositif brièvement exposé ci-dessus ; - des moyens de détermination pour déterminer des informations de 30 différence entre les motifs structurels de référence et les données hiérarchisées associées ; et des moyens de codage pour coder des données hiérarchisées en fonction des motifs structurels de référence et des informations de différence. Ces dispositifs présentent les mêmes avantages que les procédés qu'ils mettent en oeuvre et qui ont été brièvement décrits ci-dessus. La présente invention vise aussi un moyen de stockage, éventuellement amovible partiellement ou totalement, lisible par un ordinateur ou un microprocesseur conservant des instructions d'un programme d'ordinateur, permettant la mise en oeuvre des procédés tels qu'exposés ci- dessus. La présente invention vise enfin un produit programme d'ordinateur pouvant être chargé dans un appareil programmable, comportant des séquences d'instructions pour mettre en oeuvre les procédés tels qu'exposés ci-dessus, lorsque ce programme est chargé et exécuté par l'appareil programmable. D'autres aspects et avantages de la présente invention apparaîtront plus clairement à la lecture de la description qui va suivre, cette description étant donnée uniquement à titre d'exemple non limitatif et faite en référence aux dessins annexés, dans lesquels : la figure 1 présente un exemple simple d'un document de données hiérarchisées écrit en langage XML ; la figure 2 illustre un algorithme de génération de motifs structurels de référence selon l'invention ; la figure 3 représente un exemple d'algorithme permettant l'extraction de motifs structurels primaires d'ordre 1 à partir des données d'un document écrit en langage de balisage XML ; la figure 4 représente un algorithme d'extension d'un motif structurel primaire d'ordre 1 par inclusion des descriptions des motifs structurels primaires référencés ; la figure 5 représente un exemple de mise en oeuvre du groupement des motifs structurels primaires similaires ; 9 la figure 6 représente un algorithme de construction d'un motif structurel de référence englobant ; la figure 7 représente un algorithme de mise en oeuvre du procédé de codage utilisant les motifs structurels de référence ; la figure 8 est un schéma bloc illustrant un dispositif adapté à mettre en oeuvre la présente invention. La figure 2 illustre un algorithme de génération de motifs structurels de référence selon l'invention. Les motifs structurels 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 des motifs structurels primaires représentant exactement les différentes structures présentes parmi les données hiérarchisées, mais seulement quelques motifs structurels de référence qui permettent de représenter toutes les structures avec un coût réduit. Les données hiérarchisées peuvent être localisées dans un ou 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 structurels de référence seront optimisés pour représenter les données de tous ces documents. Cela n'empêche évidemment pas d'utiliser les motifs structurels 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. Dans l'étape 210, des motifs structurels sont extraits à partir des données hiérarchisées. Ces motifs structurels sont dits primaires car ils reprennent les différentes structures des données hiérarchisées. 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 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 peut également être représenté sous forme d'une structure arborescente d'informations structurelles. Les noeuds et les items enfants associés représentent dans ce cas la structure des motifs structurels sans aucune information de contenu. Dans la suite de la description, la représentation arborescente sera utilisée aussi bien pour les données hiérarchisées que pour les motifs structurels associés. Un motif structurel peut s'étendre sur un ou plusieurs niveaux hiérarchiques. Si le motif structurel s'étend sur un seul niveau hiérarchique, on dit que le motif structurel est d'ordre 1. Dans ce cas, les informations structurelles sont relatives à un noeud et à seulement ses items enfants directs. Si le motif structurel s'étend sur n niveaux hiérarchiques, on dit que le motif structurel est d'ordre n. Dans ce cas, les informations structurelles sont relatives à un noeud et à ses items enfants jusqu'à la génération (niveau) n-1. Un motif d'ordre n n'inclut pas nécessairement toutes les branches possibles qui dérivent du noeud racine, mais au moins une qui se prolonge jusqu'au niveau inférieur n-1. Des détails sur le choix de l'ordre et les avantages associés sont donnés ultérieurement. Un exemple de mise en oeuvre de cette étape d'extraction de motifs structurels primaires à partir des données hiérarchisées écrites en langage XML est donné par les figures 3 et 4. Lors de l'étape 220, les motifs structurels primaires qui présentent entre eux des similitudes au niveau structurel sont groupés ensemble. Le degré de similitude est mesuré quantitativement par l'évaluation d'une distance qui est indicative du nombre d'informations structurelles par lesquelles deux motifs structurels primaires diffèrent. Lorsque deux motifs structurels primaires sont similaires, alors les données que ces motifs structurels primaires représentent sont proches structurellement. Il est ainsi avantageux de remplacer la description d'un motif par la référence à un autre motif connu (qui lui est similaire) et par la description de la différence entre le motif structurel effectif et le motif structurel de référence de sorte à réduire la taille du document. Il est à noter que cette méthode de rapprochement entre les motifs structurels primaires permet des optimisations dans la description et, par conséquent, dans les traitements appliqués aux données comme le codage ou la recherche. Ces optimisations ne sont pas permises par les méthodes de l'état de la technique. En effet, selon les méthodes de l'état de la technique, un élément de 11 type gérant (non représenté sur la figure 1), contenant, par exemple, exactement les mêmes items enfants ( nom et prénom ) que l'élément employé , ne sera pas associé à ce dernier car les deux éléments sont de type différents. Or, les deux éléments possèdent seulement comme différence structurelle le type de l'élément, c'est-à- dire l'identifiant du noeud employé / gérant . Selon l'invention, ces deux éléments peuvent être considérés comme similaires. Plusieurs variantes de mise en oeuvre peuvent être envisagées pour former les groupes de motifs structurels similaires. Des exemples de mise en oeuvre de cette étape sont décrits ultérieurement, et en particulier en référence à l'algorithme de la figure 5. Lors de l'étape 230, un motif structurel de référence est déterminé pour représenter les motifs structurels primaires de chaque groupe. Du fait des similitudes qui existent entre les motifs structurels primaires d'un même groupe, un même motif structurel peut être utilisé pour représenter tous ces motifs. Ce motif est appelé motif structurel de référence. Le motif structurel de référence peut être choisi parmi les motifs structurels primaires du groupe ou construit à partir de ces motifs structurels primaires. Des exemples de mise en oeuvre de cette étape sont décrits ultérieurement, et en particulier en référence à l'algorithme de la figure 6. La figure 3 illustre un exemple d'algorithme permettant l'extraction de motifs structurels primaires d'ordre 1 à partir des données d'un document écrit en langage de balisage XML. Cet algorithme est exécuté de manière récursive en partant de l'élément racine du document XML. La procédure est donc lancée à l'étape 310 avec cet élément racine. Lors de l'étape 320, un item enfant est sélectionné, puis un test est effectué à l'étape 330 pour savoir si cet item est lui-même un élément XML ou 30 pas. Si l'item est lui-même un élément, la procédure d'extraction de motif pour cet item enfant est une nouvelle fois appelée (étape 331). La procédure 12 d'extraction retourne une référence au motif ainsi créé associé à l'item enfant, cette référence est ajoutée au motif de l'élément XML à l'étape 333. Optionnellement, si l'item enfant est un élément qui ne contient aucun autre item enfant (alternative positive du test de l'étape 332), aucune référence au motif (vide) associé à l'élément enfant n'est rajouté dans le motif de l'élément parent. Dans l'alternative négative du test de l'étape 330, si l'item enfant sélectionné n'est pas un élément, alors le type de cet item est ajouté au motif associé à l'élément parent. Optionnellement, une condition (étape 335) peut être rajoutée relative à l'inclusion du type de l'item enfant dans le motif. Cette condition peut également s'appliquer (cas non représenté sur l'algorithme) à l'inclusion d'une référence à un motif. La condition relative à l'inclusion d'un sous-item dans le motif structurel primaire permet d'adapter ce motif à des traitements particuliers. Par exemple, si l'objet de la création des motifs est d'identifier tous les éléments ayant un identifiant prénom , la condition d'inclusion sera que l'item doit être un élément et que soit cet élément a comme identifiant prénom , soit il est non vide. Ainsi, on obtient des structures de motifs structurels primaires réduits, mais particulièrement adaptées aux traitements envisagés. L'étape 340 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 poursuit à l'étape 320 précédemment décrite, de manière à traiter l'item enfant suivant. Dans le cas contraire, l'algorithme se termine à l'étape 350 et retourne le motif structurel primaire créé me associé à l'élément XML e. Lorsque tous les items enfants d'un élément parent sont eux-mêmes des éléments, le motif structurel d'ordre 1 associé à l'élément parent ne contiendra 30 pour ses items enfants que des références à des motifs. Lorsque plusieurs motifs structurels primaires identifiés sont identiques, il suffit de ne garder qu'un exemplaire pour les traitements ultérieurs. Un exemple de détermination des motifs d'ordre 2, dans une variante de réalisation, est obtenu en effectuant d'abord une extraction de motifs structurels primaires d'ordre 1 selon l'algorithme de la figure 3, puis une extension de ces motifs structurels primaires d'un niveau hiérarchique supplémentaire. Ce mode de réalisation est illustré en référence à la figure 4 qui présente un algorithme permettant de remplacer la référence à un motif structurel primaire par la description même de ce motif structurel primaire. La procédure est lancée à l'étape 410 avec un motif structurel primaire m. Dans l'étape 420, un item enfant s du motif m est sélectionné, et un premier test est effectué dans l'étape 430 pour vérifier si cet item enfant s référence un motif structurel primaire. Si ce n'est pas le cas, on passe à l'item enfant suivant s'il existe (test de l'étape 460 et étape 420). Si c'est le cas, un deuxième test est effectué dans l'étape 440 pour savoir si une condition prédéterminée est vérifiée. La condition prédéterminée dépend de l'application envisagée. Par exemple, pour diminuer le nombre de motifs, il peut être intéressant de n'étendre que les motifs dont les items enfants de seconde génération (les enfants des items enfants) sont de type simple, c'est-à-dire ne sont pas des noeuds. Dans l'exemple des données de la figure 1, les motifs associés aux éléments nom et prénom peuvent être insérés directement dans le motif structurel primaire associé à l'élément employé , les éléments nom et prénom représentant des items qui ne contiennent que des sous-items feuilles de type texte. Un autre exemple est consiste à d'inclure dans un motif tous les motifs auxquels il réfère et qui ne sont pas utilisés par un autre motif. Ainsi, suite au test de l'étape 440, sila condition n'est pas vérifiée, on passe à l'item enfant suivant s'il existe (test de l'étape 460 et étape 420). Si la condition est vérifiée, on remplace la référence au motif s par la description de ce motif dans l'étape 450. L'étape 460 consiste à vérifier s'il existe un autre item enfant n'ayant pas été traité. Si tel est le cas, l'algorithme se poursuit à l'étape 420 précédemment décrite. Dans le cas contraire, l'algorithme se termine à l'étape 470. D'autres variantes de réalisation peuvent être envisagées pour étendre un motif d'ordre 1 vers un motif d'ordre n. En effet, sur le même principe que celui de 14 la figure 4, les items enfants de chaque motif qui référencent un autre motif peuvent être remplacés par la description du motif référencé, et ceci récursivement jusqu'à obtenir la profondeur voulue. L'utilisation d'un motif structurel primaire d'ordre n est particulièrement avantageuse lorsque l'item du niveau le plus inférieur du motif représente un type simple, et non une référence à un motif. La figure 5 présente un exemple de mise en oeuvre de l'étape 220 du procédé de la figure 2 pour grouper les motifs structurels primaires similaires entre eux. L'algorithme débute à l'étape 500. Après cette étape, un motif structurel primaire quelconque m est sélectionné (étape 510) parmi l'ensemble M des motifs structurels primaires extraits précédemment, selon les algorithmes des figures 3 et 4 par exemple. Dans l'étape 520, un groupe g(m) est d'abord initialisé à l'ensemble vide. Ce groupe g(m) contiendra à la fin de l'exécution de l'algorithme le motif m et, éventuellement, des motifs qui lui sont similaires. Si aucun motif similaire n'est trouvé, le groupe g(m) ne contiendra qu'un seul élément qui est le motif m lui-même. Lors de l'étape 530, un motif ms est sélectionné parmi les motifs de l'ensemble M, puis la distance entre ce motif ms et le motif m est calculée (d(m, ms). Cette distance est ensuite comparée à un seuil prédéterminé, nommé valeur limite, lors de l'étape 540. Si les motifs structurels primaires m et ms sont suffisamment proches, c'est-à-dire si la distance d(m, ms) est inférieure ou égale à la valeur limite, alors l'algorithme se poursuit à l'étape 550, sinon il se poursuit directement à l'étape 560. Dans l'étape 550, le motif ms qui a été identifié comme suffisamment proche du motif ni par le calcul de la distance, est ajouté au groupe associé à m g(m). Le motif ms est également supprimé de l'ensemble M pour ne pas être repris dans d'autres groupes. L'étape 560 consiste à vérifier au moyen d'un test s'il existe un autre motif structurel primaire ms dans l'ensemble M non sélectionné. Si le test est positif, 15 l'algorithme retourne à l'étape 530 pour la sélection d'un nouveau motif ms. Sinon, l'algorithme continue à l'étape 570. L'étape 570 consiste à vérifier au moyen d'un test s'il existe encore des motifs dans l'ensemble M à grouper. Si le test est positif, l'algorithme continue à 5 l'étape 510 pour la formation d'un nouveau groupe. Sinon, l'algorithme se termine à l'étape 580. Tout motif structurel primaire appartenant au groupe g(m) est nécessairement à une distance inférieure à la valeur limite du motif structurel primaire m (le motif m est alors dit motif associé au groupe g(m)). Il est à noter 10 cependant que deux motifs quelconques du groupe peuvent être à une distance supérieure à cette valeur limite. Dans une variante de réalisation du procédé de groupement des motifs, il est possible de choisir des groupes dont les motifs structurels primaires constituant chaque groupe sont situés tous, deux à deux, à une distance 15 inférieure ou égale à la valeur limite prédéterminée. La distance d(m, ms) permet de mesurer, de manière quantitative, la similarité entre deux descriptions structurelles. Lorsque deux motifs structurels primaires sont proches, cela veut dire qu'un motif structurel primaire peut être remplacé par l'autre dans la description des données qui leur sont associées. 20 La distance entre deux motifs structurels primaires est très grande, voire infinie, si les deux motifs structurels primaires 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 25 envisagée et de la distance utilisée. Un exemple de méthode de calcul de la distance entre deux motifs structurels primaires consiste à déterminer le nombre d'informations structurelles qu'il faut rajouter, supprimer et modifier à un motif pour obtenir l'autre motif. Comme indiqué précédemment, les informations structurelles peuvent être le type 30 d'un item (identifiant de l'élément dans le cas d'un type composé), le nombre d'items enfants contenus dans un noeud, l'ordre de ces items enfants, etc. 16 Le plus souvent, lorsque les motifs structurels primaires sont très similaires (même type de noeud, même ordre des items ou l'ordre qui n'intervient pas), le calcul de distance se réduit à déterminer le nombre minimal d'ajout d'items et / ou de suppression d'items et / ou de modification d'items à réaliser pour passer d'un motif structurel primaire à l'autre. Il est à noter que l'item enfant d'un motif représente le type de l'item enfant du noeud que le motif représente. Considérons par exemple les deux motifs structurels primaires ml et m2 associés respectivement aux deuxième et troisième items enfants ( employé ) de l'élément liste de la figure 1. Ainsi, d'une part, le motif structurel primaire ml correspond à un noeud identifié par l'identifiant employé et comprend deux items enfants. Le premier item enfant est un motif structurel primaire correspondant à un noeud identifié par l'identifiant prénom , ayant un item enfant de type texte. Le second item enfant est un motif structurel primaire correspondant à un noeud identifié par l'identifiant nom , ayant un item enfant de type texte. D'autre part, le motif structurel primaire m2 correspond à un noeud identifié par l'identifiant employé et comprend trois items enfants. Le premier item enfant est un motif structurel primaire correspondant à un noeud identifié par l'identifiant prénom , ayant un item enfant de type texte. Le second item enfant est un motif structurel primaire correspondant à un noeud identifié par l'identifiant nom , ayant un item enfant de type texte. Le troisième item enfant est un motif structurel primaire correspondant à un noeud identifié par l'identifiant ville , ayant un item enfant de type texte. Selon cette première méthode de calcul, la distance entre les deux motifs structurels primaires ml et m2 est de 1. En effet, ces deux motifs structurels primaires diffèrent par l'ajout d'un item de type motif structurel primaire, à savoir l'item ville . Toutefois, cette méthode de calcul de la distance peut ne pas être représentative si l'item ajouté entre les deux motifs structurels primaires ml et m2 est la description d'un motif structurel primaire de taille importante. On peut envisager en variante, selon une seconde méthode de calcul, de modifier la méthode de calcul de la distance séparant les motifs structurels primaires ml et m2 afin de mieux prendre en compte les motifs structurels primaires, en faisant notamment intervenir la taille du motif structurel primaire considéré. Ainsi, si l'item ajouté, supprimé ou modifié est la description d'un motif structurel primaire, le coût en termes de distance peut être, par exemple, le nombre d'items enfants de ce motif structurel primaire augmenté de la valeur 1. La valeur 1 permet de prendre en compte l'identifiant du noeud décrit par le motif structurel primaire. Selon la seconde méthode de calcul de la distance entre deux motifs structurels primaires, la distance entre les primaires ml et m2 est alors de 2. Selon une troisième méthode de calcul de la distance, celleci peut aussi prendre en compte de façon différente, par des pondérations différentes, les ajouts, suppressions ou modifications d'items. Toutefois, selon cette troisième méthode de calcul, la distance entre le motif structurel primaire ml et le motif structurel primaire m2 peut être différente de la distance entre le motif structurel primaire m2 et le motif structurel primaire ml (d(ml, m2) ≠d(m2, ml)). Dans ce cas, les associations créées entre des paires de motifs structurels primaires sont dissymétriques. En effet, un motif structurel primaire ml peut être proche d'un motif structurel primaire m2 (d(ml, m2) Cela signifie que le motif structurel primaire ml peut être remplacé par le motif structurel primaire m2 dans la description de la structure du document, sans que le motif structurel primaire m2 ne puisse être remplacé par le motif structurel primaire ml. II est à noter que l'algorithme de la figure 5 pour grouper les motifs structurels primaires fonctionne dans le cas de distances dissymétriques. En effet, chaque groupe est associé à un motif structurel primaire donné. Les distances sont calculées entre chaque motif structurel primaire du groupe et le motif associé 18 au groupe, c'est-à-dire que le motif associé peut remplacer chaque motif structurel primaire du groupe, sans que nécessairement le motif associé puisse être remplacé par les différents motifs structurels primaires du groupe. Pour chaque groupe identifié, un motif structurel est déterminé pour servir de référence à tous les motifs du groupe. Le motif structurel de référence est le motif qui est utilisé à la place de tous les autres motifs du groupe dans les traitements appliqués aux données hiérarchisées. Dans un premier mode de réalisation de l'invention, le motif structurel de référence d'un groupe est choisi comme étant le motif associé au groupe. L'avantage de ce mode est que le motif associé est par construction le motif le plus proche de tous les autres motifs du groupe. Dans un second mode de réalisation, le motif structurel de référence d'un groupe donné est construit à partir des motifs structurels primaires du groupe en prenant l'union (aussi appelée réunion ) de toutes les informations structurelles de ces motifs. Ce motif ainsi construit est dit motif structurel de référence englobant. Un motif structurel ml est considéré comme englobé dans un autre motif structurel m2, quand le motif structurel ml peut être obtenu à partir du motif structurel m2 en supprimant certaines informations structurelles du motif structurel m2. Cela signifie que toutes les informations structurelles du motif structurel ml se retrouvent dans le motif structurel m2 dans l'ordre dans lequel elles se trouvent dans le motif structurel ml. Pour deux motifs structurels ml et m2, il est possible de construire leur union, c'est-à-dire un motif structurel englobant à la fois le motif structurel ml et le motif structurel m2 et le plus petit possible. Pour cela, il suffit de prendre l'ensemble des informations structurelles du motif structurel ml et d'y ajouter les informations structurelles du motif structurel m2 ne se trouvant pas dans le motif structurel ml , tout en respectant l'ordre de ces informations structurelles. II est à noter que pour certaines applications, l'ordre des informations structurelles n'a pas d'importance. Dans ce cas, les informations structurelles dans les motifs structurels peuvent être triées par catégorie et par ordre 19 lexicographique afin de simplifier les comparaisons de motifs structurels et les calculs sur les motifs structurels. L'utilisation de motifs structurels de référence englobant est particulièrement avantageuse pour les applications de codage car il permet d'avoir des taux de compression plus élevés. Cette utilisation est également avantageuse pour les applications de recherche car les motifs structurels de référence englobant permettent de simplifier la recherche d'items. Un exemple d'algorithme de construction d'un motif structurel de référence englobant est décrit en référence à la figure 6. L'algorithme débute à l'étape 600. Cette étape est suivie de l'étape 610 consistant à choisir un premier motif structurel primaire mr appartenant au groupe g. L'étape suivante (étape 620) consiste à sélectionner un second motif structurel primaire m du groupe g. L'algorithme se poursuit par la comparaison, à l'étape 630, de ce motif structurel primaire m sélectionné avec le motif structurel primaire mr. Si le motif structurel primaire mr englobe le motif structurel primaire m, c'est-à-dire si le motif structurel primaire mr comprend l'ensemble des items enfant du motif structurel primaire m et dans le même ordre, alors l'algorithme se poursuit à l'étape 650 décrite ultérieurement. Dans le cas contraire, c'est-à-dire si le motif structurel primaire mr ne comprend pas l'ensemble des items enfants du motif structurel primaire m, alors l'algorithme se poursuit à l'étape 640 au cours de laquelle le motif structurel primaire mr est mis à jour en générant un motif structurel primaire qui comprend les items enfants du motif structurel primaire m et du motif structurel primaire mr (étape 640). Cette étape est suivie de l'étape 650 consistant à vérifier au moyen d'un test s'il existe un autre motif structurel primaire qui n'a pas été traité. Dans l'affirmative, l'algorithme se poursuit à l'étape 620 précédemment décrite. Dans le cas contraire, l'algorithme se poursuit à l'étape 660 consistant à générer le motif structurel de référence ms(g) représentant le groupe g, à partir du motif mr. Le motif structurel de référence ms(g) peut être par exemple égal à mr. Une fois que les motifs structurels de référence ont été déterminés, il est 5 possible de décrire la structure du document contenant les données hiérarchisées en associant ces motifs structurels de référence aux différentes structures du document, et avantageusement aux éléments du document. Pour cela, pour chaque élément XML du document, on obtient le motif structurel primaire qui lui a été associé lors de l'extraction des motifs structurels 10 primaires réalisés notamment selon l'algorithme décrit en référence à la Figure 3, puis on recherche, parmi l'ensemble des groupes de motifs structurels primaires M, le groupe auquel appartient ce motif structurel primaire, et l'on détermine le motif structurel de référence représentatif de ce groupe. Le motif structurel de référence ainsi obtenu sera utilisé pour représenter 15 la structure de cet élément XML. Le même principe peut être appliqué lorsqu'il s'agit de représenter une structure plus complexe d'éléments par un motif structurel de référence associé. L'association entre le motif structurel de référence et la structure de données correspondante peut être mémorisée soit dans un fichier spécifique, soit 20 directement dans le document à l'aide d'un attribut particulier. Dans une variante de réalisation, et pour certaines applications comme par exemple la compression, il peut être intéressant d'appliquer le concept des motifs structurels de référence à une partie seulement du document. C'est le cas par exemple lorsque qu'un groupe ne contient qu'un seul motif structurel primaire, 25 c'est-à-dire quand aucun autre ne lui a été associé car il est trop distant de tous les autres. L'invention concerne également un procédé de codage de données hiérarchisées basé sur le concept de motifs structurels de référence. Le codage est utilisé, notamment, pour la compression des données. 30 Ce procédé comprend notamment les étapes de génération de motifs structurels de référence aptes à représenter des données hiérarchisées, de détermination des informations de différence entre les motifs structurels de référence et les données hiérarchisées et de codage des données hiérarchisées. L'objectif du codage est de réduire la taille du document contenant les données hiérarchisées pour leur échange entre une unité de codage et une unité de décodage. L'unité de codage et l'unité de décodage se trouvent par exemple dans des dispositifs distants reliés par un réseau de communication. Toutefois, elles peuvent être situées dans un même dispositif lorsqu'il s'agit de réduire la taille du document de données pour son stockage sur un disque. Les motifs structurels de référence qui serviront au codage sont enregistrés, préalablement ou lors du codage, dans le même document qui contient les données hiérarchisées codées, ce qui permet à l'unité de décodage de les utiliser lors du décodage. Cependant, il est possible que ces motifs structurels de référence soient enregistrés dans un document séparé ou échangés par tout autre moyen entre les deux unités. Un exemple de mise en oeuvre du procédé de codage utilisant les motifs structurels de référence d'ordre 1 est donné par la figure 7. La première étape (étape 710) consiste à utiliser une des mises en oeuvre du procédé de génération des motifs structurels de référence appliquée aux données hiérarchiques à coder. La seconde étape (étape 720) consiste à déterminer des informations structurelles de différence entre les motifs structurels de référence générés lors de l'étape précédente et les données hiérarchisées qui leur sont associées. En effet, des différences structurelles peuvent exister étant donné que les motifs structurels de référence ne sont pas nécessairement les motifs structurels primaires associés à ces données. L'étape suivante (étape 730) consiste à déterminer des informations de contenu relatives aux informations structurelles associées aux données hiérarchisées. Ces informations de contenu sont également vues comme des informations de différence car elles représentent les informations qu'il faut ajouter aux informations structurelles pour retrouver l'ensemble des données hiérarchisées. 22 La dernière étape (étape 740) représente l'étape de codage qui utilise les informations de différence, structurelles et de contenu, ainsi que, soit la description de la structure du motif structurel de référence elle-même, soit une référence à celle-ci, pour coder les données hiérarchisées. Afin de mettre en oeuvre les procédés de génération de motifs structurels de référence aptes à représenter des données hiérarchisées et de codage de ces données utilisant ces motifs structurels de référence, un dispositif de génération de motifs structurels de référence comprend notamment des moyens d'extraction de motifs structurels primaires, des moyens de groupement des motifs structurels primaires et des moyens de détermination de motifs structurels de référence pour chaque groupe identifié, et un dispositif de codage comprenant notamment les moyens du dispositif de génération de motifs structurels de référence, des moyens de détermination d'informations de différence entre les motifs structurels 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 structurels de référence et des informations de différence. Ces dispositifs de génération de motifs structurels de référence et de codage peuvent être incorporés dans un ordinateur 800 tel qu'illustré à la figure 8. En particulier, les différents moyens identifiés ci-dessus peuvent être incorporés dans une mémoire morte 805 ("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 810 ("Random access memory" ou RAM) est adaptée à mémoriser dans des registres les valeurs modifiées lors de l'exécution du programme de génération et de codage. Le microprocesseur 820 est intégré à un ordinateur 800 qui peut être connecté à différents périphériques et à d'autres ordinateurs d'un réseau de communication. Cet ordinateur comporte de manière connue une interface de communication 830 reliée au réseau de communication 835 pour recevoir ou transmettre des messages. L'ordinateur comporte en outre des moyens de stockage de documents, tel qu'un disque dur 870, ou est adapté à coopérer au moyen d'un lecteur de disque 880 (disquettes, disques compacts ou cartes informatiques) avec des moyens de stockage de documents amovibles, tels que des disques 885. Ces moyens de stockage fixes ou amovibles peuvent comporter le code du procédé de génération motifs structurels ou de 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. A titre de variante, le programme permettant au dispositif de génération de motifs structurels ou de codage de mettre en oeuvre l'invention peut être stocké dans la mémoire morte 805. 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 835. L'ordinateur 800 possède également un écran 840 permettant par exemple de servir d'interface avec un opérateur à l'aide du clavier 850 ou de la souris 860 ou de tout autre moyen. L'unité centrale 820 (CPU) exécutera alors les instructions relatives à la mise en oeuvre de l'invention. Lors de la mise sous tension, les programmes et méthodes relatives à l'invention stockés dans une mémoire non volatile, par exemple la mémoire 805, sont transférés dans la mémoire 810 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 890 permet la communication entre les différents sous-éléments de l'ordinateur ou liés à lui. La représentation de ce bus 890 n'est pas limitative et notamment le microprocesseur 820 est susceptible de communiquer des instructions à tout sous-élément directement ou par l'intermédiaire d'un autre sous-élément. Bien entendu, de nombreuses modifications peuvent être apportées aux exemples de réalisation décrits précédemment sans sortir du cadre de l'invention.30 REVENDICATIONS 1. Procédé de génération de motifs structurels de référence aptes à représenter des données hiérarchisées, caractérisé en ce qu'il comprend les étapes suivantes extraction de motifs structurels primaires associés aux données hiérarchisées (210), chacun des motifs structurels primaires représentant un ensemble d'informations structurelles ; - groupement des motifs structurels primaires situés, par rapport à l'un d'entre eux au moins, à une distance inférieure ou égale à une valeur prédéterminée (220) ; et détermination d'un motif structurel de référence par groupe de motifs structurels primaires (230), ledit motif structurel de référence étant apte à représenter les motifs structurels primaires du groupe qui lui est associé. 2. Procédé selon la revendication 1, 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 primaire sont relatives à un noeud et à ses items enfants directs uniquement. 3. Procédé selon la revendication 1, 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 primaire sont relatives à une pluralité de noeuds ayant une relation hiérarchique entre eux. 4. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que les données hiérarchisées sont décrites dans un langage de balisage structurant les données. 5. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que les groupes résultant de l'étape de groupement comprennent des motifs structurels primaires qui sont situés, deux à deux, à une distance inférieure ou égale à la valeur prédéterminée. 6. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que la distance entre un premier et un second motif structurel primaire est définie par le nombre d'informations structurelles à ajouter et / ou à supprimer et / ou à modifier par rapport au premier motif structurel primaire pour obtenir le second motif structurel primaire. 7. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le motif structurel de référence est le motif structurel primaire d'un groupe par rapport auquel tous les motifs structurels primaires du groupe sont situés à une distance inférieure ou égale à la valeur prédéterminée. 8. Procédé selon l'une quelconque des revendications 1 à 6, caractérisé en ce que le motif structurel de référence associé à un groupe est construit par la réunion des informations structurelles de tous les motifs structurels primaires du groupe, le motif structurel de référence ainsi construit étant dit motif structurel de référence englobant. 9. 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 structurels de référence (710) aptes à représenter les données hiérarchisées selon le procédé de génération de motifs structurels de référence conforme à l'une quelconque des revendications 1 à8; détermination des informations de différence (720, 730) entre les motifs structurels 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 structurels de référence et des informations de différence (740). 26 10. Procédé de codage selon la revendication 9, caractérisé en ce que les informations de différence entre les motifs structurels de référence et les données hiérarchisées associées comprennent des informations structurelles et des informations de contenu. 11. Dispositif de génération de motifs structurels de référence aptes à représenter des données hiérarchisées, caractérisé en ce qu'il comprend : des moyens d'extraction pour extraire des 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 de groupement pour grouper des motifs structurels primaires situés, par rapport à l'un d'entre eux au moins, à une distance inférieure ou égale à une valeur prédéterminée ; et des moyens de détermination pour déterminer un motif structurel de référence par groupe de motifs structurels, ledit motif structurel de référence étant apte à représenter les motifs structurels primaires du groupe qui lui est associé. 12. Dispositif de codage de données hiérarchisées, caractérisé en ce qu'il comprend : un dispositif de génération de motifs structurels de référence aptes à représenter les données hiérarchisées conforme à la revendication 11 ; des moyens de détermination pour déterminer des informations de différence entre les motifs structurels de référence et les données hiérarchisées associées ; et des moyens de codage pour coder des données hiérarchisées en fonction des motifs structurels de référence et des informations de différence. 13. Produit programme ordinateur pouvant être chargé dans un appareil programmable, caractérisé en ce qu'il comporte des séquences d'instructions 27 pour mettre en oeuvre un procédé de génération de motifs structurels de référence selon l'une quelconque des revendications 1 à 8, lorsque ce programme est chargé et exécuté par l'appareil programmable. 14. 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 données hiérarchisées selon la revendication 9 ou 10, lorsque ce programme est chargé et exécuté par l'appareil programmable. 15. 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 structurels de référence selon l'une quelconque des revendications 1 à 8. 16. 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 9 ou 10. 20