Brevet FR2820563A1 — publié le 20020809

r PROCÉDÉ DE COMPRESSION DÉCOMPRESSION D'UN DOCUMENT STRUCTURÉ. La présente invention concerne un procédé de compression décompression de documents structurés. Elle s'applique notamment, mais non exclusivement, à la transmission de documents tels que des images ou séquences d'images, des données vidéo ou sonores, par des réseaux de transmission de données numériques, ainsi qu'au stockage de tels documents. Un document structuré est une collection d'ensembles d'informations associés chacun à un type et des attributs, et composés entre eux selon des relations principalement hiérarchiques. Ces documents emploient un langage de structuration tel que SGML, HTML, XML, permettant notamment de distinguer les différents sous-ensembles d'informations composant le document. Par opposition, dans un document dit linéaire, les informations de contenu du document sont mélangées aux informations de présentation et de typage. Un document structuré inclut des repères de séparation des différents ensembles d'informations du document. Dans le cas des formats SGML, XML ou HTML, ces repères appelés"balises"sont de la forme" "et" ", le premier repère indiquant le début d'un ensemble d'informations"XXXX"et le second la fin de cet ensemble. Un ensemble d'informations peut être composé de plusieurs ensembles d'informations de plus bas niveau. Ainsi, un document structuré présente un schéma de structure hiérarchique ou arborescente, chaque noeud représentant un ensemble d'informations et étant relié à un noeud de niveau hiérarchique supérieur représentant un ensemble d'informations qui contient les ensembles d'informations de niveau inférieur. Les noeuds situés en bout de branche de cette structure arborescente représentent des ensembles d'informations contenant des données d'un type prédéfini, qui ne peuvent pas être décomposées en sous-ensembles d'informations. Ainsi, un document structuré contient des repères de séparation représentés sous la forme de données textuelles ou binaires, ces repères délimitant des ensembles ou sous-ensembles d'informations pouvant eux-mêmes contenir d'autres sousensembles d'informations délimités par des repères. r Par ailleurs, un document structuré est associé à ce qu'on appelle un schéma de structure définissant sous la forme de règles la structure et le type d'information de chaque ensemble d'informations du document. Un schéma est constitué de groupes imbriqués de structures d'ensembles d'informations, ces groupes 9 pouvant être des séquences ordonnées, des groupes d'éléments alternatifs ou des p groupes d'éléments nécessaires, ordonnés ou non ordonnés. A l'heure actuelle, il existe plusieurs algorithmes de compression de document numérique. Certains algorithmes de compression sont conçus pour traiter directement les données binaires du document, sans tenir compte du type de ces données. Ces algorithmes présentent l'avantage de pouvoir traiter n'importe quel document, mais sont peu performants (taux de compression peu élevé) pour traiter des documents volumineux qui sont généralement de type son ou image. On connaît par ailleurs d'autres algorithmes de compression plus efficaces, mais spécialement adaptés à un type de données, par exemple de type image ou son, de sorte qu'ils ne sont pas utilisables, ou performants s'ils sont appliqués à des documents ne contenant pas exclusivement des données pour lesquelles ils sont conçus. Par conséquent les algorithmes de compression spécifiques d'un type de données particulier sont peu efficaces et mal adaptés pour traiter les documents structurés contenant différents types de données. La présente invention a pour but de supprimer ces inconvénients. Cet objectif est atteint par la prévision d'un procédé pour la compression et décompression d'un document structuré, associé à au moins un schéma de structure arborescent définissant une structure du document et comprenant des éléments de structure imbriqués, représentant des ensembles d'informations du document, chaque élément étant associé à un type d'information, caractérisé en ce qu'il comprend les étapes consistant à : - analyser et compiler le schéma de structure du document en vue d'obtenir pour chaque élément du schéma de structure, une séquence d'instructions exécutables, comportant des instructions d'insertion de codes de contrôle et de codes d'élément ou de codes d'appel de séquences d'instructions d'élément, et des instructions de contrôle du déroulement de l'exécution de la séquence en fonction des valeurs des codes de contrôle, et - décompresser le document à décompresser qui se présente sous la forme d'un r flux binaire, cette étape comprenant l'exécution des séquences d'instructions (5) sur le flux binaire, en vue de reconstituer un document au format d'origine ayant une structure au moins équivalente. Avantageusement, au moins un type d'élément d'informations des éléments de base est associé à un algorithme de décompression adapté, le procédé comprenant l'exécution de cet algorithme de décompression pour restituer l'ensemble d'informations correspondant du document structuré d'origine, lorsqu'un code binaire correspondant audit type d'élément d'informations est repéré durant l'exécution des séquences d'instructions, dans le flux binaire c constituant le document compressé. Selon une particularité de l'invention, le procédé comprend une étape de compilation des séquences d'instructions obtenues pour chaque élément dudit schéma de structure, pour obtenir un programme binaire de décodage dédié audit schéma de structure, directement exécutable par un calculateur. Selon une autre particularité de l'invention, en vue de la compression du document structuré, le procédé comprend l'analyse et la compilation du schéma de structure du document pour déterminer pour chaque élément du schéma de structure, une séquence d'instructions exécutables, l'exécution des séquences d'instructions sur les ensembles d'informations correspondants du document à compresser, en vue de générer un flux binaire contenant les ensembles d'informations compressés du document. Selon encore une autre particularité de l'invention, au moins un type d'information des éléments de base est associé au préalable à un algorithme de compression adapté, le procédé comprenant en outre l'exécution de l'algorithme de compression lorsqu'un ensemble d'informations ayant un type d'informations associé audit algorithme est détecté durant l'exécution des séquences d'instructions, sur le document structuré. Selon encore une autre particularité de l'invention, le procédé selon l'invention comprend une étape préalable de normalisation du schéma de structure du document, de manière à obtenir un ordre unique prédéfini des éléments du schéma. De préférence, chaque code d'ensemble d'informations est repéré dans le document compressé, de manière à permettre l'accès direct à un ensemble d'informations particulier, sans qu'il soit nécessaire de décompresser les ensembles d'informations précédant l'ensemble à décompresser. Avantageusement, le procédé selon l'invention comprend une étape préalable d'optimisation et de simplification du schéma de structure du document consistant à réduire le nombre de niveaux hiérarchiques de groupes d'éléments de structure. De préférence, le document compressé comprend pour chaque ensemble d'informations du document d'origine, un code permettant de déterminer l'élément de structure associé à l'ensemble d'informations et la valeur binaire de l'ensemble d'informations compressé. Dans le document compressé, la fin d'un groupe de plusieurs occurrences d'ensembles d'informations de même type est de préférence marquée par un code binaire déterminé dans la séquence d'instructions relative au type des ensembles d'informations. Alternativement, chaque élément du schéma de structure est en outre associé à un ensemble de nombres d'occurrences possibles, indiquant le nombre de fois qu'un ensemble d'informations ayant cet élément de structure peut apparaître dans l'ensemble d'informations de niveau immédiatement supérieur auquel il appartient. Un mode de réalisation préféré de l'invention sera décrit ci-après, à titre d'exemple non limitatif, avec référence aux dessins annexés dans lesquels : La figure 1 représente sous la forme d'un schéma-bloc l'enchaînement des différentes étapes du procédé selon l'invention ; Les figures 2a, 2b et 2c représentent graphiquement un schéma de structure sous la forme d'un arbre ; La figure 3 montre un schéma de structure obtenu en appliquant une méthode de réduction selon l'invention au schéma de structure représenté sur la figure 2 ; r Les figures 4a, 4b et 4c montrent un schéma de structure obtenu en appliquant une autre méthode de réduction selon l'invention au schéma de structure représenté sur la figure 2. La figure 1 représente l'enchaînement des différentes étapes du procédé selon l'invention. Ce procédé est conçu pour traiter un document structuré constitué d'un schéma de structure 1 définissant la structure du document et des informations structurées 2 du document. Dans le langage XML-Schema, un schéma de structure présente par exemple la forme suivante : element name="C" > element name="A"type="TA"minOccurs=l maxOccurs=l/ > element name="B"type="TB"min0ccurs=l max0ccurs=l/ > Ce schéma indique que l'élément nommé"C"présente une structure complexe constituée d'un premier élément nommé"a2"de type booléen qui est optionnel, d'un second élément nommé"al"de type entier qui est toujours présent dans la structure, et d'un groupe d'éléments alternatifs nommés"A"et"B"de types respectifs"TA"et"TB", l'un des ces deux éléments étant présent une seule fois dans la structure. Les types"TA"et"TB"sont définis dans le schéma de structure du document par une formulation analogue. D'une manière générale, on utilise les groupes d'éléments suivants pour définir une structure de document : - SEQ : qui définit une liste d'éléments ordonnés qui doivent tous apparaître r dans le document et dans l'ordre indiqué, CHO : qui définit un ensemble d'éléments alternatifs, un seul élément du 1 groupe devant apparaître, - ET : qui définit un ensemble d'éléments qui doivent tous apparaître dans le document et dans un ordre quelconque qui ne doit pas être modifié, - ET NO : qui définit un ensemble d'éléments qui doivent tous être présents dans le document dans un ordre quelconque qui n'a pas d'importance, et - ANY : qui comprend un élément quelconque parmi tous les éléments possibles que l'on peut trouver dans le document. Selon l'invention, cette formulation est analysée et transformée à l'étape 11 du procédé pour obtenir des arbres syntaxiques 4, à raison d'un arbre par élément de structure. L'arbre syntaxique correspondant à l'élément de structure TC est s symbolisé par l'expression suivante : TCSEQ [l, l] (ET [l, l] (al [l, l], a2b. [0, l]), CHO [l, l] (ATA [l, l], BTB [l, l])) dans laquelle : "A [x, y]" indique que l'élément A est répété de x à y fois dans le document, y pouvant être égal à"*"représentant une valeur indéterminée. Cette expression peut être représentée par l'arbre montré sur la figure 2c, comprenant un élément racine"TC"43 constitué d'une occurrence unique d'un groupe de type séquence 44. Ce groupe comprend une occurrence unique d'un groupe de type"ET"non ordonné 45 et une occurrence unique d'un groupe alternatif 46. Le groupe 45 est constitué d'une occurrence unique d'un entier nommé"al"et d'un booléen nommé"a2", et le groupe 46 comprend une occurrence unique d'un élément nommé"A"de type"TA"et d'un élément nommé"B"de type"TB". Les types"TA"et"TB"obtenus à l'étape 11 sont par exemple donnés par les formules suivantes : TA-SEQ [l, l] (ET [l, l] (a3i [l, l], a4. JO, l]), SEQ [l, l] (XTc [lJ], YTc [l, l)) TB- SEQ [l, l] (al [l, l], a5, [l, l]) et représentés par les arbres montrés respectivement sur les figures 2a et 2b. Le type"TA"31 comprend un groupe unique 32 de type séquence constitué de r deux groupes uniques 33, 34, respectivement de type ET et SEQ. Le groupe 33 comprend deux occurrences uniques de type entier, nommées respectivement "a3"et"a4". Le groupe 34 comprend deux occurrences uniques de type"TC" nommées respectivement"X"et"Y". Le type"TB"39 est constitué d'un groupe unique 40 de type séquence comprenant deux booléens respectivement nommés"al"et"a5". Bien que dans la description qui précède, on a distingué le nom de chaque élément et son type, le procédé selon l'invention s'applique également aux langages de structuration qui ne font pas cette distinction. En outre, certains langages comme le langage XML Schéma autorisent ce que l'on appelle le polymorphisme ou l'utilisation de sous-types. De tels sous-types sont définis de la manière suivante : complexType type="TA2" > extension base="TA" > element name="X"type="TA"/ > Cette syntaxe définit les types TAl et TA2 comme des sous-types du type TA par restriction ou extension, et l'élément d'informations X de type TA. Un document ayant ce schéma de structure peut comprendre un élément X de type TAI qui peut être introduit de la manière suivante : De plus certains types possédant ainsi des sous-types peuvent être déclarés abstraits, ce qui signifie que les éléments d'informations dans un document ayant un schéma de structure comprenant la définition d'un type abstrait ne peuvent pas contenir des éléments d'informations ayant ce type. En fait, les types abstraits ne sont utilisés que pour créer des hiérarchies ou des classes de r types. Un type abstrait est défini dans le langage XML Schéma de la manière e suivante : Par ailleurs, les éléments de structure doivent être déterministes, c'est-à-dire qu'un élément ne doit pas pouvoir être interprété de plusieurs manières différentes. Par exemple, dans le schéma"CHO (a, SEQ (a, b))", dans le cas où "a"apparaît, on ne sait pas si"b"doit apparaître ensuite. Il existe à cet effet des algorithmes qui peuvent être appliqués par le procédé selon l'invention pour transformer un schéma non déterministe en un schéma déterministe. On peut par exemple se référer aux documents ["Regular expressions into finite automata"Brüggemann-Klein, Anne, Extended Abstract in I. Simon, Hrsg., LATIN 1992, S. 97-98. Springer-Verlag, Berlin 1992. Full Version in Theoretical Computer Science 120 : 197-213, 1993]. Ainsi, le schéma ci-avant peut par exemple être remplacé par"SEQ (a, b [0, l])". A l'étape 12 suivante du procédé selon l'invention, les éléments du schéma de structure transformés en arbres syntaxiques peuvent tout d'abord subir un traitement de réduction ou de simplification. Ce traitement de réduction peut consister par exemple à effectuer un a aplatissement global en générant un seul arbre syntaxique 51 à partir de tous les p arbres 31, 39 et 43, comme cela est représenté sur la figure 3. Cet arbre représente en fait un dictionnaire de tous les types d'éléments susceptibles d'être rencontrés dans le document, ces éléments étant rassemblés dans un groupe 52 de type alternatif apparaissant au moins une fois [1, *] dans le document. Dans cet arbre, les éléments de type complexe"A","B","X"et"Y" sont associés à un type"ANY", et l'élément"al"qui apparaissait deux fois S (dans les éléments"TB"et"TC") avec des types différents, est associé à un type par défaut"pcdata"selon le langage XML ou au type de l'élément dans le p document initial, par exemple texte. Un même ensemble d'informations peut en effet être représenté de plusieurs manières : par exemple une séquence binaire peut également être considérée comme une chaîne de caractères ou un nombre entier. r Alternativement, ce traitement de réduction consiste à aplatir localement les arbres syntaxiques pour obtenir les arbres représentés 31', 39'et 43'sur les figures 4a à 4c. Dans chacune de ces figures, les groupes 32 à 34 (figure 2a), 40 (figure 2b) et 44 à 46 (figure 2c) ont été respectivement remplacés par un groupe 53,54, 55 de type alternative apparaissant au moins une fois [1, *]. Les arbres"TA", Les arbres"TA","TB"et"TC"peuvent en outre subir un traitement supplémentaire pour supprimer les ambiguïtés apparaissant dans le schéma de structure. Dans certains cas, les arbres syntaxiques peuvent être simplifiés d'une manière non destructive, tout en améliorant la compacité du code binaire qui pourra être généré. Une telle simplification peut être effectuée dans le cas d'un groupe d'éléments contenant un seul élément X dont le nombre minimum d'occurrences nx est égal à 0 ou 1, de la forme : GROUP [nG, mG] (X [nx, mx]) dans laquelle GROUP peut être un groupe de type SEQ, CHO ou ET. Un tel groupe peut être remplacé par l'élément suivant : X na. nx, mG. mx]. Un autre cas de simplification non destructive est possible dans le cas d'un groupe d'éléments alternatifs CHO comprenant au moins un élément ou groupe d'éléments dont le nombre d'occurrences minimum est égal à 0. Ainsi, le groupe : CHO [nc, mc] (Xl [nxl, mxl], X2 [0, mx2], X3 [nX3, mX3]) peut être remplacé par : CHO [O, mc] (Xl [nxl, mxl], X2 [l, mx2], X3 [nx3, mx3]) De même, un groupe CHO [1, !] (.., CHO [1, !] (...),...) d'une unique occurrence de type CHO contenant notamment une unique occurrence de type CHO, peut être simplifié en étant remplacé par un groupe unique CHO [1, 1] (...) de type CHO contenant tous les éléments des deux groupes de type CHO. A l'étape 12, les arbres"TA", "TB"et"TC"subissent également un traitement r de normalisation qui consiste à réordonner le schéma de manière à obtenir un ordre unique des éléments du schéma. Ce traitement affecte ensuite un numéro binaire aux différents noeuds des arbres syntaxiques obtenus à la suite des traitements précédents. Ce numéro est utilisé lors de la compression de l'élément correspondant. Le traitement de normalisation consiste en particulier à attribuer à chaque groupe une signature constituée de la concaténation du nom du groupe avec la signature de tous les éléments et des sous-groupes du groupe, préalablement ordonnés. Ainsi, le groupe 53 sur la figure 4 est associé à la signature "CHO. a3. a4. X. Y". Lors de ce traitement, on considère que les groupes ordonnés (SEQ) sont déjà normalisés. Les groupes à normaliser sont donc les groupes de type alternatif ("CHO"), et les groupes"ET"et"ET Ce traitement comprend les étapes suivantes pour chaque groupe G composé de sous-groupes gi et d'éléments ei - la normalisation des sous-groupes g, éventuels du groupe G avant de normaliser le groupe G, l'algorithme de normalisation étant récursif, - le rangement des éléments ej éventuels du groupe G avant les sous-groupes e e ev gi, - le rangement des éléments ei dans un ordre prédéfini, - le rangement des sous-groupes g, dans l'ordre prédéfini, et - la détermination de la signature du groupe G donnée par la concaténation de toutes les signatures de ses composants (éléments et sous-groupes) suivant l'ordre établi à la suite des étapes précédentes. L'ordre prédéfini de rangement des composants du groupe peut être l'ordre alphanumérique de leurs signatures respectives, ou l'ordre décroissant de leur nombre minimal d'occurrences, les composants ayant le même nombre minimal d'occurrences étant ensuite rangés par ordre alphanumérique. Il est à noter que ce traitement de normalisation n'est pas nécessaire dans le procédé selon l'invention. L'ordre d'apparition des composants dans le schéma peut en effet être conservé. L'étape 13 suivante du procédé consiste à générer une séquence d'instructions 5, également appelée"syntaxe binaire", décrivant un flux binaire. Ce traitement r consiste à générer pour chaque arbre syntaxique ou type complexe du schéma de structure une séquence d'instructions, en commençant par les noeuds de plus bas niveau dans les arbres syntaxiques du schéma de structure arborescente du document. Des instructions d'appel aux syntaxes binaires ainsi générées pour les n noeuds de bas niveau, sont insérées ensuite dans les syntaxes binaires des noeuds de plus haut niveau dans lesquels les éléments de bas niveau apparaissent. De c cette manière, on obtient une syntaxe binaire pour l'ensemble du schéma de s structure du document, laquelle appelle les syntaxes binaires des éléments de plus bas niveau, d'une manière analogue à un logiciel comprenant un programme principal qui appelle des sous-programmes, lesquels peuvent également appeler d'autres sous-programmes, et ainsi de suite. La syntaxe binaire d'un élément X de type TX est de la forme suivante : r XTX , Ix ITX l : 1 : 1 r Si le type TX possède un ou plusieurs sous-types, il représente ce que l'on 1 appelle un polymorphisme. Dans ce cas, il est en outre associé à la syntaxe binaire suivante : XTX poly Si le type TX comporte les sous-types SI, S2,..., Sn, il faut considérer deux cas selon que le type TX par défaut est abstrait ou non. ITX Il Si le type TX par défaut est abstrait, on génère la syntaxe binaire"TXyoly" suivante, les sous-types SI,..., Sn étant au préalables rangés dans l'ordre de leurs signatures respectives : Table 1 if(flagPoly==0) { X S1 } else if(flagPoly=l) { X S2 j else if (flagpoly = k) { XSk+i } else if (flagPoly=n-l) { X Sn J v r E () étant la fonction arrondi à l'entier supérieur, et"flagPoly"contenant le code du numéro du sous-type à appliquer à l'élément X, et"X"indiquant les emplacements où doit être inséré le code de l'élément X. Si 2E(log)2(n) > n, on peut ajouter la ligne suivante à la fin de la syntaxe binaire pour détecter des dysfonctionnements : else SpecifieProcess "SpecificProcess"étant une procédure conçue pour signaler une erreur de traitement dans le cas où "flagPoly" n'a pas une valeur correspondant à un soustype de TX. Si le type par défaut TX n'est pas abstrait, la syntaxe binaire de Tu moly est obtenue en insérant la syntaxe binaire précédente dans la syntaxe binaire suivante : Table 2 typeInfbFlagIbit if (typeInfoFlag) { syntaxe binaire du polymorphisme J else XTX X TX dans laquelle "typeInfoFlag"est un code indiquant si X a le type TX ou l'un des sous-types de TX. Ensuite, on détermine la syntaxe binaire du nombre d'occurrences [n, m] de chaque élément X dont on a déterminé la syntaxe binaire. A cet effet, on distingue trois cas. Dans le premier cas, m et n sont égaux à 1, c'est-à-dire que l'élément X est associé aux nombres d'occurrences [1, 1]. La syntaxe binaire produite correspond à la celle qui a été générée pour l'élément X. r Dans le second cas, n = 0 et m = 1, la syntaxe binaire générée est la suivante : 1 Table 3 flags 1 bit if (flagX) { syntaxe binaire de X } binaire de X syntaxe } r dans laquelle flagX est un code sur un bit indiquant la présence ou non de X dans le document. Cette syntaxe binaire est analogue à une séquence d'instructions de programmation, dans laquelle l'élément X est inséré si la valeur de l'indicateur flagX est à"vrai". Dans le troisième cas, m-n est inférieur à une constante de seuil prédéterminée, 16 par exemple 2 (=65536), ce qui signifie que le nombre d'occurrences peut être p codé sous la forme d'un entier non signé sur 16 bits. Dans ce cas, la syntaxe binaire de l'élément X [n, m] est la suivante : Table 4 loopflagX E(log2(m-n-l)) bits for (k=0;k { syntaxe binaire de X J r dans laquelle "loopFlagX" est le code du nombre d'occurrences successives de X dans le document, auquel on a retranché le nombre n minimum d'occurrences de X, et Eo est la fonction arrondi à l'entier supérieur. Cette syntaxe indique que"loopflagX"est codé sur E (log2 (m-n+l)) bits et que X doit être inséré un nombre de fois égal à (loopflagX + n). Dans le quatrième cas, m n'est pas borné ou m-n est supérieur la constante de seuil prédéterminée. La syntaxe binaire générée est analogue à celle du troisième cas, à la différence que "loopflagX" n'est pas codé sur E (log2 (m-n+l)) bits, mais dans un autre format permettant de coder n'importe quel entier. Ce format peut par exemple être le format"UINTVLC"constitué d'ensembles d'un nombre prédéterminé de bits, par exemple 5 bits, le premier bit de chaque ensemble indiquant si oui ou non cet ensemble est le dernier du code du nombre entier, et les quatre bits suivants de l'ensemble étant utilisés pour coder le nombre entier. e Dans le troisième et quatrième cas, si le nombre d'occurrence minimum n est nul, on ajoute de préférence la syntaxe binaire suivante : Table 5 shuntFlagX 1 bit if (shuntFlagX) { syntaxe binaire de X[n,m] } r dans laquelle"shuntFlag"désigne un code sur 1 bit indiquant si oui ou non le nombre d'occurrences est nul, et la ligne"syntaxe binaire de X [n, m]"est la syntaxe binaire du nombre d'occurrences de X correspondant au troisième ou au quatrième cas. Alternativement, on peut choisir un autre type de codage dans lequel il n'est pas nécessaire d'introduire le nombre d'occurrences des éléments d'un schéma de structure. Ce type de codage utilise la syntaxe binaire suivante : Table 6 Table 6 flagX 1 bit syntaxe binaire de X flag X 1 bit } dans laquelle flagX est un code sur un bit indiquant si oui ou non ce code est suivi d'une nouvelle occurrence de X. Cette solution présente l'avantage de ne pas avoir à analyser tout le schéma de structure du document pour déterminer les nombres d'occurrences minimum et maximum de chaque élément de la structure. La syntaxe binaire d'un groupe de type séquentiel SEQ (X1, X2,..., Xn) est la suivante : Table 7 syntaxe binaire de X1 syntaxe binaire de X2 ... syntaxe binaire de Xn La syntaxe binaire d'un groupe de type alternatif CHO (X1, X2,..., Xn) est la v r suivante : TableS flagChoX E(log2(n)) bits if (flagCho=0) {L syntaxe binaire de X1 J elseif (flagCho=1) { syntaxe binaire de X2 } elseif (nagCho#n-l) { syntaxe binaire de Xn v r dans laquelle n est le nombre d'éléments dans le groupe, et"flagCho"est le code de l'élément à sélectionner dans le groupe CHO. 1 Comme précédemment, si 2' " > n, on peut ajouter la ligne suivante à la fin de la syntaxe binaire pour détecter des dysfonctionnements : else specificProcess r Cette instruction permet d'appeler une procédure de signalement d'erreur dans le cas où la valeur de l'indicateur"flagCho"ne correspond pas à l'un des éléments du groupe CHO. Dans le cas où l'on ne code pas le nombre d'occurrences, on peut également utiliser une valeur de"flagCho"non utilisée (si 2E ' (")) > n) pour marquer la dernière occurrence du groupe CHO : Table 9 flagCho E(log2(n)) bits while (FlagCho !=n) { if (flagCho#0) { insertion syntaxe binaire de XI } elseif (flagCho#l) { syntaxe binaire de X2 elseif (flagCho#n-1) syntaxe binaire de Xn } flagChoE (log2 (n)) bits } flagCho E(log2(n)) bits La syntaxe binaire du groupe de type ET est générée par une procédure récursive. Elle consiste en une imbrication de groupes de types CHO, chacun déterminant quel est l'élément présent dans la description. D'une manière plus précise, pour générer une telle syntaxe binaire, on distingue deux cas, selon que le groupe comprend un seul ou plusieurs éléments. Si le groupe ne contient qu'un seul élément, la syntaxe binaire d'un tel groupe est la même que celle d'un groupe de type séquence à un élément. Si le groupe contient n éléments, il peut s'écrire de la forme ET (X), X2,..., Xn). La syntaxe binaire d'un tel groupe est la suivante : Table 10 flagChoX E(log2(n)) bits if (flagCho#0) syntaxe binaire de XI syntaxe binaire de ET (X2,..., Xn) } elseif (flagCho#l) { syntaxe binaire de X2 syntaxe binaire de ET (il, X3,..., Xn) } elseif flagCho-n-l) syntaxe binaire de Xk syntaxe bînaire de ET(X1, ..., Xk-1, Xk+1, ..., Xn) } elseif (flagCho#n-1) { syntaxe binaire de Xn syntaxe binaire de ET(X1, X2, ..., Xn-1) } l Cette syntaxe binaire est obtenue à partir de la syntaxe binaire d'un groupe CHO (X), X2,..., Xn), dans laquelle on a ajouté, à la suite de la syntaxe binaire de chaque élément Xk du groupe (k étant compris entre 1 et n), la syntaxe binaire d'un groupe ET (XI,..., Xk-i, Xk+i,..., Xn) dans lequel on a retiré l'élément Xk. Cette syntaxe binaire est donc récursive. La syntaxe binaire du groupe de type ET NO est identique à celle d'un groupe SEQ, dans lequel on peut en outre optimiser le codage en adoptant un ordre r approprié des éléments du groupe. L'étape suivante 14 consiste à relire le document 2, à compresser les données qu'il contient en exécutant les syntaxes binaires qui ont été générées sur la structure du document, en vue d'obtenir un flux binaire comportant une succession de codes binaires dans lesquels on trouve la valeur compressée de chaque élément ou ensemble d'informations de base du document. Plus précisément, il s'agit de déterminer à partir du contenu du document, les valeurs à insérer dans le flux binaire, des différents codes"typeInfoFlag" "flagX","loopflagX",... définis par les séquences binaires. Selon un premier type de codage, ce flux binaire est de la forme (K. N. Vi.. VN) e pour chaque élément ou groupe d'éléments e, N étant le nombre d'occurrences de l'élément e ou le nombre d'ensembles d'informations successifs correspondant à l'élément e, K étant le code permettant de déterminer l'élément A s e, et Vt-. VN les valeurs respectives, éventuellement compressées des N occurrences de l'élément e. Si e est un groupe d'éléments, sa valeur V est décomposée en autant de séquences binaires (K. N. V) qu'il contient d'éléments. Toutefois, dans certains cas, N peut être omis, notamment lorsque ce nombre est fixe. Il en est de même de K dans le cas par exemple d'un groupe de type séquence. A titre d'exemple de comparaison, si l'on considère le format étendu de représentation des durées, tel que défini par la norme ISO 8601 : sPnYnMnDTnHnMnS dans lequel s est le signe"+"ou"-", nY représente un nombre of d'années (entier infini), nM un nombre de mois (entier infini), nD un nombre de jours (entier infini),'T'est un caractère séparateur entre la date et le temps, nH un nombre d'heures (entier infini), nM un nombre de minutes (entier infini) et nS un nombre de secondes (décimal), tous ces éléments étant optionnels. Ce format correspond à un schéma de structure qui peut être représenté de la manière suivante : dans laquelle"\+"indique l'insertion du caractère"+"," (Xly)" indique l'insertion ----de l'élément x ou y," ?" indique que l'insertion de l'élément précédent est optionnelle, et"\d+"représente un nombre binaire sur un nombre de bits quelconque. Cette structure correspond à la syntaxe binaire suivante : Table 11 Durée Nombre de bits Signe 1 YearDefined1 if (YearDefined) Années UINT VLC MonthDefined 1 if (MonthDefined) Mois UINT VLC DayDefined 1 if (DayDefined) Jour UINT VLC HoursDefined1 if (HoursDefined) Heures UINT VLC MinutesDefined 1 if (MinutesDefined) Minutes UINT VLC SecondsDefined 1 if (SecondsDefined) Secondes UINT VLC, UINT VLC dans laquelle la valeur Signe vaut 0 pour représenter le signe"+"et 1 pour représenter le signe Ainsi, la durée"+P1347Y"est codée de la manière suivante : + +1347Y M D H M S 0 1 1 0101 00100 00011 0 0 0 0 0 ------ Ce codage nécessite 22 bits, tandis que le codage classique nécessite 48 bits. 1 La durée"-P1Y2MT2H"est codée de la manière suivante : 1 1Y 2M D 2H M S 1 100001 100010 0 100010 0 0 r soit sur 22 bits au lieu de 72 avec le codage classique. Au préalable, on peut réaliser un entête général du document compressé qui regroupe plusieurs paramètres codés, utiles à la description du document. Ainsi, un tel entête peut comprendre une signature du ou des schémas de structure utilisés, et un ensemble de paramètres décrivant le codage utilisé, comme par exemple : - un paramètre indiquant si le codage de la longueur de chaque élément est obligatoire ou optionnel ou non présent dans le document, - un paramètre indiquant si les éléments peuvent ou non être sous-typés, c'est- à-dire associés à un type plus précis que leur type de base, et - un paramètre indiquant le type de codage utilisé pour le nombre d'occurrences. Chaque élément d'information du document peut également être associé à un entête, sa présence et sa nature étant précisés dans l'entête du document. L'entête d'un élément peut ainsi comprendre la longueur codée de celui-ci, de manière à permettre, lors de la décompression du document, l'accès à un élément particulier sans décompresser tous les éléments précédents dans le document. Les entêtes d'éléments sont insérés dans le document par exemple juste avant le codage de la valeur des éléments. D'une manière générale, la décompression du document consiste à lire séquentiellement le document compressé, en exécutant les syntaxes binaires générées à partir du schéma sur le flux binaire obtenu par la lecture séquentielle du document compressé. Ce traitement permet en outre de vérifier que la structure du document compressé correspond au schéma compilé en syntaxes binaires. Lorsque le nombre d'occurrences des éléments du schéma de structure n'est pas codé, le codage des éléments n'est alors plus que de la forme KV, le codage de chaque ensemble d'éléments de même type se terminant par un bit Kesc valant 0. En fait, ce type de codage n'est intéressant que pour le codage de formes complexes, et pour des éléments n'ayant pas de nombre d'occurrences maximal ou un nombre d'occurrences minimum nul. Il est en particulier tout à fait adapté au codage de groupes de type alternatif comprenant un nombre d'éléments r p différent de 2P, p étant un nombre entier. Ce type de codage peut être combiné avec le précédent. Il suffit alors pour cela, de l'indiquer dans l'entête du document compressé et d'attribuer un bit aux endroits du codage où doivent se trouver un nombre d'occurrences. Selon l'invention, au moins un type de base des ensembles d'informations du document est associé à un module externe de compression 16. De cette manière, lors de la lecture du document, les types respectifs des ensembles d'informations rencontrés sont analysés, et lorsqu'un type d'ensemble d'informations est associé à un module externe de compression 16, celui-ci est appliqué au contenu de l'ensemble d'information et le résultat de la compression inséré dans le document compressé en tant que valeur de l'ensemble de d'information correspondant. Les modules externes de compression peuvent par exemple appliquer la norme "mp3"pour les informations sonores, "jpeg"pour les images et"MPEG 1"ou "MPEG 2"pour les données de type vidéo. Si aucun module de compression n'est associé à un type d'ensemble d'informations, on peut utiliser un module de compression par défaut ou récupérer les ensembles d'informations ayant ce type tels qu'ils apparaissent dans le document initial. Par exemple, le codage la structure CHO [0, *] (al, a2, a3) produit la syntaxe binaire suivante : Table 12 loopflagCho UINT VLC bits for (k=0 ; k ; k++) { flagCho 2 bits if (flagCho#0) { valeur Val de al } elseif (flagCho==I) valeur Va2 de a2 } elseif (flagCho==2) { valeur Va3 de a3 } J r Si maintenant on souhaite coder l'occurrence" a2 a3 a1 a1 a3" ayant cette structure, le résultat du codage est le suivant dans le cas où l'on code le nombre d'occurrences : 00101 01 Val 10 Va3 00 Va, 00 Val 10 Va3 dans lequel"00101"représente la valeur binaire du nombre d'occurrences soit 5 dans le format"UINTVLC", et Val, Va2 et Va3 sont respectivement les valeurs des occurrences de a â2 et a3. Dans le cas où l'on ne code pas le nombre d'occurrences, le codage est le suivant : 01 V, 10 Va3 00 Val 00 Va1 10 Va3 11 "11"correspondant au code de fin du nombre d'occurrences qui est dans ce cas intégré dans le code de sélection du groupe CHO. Dans le premier cas, on obtient un codage sur 15 bits en plus des codes des valeurs des éléments, tandis que dans le second cas, on obtient un codage plus compact sur 12 bits. Le traitement de codage de l'occurrence"b2 bl a,"ayant pour structure ! conduit à la syntaxe binaire suivante : ! Table 13 shuntFlagSeqIbit if (shuntFlagSeq) { loopflagSeq UINT VLC bits for (k=0 ; k ; k++) { shuntFlagal 1bit if (shuntFlagal) { loopflagal UINT VLC bits for (k=0;k { code valeur Va1 de al } } shuntFlagCho 1 bit if (shuntFlagCho) { loopflagacho UINT VLC bits for (k=0;k { flagCho 1 bit if (flagCho-=0) { code valeur Vb1 de bl } elseif (flagCho code valeur Vb2 de b2 } } } J r Cette syntaxe binaire conduit au codage suivant : 1 nombre d'occurrences de la séquence différent de 0 00010 nombre d'occurrences de la séquence (ici 2 fois) 0 nombre d'occurrences de a = 0 1 nombre d'occurrences de CHO différent de 0 00010 nombre d'occurrences de CHO (2 fois) 1 code du choix de b2 Vb2 codage de la valeur de b2 0 codage du choix de b, Vbl codage de la valeur de bl. 1 nombre d'occurrences de a = 0 00001 nombre d'occurrences de al (1 fois) Val codage de la valeur de a, 0 nombre d'occurrences de CHO = 0 Si l'ordre des attributs n'est pas utile (comme dans le langage XML), on peut effectuer un codage qui réordonne les attributs des éléments dans un ordre prédéterminé, par exemple suivant un ordre alphanumérique, puis suivant le fait qu'ils sont requis ou non. Cette disposition permet de réduire d'autant la taille de la description compressée. Si dans l'entête du document, il est indiqué que le codage de la longueur est optionnel ou obligatoire, les éléments sont associés à un entête dans le document compressé, contenant la longueur en nombre de bits de la valeur de l'élément. Cette particularité permet un accès direct à un élément du document compressé sans avoir à décompresser les éléments situés avant dans le document, en lisant à l'aide des syntaxes binaires uniquement les longueurs r respectives de ces éléments jusqu'à l'élément recherché. La longueur des éléments peut être codée de la manière suivante. Dans le cas où dans l'entête du document, il est indiqué que le codage de la longueur des éléments est obligatoire, la longueur L des éléments en nombre de bits est calculée à l'aide la formule suivante : où p représente le nombre d'octets (en codage ASNI ou utilisant les bits de poids fort de chaque octet utilisé pour coder ce nombre) utilisés pour coder la longueur de l'élément, et h représente le nombre de bits restants de cette longueur (h Il est à noter que le module externe de compression 16 qui est appelé pour effectuer le codage de la valeur d'un élément peut fournir en retour cette longueur. Dans le cas où le codage de la longueur des éléments n'est pas obligatoire, la valeur du premier bit correspondant à la valeur de l'élément indique si les bits suivants représentent ou non la longueur de l'élément. Le traitement de décompression d'un document ainsi compressé est effectué en exécutant les étapes 11 à 14 sur le schéma de structure du document pour obtenir les syntaxes binaires des éléments de structure du schéma de structure du document, puis en exécutant l'étape 14'de décodage ou de décompression du document, cette étape consistant à parcourir le document compressé en exécutant les syntaxes binaires obtenues à la suite des étapes 11 à 14, de manière à pouvoir déterminer le type et le nom des éléments d'information compressés rencontrés dans le document. Les valeurs des éléments qui ont été obtenues à l'aide de modules 16 de compression externes sont décompressées à l'aide de modules de décompression 16'correspondants. Il est à noter que si l'on doit traiter (compresser ou décompresser) plusieurs documents ayant le même schéma de structure, les étapes Il à 13 ne sont exécutées qu'une seule fois, seules les étapes 15 et 16 (ou 15'et 16') devant être appliquées à chaque document à traiter. En outre, par un traitement de conversion approprié, la syntaxe binaire d'un schéma de structure, qui est proche d'un langage de programmation classique, peut être compilée 17 pour générer un code binaire 6 directement exécutable par le processeur d'un calculateur. Le procédé selon l'invention permet donc de générer automatiquement un programme de décompression exécutable, donc très rapide, dédié à un schéma de structure donné. v REVENDICATIONS REVENDICATIONS 1 r 1. Procédé pour la compression et décompression d'un document 1 structuré, associé à au moins un schéma de structure arborescent (1 ; 31, 39, 43) définissant une structure du document et comprenant des éléments de structure (32,33, 34,40, 44,45, 46, a3, a4, X, Y, al, a5, al, a2, A, B) imbriqués, représentant des ensembles d'informations du document, chaque élément étant associé à un type d'information, caractérisé en ce qu'il comprend les étapes consistant à : - analyser (11) et compiler (13) le schéma de structure du document en vue d'obtenir pour chaque élément du schéma de structure, une séquence d'instructions exécutables (5), comportant des instructions d'insertion de codes de contrôle et de codes d'élément ou de codes d'appel de séquences d'instructions d'élément, et des instructions de contrôle du déroulement de l'exécution de la séquence en fonction des valeurs des codes de contrôle, et - décompresser (15') le document à décompresser (10) qui se présente sous la forme d'un flux binaire, cette étape comprenant l'exécution des séquences d'instructions (5) sur le flux binaire, en vue de reconstituer un document au format d'origine ayant une structure au moins équivalente. 2. Procédé selon la revendication 1, caractérisé en ce qu'au moins un type d'élément d'informations des éléments de base est associé à un algorithme de décompression (16') adapté, le procédé comprenant l'exécution de cet algorithme de décompression pour restituer l'ensemble d'informations correspondant du document structuré (2) d'origine, lorsqu'un code binaire correspondant audit type d'élément d'informations est repéré durant l'exécution des séquences d'instructions (5), dans le flux binaire constituant le document compressé (10). 3. Procédé selon la revendication 1 ou 2, caractérisé en ce qu'il comprend une étape de compilation (17) des séquences d'instructions (5) obtenues pour chaque élément dudit schéma de structure, pour obtenir un programme binaire de décodage (6) dédié audit schéma de structure, directement exécutable par un calculateur. p 4. Procédé selon l'une des revendications 1 à 3, caractérisé en ce que, en vue de la compression du document structuré (2), il comprend l'analyse (11) et la compilation (13) du schéma de structure du r document pour déterminer pour chaque élément du schéma de structure, une séquence d'instructions exécutables (5), l'exécution (15) des séquences d'instructions (5) sur les ensembles d'informations correspondants du document à compresser (2), en vue de générer un flux binaire (10) contenant les ensembles d'informations compressés du document. 5. Procédé selon la revendication 4, caractérisé en ce qu'au moins un type d'information des éléments de base est associé au préalable à un algorithme de compression (16) adapté, le procédé comprenant en outre l'exécution de l'algorithme de compression (16) lorsqu'un ensemble d'informations ayant un type d'informations associé audit algorithme est détecté durant l'exécution des séquences d'instructions (5), sur le document structuré (2). 6. Procédé selon l'une des revendications 1 à 5, caractérisé en ce qu'il comprend une étape préalable de normalisation (12) du schéma de structure (5) du document, de manière à obtenir un ordre unique prédéfini des éléments du schéma. 7. Procédé selon l'une des revendications 1 à 6, caractérisé en ce que chaque code d'ensemble d'informations est repéré dans le document compressé, de manière à permettre l'accès direct à un ensemble d'informations particulier, sans qu'il soit nécessaire de décompresser les ensembles d'informations précédant l'ensemble à décompresser. 8. Procédé selon l'une des revendications 1 à 7, caractérisé en ce qu'il comprend une étape (12) préalable d'optimisation et de simplification du schéma de structure du document consistant à réduire le nombre de niveaux hiérarchiques de groupes d'éléments de structure. 9. Procédé selon l'une des revendications 1 à 8, caractérisé en ce que le document compressé (10) comprend pour chaque ensemble d'informations du document d'origine, un code permettant de déterminer l'élément de structure associé à l'ensemble d'informations et la valeur binaire de l'ensemble d'informations compressé. 10. Procédé selon la revendication 9, caractérisé en ce que dans le document compressé (10), la fin d'un groupe de v plusieurs occurrences d'ensembles d'informations de même type est marquée par un code binaire déterminé dans la séquence d'instructions relative au type des ensembles d'informations. 11. Procédé selon l'une des revendications 1 à 10, caractérisé en ce que chaque élément du schéma de structure est en outre associé à un ensemble de nombres d'occurrences possibles, indiquant le nombre de fois qu'un ensemble d'informations ayant cet élément de structure peut apparaître dans l'ensemble d'informations de niveau immédiatement supérieur auquel il appartient.