FR2901037A1

FR2901037A1 - Procede et dispositif de generation de motifs structurels de reference aptes a representer des donnees hierarchisees

Info

Publication number: FR2901037A1
Application number: FR0604209A
Authority: FR
Inventors: Herve Ruellan; Romain Bellessort
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 2006-05-11
Filing date: 2006-05-11
Publication date: 2007-11-16
Anticipated expiration: 2026-05-11
Also published as: US8046680B2; FR2901037B1; US20070276827A1

Abstract

L'invention concerne un 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 ; détermination du degré d'utilisation de motifs structurels primaires extraits en fonction du nombre de données hiérarchisées aptes à être représentées par lesdits motifs structurels primaires ; groupement de motifs structurels primaires en groupes de motifs structurels primaires (220) ; ledit groupement étant effectué en fonction du degré d'utilisation d'au moins un motif structurel primaire et d'une mesure de distance entre des motifs structurels primaires; et détermination d'un motif structurel de référence par groupe de motifs structurels primaires déterminé (230), ledit motif structurel de référence étant apte à représenter les motifs structurels primaires du groupe qui lui est associéL'invention concerne également le procédé de codage de données hiérarchisées associé.

Description

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 <liste> et la balise fermante </liste> , 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 3

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.org/TR/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 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 performantes 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 ; détermination du degré d'utilisation de motifs structurels primaires extraits en fonction du nombre de données hiérarchisées aptes à être 20 représentées par lesdits motifs structurels primaires ; - groupement de motifs structurels primaires en groupes de motifs structurels primaires ; ledit groupement étant effectué en fonction du degré d'utilisation d'au moins un motif structurel primaire et d'une mesure de distance entre des motifs structurels primaires; et 25 détermination d'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é. L'invention prévoit d'analyser des données hiérarchisées pour en extraire 30 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. 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 5 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 détermination du degré d'utilisation de motifs structurels primaires extraits et d'une étape de regroupement de motifs structurels primaires en fonction du degré d'utilisation des motifs structurels primaires et d'une mesure de distance entre des 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 un mode de réalisation, l'étape de groupement des motifs structurels primaires comprend les étapes suivantes : - sélection du motif structurel primaire présentant un degré d'utilisation parmi les degrés d'utilisation les plus élevés ; - groupement des motifs structurels primaires situés, par rapport au motif structurel primaire sélectionné, à une distance inférieure ou égale à une 5 valeur prédéterminée ; et - répétition des étapes de sélection et de groupement parmi les motifs structurels primaires non encore groupés. Selon ce mode de réalisation, la sélection d'un motif structurel primaire de degré d'utilisation élevé permet de déterminer qu'un nombre important de 10 données hiérarchisées sont aptes à être décrites par ces motifs structurels primaires. Le motif structurel primaire ainsi sélectionné permet ensuite d'effectuer un groupement des motifs structurels primaires en fonction de ce motif sélectionné. Selon une caractéristique, la distance entre un premier et un second 15 motif structurel primaire est également fonction du degré d'utilisation du premier motif structurel primaire. Selon un mode de réalisation, l'étape de groupement des motifs structurels primaires comprend les étapes suivantes : - sélection d'un motif structurel primaire ; 20 groupement des motifs structurels primaires situés, par rapport au motif structurel primaire sélectionné, à une distance inférieure ou égale à une valeur prédéterminée, ladite distance étant pondérée par le degré d'utilisation des motifs structurels primaires ; et répétition des étapes de sélection et de groupement parmi les motifs 25 structurels primaires non encore groupés. Selon 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 30 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 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 degré d'utilisation d'un motif structurel primaire est déterminé en fonction du nombre de données hiérarchisées dont les informations structurelles correspondent aux informations structurelles de ce motif structurel primaire.

Selon un autre mode de réalisation, le motif structurel de référence associé à un groupe correspond au motif structurel primaire parmi les motifs structurels primaire du groupe ayant le degré d'utilisation le plus élevé. Selon encore 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 déterminé é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. Selon un mode de réalisation de la détermination d'un motif structurel de référence, le motif structurel de référence associé à un groupe est déterminé en fonction d'au moins certains des motifs structurels primaires du groupe et, pour chaque motif structurel primaire, d'une mesure de représentativité par rapport aux données hiérarchiques associées à des motifs structurels primaires du groupe, le motif structurel de référence ainsi déterminé étant dit motif structurel de référence médian. 8

Plus particulièrement, le motif structurel de référence associé à un groupe est déterminé en fonction des motifs structurels primaires ayant les mesures de représentativité les plus élevées. Selon une caractéristique de réalisation, la mesure de représentativité d'un motif structurel primaire est fonction des degrés d'utilisation des motifs structurels primaires du groupe. Selon une caractéristique, la mesure de représentativité d'un motif structurel primaire est la somme des degrés d'utilisation des motifs structurels primaires du groupe, pondérée par les distances entre le motif structurel primaire considéré et les motifs structurels primaires du groupe. Selon un mode de réalisation de la détermination d'un motif structurel de référence, le procédé comprend une étape de détermination d'un motif structurel de référence complémentaire associé à un groupe, le motif structurel de référence complémentaire comprenant des informations structurelles de motifs structurels primaires du groupe non comprises dans le motif structurel de référence médian 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 9

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 détermination pour déterminer le degré d'utilisation de motifs structurels primaires extraits en fonction du nombre de données hiérarchisées aptes à être représentées par lesdits motifs structurels primaires ; des moyens de groupement de motifs structurels primaires en groupes de motifs structurels primaires ; ledit groupement étant effectué en fonction du degré d'utilisation d'au moins un motif structurel primaire et d'une mesure de distance entre des motifs structurels primaires; 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 d'informations, é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 25 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 ; 30 la figure 5 représente un exemple de mise en oeuvre du groupement des motifs structurels primaires similaires ; 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 9 représente un algorithme de mise en oeuvre du procédé de construction d'un motif structurel de référence médian ; et la figure 10 représente un algorithme de mise en oeuvre du procédé de 10 construction d'un motif structurel de référence complémentaire.

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 15 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 20 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 25 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 30 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. 13

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 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émentracine du document XML. La procédure est donc lancée à l'étape 310 avec cet élément racine. 14

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 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 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. 15 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 pour ses items enfants que des références à des motifs. Lorsque plusieurs motifs structurels primaires identifiés sont identiques, il 5 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. 10 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 15 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 20 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 25 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 consiste à 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, si la condition n'est pas vérifiée, on 30 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. 16

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 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. Cette étape est suivie d'une étape 510 dans laquelle le motif structurel primaire m le plus utilisé dans la structure de données hiérarchisées est sélectionné parmi l'ensemble M des motifs extraits précédemment, selon les algorithmes des figures 3 et 4 par exemple. La sélection d'un tel motif structurel primaire est décrite plus en détails ultérieurement.

La sélection du motif structurel primaire le plus utilisé est particulièrement avantageuse, car cela permet de traiter en priorité les motifs structurels participant le plus à la description du document. Ainsi les parties du document possédant les structures les plus fréquentes seront décrites avec plus de précision que les autres. Cette sélection est particulièrement avantageuse dans le cas du codage de document XML, car elle permet de coder plus efficacement les parties du document possédant les structures les plus fréquentes. Ceci implique un coût de codage faible car la différence entre la structure de données et le motif structurel primaire correspondant ne représente que des informations de contenu.

A 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 17

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. En variante, ce seuil prédéterminé peut dépendre du nombre de motifs structurels primaires restant dans l'ensemble M, le seuil augmentant quand ce nombre de motifs structurels primaires restant diminue. Ainsi, les groupes constitués pour les motifs structurels primaires les plus utilisés ne contiendront que des motifs structurels primaires très proches les uns des autres, tandis que les groupes constitués pour les motifs structurels primaires les moins utilisés pourront contenir des motifs structurels primaires relativement loin les uns des autres.

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 m 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, 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 à 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 18

primaire m (le motif m est alors dit motif associé au groupe g(m)). II est à noter 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 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. 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 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 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. 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 30 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. 20

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, celle-ci 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 10 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) limite), sans que le 15 motif structurel primaire m2 soit proche du motif structurel primaire ml (d(m2, ml) limite). 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 20 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é 25 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. Dans une variante de réalisation, le calcul de la distance est pondéré par le degré d'utilisation d'un motif. Considérons un groupe de motifs structurels 30 primaires g(m) associé au motif structurel primaire m. Comme décrit précédemment, tout motif structurel primaire r du groupe g(m) est à une distance d(m, r) du motif m. Or, il peut être particulièrement avantageux de considérer une 21

distance pondérée d(m, r, u(r)) égale à d(m, r) x A x u(r), où u(r) est le degré d'utilisation du motif r et A un paramètre de pondération. Ainsi, plus le motif r est utilisé, plus la distance pondérée augmente et r s'éloigne par conséquent du motif m. Cela favorise la création d'un groupe g(r) associé à r différent de g(m), même s'il existe peu de différences structurelles entre m et r car il existe beaucoup d'occurrences du motif r dans les données hiérarchiques. Inversement, moins le motif r est utilisé, plus la distance diminue et r se rapproche du motif m. Cela favorise la représentation du motif r par le motif m même s'il existe de nombreuses différences structurelles car il existe très peu d'occurrences du motif r dans les données hiérarchiques. Dans l'un ou l'autre cas, les coûts de codage sont plus faibles. Lors de l'étape 510 de la figure 5, le motif structurel primaire m le plus utilisé dans la structure de données hiérarchisées est sélectionné parmi l'ensemble M des motifs extraits.

Dans le cas particulier des motifs structurels primaires d'ordre 1, le motif m sélectionné est celui dont la structure correspond au nombre le plus élevé de noeuds. Dans le cas d'un document écrit en langage XML, le degré d'utilisation u(m) d'un motif m correspond au nombre d'éléments XML pouvant être 20 représentés par le motif structurel primaire m. Une méthode de calcul pour cette valeur consiste à calculer, pour chaque motif structurel primaire m, le nombre d'éléments du document XML directement représentés par ce motif structurel primaire. Selon un mode de réalisation, cette valeur est obtenue directement lors 25 de l'extraction des motifs structurels primaires réalisée au moyen notamment de l'algorithme de la figure 3. Selon une variante de réalisation, pour chaque motif structurel primaire m, la valeur du degré d'utilisation u(m) est calculée en faisant la somme du nombre d'éléments directement représentés par le motif structurel primaire m et du 30 nombre d'éléments directement représentés par des motifs structurels primaires proches (situés à une distance inférieure à la valeur limite) du motif structurel 22

primaire m, c'est-à-dire par le nombre d'éléments pouvant être représentés par le motif structurel primaire m. Toutefois, selon cette méthode, seuls les motifs structurels primaires se trouvant dans l'ensemble des motifs structurels primaires M en cours sont comptabilisés. Toutes les variantes de réalisation précédentes pour le calcul du degré d'utilisation d'un motif structurel primaire associé à un élément XML peuvent être étendues à un motif structurel primaire d'ordre n. Selon une autre variante de réalisation de l'étape 510 de la figure 5, le motif structurel primaire sélectionné est un motif quelconque parmi l'ensemble M des motifs structurels primaires extraits. Cette variante de réalisation est toutefois avantageuse en prenant comme mesure de distance pour la formation des groupes une distance pondérée par le degré d'utilisation des motifs comme décrit précédemment.

Selon une variante de réalisation de l'étape de groupement des motifs structurels primaires, les motifs structurels primaires ne représentant que peu de structures parmi les données hiérarchisées ne sont pas considérés. Dans ce cas, l'étape 570 est modifiée pour vérifier si le nombre de motifs structurels primaires restant dans l'ensemble M est inférieur à un seuil prédéterminé. Si c'est le cas, l'algorithme se termine. Sinon, l'algorithme se poursuit à l'étape 510. Selon une autre variante, l'étape 570 est modifiée pour vérifier que le degré d'utilisation du motif structurel primaire le plus utilisé restant dans l'ensemble M est inférieur à un seuil prédéterminé. Si c'est le cas, l'algorithme se termine, sinon, l'algorithme se poursuit à l'étape 510. Cette vérification permet de ne pas regrouper les motifs structurels primaires les moins utilisés et de ne conserver que ceux représentant la structure d'un nombre suffisant de parties du document. Cette variante est particulièrement avantageuse pour le codage d'un document. Dans ce cas, le concept de motifs ne sera pas utilisé pour représenter les 30 structures de données correspondantes. 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 23

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. 5 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 10 de ces motifs. Ce motif ainsi construit est dit motif structurel de référence englobant. Il est également possible de construire un motif structurel de référence englobant en forçant à avoir lors de l'étape de groupement des motifs structurels primaires, un motif structurel primaire englobant tous les autres. 15 Ceci peut être obtenu en redéfinissant la distance d(m, ms) en une distance unilatérale conditionnée par une inclusion du motif ms dans le motif m. Ainsi, si le motif ms n'est pas inclus dans le motif m, la distance est considérée comme très grande ou infinie. Si le motif ms est inclus dans le motif m, la distance entre ces motifs est calculée selon les méthodes décrites précédemment. Tous 20 les motifs ms associés au motif m seront englobés dans le motif m, et il suffit alors de choisir le motif m comme motif structurel de référence pour le groupe g(m). Un motif ml est considéré comme englobé dans un autre motif m2, quand le motif ml peut être obtenu à partir du motif m2 en supprimant certaines informations structurelles du motif m2. Cela signifie que toutes les informations 25 structurelles du motif ml se retrouvent dans le motif m2 dans l'ordre dans lequel elles se trouvent dans le motif 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 30 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 24

structurelles du motif structurel m2 ne se trouvant pas dans le motif structurel ml, tout en respectant l'ordre de ces informations structurelles. Il 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 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 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. D'autres variantes de construction des motifs structurels de référence existent comme par exemple les motifs structurels de référence médians et les motifs structurels de référence complémentaires. Un exemple d'algorithme de construction d'un motif structurel de référence médian est décrit en référence à la figure 9. L'algorithme débute à l'étape 910 par l'initialisation d'une variable cr à une valeur nulle et une variable mr à une valeur nulle. Dans la pratique, cette variable cr est initialisée à une valeur très grande. La variable mr correspond à la détermination du meilleur candidat parmi les motifs structurels primaires pour la détermination du motif structurel de référence médian. La variable cr correspond à la mesure de représentativité de ce meilleur candidat. Plus cette mesure est grande, plus le candidat est représentatif de l'ensemble du groupe.

L'étape suivante (étape 920) consiste à sélectionner un motif structurel primaire m dans le groupe g courant. L'algorithme se poursuit par le calcul de la mesure de représentativité c(m) de ce motif m. Cette mesure de représentativité correspond à la somme d'une mesure de proximité de ce motif m avec les autres motifs du groupe. En pratique, cette mesure de proximité est inversement proportionnelle à la distance entre deux motifs.. En variante, cette somme peut être pondérée par le nombre d'éléments du document XML directement représentés par chacun des motifs structurel primaires du groupe.

La formule de calcul de la mesure de représentativité c(m) peut ainsi être : n(k) c(m) _ + n (m) keg,kzm 1+ d (in, k) où n(k) est le nombre de noeuds associés au motif k. En variante, le calcul de c(m) peut être identique au calcul de u(m). L'algorithme se poursuit par la comparaison de la mesure de 5 représentativité c(m) avec la mesure de représentativité cr du motif structurel

primaire mr lors de l'étape 930. Si le motif m est plus représentatif que le motif mr, c'est-à-dire si c(m) est supérieure à cr, alors l'algorithme se poursuit à l'étape 940. L'étape 940 consiste à mettre à jour les variables cr et mr. La variable mr 10 prend pour valeur le motif m, tandis que la variable cr prend pour valeur la mesure de représentativité c(m) du motif m. Dans tous les cas, l'algorithme se poursuit à l'étape 950 consistant à vérifier au moyen d'un test s'il existe un autre motif structurel primaire du groupe g qui n'a pas été traité. 15 Dans l'affirmative, l'algorithme se poursuit à l'étape 920 précédemment décrite. Dans le cas contraire, l'algorithme se poursuit à l'étape 960 consistant à générer le motif structurel de référence mm(g) représentant le groupe g à partir du motif structurel primaire mr. 20 L'algorithme se termine à l'étape 970. Un exemple d'algorithme de construction d'un motif structurel de référence complémentaire est décrit en référence à la figure 10. L'algorithme débute à l'étape 1010 par la détermination des motifsstructurels de référence médians comme décrit en référence à la figure 9. 25 L'algorithme se poursuit à l'étape 1020 par l'initialisation d'une variable mr à une valeur consistant en un ensemble de motifs constitué d'un unique élément qui est le motif structurel de référence médian mm(g) du groupe g. Cette variable correspond à l'ensemble des motifs structurels de référence pour g. L'étape suivante (étape 1030) consiste à calculer l'ensemble de motifs gr, 30 l'ensemble des motifs du groupe g non entièrement décrits par le motif structurel de référence mr. Cette étape consiste à déterminer tous les motifs du groupe g 27

qui ne sont pas englobés dans l'union de plusieurs motifs de l'ensemble de motifs structurels de référence mr. En pratique, cette étape consiste à calculer l'union de tous les motifs de l'ensemble de motifs structurels de référence mr, puis à vérifier pour chaque motif de g si ce motif est englobé dans cette union. Si ce motif n'est pas englobé dans l'union ainsi calculée, alors il est ajouté à l'ensemble de motifs gr. L'algorithme se poursuit à l'étape 1040 consistant à vérifier si l'ensemble de motifs gr est vide. Si tel est le cas, l'algorithme se poursuit à l'étape 1070 décrite ultérieurement.

Dans la négative, l'algorithme se poursuit à l'étape 1050 par la détermination du motif structurel de référence médian mm(gr) de l'ensemble de motifs gr. Cette détermination est réalisée comme précédemment décrit en référence à la figure 9. Après l'étape 1050, l'étape 1060 optimise le motif structurel de référence mm(gr) avant de l'ajouter à l'ensemble de motifs structurels de référence mr. Cette optimisation consiste à enlever du motif structurel de référence mm(gr) tous les items de ce motif contenus dans un motif de l'ensemble de motifs structurels de référence mr, cette suppression respectant l'ordre des items. Ainsi, le motif optimisé correspond à la différence entre l'union des motifs de l'ensemble de motifs structurels de référence mr et la moyenne des motifs de l'ensemble de motifs gr. En variante, l'optimisation du motif structurel de référence mm(gr) comprend aussi la suppression de l'identifiant de l'élément XML qu'il représente. Selon une autre variante, le calcul du motif structurel de référence médian pour l'ensemble de motifs gr lors de l'étape 1050 utilise une formule différente pour la mesure de la représentativité c(m) que lors du calcul des motifs structurels de référence médians pour les groupes de M lors de l'étape 1010. Ceci permet par exemple d'utiliser une formule pour la mesure de la représentativité c(m) permettant d'obtenir un motif structurel de référence médian proche de l'intersection des motifs du groupe considéré lors de l'étape 1010, tandis que lors de l'étape 1050, on utilisera une formule pour la mesure de la représentativité 28

c(m) permettant d'obtenir un motif structurel de référence médian proche du motif englobant pour les motifs considérés. Après l'étape 1060, l'algorithme se poursuite à l'étape 1030 décrite précédemment.

Dans le cas où l'ensemble de motifs gr est vide à l'étape 1040, l'algorithme se poursuit à l'étape 1070 consistant à générer la liste de motifs structurels de référence mc(g) représentant le groupe g à partir de l'ensemble de motifs structurels de référence mr. Parmi cette liste de motifs structurels de référence mc(g), le motif structurel de référence médian a un rôle particulier : il est le motif structurel de référence principal parmi l'ensemble des motifs structurels de référence complémentaires pour le groupe g. L'algorithme se termine à l'étape 1080. Une fois que les motifs structurels de référence ont été déterminés, il est 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 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. Dans le cas où les motifs structurels de référence complémentaires sont utilisés, on commence par déterminer quel motif structurel de référence principal est le plus proche de l'élément XML. Puis, parmi tous les motifs structurels de référence complémentaires liés à ce motif structurel de référence principal, on détermine ceux qui permettent de décrire entièrement le motif structurel primaire associé à l'élément XML. En pratique, on recherche un groupe de motifs structurels complémentaires dont l'union avec le motif structurel de référence principal englobe le motif de base associé à l'élément XML. 29

Les motifs structurels de référence ainsi obtenus seront utilisés pour représenter 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 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, 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. 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. 30

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 5 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 10 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 15 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. 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 20 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 25 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 30 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 31

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 32

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.

Claims

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 ; détermination du degré d'utilisation de motifs structurels primaires extraits en fonction du nombre de données hiérarchisées aptes à être représentées par lesdits motifs structurels primaires ; groupement de motifs structurels primaires en groupes de motifs structurels primaires (220) ; ledit groupement étant effectué en fonction du degré d'utilisation d'au moins un motif structurel primaire et d'une mesure de distance entre des motifs structurels primaires; et détermination d'un motif structurel de référence par groupe de motifs structurels primaires déterminé (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. 34

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 l'étape de groupement des motifs structurels primaires comprend les étapes suivantes : sélection du motif structurel primaire présentant un degré 10 d'utilisation parmi les degrés d'utilisation les plus élevés ; - groupement des motifs structurels primaires situés, par rapport au motif structurel primaire sélectionné, à une distance inférieure ou égale à une valeur prédéterminée ; et répétition des étapes de sélection et de groupement parmi les 15 motifs structurels primaires non encore groupés.

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 fonction du degré d'utilisation du premier motif structurel primaire. 20

7. Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que l'étape de groupement des motifs structurels primaires comprend les étapes suivantes : sélection d'un motif structurel primaire ; 25 groupement des motifs structurels primaires situés, par rapport au motif structurel primaire sélectionné, à une distance inférieure ou égale à une valeur prédéterminée, ladite distance étant pondérée par le degré d'utilisation des motifs structurels primaires ; et répétition des étapes de sélection et de groupement parmi les motifs 30 structurels primaires non encore groupés. 35

8. 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.

9. 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 fonction du 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.

10. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le degré d'utilisation d'un motif structurel primaire est déterminé en fonction du nombre de données hiérarchisées dont les informations structurelles correspondent aux informations structurelles de ce motif structurel primaire.

11. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le motif structurel de référence associé à un groupe correspond au motif structurel primaire parmi les motifs structurels primaire du groupe ayant le degré d'utilisation le plus élevé.

12. Procédé selon l'une quelconque des revendications 1 à 10, 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 déterminé étant dit motif structurel de référence englobant.

13. Procédé selon l'une quelconque des revendications 1 à 10, caractérisé en ce que le motif structurel de référence associé à un groupe est déterminé en fonction d'au moins certains des motifs structurels primaires du groupe et, pour chaque motif structurel primaire, d'une mesure de 36 représentativité par rapport aux données hiérarchiques associées à des motifs structurels primaires du groupe, le motif structurel de référence ainsi déterminé étant dit motif structurel de référence médian.

14. Procédé selon la revendication 13, caractérisé en ce que le motif structurel de référence associé à un groupe est plus particulièrement déterminé en fonction des motifs structurels primaires ayant les mesures de représentativité les plus élevées.

15. Procédé selon la revendication 13 ou 14, caractérisé en ce que la mesure de représentativité d'un motif structurel primaire est fonction des degrés d'utilisation des motifs structurels primaires du groupe.

16. Procédé selon l'une quelconque des revendications 13 à 15, caractérisé en ce que la mesure de représentativité d'un motif structurel primaire est la somme des degrés d'utilisation des motifs structurels primaires du groupe, pondérée par les distances entre le motif structurel primaire considéré et les motifs structurels primaires du groupe.

17. Procédé selon l'une quelconque des revendications 13 à 16, caractérisé en ce que le procédé comprend une étape de détermination d'un motif structurel de référence complémentaire associé à un groupe, le motif structurel de référence complémentaire comprenant des informations structurelles de motifs structurels primaires du groupe non comprises dans le motif structurel de référence médian du groupe.

18. 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 Ià17; 37 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).

19. Procédé de codage selon la revendication 18, 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. 10

20. 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 15 primaires représentant un ensemble d'informations structurelles ; - des moyens de détermination pour déterminer le degré d'utilisation de motifs structurels primaires extraits en fonction du nombre de données hiérarchisées aptes à être représentées par lesdits motifs structurels primaires ; 20 des moyens de groupement de motifs structurels primaires en groupes de motifs structurels primaires ; ledit groupement étant effectué en fonction du degré d'utilisation d'au moins un motif structurel primaire et d'une mesure de distance entre des motifs structurels primaires ; et des moyens de détermination pour déterminer un motif structurel de 25 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é.

21. Dispositif de codage de données hiérarchisées, caractérisé en ce 30 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 20 ;5 38 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.

22. 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 structurels de référence selon l'une quelconque des revendications 1 à 17, lorsque ce programme est chargé et exécuté par l'appareil programmable.

23. 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 18 ou 19, lorsque ce programme est chargé et exécuté par l'appareil programmable.

24. 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 à 17.

25. 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 18 ou 19.