FR2951038A1

FR2951038A1 - Procede et dispositif associe de decodage d'un flux binaire correspondant a un document structure code

Info

Publication number: FR2951038A1
Application number: FR0956969A
Authority: FR
Inventors: Herve Ruellan; Romain Bellessort
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 2009-10-06
Filing date: 2009-10-06
Publication date: 2011-04-08
Anticipated expiration: 2029-10-06
Also published as: FR2951038B1

Abstract

La présente invention concerne un procédé et un dispositif correspondant de décodage d'un flux binaire (2) comprenant des événements codés (30) et correspondant notamment à un document structuré (1) codé. Le procédé comprend notamment les étapes consistant à : - récupérer (E410) une pluralité (Value) de valeurs de codage (30) consécutives dudit flux binaire (2); - prédire (E400) la taille binaire (20) desdits valeurs récupérées, et éventuellement prédire (E432) des valeurs récupérées pour former une pluralité prédite (predicted) de valeurs de codage (21); - réaligner (E426), fonction des tailles binaires prédites, les valeurs de codage récupérées pour correspondre à un alignement binaire donné, notamment celui des valeurs de codage prédites; - valider (E430, E434) la prédiction des tailles binaires, par exemple en vérifiant la prédiction des valeurs de codage par comparaison des pluralités prédite et réalignée; - traiter ou décoder (E460) les événements correspondant aux tailles binaires validées.

Description

La présente invention concerne un procédé et un dispositif correspondant de traitement, généralement de décodage, d'un flux binaire comprenant des événements codés et correspondant notamment à un document structuré codé. Elle s'applique en particulier aux documents structurés de type XML (acronyme de "eXtensible Markup Language" pour langage de balisage extensible) codés sous la forme d'un flux binaire type EXI ("Efficient XML Interchange") ou Fast Infoset. Un document XML est composé d'éléments, chaque élément commençant par une balise ouvrante comportant le nom de l'élément (par exemple: <balise>) et se terminant par une balise fermante comportant, elle aussi, le nom de l'élément (par exemple: </balise>). Chaque élément peut contenir d'autres éléments ou des données textuelles. D'autre part, un élément peut être précisé par des attributs, chaque attribut étant défini par un nom et ayant une valeur. Les attributs sont placés dans la balise ouvrante de l'élément qu'ils précisent (par exemple: <balise attribut="valeur">). De façon connue en soi, la syntaxe XML permet aussi de définir des commentaires, des instructions de traitement et des sections d'échappement.

On considère dans la suite que des données XML sont décrites en terme d'Items" ou "événements", chaque item ou événement pouvant être un début d'élément (par exemple <balise>), une fin d'élément (par exemple </balise>), un attribut (par exemple attribut="valeur"), un contenu textuel, un commentaire, une instruction de traitement ou une section d'échappement.

Le langage XML présente de nombreux avantages et est devenu un langage de référence pour stocker des données dans un fichier ou pour échanger des données. Le langage XML permet en particulier de disposer de nombreux outils pour traiter les fichiers générés. En particulier, un document XML peut être édité manuellement avec un simple éditeur de texte. En outre, comme un document XML contient sa structure intégrée aux données, ce document est très lisible même sans en connaître la spécification.

Le principal inconvénient de la syntaxe XML est d'être très prolixe. Ainsi la taille d'un document XML peut être plusieurs fois supérieure à la taille intrinsèque des données. Cette taille importante des documents XML induit aussi un temps de traitement important lors de la génération et de la lecture de documents XML. Elle induit aussi un temps de transmission important.

Pour remédier à ces inconvénients, des méthodes de compression et d'encodage d'un document XML ont été recherchées. Le but de ces méthodes est de coder le contenu du document XML sous une forme plus efficace, tout en permettant de reconstruire facilement le document XML. C'est notamment le cas des formats binaires tels que EXI (format utilisé comme base pour la standardisation d'un format XML binaire par le groupe de travail EXI du W3C - "World Wide Web Consortium", organisation produisant des standards pour le Web) ou Fast Infoset spécifié par la norme ITU-T Rec. X.891 1 ISO/IEC 24824-1. Ces formats ont pour caractéristique de prendre en compte un nombre important d'informations structurelles du document afin de compresser davantage les données. Par exemple, la recommandation EXI, disponible au travers du document "Efficient XML Interchange (EXI) Format 1.0 - W3C Working Draft 28 July 2008", prend en compte l'ordre d'apparition des différents événements au sein d'un document structuré pour construire une ou plusieurs grammaires qui permettent d'encoder les événements les plus fréquents sur un faible nombre de bits. Une grammaire est composée d'un ensemble de productions, chaque production comprenant une description d'événement XML, une valeur de codage associée et l'indication de la grammaire suivante à utiliser. Pour coder un événement XML à l'aide d'une grammaire, la production contenant la description la plus précise de l'événement XML est utilisée. La valeur de codage contenue dans cette production est utilisée pour représenter l'événement dans le flux binaire codé, et les informations contenues dans l'événement et non décrites dans la production sont codées à la suite. Une grammaire selon Efficient XML est évolutive. Dans un certain nombre de cas, après l'occurrence d'un événement XML déjà décrit par une production de la grammaire (s'il n'est pas décrit par une production, il ne peut être encodé par la grammaire), la grammaire est modifiée pour inclure une nouvelle production plus efficace correspondant à cet événement XML. Cette production peut soit contenir une description plus précise de l'événement, diminuant le nombre d'informations à coder pour représenter l'événement, soit avoir une valeur de codage plus compacte. Les valeurs de codage, ou "codes", sont exprimées sous forme de "priorités" ayant, généralement, entre 1 et 3 niveaux. Coder une valeur de codage revient à coder les valeurs de sa priorité. Ces valeurs sont généralement exprimées sur un octet (8 bits) et manipulées ainsi par l'encodeur. Toutefois, chaque niveau peut être codé sur le nombre de bits minimum pour pouvoir coder la plus grande valeur de ce niveau associée à une production de la grammaire. Aussi, pour un niveau prenant des valeurs de 0 à 6, on utilise trois bits de codage. Pour coder un document XML, un ensemble de grammaires est utilisé. Quelques grammaires servent à coder la structure propre au document XML. En outre, pour chaque type d'événement XML présent dans le document (un type d'élément XML étant un ensemble d'événements ayant le même nom), un ensemble de grammaires est utilisé pour coder les événements XML de ce type. L'indication de la grammaire suivante au niveau des productions permet de naviguer à l'intérieur de ces grammaires. Un ensemble de dictionnaires de chaînes ou de valeurs est également utilisé pour encoder les noms d'événements ou attributs, et autres contenus du document XML. Ces dictionnaires évoluent également par l'incorporation de nouvelles chaînes/valeurs rencontrées dans le document et codées. Les règles de grammaires utilisées peuvent soit être des règles génériques, communes à tous les documents XML et construites à partir de la syntaxe XML, soit être des règles spécifiques à un type de document, construites à partir d'un Schéma XML décrivant la structure de ce type de document. Lors du décodage, le processus inverse est utilisé : la valeur de codage correspondant à un événement EXI est extraite du flux binaire EXI, et permet d'identifier l'événement XML codé ainsi que les informations complémentaires à décoder. En outre, lors du décodage, les mêmes règles d'évolution des grammaires et des dictionnaires de chaînes sont utilisées, permettant d'avoir à tout moment un ensemble de règles de grammaires et de dictionnaires identique à celui qui était utilisé lors du codage. A titre d'exemple, le fragment XML suivant est utilisé pour décrire le codage d'un document XML à l'aide de la spécification EXI: <person> <firstname>John</firstname> <lastname>Smith</lastname> </person> Au début de l'encodage de ce fragment, puisque l'encodeur n'a pas encore rencontré d'événement "person", ici un début d'élément <person>, une grammaire par défaut est créée pour cet événement. Il s'agit d'une grammaire ne contenant que des productions génériques. Durant l'encodage de l'élément "person", de nouvelles productions seront créées et insérées pour rendre la grammaire liée à l'élément "person" plus efficace. La grammaire par défaut utilisée pour coder le contenu de l'élément "person" est la suivante (de manière simplifiée par rapport à la spécification Efficient XML, notamment en utilisant une seule grammaire pour coder l'élément "person") : Les événements EE, SE, CH représentés ici (d'autres événements sont prévus dans la recommandation EXI) utilisés pour décrire les événements ElementContent : EE 0 SE (*) ElementContent 1.0 CH ElementContent 1.1 XML sont appelés événements EXI et sont directement associés aux valeurs de codage (ou "priorités") du flux EXI binaire. En particulier, "EE" correspond à l'événement de fin d'élément, "SE (*)" correspond un événement de début d'élément quelconque (générique, le nom n'est donc pas précisé), et "CH" correspond à un événement de contenu textuel. Lors de l'encodage, après avoir reçu l'événement correspondant au début d'élément "person" (SE (person)), et l'avoir codé par exemple de façon littérale (ou à l'aide d'une grammaire appropriée de plus haut niveau), l'encodeur sélectionne la grammaire de codage du contenu de l'élément "person", décrite ci-dessus. Ensuite, l'encodeur reçoit l'événement de début d'élément "firstname" (<firstname> correspondant à un événement EXI SE (firstname)). La production la plus précise qui correspond à cet événement dans la grammaire ci-dessus est la deuxième : SE (*) ElementContent 1.0 L'encodeur code donc cet événement en insérant la priorité "1.0" dans le flux EXI binaire. Comme le premier niveau de priorité comprend deux valeurs distinctes ("0" et "1") parmi les productions de la grammaire, ce niveau peut être codé sur un bit, avec la valeur "1". De même, le deuxième niveau de priorité comprend deux valeurs distinctes et peut être codé sur un bit, avec la valeur "0". La priorité "1.0" est donc codée ici avec les deux bits "10". Cette donnée codée est ainsi générée initialement sur un ou plusieurs octets. Selon différentes options de codage disponibles dans la recommandation EXI, cette valeur de codage est alors insérée, telle qu'elle, dans le flux EXI, sous la forme d'un ou plusieurs octets entiers (option dite "byte-aligned" où chaque nouvelle valeur codée recommence sur un nouvel octet), ou bien sous une forme compactée avec uniquement deux bits (option dite "bit-packed" où les valeurs codées sont concaténées les unes aux autres sur un nombre minimal de bits pour représenter toutes les priorités possibles). Comme on peut aisément le comprendre, cette dernière option produit une version plus compacte du flux binaire codé, mais requiert, en contrepartie, un temps de traitement légèrement allongé pour procéder au compactage (concaténation) lors de l'encodage, ou au réalignement sur les octets lors du décodage. Ensuite, comme la production ne précise pas le nom de l'élément, "firstname" est codé, par exemple de façon littérale à l'aide d'un format spécifique à la spécification Efficient XML (similaire au format UTF8). On poursuit ensuite l'encodage du contenu de "firstname". Dans ce dessein, on recherche la production associée à cet élément. Comme aucun élément "firstname" n'a encore été rencontré, on crée une grammaire "firstname" à partir de la grammaire par défaut évoquée précédemment. L'élément "firstname" contient un noeud texte pour unique enfant. On encode ce noeud texte, par exemple littéralement. Une fois ce noeud texte encodé, on met à jour la grammaire de "firstname" en insérant une production texte CH. Grammaire "firstname" ElementContent : CH 0 EE 1 SE (*) ElementContent 2.0 CH ElementContent 2.1 Une fois le contenu de "firstname" codé, l'encodeur modifie la grammaire associée à l'élément "person" pour adapter la grammaire aux données XML rencontrées. Pour cela, une nouvelle production est ajoutée à la grammaire, cette production correspondant au début d'élément "firstname". A cette production est associée la priorité "0", et les autres priorités sont décalées pour conserver l'unicité des priorités. On rappelle ici que le décodeur agissant de façon symétrique sera en mesure de réaliser des décalages de priorités (ou index) similaires au fur et à mesure du décodage des données reçues. Ainsi la grammaire "person" devient : Grammaire "person" ElementContent : SE (firstname) ElementContent 0 7 SE (*) ElementContent 2.0 CH ElementContent 2.1 L'événement suivant du fragment XML à coder est le début de l'élément "lastname". Comme pour "firstname", cet élément est codé à l'aide de la production : SE (*) ElementContent 2.0 puisque aucune production correspondant à l'élément "lastname" n'est trouvée. Le premier niveau de priorité ayant maintenant trois valeurs possibles, il est codé sur deux bits, avec la valeur "2". Le deuxième niveau de priorité est toujours codé sur un seul bit. La priorité "2.0" est donc codée ici avec les trois bits "100". Selon l'option "byte-aligned" ou "bit-packed" choisie, ces priorités sont soit insérées sur des octets entiers, soit compactées et concaténées.

Le nom de l'élément, "lastname", est ensuite codé, par exemple littéralement. Puis le contenu de "lastname" est codé à l'aide de la grammaire associée à l'élément "lastname", à créer si nécessaire lors de la première itération, de façon similaire à ce qui est décrit ci-dessus pour la grammaire "firstname".

Suite à l'encodage de l'élément "lastname", la grammaire "person" est modifiée pour y ajouter une production correspondant au début de l'élément "lastname" (avec décalage des priorités), et elle devient alors : Grammaire "person" ElementContent : 30 Ensuite, l'événement de fin d'élément, correspondant à la fin de l'élément "person" est codé, en utilisant la production : SE (lastname) ElementContent 0 SE (firstname) ElementContent 1 EE 2 SE (*) ElementContent 3.0 CH ElementContent 3.1 Si, par la suite, dans le document XML, le codeur rencontre un autre élément "person" similaire, cet élément va être codé à partir de cette grammaire. Ainsi le premier événement correspondant au contenu de l'élément "person" est l'événement de début de l'élément "firstname". Cet élément est codé avec la production: SE (firstname) ElementContent 1 On note que la production 3.0 SE (*) ElementContent correspond aussi à cet événement, mais est moins précise (elle ne 10 précise pas le nom "firstname" de l'élément). C'est donc la première production qui est utilisée pour une efficacité de codage accrue. L'encodeur code donc la priorité de cette production, à savoir la valeur "1", qui est codée sur deux bits (car prenant des valeurs de 0 à 3), soit "01". Il n'y a pas besoin de coder le nom de l'élément, puisque celui-ci est 15 précisé par la production et ressort du codage littéral initial lorsque l'élément "firstname" a été rencontré pour la première fois. L'encodeur code ensuite le contenu de l'élément "firstname". Comme une production spécifique à l'événement de début de l'élément "firstname" existe déjà dans la grammaire, il n'est pas nécessaire 20 d'ajouter une nouvelle production à la grammaire. L'encodeur code ensuite, de manière similaire, l'événement de début de l'élément "lastname", en codant uniquement la priorité "0" avec les deux bits ,,00,,. Ainsi, pour le codage du deuxième élément "person" similaire au 25 premier, le code généré est plus compact, puisqu'il n'est plus nécessaire de coder le nom des éléments contenus dans "person", ni littéralement (en codant l'intégralité de la chaîne de caractères), ni même à l'aide d'un index. On observe ainsi, tout au long du codage d'un document XML, que l'on navigue d'une grammaire à l'autre pour trouver les productions adaptées au 30 codage des événements XML. Cette navigation est fonction de l'événement XML qui vient d'être codé, et dont la production associée indique la grammaire suivante à utiliser.

La recommandation EXI prévoit par ailleurs des mécanismes pour préparer, avant le codage ou le décodage, les grammaires en tout ou partie, à partir d'un fichier de description structurelle de documents, dit Schéma XML ("XML Schema").

Si un tel schéma XML est disponible pour décrire le contenu de l'élément "person", à savoir un élément "firstname" et un élément "lastname", il est possible de construire dès le départ la grammaire générée après la fin du codage du premier élément "person". Cependant, si le schéma précise en outre que les éléments "firstname" et "lastname" doivent être ordonnés à l'intérieur de l'élément "person" ("firstname" précédant "lastname"), il est possible de générer les grammaires suivantes pour décrire le contenu de l'élément "person" (toujours de manière simplifiée par rapport à la spécification Efficient XML). ElementContentl : SE (firstname) ElementContent2 0 EE 1.0 SE (*) ElementContentl 1.1 CH ElementContentl 1.2 ElementContent2 : SE (lastname) ElementContent3 0 EE 1.0 SE (*) ElementContent2 1.1 CH ElementContent2 1.2 ElementContent3 : EE 0 SE (*) ElementContent2 1.0 CH ElementContent2 1.1 Ces grammaires se servent de l'ordre connu d'apparition des éléments "firstname" et "lastname" pour séparer les productions en plusieurs grammaires et diminuer le nombre de productions par grammaire, et par conséquent le nombre de bits nécessaires pour coder une priorité. Ces grammaires peuvent même être réduites si l'on n'accepte pas les déviations par rapport au schéma. Une déviation correspond à la présence d'un événement XML non décrit par le schéma. Ce peut être la présence d'un élément XML autre que ceux décrits par le schéma, ou la présence d'un élément XML décrit par le schéma, mais à un endroit non prévu par le schéma. Lors de l'utilisation d'un schéma pour construire les grammaires EXI, un premier mode, le mode déviation, permet de prendre en compte ces déviations et de les coder. Un autre mode, le mode strict, n'autorise pas ces déviations et ne permet pas de coder un document contenant une telle déviation. Dans ce dernier mode, il est ainsi possible de s'affranchir des productions dites "génériques" (telles que SE(*)) utiles pour traiter des événements inattendus) et celles qui ne se réaliseront pas.

Aussi, dans le mode strict, les grammaires deviennent: ElementContentl : SE (firstname) ElementContent2 0

ElementContent2 : SE (lastname) ElementContent3 0

ElementContent3 : EE 0 Dans ce cas, chaque grammaire ne contenant qu'une seule priorité, cette priorité n'a pas besoin d'être codée. Ainsi, l'ensemble des événements décrivant le contenu de l'élément "person" tel que décrit ci-dessus est codé en zéro bit (tous les événements peuvent être prédits de façon sûre) et peut être décodé rapidement par prédiction.

Le décodage d'un flux binaire résultant de tels encodages ou l'accès à une partie du document encodé sont généralement réalisés en accédant successivement aux événements, par exemple EXI, composant le flux binaire puis en les décodant les uns après les autres. Dans le cas de l'activation de l'option "bit-packed" de compactage des données codées, un réalignement des données codées sur les limites d'octets est alors mené pour pouvoir être manipulées par le décodeur et comparées avec d'autres données manipulées, sous la même forme, par ce décodeur. Les interfaces de programmation SAX (« Simple API for XML » en anglais, ou « Interface de programmation simple pour XML » en français) et StAX (« Streaming API for XML » en anglais, ou « Interface de programmation au fur et à mesure pour XML » en français) permettent cet accès événement EXI par événement EXI. Ce décodage séquentiel introduit des temps de traitement longs, principalement car un nouvel événement EXI ne commencera à être décodé que lorsque l'événement EXI précédent aura été totalement décodé. Pour améliorer l'efficacité du décodage, on a pu faire appel à des processeurs actuels disposant de plusieurs unités de traitement pouvant fonctionner en parallèle (par exemple les processeurs mufti-coeurs). De tels processeurs sont coûteux et parfois non intégrables dans des équipements de petite taille. Récemment, l'introduction d'instructions uniques à données multiples, autrement connues sous l'acronyme SIMD pour "Single Instruction Multiple Data", a ouvert de nouvelles perspectives pour réaliser de traitements parallèles. Les instructions SIMD, mises en oeuvre notamment dans les instructions AltiVec des processeurs PowerPC ou les instructions MMX ou SSE des processeurs Pentium, permettent d'effectuer, en un seul cycle d'instruction, des opérations sur plusieurs opérandes différents. Notons que de telles instructions peuvent être mises en oeuvre sur chaque coeur d'un processeur mufti-coeurs pour améliorer les performances de calcul. Ces instructions SIMD ont ainsi pu être utilisées, comme décrit par la publication US 2008/033974, pour accélérer le décodage de documents XML à l'aide d'une technique de flux de bits parallèles, encore connue sous le nom de Parabix ("Parallel bit streams for XML").

Cette technique réalise le décodage d'un flux binaire aligné sur les octets (c'est-à-dire sensiblement selon l'option "byte-aligned", car les données sont encodées en mode UTF-8) et met en oeuvre les étapes suivantes : - transformation du flux codé d'octets en huit flux de bits. Ainsi, à partir d'un flux de 128 octets, on obtient huit flux de 128 bits, chacun des flux de bits contenant le bit placé à une position donnée pour chacun des 128 octets. Cette transformation peut être réalisée selon le principe "inductive doubling" consistant à diviser récursivement le flux par deux: chaque octet est coupé en deux demi-octets, les demi-octets étant regroupés ensemble pour obtenir deux flux de 128 demi-octets; puis l'opération est répétée, mais avec des tailles deux fois moindres, pour obtenir quatre flux de 128 quart d'octets; enfin, une nouvelle répétition permet d'obtenir les huit flux de 128 huitièmes d'octets, c'est-à-dire de 128 bits ; - génération de flux lexicaux décrivant le contenu du flux XML.

Ainsi, il y a un flux lexical qui correspond au caractère « < », utilisé en XML pour noter les débuts d'éléments. Ces flux lexicaux sont calculés à partir des huit flux de bits ; - décodage du flux XML à partir des huit flux de bits et des flux lexicaux. Les flux lexicaux permettent de déterminer les limites des événements XML. A partir de ces limites et des huit flux de bits, des événements représentant le contenu XML sont générés. L'accélération du décodage dans cette méthode réside principalement dans les opérations de détermination des marqueurs lexicaux XML qui peuvent être effectuées sur 128 octets en parallèle, en utilisant peu d'opérations pour chaque marqueur lexical. Par ailleurs, ces déterminations partagent des étapes qui peuvent être factorisées, ce qui permet de réduire encore les calculs. Ces mêmes instructions uniques à données multiples peuvent également être utilisées lors du codage pour paralléliser certaines opérations sur plusieurs opérandes.

Les instructions SIMD constituent donc des moyens efficaces pour accélérer les traitements tels que le codage ou le décodage de document structuré. Toutefois, ces instructions ne sont pas adaptées aux formats de codage dans lesquels les données codées sont compactées (par exemple l'option "bit-packed") et ne sont donc pas alignées sur les limites d'octets. Cette inadaptation est évidente lors du décodage puisque le décodeur ne connaît pas le nombre de bits utilisés pour chaque donnée codée tant qu'il n'a pas décodé les données précédentes. En effet, comme expliqué ci- dessus, le nombre de bits utilisés dépend du nombre de productions dans la grammaire courante, cette dernière étant fonction de la production utilisée lors du codage de la donnée précédente. Le décodeur est ainsi dans l'impossibilité de traiter simultanément deux données codées successives ou plus.

L'invention vise à pallier ces inconvénients de l'art antérieur pour permettre de réaliser, de façon groupée, le compactage ou le réalignement de plusieurs données codées, notamment à l'aide d'instructions de type SIMD. Il en résulte des traitements (décodage, accès à une partie du document codé) accélérés.

Dans ce dessein, l'invention concerne notamment un procédé de traitement d'un flux binaire correspondant notamment à un document structuré codé, le flux binaire comprenant des valeurs de codage d'événements, le procédé comprenant les étapes consistant à : - récupérer une pluralité de valeurs de codage d'événements 25 consécutives dudit flux binaire ; - prédire la taille binaire desdites valeurs de codage récupérées ; - réaligner, à l'aide desdites tailles binaires prédites, les valeurs de codage de ladite pluralité récupérée pour correspondre à un alignement binaire donné ; 30 - valider la prédiction d'au moins une partie des tailles binaires ; - traiter les événements correspondant aux tailles binaires dont la prédiction est validée.

Selon l'invention, on cherche à connaître les valeurs de codage dont on a réalisé correctement le décompactage, c'est-à-dire le réalignement avec le format utilisé par le décodeur. En effet, ce décompactage permet ensuite au décodeur de trouver, dans les grammaires ou dictionnaires de décodage, les événements EXI et XML correspondants sans difficulté. Pour connaître ces valeurs, on fait des suppositions sur leur taille compactée (prédiction des tailles) que l'on valide généralement à l'aide des valeurs de codage elles-mêmes. En effet, la taille compactée d'une valeur dépend du type de valeur à coder. En particulier, dans le cas d'une valeur de priorité, la taille compactée dépend de la grammaire contenant la production correspondant à cette priorité. Or la grammaire utilisée dépend de l'événement précédent, donc de la valeur de la priorité précédente. Ainsi, pour vérifier la prédiction de taille d'une valeur, il peut suffire (dans le cas d'une priorité) de vérifier la prédiction de la valeur précédente.

Grâce notamment aux instructions SIMD, les opérations visant au réalignement des valeurs peuvent être menées simultanément sur plusieurs valeurs, sans être limité par le parcours séquentiel des grammaires et tables de décodage normalement nécessaire pour connaître la taille compactée de la valeur suivante. Le décodage des flux EXI est donc accéléré.

Par ailleurs, le traitement des valeurs ainsi délimitées dans le flux EXI peut être mené de façon classique, en récupérant directement les valeurs réalignées, pour par exemple les décoder ou accéder directement à une partie souhaité du document codé. Dans un mode de réalisation principale de l'invention, le procédé 25 comprend en outre les étapes consistant à : - prédire des valeurs de codage récupérées de sorte à former une pluralité prédite de valeurs de codage, lesdites valeurs de codage de la pluralité prédite étant selon ledit alignement binaire donné ; et - vérifier la prédiction des valeurs de codage par comparaison des 30 pluralités prédite et réalignée de sorte à valider la prédiction d'au moins une partie des tailles binaires.

On réalise ici la validation des prédictions des tailles à l'aide d'une vérification de certaines valeurs de codage, généralement les priorités des grammaires. Dans un mode de réalisation, le procédé comprend l'association, à au moins une table de décodage dudit flux binaire, d'une séquence de prédictions dont les entrées comprennent au moins une valeur de codage d'événement et une taille binaire associée à cette valeur de codage; et lesdites prédictions des valeurs de codage et des tailles binaires sont récupérées de ladite séquence de prédictions associée à la table de décodage courante. L'accès aux prédictions est ainsi immédiat pour un ensemble d'événements à décoder. En particulier, de telles séquences de prédictions permettent d'obtenir aisément ces prédictions indépendamment de la taille des opérandes des instructions SIMD utilisées. Notamment, lesdites tables de décodage sont des grammaires (de préférence EXI) correspondant à un type d'élément structuré. Selon une caractéristique particulière, le procédé comprend une étape de construction de ladite séquence de prédictions à partir d'au moins une prédiction simple associée à au moins une entrée des tables de décodage, ladite prédiction simple renseignant une autre entrée de table de décodage (et donc une autre valeur de codage). A titre d'exemple, dans le cas EXI, une telle entrée peut être une production. Une prédiction simple comprend notamment l'indication d'un événement (ou d'une entrée correspondante des tables) susceptible de se produire après l'entrée concernée, par exemple une production EXI qui ferait suite à une première production. Ces prédictions simples peuvent notamment être mises à jour en fonction du résultat des prédictions effectuées selon l'invention. Grâce à ces productions simples, la constitution, voire la mise à jour, des séquences de prédictions s'avère simple.

En particulier, ladite construction comprend le parcours d'une pluralité d'entrées des tables de décodage en navigant à l'aide des prédictions simples associées auxdites entrées parcoures, et l'ajout desdites prédictions simples parcourues à ladite séquence de prédictions. Cette réalisation des séquences de prédictions utiles pour des traitements simultanés avec des instructions SIMD reste ainsi de complexité simple. Et notamment, ledit parcours est réalisé jusqu'à atteindre une prédiction simple d'une table de décodage renseignant une entrée d'une autre table de décodage à laquelle est déjà associée une séquence de prédictions. On évite ainsi un bouclage infini générant une séquence infinie. De plus, cette disposition optimise l'invention puisque, à terme, les entrées des tables de décodage ne seront chacune que dans une seule séquence de prédictions.

Selon une caractéristique, le procédé comprend la mise à jour de ladite séquence de prédictions en fonction de ladite vérification. En particulier, ladite séquence de prédictions est mise à jour par découpage au niveau d'une valeur de codage pour laquelle une information de statistique de prédictions atteint une valeur seuil. Typiquement, cette valeur de codage correspond à un événement trop souvent mal prédit. Cette disposition permet d'optimiser les séquences de prédictions pour un meilleur décodage de flux EXI. Selon une autre caractéristique de l'invention, au moins un masque de décalage de bits est calculé pour le réalignement de l'ensemble des valeurs de codage. En particulier, un masque de décalage de bits est stocké en mémoire, associé à ladite séquence de prédictions. Le masque est notamment mémorisé dans un registre de la taille des opérandes des instructions SIMD. Un tel masque permet ainsi, en un cycle d'instruction, de procéder au réalignement de plusieurs valeurs de codage du flux EXI. Selon une autre caractéristique de l'invention, ledit traitement comprend le décodage de la première valeur de codage récupérée dont la prédiction est erronée, à l'aide d'une information de lien associée à une entrée de ladite séquence de prédictions. Cette disposition permet de poursuivre efficacement le décodage alors même qu'une erreur de prédiction peut avoir eu lieu, car on récupère ainsi une entrée de table de décodage pour la valeur mal prédite et la suite du décodage du flux EXI peut être réalisée soit classiquement, soit par une nouvelle mise en oeuvre de l'invention.

Selon une encore autre caractéristique de l'invention, ladite séquence de prédictions comprend un nombre d'entrées qui est un multiple du nombre de valeurs contenues, selon ledit alignement binaire de la pluralité prédite, dans un opérande d'instruction unique à multiples données (SIMD).

Ainsi, le décodage peut être réalisé de façon optimale (en termes de vitesse) car, à tous les cycles de calcul, les instructions uniques à multiples données (SIMD) manipuleront un nombre maximal d'événements, tant que les prédictions sont validées. Dans un mode de réalisation de l'invention, ladite vérification comprend l'application d'un masque de prédiction de sorte à ne pas prendre en compte au moins une valeur de codage lors de ladite comparaison. Notamment, ladite pluralité de valeurs de codage récupérées est stockée, sous forme réalignée, dans un deuxième registre d'instruction unique à multiples données. Notamment, ladite vérification met en oeuvre au moins une instruction unique à multiples données (SIMD) ayant, pour première opérande, ledit deuxième registre stockant ladite pluralité de valeurs de codage récupérées réalignées et, pour seconde opérande, un troisième registre stockant ladite pluralité de valeurs de codage prédites, de sorte à obtenir une indication de comparaison pour chaque valeur de codage.

En particulier, ladite vérification comprend l'application d'un masque de prédiction au résultat de ladite instruction unique à multiples données, de sorte à effacer ladite indication de comparaison pour au moins une valeur de codage. Cette disposition permet la mise en oeuvre de l'invention même pour les valeurs pour lesquelles la prédiction de valeurs n'est pas utilisée, typiquement des valeurs de contenu. Le masque exclut donc de telles valeurs pour la comparaison. Dans un mode de réalisation de l'invention, le réalignement des valeurs de codage met en oeuvre au moins une instruction unique à multiples données (SIMD) de décalage de bits. Notamment, le procédé comprend la concaténation des tailles binaires prédites dans un premier registre d'instruction unique à multiples données (SIMD). Egalement, on envisage que les valeurs de décalage de bits pour chaque valeur de codage récupérée sont calculées à l'aide d'au moins une instruction unique à multiples données (SIMD) appliquée audit premier registre. L'utilisation des instructions SIMD dans la plupart des calculs menant au réalignement assure un décodage plus rapide puisque, en un cycle d'instruction, on détermine le décalage de bits pour tous les événements de ladite pluralité. A titre d'exemple, des registres courants d'instructions SIMD ont une taille de 128 bits, permettant par exemple de réaligner seize événements codés en un cycle. Dans un autre mode de réalisation, ledit réalignement met en oeuvre une pluralité d'instructions uniques à multiples données (SIMD) aptes à réaliser un alignement progressif des valeurs de codage récupérées, par décalage itératif de sous-groupes de valeurs de codage successives. L'itération est naturellement arrêtée lorsque l'alignement obtenu correspond à celui des valeurs de codage prédites, par exemple lorsque chaque événement récupéré est désormais représenté sur un octet.

En particulier, on divise par deux les sous-groupes d'une itération SIMD à l'autre. Cette disposition offre une mise en oeuvre simple du réalignement à l'aide des instructions SIMD déjà existantes sur les processeurs actuels. Dans un mode de réalisation simplifié de l'invention, ladite validation comprend la comparaison d'au moins une partie du flux binaire récupéré avec une structure prédéfinie, et, en cas de comparaison positive, on utilise une séquence de prédictions associée à ladite structure prédéfinie pour prédire les tailles binaires. Cette configuration permet de simplifier la validation des prédictions par l'utilisation préalable d'une structure prédéfinie. En effet, si les valeurs binaires récupérées du flux sont semblables, au moins en partie (là où elles se révèlent pertinentes, en utilisant des masques par exemple), à une structure connue, alors il est prévu d'utiliser directement la séquence de prédictions rattachée à cette structure et de considérer son contenu comme désormais validé, notamment pour connaître concrètement les tailles permettant le décompactage/réalignement. Ainsi, on évite de mener des vérifications ultérieures sur des valeurs prédites.

On dispose ainsi d'un mécanisme plus rapide et plus efficace, permettant en particulier des accès plus rapides à des emplacements précis d'un document structuré codé. Corrélativement, l'invention vise un dispositif de traitement d'un flux 5 binaire comprenant des valeurs de codage d'événements d'un document structuré, le dispositif comprenant : - un moyen apte à récupérer une pluralité de valeurs de codage d'événements consécutives dudit flux binaire ; - un moyen de prédiction pour prédire la taille binaire desdites 10 valeurs de codage récupérées ; - un moyen de réalignement apte à réaligner, à l'aide desdites tailles binaires prédites, les valeurs de codage de ladite pluralité récupérée pour correspondre à un alignement binaire donné ; - un moyen de validation apte à valider la prédiction d'au moins une 15 partie des tailles binaires ; - un module de traitement pour traiter les événements correspondant aux tailles binaires dont la prédiction est validée. Le dispositif de décodage présente des caractéristiques et avantages analogues au procédé de décodage selon l'invention. 20 De façon optionnelle, le dispositif peut comprendre des moyens se rapportant aux caractéristiques du procédé de décodage exposé précédemment. Notamment, le moyen de prédiction est également apte à prédire des valeurs de codage récupérées de sorte à former une pluralité prédite de valeurs 25 de codage, lesdites valeurs de codage de la pluralité prédite étant selon ledit alignement binaire donné; et le moyen de validation est apte à vérifier la prédiction des valeurs de codage par comparaison des pluralités prédite et réalignée de sorte à valider la prédiction d'au moins une partie des tailles binaires. 30 En particulier, le dispositif peut comprendre des instructions uniques à données multiples et des registres associés pour stocker simultanément des informations (valeurs de codage, tailles prédites, valeurs prédites, masques de décalage de bits) relatives à une pluralité de valeurs de codage successives à traiter. Dans un mode de réalisation, le dispositif comprend des tables de décodage auxquelles sont associées des séquences de prédictions dont les entrées comprennent au moins une valeur de codage d'événement et une taille binaire associée à cette valeur de codage. En particulier, le dispositif comprend des prédictions simples associées à des entrées des tables de décodage et renseignant une autre entrée de table de décodage, et des moyens de construction d'une telle séquence de prédictions à partir des prédictions simples. Un moyen de stockage d'informations, éventuellement totalement ou partiellement amovible, lisible par un système informatique, comprend des instructions pour un programme informatique adapté à mettre en oeuvre le procédé de traitement conforme à l'invention lorsque ce programme est chargé et exécuté par le système informatique. Un programme d'ordinateur lisible par un microprocesseur, comprend des portions de code logiciel adaptées à mettre en oeuvre le procédé de traitement conforme à l'invention, lorsqu'il est chargé et exécuté par le microprocesseur.

Les moyens de stockage d'information et programme d'ordinateur présentent des caractéristiques et avantages analogues aux procédés qu'ils mettent en oeuvre. Grâce à l'invention, on améliore le décodage de flux binaire, par exemple de type EXI, en décompactant, en un groupe d'instructions, une pluralité d'événements EXI codés sous forme compactée ("bit-packed"). D'autres particularités et avantages de l'invention apparaîtront encore dans la description ci-après, illustrée par les dessins ci-joints, dans lesquels : - la figure 1 représente un exemple de grammaires EXI mettant en 30 oeuvre la présente invention ; - les figures 2a à 2c illustrent la constitution d'un exemple de flux binaire à traiter par l'invention, ainsi qu'un tel exemple avant et après le décompactage ; - la figure 3 représente, sous forme d'ordinogramme, des étapes générales de décodage selon l'invention ; - la figure 4 représente, sous forme d'ordinogramme, des étapes de mise à jour d'une prédiction simple selon l'invention, mise en oeuvre lors du décodage de la figure 3 ; - la figure 5 représente, sous forme d'ordinogramme, des étapes de construction de séquences de prédictions selon l'invention, mise en oeuvre lors du décodage de la figure 3 ; - la figure 6 illustre une séquence de prédictions selon l'invention pour l'exemple des figures 2 ; - la figure 7 représente, sous forme d'ordinogramme, des étapes 15 du décodage de l'invention mises en oeuvre lors du décodage général de la figure 3 ; - les figures 8a à 8h illustrent les opérations de décodage de la figure 7 pour l'exemple de la figure 2 ; - la figure 9 représente, sous forme d'ordinogramme, des étapes 20 de mise à jour des séquences de prédictions selon l'invention ; et - la figure 10 montre une configuration matérielle particulière d'un dispositif de décodage ou d'encodage apte à une mise en oeuvre du procédé selon l'invention. La présente invention est notamment mise en oeuvre pour le 25 décodage d'un flux binaire, de type EXI dans la suite de la description, correspondant à un document structuré XML codé, le flux binaire comprenant des valeurs de codage d'événements, le procédé comprenant les étapes consistant à : - récupérer une pluralité de valeurs de codage d'événements 30 consécutives dudit flux binaire ; - prédire la taille binaire desdits valeurs de codage récupérées, et éventuellement prédire des valeurs de codage récupérées de sorte à former une pluralité prédite de valeurs de codage ; - réaligner, à l'aide desdites tailles binaires prédites, les valeurs de codage de ladite pluralité récupérée pour correspondre à un alignement binaire donné, lequel peut notamment être celui des valeurs de codage de la pluralité prédite ; - valider la prédiction d'au moins une partie des tailles binaires, par exemple en vérifiant la prédiction des valeurs de codage par comparaison des pluralités prédite et réalignée ; - traiter les événements correspondant aux tailles binaires dont la prédiction est validée. A l'aide d'instructions uniques à multiples données (SIMD) notamment, ces étapes conduisant au réalignement et celles éventuellement de vérification peuvent être menées simultanément sur un grand nombre d'événements codés. Comme on le verra par la suite en détail, un élément clé du décodage efficace selon l'invention à l'aide typiquement d'instructions SIMD est la détermination au préalable (par prédiction) des tailles compactées des valeurs de codage, afin d'identifier chacune des valeurs de codage dans le flux EXI et de procéder au décodage des événements correspondant à ces valeurs, en une seule fois. Le réalignement des valeurs de codage avec celles prédites permet de procéder à une vérification de celles-ci par comparaison afin d'en déduire si les prédictions sont exactes et donc si les tailles prédites sont aussi exactes. Ainsi toutes les valeurs qui précèdent la première valeur mal prédite ont été correctement délimitées dans le flux binaire EXI, et cela de façon simultanée grâce aux instructions SIMD. Le décodage des événements correspondants à ces valeurs délimitées peut alors être mené de façon classique en faisant correspondre ces valeurs avec les priorités des grammaires EXI ou les index des dictionnaires de décodage.

On constate donc que la prédiction exacte de toutes les valeurs de codage peut être optionnelle, le principal étant de prédire la taille utilisée dans le flux EXI pour coder cette valeur. Il est intéressant, pour valider la prédiction, de disposer d'un certain nombre de valeurs dont on peut obtenir une prédiction supposée certaine. C'est le cas des priorités utilisées pour les productions EXI, au contraire des contenus associés aux événements (valeur d'un attribut par exemple) qui sont généralement fortement variables. Dans le mode de réalisation préféré de l'invention, les grammaires EXI sont adaptées, comme illustré par la figure 1, pour permettre la génération de prédictions. Pour rappel, les grammaires EXI 10 comprennent des productions 11 qui associent un événement EXI 12 (correspondant à un type d'événement XML) à une valeur de codage 13 (ou "priorité"). Sur la figure 1, on associe en outre aux productions 11 des prédictions dites "simples" 14 consistant, pour la majorité des productions, à indiquer la production utilisée à la suite de cette première production pour traiter l'événement de même profondeur suivant celui traité par cette production. La "profondeur" ici a le même sens que la "profondeur" des éléments XML au sein du document XML 1. Chaque prédiction simple 14 de production 11 contient une information statistique (non représentée) sur la ou les productions effectivement utilisées lors des occurrences de la production 11. Par exemple, le modèle de prédiction simple 14 de production utilisé est un système avec deux états de probabilité et une prédiction. Les deux états correspondent à "peu probable" et "très probable".

Les données statistiques peuvent être collectées dans un premier temps à partir du document EXI 2 à décoder ou par l'intermédiaire du codage/décodage de données XML similaires aux données à coder/décoder. Ces données statistiques peuvent aussi être initialisées à partir d'un schéma XML. Dans le cadre d'un mode préféré de mise en oeuvre, on se limite à récupérer les données statistiques au fur et à mesure du décodage des données EXI. Le principal avantage est un coût très faible en termes de complexité calculatoire et de temps de traitement tout en conservant des performances de prédiction intéressantes. Ainsi, au début du décodage, l'état initial d'une prédiction simple 14 est "peu probable" avec aucune production associée.

Puis au cours du décodage, lorsqu'une production est utilisée, la mise à jour de la prédiction simple se fait comme suit : - si cette production utilisée correspond à celle de la prédiction simple 14 associée à la production précédente, l'état de cette prédiction simple passe de "peu probable" à "très probable", ou reste à "très probable" ; - si cette production utilisée ne correspond pas à celle de la prédiction simple et que l'état est "peu probable", alors le modèle de prédiction remplace l'ancienne production prédite 14 par cette nouvelle production, avec un état "peu probable" associé. C'est aussi le traitement qui est réalisé si le modèle ne contenait pas de production du fait de l'état initial par exemple ; - enfin, si cette production ne correspond pas à celle de la prédiction simple 14 mais que l'état est "très probable", l'état passe à "peu probable". Dans ce modèle, la production simple contenue 14 est celle qui est retournée quand un algorithme recherche une production simple à partir de la production courante 11. Dans une variante, la production contenue n'est retournée que si l'état est à "très probable" (aucune prédiction n'étant alors réalisée depuis cette production courante 11 pour un état "peu probable"). Cette modélisation des prédictions simples 14 permet de mémoriser et de conserver une production utilisée fréquemment dans une circonstance particulière. Toutefois d'autres modèles plus complexes peuvent être mis en oeuvre, en conservant par exemple une liste des dernières productions utilisées suite à la production courante 11 et en retournant la production la plus utilisée. Dans ce cas, chaque prédiction simple 14 contient une ou plusieurs productions probables, avec éventuellement des taux de probabilité correspondant. Toujours en référence à la figure 1, pour chaque production 11 correspondant à un événement EXI ou XML ayant une valeur ou un contenu (c'est le cas des attributs qui prennent une valeur, des contenus textuels, des débuts d'élément dont le nom n'est pas précisé, ou encore des commentaires et instructions de traitement), une prédiction simple 15 portant sur ce contenu est associée à la production 11.

Dans une mise en oeuvre particulière de l'invention, seuls les événements correspondant à une valeur textuelle ou un attribut dont le nom est précisé ont des prédictions simples de contenu 15 associées. En effet, les autres événements sont soit trop peu fréquents pour qu'il soit intéressant de les traiter (en particulier pour les commentaires ou les instructions de traitement), soit trop variables pour pouvoir réaliser des prédictions correctes sur leur contenu et surtout sur la taille (c'est le cas des événements représentant un attribut dont le nom n'est pas précisé). Pour les productions 11 correspondant à une valeur textuelle ou un attribut, les prédictions simples 15 de contenu sont composées d'un état et du type de codage pour la valeur textuelle. Comme pour les prédictions simples 14 de production, cet état peut par exemple prendre deux valeurs "peu probable" et "très probable". Le type de codage indiqué est soit la table d'index local, soit la table d'index global, soit la longueur de la chaîne dans le cas d'un codage littéral.

La mise à jour des prédictions simples 15 de contenu est similaire à celle des prédictions simples 14 de production. Comme on le verra par la suite, l'invention offre un décodage de flux EXI efficace en délimitant simultanément plusieurs valeurs de codage dans ledit flux EXI, dans la mesure où leur taille binaire dans le flux EXI peut être prédite.

Les prédictions simples 14 de production, étant plus cernables, serviront à valider les prédictions de tailles. Comme illustré par la figure 1, une prédiction simple 16 est également associée à chaque grammaire représentant le début du contenu d'un élément (c'est-à-dire la grammaire utilisée après avoir traité la balise de début d'élément ouvrant ledit élément). Cette prédiction concerne la production utilisée pour traiter le premier événement représentant une partie du contenu de cet élément. Dans notre exemple, il s'agit de l'événement AT(title).

La mise à jour de cette prédiction simple 16 est similaire à celle des prédictions simples 14 et 15 décrite ci-dessus.

Enfin, afin d'améliorer les performances de prédiction selon l'invention, on associe une séquence de prédictions 17 à chacune des grammaires représentant le début du contenu d'un élément. Cette séquence de prédictions 17 liste en particulier des informations de prédictions simples pour plusieurs événements consécutifs, ici AT(title), puis SE(firstname), etc.

Comme il sera décrit ci-après en référence à la figure 5, cette séquence de prédictions 17 est construite, pour la grammaire 10, à partir des prédictions simples 14, 15 et 16.

Selon une réalisation de l'invention, la prédiction des tailles binaires des valeurs de codage d'événements est réalisée à l'aide de cette séquence de prédictions 17.

Une séquence de prédictions 17 est constituée d'un ensemble 15 d'informations (dont un exemple plus détaillé est fourni dans la suite en référence à la figure 6).

La première de ces informations est une liste des tailles binaires 20 de valeurs de codage correspondant aux événements prédits dans la séquence, dans le format compacté utilisé lors du codage binaire EXI

20 (fournissant le flux EXI 2). La taille binaire d'une valeur de codage est par exemple le nombre minimal de bits nécessaires pour coder l'ensemble des valeurs de codage. Comme expliqué précédemment en lien avec les priorités EXI, cette taille peut être la somme des nombres minimaux de bits pour coder

l'ensemble des trois priorités d'une même grammaire: 25 L [log2(nombre de priorités i)1 où [1 est la valeur entière supérieure. i=1,2,3 La deuxième de ces informations est une liste des valeurs de codage 21 prédites. Ces valeurs de codage sont mémorisées dans le format dans lequel le décodeur les manipule, généralement chaque valeur étant exprimée sur un octet.

30 Ces valeurs correspondent, dans le cas d'événements structurels EXI, aux priorités 13 correspondantes. On notera que pour certaines valeurs, il peut ne pas y avoir de valeur prédite car la valeur n'influe pas sur la suite du décodage, seule la connaissance de la taille binaire de la valeur de codage compacté est nécessaire. C'est le cas par exemple pour les valeurs représentant un caractère, ou pour les valeurs représentant un index dans une table de valeurs.

La troisième de ces informations est un ensemble de liens 22 (par exemple des pointeurs informatiques) vers des productions 11 ou grammaires 10 correspondant aux valeurs de codage 21. Ces liens permettent à l'algorithme de décodage de redémarrer quand une erreur de prédiction survient, en se rattachant par exemple à la dernière production correctement prédite. Notamment, on peut prévoir que seules les valeurs de codage 21 correspondant à une priorité ont une telle information associée. Enfin, à chaque séquence de prédictions sont associées des statistiques (non représentées) indiquant la pertinence de cette séquence. Ces statistiques sont décrites par la suite en référence à la figure 9 lors de la mise à jour des séquences de prédictions. Dans la suite de la description, on s'intéresse au décodage d'un flux EXI 2 codé en mode "bit-packed" pour lequel le décompactage ou ré-alignement des valeurs de codage est réalisé en utilisant des instructions SIMD portant sur des opérandes, par exemple, de 128 bits. Cela permet ainsi de décompacter simultanément 16 valeurs de 8 bits (c'est-à-dire 16 octets au total). Toutefois, il n'y a aucune difficulté pour l'homme du métier à étendre l'invention à des tailles d'opérandes différentes et/ou à des formats de valeurs décompactées différents de 8 bits. Pour des raisons de simplicité d'explication, la description qui suit s'appuie sur un exemple de décodage de 8 valeurs, c'est-à-dire que le nombre de valeurs de cet exemple a été diminué de moitié par rapport aux algorithmes décrits. Toutefois, l'extension de cet exemple à un exemple de 16 valeurs est immédiate. La figure 2a illustre l'exemple pour la suite de la description, en listant huit types de valeurs (première colonne) présentes dans le flux EXI 2 (codé avec l'option "bit-packed") que l'on souhaite décompacter simultanément avant décodage. La deuxième colonne renseigne la taille binaire des valeurs de codage correspondantes dans le flux EXI 2. La figure 2b montre le flux EXI avec ces huit valeurs 30. A titre d'exemple, la première valeur de codage vaut "001", la deuxième "00", la troisième "0100", etc. Les indications "+" et "-" en dessous permettent de délimiter chacune de ces huit valeurs (jusqu'aux symboles "." qui désignent la suite du flux EXI qui peut initialement être chargée en mémoire). Afin de pouvoir être traitées pour le décodage, ces valeurs de codage 30 doivent être décompactées pour obtenir un flux similaire au flux illustré à la figure 2c. Dans ce flux, chaque valeur de codage a été réalignée sur un octet (8 bits). Ce réalignement nécessite l'introduction de bits d'alignement dont la valeur est '0' (indiqués dans le flux réaligné par des "."). On décrit maintenant, en référence à la figure 3, un algorithme général de décodage selon l'invention.

Dans une première étape E100, on teste s'il reste des données à décoder, c'est-à-dire des valeurs de codage (ou événements codés) dans le flux EXI 2. Si ce n'est pas le cas, l'algorithme se termine à l'étape E110. Si au contraire il reste des événements à décoder, l'algorithme se poursuit à l'étape E120 en testant si une séquence de prédictions 17 est associée à la grammaire courante (c'est-à-dire à la grammaire devant être utilisée pour décoder la valeur suivante). Si c'est le cas (sortie oui de l'étape E120), l'algorithme se poursuit à l'étape E130 en procédant au décodage prévu par l'invention. Ce décodage utilise la séquence de prédictions 17 pour décompacter simultanément un ensemble de valeurs de codage 30, notamment les huit valeurs de notre exemple ci-dessus. Ce décodage est décrit ci-après en référence à la figure 7. Après cette étape, l'algorithme retourne à l'étape El 00 pour traiter des données suivantes à décoder.

Dans le cas où aucune séquence 17 n'est détectée (sortie non de l'étape E120), l'algorithme se poursuit à l'étape E140 en testant si une prédiction simple 14, 15 ou 16 est disponible.

De préférence, ce test est réalisé de la manière suivante. En premier lieu, l'algorithme vérifie si la grammaire courante 10 correspond au début du contenu d'un élément XML. Si ce n'est pas le cas, aucune prédiction simple 14, 15 ou 16 n'est disponible. Si c'est le cas, l'algorithme vérifie si une prédiction simple 16 est associée à cette grammaire 10. Dans une variante, le test recherche aussi les prédictions simples pour une grammaire courante ne correspondant pas au début du contenu d'un élément. Dans un tel cas, comme aucune prédiction simple 16 n'est associée à une telle grammaire 10, la recherche s'effectue à partir de la dernière production utilisée : l'algorithme vérifie si une prédiction simple 14 ou 15 est associée à la dernière production utilisée. Si une prédiction simple 14, 15 ou 16 est disponible, l'algorithme se poursuit à l'étape E150, qui procède à la construction d'une séquence 17 de productions prédites (pour la grammaire courante) à partir de cette prédiction simple 14, 15 ou 16. Cette étape est décrite plus en détail ci-après, en référence à la figure 5. Après l'étape E150, l'algorithme utilise la séquence de prédictions 17 ainsi construite pour réaliser un décodage selon l'invention lors de l'étape E130. Si aucune prédiction simple 14, 15 ou 16 n'est disponible, l'algorithme se poursuit à l'étape E160 au cours de laquelle un décodage classique est réalisé. Un tel décodage classique permet, bien entendu, de mettre à jour (étape E170) les prédictions simples 14, 15 ou 16 en modifiant par exemple les états "très probable" ou "peu probable" évoqués précédemment. Cette mise à jour permet notamment d'ajouter des prédictions simples pour des productions 11 ou des grammaires 10 qui n'en disposaient pas. En référence à la figure 4, cette mise à jour E170 comprend une première étape E200 consistant à obtenir la production utilisée lors du décodage classique E160 et celle correspondant à la prédiction simple 14, 15 ou 16 à mettre à jour. A l'étape suivante E210, on met à jour les statistiques de la prédiction simple 14, 15 ou 16.

Puis, lors de l'étape E220, on met à jour la liste des productions prédites. Dans la mise en oeuvre préférée de l'invention, aussi bien pour les prédictions simples de production que pour les prédictions simples de contenu, 5 ces deux étapes E210 et E220 sont fusionnées. De retour à la figure 3, après la mise à jour E170 de la prédiction simple associé à la production précédente 11 ou à la grammaire courante 10, le décodage se poursuit à l'étape E100 par la prise en compte de données suivantes. 10 On décrit maintenant, en référence à la figure 5, l'étape E150 de construction d'une nouvelle séquence de prédictions 17 pour une grammaire 10. On rappelle ici qu'une séquence de prédictions 17 comprend une liste de tailles binaires 20 correspondant au format compacté du flux EXI 2, une liste de valeurs de codage prédites 21 mémorisées chacune dans un format non 15 compacté, par exemple sur un octet, et un ensemble de liens 22. Lors du démarrage de l'algorithme de construction d'une séquence de prédictions 17, une grammaire 10 correspondant au début du contenu d'un élément XML est sélectionnée. Cette grammaire 10 est l'objet courant initial pour l'algorithme. Toutefois, dans d'autres mises en oeuvre de l'invention dont 20 les adaptations sont à la portée de l'homme du métier, d'autres types d'objets (notamment d'autres grammaires ou des productions) peuvent être sélectionnés au démarrage de cet algorithme. La première étape E300 consiste à obtenir la ou les prédictions simples 14, 15, 16 associées à l'objet courant. 25 Dans le cas d'une grammaire 10 de début de contenu d'élément, il s'agit de la prédiction simple 16 de production associée à cette grammaire 10. Dans le cas d'une production 11 correspondant à un événement sans contenu, il s'agit de la prédiction simple 14 de production associée à cette production. 30 Dans le cas d'une production 11 représentant un contenu textuel ou un attribut dont le nom est précisé, il s'agit de la prédiction simple 15 de contenu correspondant à la valeur, et de la prédiction simple 14 de production associée à cette production. Lors de l'étape suivante E310, on ajoute cette ou ces prédictions 14, 15, 16 à la séquence de prédictions 17, tout en conservant l'ordre dans lequel elles sont utilisées pour le traitement du flux EXI 2. Cet ajout consiste à renseigner, si possible, la taille binaire 20, la valeur de codage prédite 21 et le lien 22. En particulier, pour une prédiction simple 14 ou 16 de production, les informations suivantes sont utilisées : - la taille binaire 20 de la valeur à décoder 30 dans le format utilisé lors du codage. Cette taille binaire "compactée" est fonction du nombre de productions possibles au niveau de la prédiction, comme il est décrit dans la spécification EXI ; - la valeur de codage prédite 21 qui est la valeur de priorité correspondant à la production prédite ; et - le lien 22 qui pointe sur la grammaire contenant la production prédite (si la production a été prédite de manière erronée, il faudra utiliser cette grammaire pour commencer de nouveau le décodage normal du document EXI 2).

Pour une prédiction simple 15 de contenu, les informations dépendent du type de codage de la valeur: valeur indexée ou valeur codée littéralement. Dans le cas d'une valeur indexée (localement ou globalement), deux valeurs sont prédites et insérées dans la séquence 17 : une valeur correspondant à l'indication d'une valeur indexée, et une valeur d'index. Pour la valeur indicative, les informations suivantes sont utilisées : - la taille binaire 20 de la valeur à décoder qui est généralement de 8 bits ; - la valeur de codage prédite 21 qui est celle permettant d'encoder le type d'index utilisé: 0 pour un index local, 1 pour un index global ; et - aucun lien n'est associé. Pour la valeur d'index, les informations suivantes sont utilisées : - la taille binaire 20 de la valeur à décoder qui dépend du nombre de valeurs contenues dans l'index ; - la valeur prédite 21 qui n'est pas définie. On n'en tiendra donc pas compte dans la vérification de la prédiction selon l'invention, comme illustré ci-5 après avec la notion de masque de valeurs ; et - aucun lien n'est associé. Dans le cas d'une valeur littérale, plusieurs valeurs sont prédites : une valeur correspondant à la longueur de la chaîne et un ensemble de valeurs représentant chacun des caractères de la chaîne. 10 Pour une longueur de la chaîne, les informations suivantes sont utilisées et mémorisées dans la séquence 17 : - la taille binaire 20 de la valeur à décoder qui est le nombre de bits nécessaires à coder cette longueur ; - la valeur prédite 21 est la longueur de la chaîne ; 15 - aucun lien 22 n'est associé. Pour chaque caractère, dans la mise en oeuvre préférée, les informations suivantes sont utilisées : - la taille binaire 20 de la valeur à décoder qui est généralement de 8 bits ; 20 - la valeur prédite 21 qui est partiellement définie : elle doit être inférieure ou égale à 127. En effet, seuls les caractères dont la valeur est inférieure ou égale à 127 sont codés sur 8 bits. Les caractères dont la valeur est supérieure à 127 sont codés sur plus de 8 bits ; - aucun lien 22 n'est associé. 25 Dans une variante de mise en oeuvre concernant les caractères, des statistiques sont réalisées sur la taille des caractères utilisés, soit de manière générale dans le document EXI, soit de manière particulière pour chaque type de valeur. Ces statistiques sont ensuite utilisées pour générer les informations de la séquence de prédictions 17 correspondant aux caractères. En outre, dans 30 un tel cas, il est possible de vérifier que les caractères sont bien codés sur le nombre d'octets prédits en utilisant de manière particulière les valeurs prédites comme décrit ci-après.

On note que dans notre exemple ci-dessus, on considère que chaque valeur prédite 21 insérée dans la séquence 17 est exprimée sur un octet (8 bits). Toutefois, dans certains cas ces valeurs doivent être codées sur plusieurs octets (en raison de la grande valeur qu'elles prennent). Dans ce cas, une adaptation peut être menée selon laquelle ces valeurs sont ajoutées à la séquence 17 comme des ensembles de valeurs (partielles) codées chacune sur un octet. On poursuit la création de la séquence 17 avec l'étape E320 qui consiste à obtenir l'objet suivant (grammaire ou production généralement).

Si l'objet courant est une grammaire 10 ou une production 11 ne correspondant pas à une fin d'élément (EE dans le langage EXI), alors l'objet suivant est la production prédite 14/16. Si cette production prédite 14/16 correspond à un début d'élément (noté SE en EXI), alors cette production prédite est mémorisée et l'objet suivant 15 devient la grammaire 10 correspondant à ce début d'élément. Si l'objet courant est une production 11 correspondant à une fin d'élément (EE), alors l'objet suivant est la production (SE) décrivant le début de l'élément suivant l'élément courant, si elle a été mémorisée précédemment (voir ci-dessus). Ceci permet d'utiliser, comme prédiction suivante, la prédiction 14 20 liée à la production 11 du début de l'élément suivant, qui décrit ce qui suit l'élément courant (une fois ce dernier entièrement traité). En d'autres termes, la prédiction concerne l'événement de même profondeur dans le document XML 1 suivant l'événement de début d'élément considéré. Si la production n'a pas été mémorisée, l'objet suivant n'est pas 25 défini et l'algorithme se termine à l'étape E340. Si l'objet suivant est défini, il devient l'objet courant, et l'algorithme vérifie, à l'étape E330, que cet objet courant possède bien une ou plusieurs prédictions simples 14, 15 ou 16. Cette étape consiste à vérifier, d'une part, que cet objet courant peut 30 bien être associé à des prédictions simples (par exemple, l'objet courant ne doit pas être une production représentant un commentaire), et, d'autre part, que toutes les prédictions simples 14, 15, 16 associées à cet objet courant ont bien une prédiction définie. Dans l'affirmative de l'étape E330, le traitement de construction de la séquence 17 se poursuit en retournant à l'étape E300 pour intégrer ces nouvelles prédictions simples à la séquence 17. Dans la négative, le traitement prend fin à l'étape E340. On observe que dans le cas où un objet suivant est une grammaire correspondant à un début d'élément et que cette grammaire comprend déjà une séquence de prédictions 17, cette dernière peut être concaténée à la séquence en cours de construction (pour une grammaire précédente) en conservant l'ordre des événements EXI. On accélère ainsi cette opération de construction en évitant de parcourir à nouveau des prédictions simples 14, 15, 16 qui ont déjà permis de créer cette autre séquence 17. Toutefois, si l'on souhaite tenir compte des prédictions simples qui ont été mises à jour, cette concaténation peut être omise. On note également que la première taille binaire 20 d'une séquence 17 est toujours correcte puisqu'elle correspond à la taille de la première valeur encodée pour décrire le début d'élément et que cette taille est connue (fonction du nombre de priorités utilisées dans la grammaire courante). Par contre, la première valeur prédite n'est pas nécessairement correcte. Il en résulte donc un possible décalage au niveau de la vérification des prédictions, duquel on tire une règle pour une mise en oeuvre de l'invention : la première valeur prédite non correcte correspond à une taille prédite correcte (généralement la dernière correctement prédite).

Par ailleurs, un risque important existe que l'algorithme de construction de la séquence de prédiction 17 boucle sur lui-même de façon infinie, par exemple dans le cas d'un élément souvent répété (la prédiction simple 14 associée à la production 11 de début de cet élément indiquera ce même début d'élément). Pour éviter un tel bouclage, on propose ici des mécanismes d'arrêt de boucle, comme suit : - une première méthode consiste à limiter la longueur des séquences de prédictions 17. Ainsi à l'étape E320, on vérifie également la longueur de la séquence 17 en cours de construction, et on termine le traitement de construction dès que cette longueur est supérieure à une valeur prédéfinie. Par exemple, dès que cette longueur atteint un multiple prédéfini du nombre de valeurs que l'on peut mémoriser dans un opérande d'instruction SIMD ; - une deuxième méthode consiste à détecter les boucles au niveau des prédictions simples 14, 15, 16, par exemple lorsqu'une même prédiction simple (ou un même motif de prédictions simples) est rappelé. Lorsqu'une telle boucle est détectée, l'algorithme se termine après un certain nombre d'itérations de cette boucle. En particulier, on veillera à choisir un nombre d'itérations limitant la taille totale de la séquence 17, mais aussi rendant la taille de la séquence la plus proche possible d'un multiple de 16 (de façon générale, d'un multiple du nombre de valeurs que l'on peut traiter par un seul opérande des instructions SIMD). On optimise ainsi l'utilisation des instructions SIMD dont le remplissage des opérandes est maximisé. Par exemple, si le nombre de prédictions simples 14, 15, 16 correspondant à une itération de la boucle est de 8, alors deux itérations de cette boucle seront effectuées. Si ce nombre est 12, 4 itérations seront effectuées, permettant d'obtenir 4 * 12 = 3 * 16 = 48 prédictions dans la séquence.

En complément, même si le traitement construit une séquence de prédictions 17 ayant la taille maximale autorisée, certaines des prédictions peuvent être supprimées de sorte à arrêter la séquence 17 à un endroit optimal pour commencer une autre séquence de prédictions. Cet endroit optimal peut être le début d'un élément XML ou le début d'un élément auquel est déjà associée une séquence de prédictions dont les statistiques montrent qu'elle est utilisée efficacement. En reprenant l'exemple du tableau de la figure 2a, cet algorithme de génération d'une séquence de prédictions 17 va générer les informations représentées sur la figure 6.

Dans cet exemple, toutes les valeurs sont indiquées en mode binaire.

La première colonne indique le type de la valeur de codage prédite. Cette colonne est ajoutée pour une meilleure compréhension du tableau et n'est pas présente dans la séquence de prédictions 17. La deuxième colonne contient la taille binaire 20 de la valeur de codage prédite. Cette taille est représentée en tant que valeur binaire ("0000 0011" correspondant par exemple à un taille de "3" bits). La troisième et la quatrième colonne contiennent la valeur de codage prédite 21 dans un format binaire sur un octet et un masque associé 23. Ces valeurs et masques sont utilisés lors de la vérification de la prédiction des tailles binaires 21 comme décrit ci-après. La troisième colonne contient effectivement la valeur de codage prédite quand cette valeur est présente, ou la valeur 0 dans le cas contraire. La quatrième colonne contient un masque permettant de vérifier si la valeur prédite doit être égale à la valeur décodée ou non. Comme expliqué ci-dessus, dans l'exemple illustré ici, on est amené à comparer les priorités pour encoder les productions, alors que certaines valeurs de contenu ne sont pas prises en compte car difficilement prédictibles (donc le masque 23 est agencé pour ne pas en tenir compte et vaut "0"). Le masque permet ainsi de déterminer quelles sont les valeurs qui doivent être vérifiées lors de la vérification de la prédiction des tailles binaires 21. On peut noter le cas particulier de la valeur de type caractère (dernière ligne) : un seul bit du masque est à 1, le bit de poids fort. En effet, lors de la prédiction d'un caractère, la valeur de ce caractère importe peu. Par contre, il est important de vérifier que ce caractère est bien codé sur le nombre d'octets prédits. Dans le cas de l'exemple, le caractère est prédit pour être codé sur un seul octet, ce qui implique d'après la spécification EXI que le bit de poids fort de cet octet soit 0. La valeur prédite 21 et le masque de valeur 23 associés à ce caractère prédit permettent donc de vérifier cette prédiction de bit de poids fort.

La cinquième colonne contient un lien 22 vers la grammaire contenant les productions prédites, dans le cas où la prédiction porte sur une production. Ce lien permet de retrouver la grammaire à utiliser en cas d'erreur de prédiction. La sixième colonne contient une indication de ce que représente la valeur prédite 21. Ainsi, dans le cas d'une priorité, cette indication correspond à l'événement représenté par cette priorité. Dans le cas d'une valeur textuelle, cette indication correspond au type de codage de cette valeur et éventuellement comporte un pointeur vers le dictionnaire utilisé pour le codage de cette valeur. Après l'obtention des séquences de prédictions 17 associées à tout ou partie des grammaires EXI, on décrit maintenant, en référence aux figures 7 et 8, l'étape de décodage selon l'invention, correspondant à l'étape E130 de la figure 3. Ce décodage, et plus particulièrement les opérations permettant la délimitation des valeurs de codage présentes dans le flux EXI 2 et leur décompactage pour avoir le même format que les valeurs manipulées dans les grammaires, est réalisé à l'aide d'instructions SIMD, dont une brève présentation est donnée à la fin de la présente description. Lors de la première étape E400, on obtient des prédictions de taille binaire 20 de valeurs de codage du flux EXI à décoder. Ces prédictions sont obtenues à partir de la séquence de prédictions 17 utilisée. Ainsi, dans le cas de l'exemple précédent, ces prédictions sont les tailles 20 décrites dans le tableau de la figure 6. Ces prédictions (chacune sur un octet) sont concaténées dans un registre SIMD (128 bits), tel qu'illustré par la figure 8a. Il est à noter que dans un souci de compacité des exemples, les figures 8a à 8h décrivent des données sur 64 bits uniquement (correspondant à 8 valeurs uniquement au lieu de 16). Le nombre de bits de remplissage pour chaque valeur de codage 30 à décoder est alors calculé, comme suit : 8 ù taille binaire 20, ce qui correspond aux instructions SIMD suivantes. padding size = simd sub 8(simd const 8(8), value size); La figure 8b illustre le nombre de bits de remplissage "padding size" ainsi obtenus.

Il est à noter que si le nombre de prédictions dans la séquence 17 est supérieur à 16, l'ensemble des valeurs correspondant à ces prédictions ne pourra être traité simultanément. Dans ce cas, seules les tailles binaires 20 correspondant aux 16 premières prédictions sont chargés dans le registre SIMD. La deuxième étape E410 est l'obtention des valeurs de codage 30 à décoder, depuis le flux EXI 2. Cette obtention consiste à charger ces valeurs dans un registre SIMD. Il est à noter que dans la plupart des cas, le début de la première valeur à décoder n'est pas aligné sur une limite d'octet (option "bit- packed"). Ceci est à prendre en compte lors du chargement des valeurs et peut être réalisé par des algorithmes classiques. Dans l'exemple précédent, les valeurs chargées dans un registre SIMD sont représentées sur la figure 8c. A ce stade, ne connaissant pas la longueur correspondant aux 16 valeurs, on récupère 128 bits consécutifs du flux. La troisième étape E420 concerne le décompactage proprement dit des valeurs ainsi récupérées, sur la base des tailles binaires prédites. Cette opération permet le réalignement des valeurs de codage récupérées pour correspondre à l'alignement binaire des valeurs manipulées par le décodeur (généralement alignées sur les octets). Ce décompactage est réalisé en trois sous-étapes. La première sous-étape E422 consiste à compter le nombre de bits de remplissage pour une, deux, quatre et huit valeurs (dans notre exemple). Ce comptage est réalisé par les instructions SIMD suivantes : 25 count8 = padding size countl6 simd add 161h(count8, count8); count32 simd add 321h(countl6, countl6); count64 simd add 641h(count32, count32); Ce comptage revient à additionner le nombre de bits de remplissage 30 pour deux valeurs consécutives, ce qui donne la valeur countl6, puis pour quatre et enfin huit valeurs consécutives. Ainsi en reprenant l'exemple, on obtient les comptes de la figure 8d.

La sous-étape suivante E424 consiste à calculer des masques de décalage de bits à partir des valeurs calculées précédemment. Ces masques de décalage ont pour but, comme décrit ci-après, de décaler progressivement les seize valeurs de codage 30 récupérées pour les aligner avec le format des valeurs manipulées par le décodeur (dans notre exemple, les valeurs sont sur un octet). Le calcul de ces masques de décalage consiste à appliquer les instructions SIMD suivantes: mask8 = simd const 16((1 « 8) - 1); shift8 = simd and(simd srli(count8, 8), mask8); maskl6 = simd const 32((1 « 16) - 1); shiftl6 = simd and(simd srli(countl6, 16), maskl6); mask32 = simd const 64((1 « 32) - 1); shift32 = simd and(simd srli(count32, 32), mask32); mask64 = simd const 128((1 « 64) - 1); shift64 = simd and(simd srli(count64, 64), mask64); Il est à noter que si les masques de décalage (les valeurs shift8, shiftl6...) sont propres à chaque séquence de prédictions, les masques (les valeurs mask8, maskl6...) utilisés pour les calculer sont des constantes qui n'ont pas besoin d'être recalculées à chaque exécution de l'algorithme. D'autre part, ces masques de décalage sont invariants pour une même séquence de prédictions 17 et peuvent donc être mémorisés avec cette séquence. Ceci permet d'accélérer le décodage en occupant cependant plus de mémoire. Des stratégies de mémorisation de ces masques plus élaborées peuvent donc être mises en place. L'application de ces calculs à notre exemple est illustrée par la figure 8e. Enfin, la dernière sous-étape, notée E426, est le décompactage lui-même. Ce décompactage est réalisé en séparant les seize valeurs en deux groupes de huit valeurs, chacune dans une moitié de registre SIMD. Ainsi, chaque groupe de huit valeurs est aligné sur un bloc de 64 bits (correspondant à value64 non représenté sur la figure 8f). Puis le processus est recommencé pour séparer chaque groupe en deux, jusqu'à ce que chaque valeur soit isolée sur un bloc de huit bits (successivement value32, valuel6 et value8 sur la figure 8f). Une dernière opération permet alors d'aligner chacune de ces valeurs (voir bytes sur la figure 8f). On observe d'ailleurs que le décalage de cette étape insère des "0" dans la suite binaire, ce qui a pour autre effet d'expulser, de cette suite, les bits au-delà des 16 valeurs souhaitées (correspondant aux bits marqués d'un "." dans value sur la figure 8f) Ces opérations sont réalisées par les instructions SIMD suivantes: shifted = simd and(simd srl 128(value, shift64), mask64); masked = simd andc(value, mask32); value64 = simd or(shifted, masked); shifted = simd and(simd srl 64(value64, shift32), mask32); masked = simd andc(value64, mask32); value32 = simd or(shifted, masked); shifted = simd and(simd srl 32(value32, shiftl6), maskl6); masked = simd andc(value32, maskl6); valuel6 = simd or(shifted, masked); shifted = simd and(simd srl 16(valuel6, shift8), mask8); masked = simd andc(valuel6, mask8); value8 = simd or(shifted, masked); bytes = simd srl 8(value8, count8); Les valeurs obtenues pour notre exemple sont représentées sur la figure 8f (les points "." au final montrant les décalages de bits réalisés par l'insertion de "0"). Ainsi, à partir de l'ensemble de valeurs initialement compactées (figure 8c), on obtient la liste de ces valeurs chacune représentée sur 1 octet. L'étape suivante E430 consiste alors à vérifier les prédictions. Pour cela, on charge tout d'abord (E432), dans deux registres SIMD (predicted et predictmask), les valeurs de décodage prédites 21 à partir de la séquence de prédictions 17 (voir figure 8g ù cette opération pouvant être réalisée à n'importe quelle autre étape précédente, notamment lors de l'étape E400 où on accède déjà à la séquence 17) et les masques associés. Puis la liste des valeurs décompactées bytes est comparée (étape E434) à la liste predicted des valeurs prédites, en tenant compte du masque predict mark.

Les instructions SIMD utilisées pour cette comparaison sont les suivantes : error = simd and(simd xor(bytes, predicted), predict mask) Ainsi, l'opérande error contient pour chaque valeur décompactée une vérification de la prédiction correspondante (valant 0 si la valeur est correctement prédite û voir figure 8h pour notre exemple). On voit ainsi que l'on a, à l'aide d'instructions SIMD, décompacté et réaligné simultanément plusieurs valeurs de codage, afin de les utiliser pour identifier, dans les grammaires ou autres tables de décodage, les valeurs et événements XML correspondant.

Dans une variante, cette étape de l'invention peut être simplifiée. En effet dans certains cas, un ensemble de prédictions peut être vérifié de manière plus simple. Par exemple, dans le cas d'une structure bien définie (cette structure pouvant correspondre par exemple à un élément XML avec l'ensemble de ses attributs et sous-éléments), la simplification consiste à vérifier que les valeurs à décoder correspondent bien à cette structure pour pouvoir utiliser la séquence de prédictions correspondant à cette structure sans avoir besoin d'effectuer de vérifications supplémentaires. On peut ainsi omettre de vérifier les prédictions pour cette séquence, et poursuivre le traitement (décodage par exemple) de cette séquence et le traitement des éléments suivants cette structure bien définie. Dans un tel cas, la vérification peut être réalisée par exemple en testant quelques bits parmi les valeurs à décoder par comparaison avec la structure bien définie, cette vérification étant réalisée a priori, entre les étapes E410 et E420. En outre, si la structure est suffisamment longue, cette étape est réalisée au début du décodage de la structure. Et si l'algorithme réalise plusieurs fois les étapes E400 à E460 pour décoder le flux binaire correspondant à la structure, cette vérification n'est pas réitérée tant que l'on décode le flux binaire correspondant à la structure.

A l'étape suivante E440, la séquence de prédictions 17 est mise à jour en utilisant cette vérification de prédictions. Cette étape est décrite après, plus en détail en référence à la figure 9. Ensuite, le flux de données est mis à jour (étape E450). Cela consiste à marquer la position de la prochaine valeur à décoder. Ceci est réalisé à partir de l'indication de la première valeur erronée et de la taille des valeurs correctement décompactées. Dans notre exemple (figure 8h), la 7ème valeur n'a pas été correctement prédite. Cela signifie, selon la règle vue ci-dessus selon laquelle, malgré la valeur erronée, la prédiction de la taille binaire est bonne, que l'on sait que la 7ème valeur a tout de même bien été délimitée et donc décompactée. On peut donc positionner le marqueur de la prochaine valeur à décoder au début de la 8ème valeur. Pour cela, on détermine la taille binaire totale des valeurs correctement décodées, ici 32 bits. Le marqueur de la prochaine valeur à décoder est donc positionné sur le bit suivant à savoir sur le 33ème bit du flux EXI 2 (figure 8c). Puis, l'étape suivante E460 consiste à décoder effectivement l'ensemble des valeurs décompactées (les sept premières donc). Pour toutes les valeurs correctement prédites, ce décodage utilise l'information décrivant le contenu XML représenté par cette valeur pour générer l'événement (ou la partie d'événement) correspondant à cette valeur. On diminue ainsi les traitements à réaliser. Comme évoqué précédemment, pour la première valeur incorrectement prédite, la taille de cette valeur a cependant été correctement prédite et la valeur a donc été correctement décompactée. Cependant l'information décrivant le contenu XML ne correspond pas à cette valeur. Le décodage s'effectue alors à partir de la grammaire indiquée dans l'information de lien 22 pour cette valeur. Si aucune information de lien 22 n'existe pour cette valeur, on utilise l'information indiquée pour une valeur précédente (l'information de lien utilisée est la dernière information de lien présente pour l'une des valeurs correctement prédites ou pour cette valeur incorrectement prédite).

Il est à noter qu'un cas particulier d'erreur de prédiction est celui où la longueur d'une chaîne de caractères est erronée. Dans un tel cas, les prédictions de caractères peuvent néanmoins être utilisées tant qu'elles correspondent à des caractères effectivement présents dans la chaîne à décoder : les prédictions correspondant à des caractères positionnés avant la fin réelle de la chaîne de caractère restent valides. Ce cas particulier de gestion des erreurs de prédiction peut être mis en oeuvre pour accélérer le décodage des chaînes de caractères. En outre, quand une erreur survient sur la prédiction de la longueur d'une chaîne de caractères, il est possible de continuer d'utiliser les prédictions pour les valeurs survenant après la chaîne. Ceci peut être réalisé en adaptant l'algorithme décrit ici. En variante, les chaînes de caractères peuvent être traitées de manière spécifique : le décompactage optimisé décrit par cet algorithme est alors réalisé pour un ensemble de valeurs y compris la longueur de la chaîne de caractères. Mais la chaîne elle-même est décodée de manière spécifique. Ensuite, le décompactage optimisé est repris pour traiter les valeurs suivant cette chaîne de caractères. Il est à noter que pour le décodage d'une chaîne de caractères, des instructions de type SIMD peuvent être utilisées avec profit. En effet, il est intéressant d'utiliser de telles instructions d'une part pour aligner la chaîne codée sur des limites d'octets, par de simples instructions de décalage de bits. D'autre part, le décodage de la chaîne de caractères depuis le codage utilisé par la spécification EXI vers un codage classique comme UTF-8 ou UTF-16 peut être réalisé de manière optimisée avec des instructions SIMD, à l'aide d'algorithmes similaires à ceux décrits par Parabix. Dans une variante d'utilisation de l'invention, le décodage complet du document n'est pas réalisé. Ainsi, dans certains cas, il peut être intéressant de parcourir au plus vite le début du document pour atteindre une partie particulière du document qui sera décodée complètement. Dans l'exemple d'une liste de personne, cela permet par exemple de ne décoder que les informations concernant une personne particulière. Dans cette variante, l'étape E460 n'est pas réalisée tant que la partie du document traitée correspond à une partie non intéressante (par exemple tant que l'on n'a pas atteint une balise <personne particulière> attendue) : en effet les étapes précédentes ont réalisé l'ensemble des traitements nécessaires pour permettre au décodeur de traiter la suite du document. L'utilisation de l'invention dans un tel cadre permet d'accélérer le traitement rapide d'une partie d'un document. Toujours en référence à la figure 7, à l'étape suivante E470, l'algorithme vérifie si d'autres prédictions sont disponibles et peuvent être utilisées. Cette vérification tient compte du résultat de l'étape E430. En effet, si une erreur de prédiction a été détectée à l'étape E430, alors d'autres prédictions ne peuvent être utilisées. L'algorithme se termine à l'étape E480. Si, en revanche, aucune erreur de prédiction n'a été détectée à l'étape E430, et s'il reste des prédictions non utilisées dans la séquence de prédictions initiale 17, alors l'algorithme se poursuit en retournant à l'étape E400 avec les prédictions suivantes de la séquence. Sinon l'algorithme se termine à l'étape E480. Il est à noter que cet algorithme fonctionne de façon optimale si le nombre de prédictions disponible dans la séquence est un multiple de 16 : à chaque itération de l'algorithme, seize valeurs seront décompactées simultanément. Si moins de seize prédictions sont disponibles pour une itération de l'algorithme, les prédictions manquantes sont remplacées par les valeurs suivantes : la taille de la valeur est 0, la valeur prédite est 255 (c'est-à-dire 1111 1111 en binaire) et le masque de la valeur prédite est 255 (1111 1111 en binaire). Ceci permet d'utiliser l'algorithme sans modification tout en générant une erreur pour ces prédictions manquantes afin de stopper le décodage en arrivant sur ces valeurs factices. On décrit maintenant, en référence à la figure 9, l'étape E440 de mise à jour des séquences de prédictions 17 en fonction du résultat de la vérification des prédictions E430.

La première étape E500 consiste à mettre à jour de statistiques d'utilisation de la séquence. Cette étape utilise pour cela les résultats de la vérification de prédictions de cette séquence. Dans un mode de réalisation de l'invention, les statistiques d'utilisation de la séquence sont composées d'une liste qui contient les positions où ont eu lieu des erreurs de prédiction pour les dernières utilisations de cette séquence 17. Dans une variante, les statistiques d'utilisation de la séquence sont composées d'une liste comportant deux entrées correspondant aux positions des deux dernières erreurs. L'étape suivante E510 consiste alors à vérifier si la séquence de prédictions 17 est fiable ou non par rapport au flux EXI 2 en cours de décodage. Cette vérification s'appuie sur les statistiques d'utilisation de la séquence. Dans l'exemple de statistiques ci-dessus, l'algorithme utilise la liste des positions où une erreur de prédiction s'est produite. Si une position a une fréquence importante dans cette liste (par exemple au-delà de 25% des erreurs), alors la séquence 17 n'est pas considérée comme fiable. Dans la variante de mise en oeuvre, si les deux positions de la liste de statistiques sont égales, alors la séquence 17 n'est pas considérée comme fiable. Dans les autres cas, la séquence 17 est considérée comme fiable et le traitement prend fin à l'étape E530. Si la séquence de prédictions 17 n'est pas considérée comme fiable, l'algorithme se poursuit à l'étape E520 au cours de laquelle la séquence de prédictions 17 est mise à jour. Selon une mise en oeuvre préférée de l'invention, cette mise à jour consiste à couper la séquence 17 à la position où une erreur de prédiction se produit fréquemment, notamment à l'endroit de l'erreur de prédiction la plus fréquente. On ne conserve ainsi, associée à la grammaire 10 correspondante, que le début de la séquence 17, c'est-à-dire les événements et valeurs statistiquement correctement prédites.

Selon une seconde mise en oeuvre, la séquence de prédictions 17 peut être reconstruite intégralement en reproduisant le traitement de la figure 5, puis comparée à la séquence 17 existante pour vérifier si la position fréquente d'erreur comprend une prédiction différente.

Si c'est le cas, alors la nouvelle séquence de prédictions remplace l'ancienne. Sinon, l'ancienne séquence est coupée à cette position. Dans une variante plus simple de cette seconde mise en oeuvre, au lieu de reconstruire toute la séquence 17 avant vérification, on peut vérifier directement si la prédiction fréquemment erronée a été modifiée au niveau de la prédiction simple correspondante. Pour ce faire, on identifie tout d'abord la production 11 (correspondant à la valeur prédite précédant celle fréquemment erronée) ou la grammaire 10 (dans le cas où l'événement précédent est un début d'élément) ayant produit cette prédiction, puis on vérifie si la prédiction simple 14/16 associée à cette production ou grammaire a été modifiée. Si tel est le cas, on modifie la séquence à compter de cette prédiction. Suite à cette mise à jour, l'algorithme se termine à l'étape E530. Un cas particulier de mise à jour d'une séquence de prédictions 17 est le changement de taille d'un dictionnaire de valeurs, en particulier quand ce changement de taille provoque un changement de taille du codage des index pour ce dictionnaire. En effet, les prédictions portant sur un index dans ce dictionnaire utilisent cette taille de codage des index. Or la vérification des prédictions ne vérifie que la taille prédite pour savoir si elle est correcte. Par conséquent, quand un changement de taille de codage des index survient pour un dictionnaire, l'ensemble des prédictions portant sur ces index doit être modifié. Cette modification est réalisée en associant à chaque dictionnaire les prédictions simples qui correspondent à un index de ce dictionnaire. Ainsi, lors d'un changement de taille de codage des index de ce dictionnaire, ces prédictions simples peuvent être modifiées.

Ensuite, ces modifications sont reportées dans les séquences de prédictions 17 construites à partir de ces prédictions simples. Ceci peut être réalisé par exemple en reconstruisant les séquences de prédictions selon les mécanismes de la figure 5. En variante, il est possible d'optimiser cette opération en modifiant directement les séquences de prédictions 17 déjà construites. On notera enfin que, pour un petit dictionnaire de valeurs, la taille de codage des index pour ce dictionnaire va changer fréquemment : en effet, la taille de codage d'un index est égale à la valeur entière du logarithme en base 2 de la taille du dictionnaire. Comme cette opération de mise à jour des prédictions est coûteuse, les prédictions simples de contenu ne sont pas considérées comme valides (c'est-à-dire qu'elles ne peuvent être intégrées à une séquence de prédiction, à l'étape E330) si ces prédictions correspondent à une valeur indexée et que la taille de l'index est trop petite (par exemple, inférieure ou égale à 4 ou à 8). Il ressort clairement de ce qui précède que la délimitation des valeurs de codage dans un flux EXI et leur décompactage peuvent être réalisés simultanément pour un grand nombre d'événements EXI, notamment par la mise en oeuvre des instructions de type SIMD, en dépit de la non connaissance de ces tailles eu égard à leur dépendance aux événements précédents non encore décompactés et décodés. Cette efficacité est obtenue par la prédiction des tailles binaires de ces valeurs EXI, et la validation de tout ou partie de ces prédictions par comparaison des valeurs EXI ainsi récupérées et décompactés avec des valeurs également prédites. Si les valeurs ont bien été prédites, c'est que le décompactage est correct et donc les tailles prédites sont exactes. Outre la mise en oeuvre de ces traitements pour le décodage d'un flux binaire comme illustré ci-dessus, ils peuvent permettre d'accéder, à moindre coût et de façon rapide, une partie précise du document structuré codé. En effet, l'invention permet de parcourir rapidement les événements codés jusqu'à atteindre le premier de la partie à accéder (généralement un début d'élément avec un nom donné, ou une position donnée dans le document codé).

La mise en oeuvre d'instructions SIMD peut également être réalisée lors du codage de documents structurés tels XML en un flux EXI, notamment lors des opérations de compactage d'un grand nombre de valeurs de codage récupérées des dictionnaires et grammaires. Par exemple, le procédé consiste à: - déterminer les valeurs de codage d'une pluralité d'événements consécutifs dudit document ; - déterminer une taille de compactage pour chaque valeur de codage (généralement le nombre minimal de bits pour encoder l'ensemble des priorités de la grammaire correspondante) ; et - compacter simultanément lesdites valeurs de codage à l'aide desdites tailles de compactage en utilisant au moins une instruction unique à multiples données. Il s'agit principalement d'effectuer les opérations inverses de celles décrites ci-dessus pour le décompactage. En référence maintenant à la figure 10, il est décrit à titre d'exemple une configuration matérielle particulière d'un dispositif de traitement d'un document structuré et/ou d'un flux binaire correspondant à un tel document codé apte à une mise en oeuvre du procédé selon l'invention. Un dispositif de traitement d'information mettant en oeuvre l'invention est par exemple un micro-ordinateur 50, une station de travail, un assistant personnel, ou un téléphone mobile connecté à différents périphériques. Selon encore un autre mode de réalisation de l'invention, le dispositif se présente sous la forme d'un appareil photographique muni d'une interface de communication pour autoriser une connexion à un réseau Les périphériques reliés au dispositif selon l'invention comprennent par exemple une caméra numérique 64, ou un scanner ou tout autre moyen d'acquisition ou de stockage d'images, relié à une carte d'entrée/sortie (non représentée) et fournissant au dispositif des données multimédia, éventuellement sous forme de documents XML ou de flux EXI / Fast Infoset. Le dispositif 50 comporte un bus de communication 51 auquel sont reliés : - une unité centrale de traitement CPU 52 se présentant par exemple sous la forme d'un microprocesseur ; - une mémoire morte 53 dans laquelle peuvent être contenus les programmes dont l'exécution permet la mise en oeuvre du procédé selon l'invention. Il peut s'agir d'une mémoire flash ou EEPROM ; - une mémoire vive 54 qui, après la mise sous tension du dispositif 50, contient le code exécutable des programmes de l'invention nécessaires à la mise en oeuvre de l'invention. Cette mémoire vive 54 est de type RAM (à accès aléatoire), ce qui offre des accès rapide comparés à la mémoire morte 53 ; - un écran 55 permettant de visualiser des données notamment vidéo et/ou de servir d'interface graphique avec l'utilisateur qui peut ainsi interagir avec les programmes de l'invention, à l'aide d'un clavier 56 ou de tout autre moyen tel qu'un dispositif de pointage, comme par exemple une souris 57 ou un crayon optique ; - un disque dur 58 ou une mémoire de stockage, telle qu'une mémoire de type compact flash, pouvant comporter les programmes de l'invention ainsi que des données utilisées ou produites lors de la mise en oeuvre de l'invention ; - un lecteur de disquettes 59 optionnel, ou un autre lecteur de support de données amovible, adapté à recevoir une disquette 63 et à y lire / écrire des données traitées ou à traiter conformément à l'invention ; et - une interface de communication 60 reliée au réseau de télécommunications 61, l'interface 60 étant apte à transmettre et à recevoir des données. Le bus de communication 51 autorise une communication et une interopérabilité entre les différents éléments inclus dans le dispositif 50 ou reliés à celui-ci. La représentation du bus 51 n'est pas limitative et, notamment, l'unité centrale 52 est susceptible de communiquer des instructions à tout élément du dispositif 50 directement ou par l'intermédiaire d'un autre élément du dispositif 50. Les disquettes 63 peuvent être remplacées par tout support d'information tel que, par exemple, un disque compact (CD-ROM) réinscriptible ou non, un disque ZIP ou une carte mémoire. D'une manière générale, un moyen de stockage d'information, lisible par un micro-ordinateur ou par un microprocesseur, intégré ou non au dispositif de traitement, éventuellement amovible, est adapté à mémoriser un ou plusieurs programmes dont l'exécution permet la mise en oeuvre du procédé selon l'invention. Le code exécutable permettant, au dispositif de traitement, la mise en oeuvre de l'invention peut être indifféremment stocké en mémoire morte 53, sur le disque dur 58 ou sur un support numérique amovible tel que par exemple une disquette 63 comme décrite précédemment. Selon une variante, le code exécutable des programmes est reçu par l'intermédiaire du réseau de télécommunications 61, via l'interface 60, pour être stocké dans un des moyens de stockage du dispositif 50 (tel que le disque dur 58 par exemple) avant d'être exécuté. L'unité centrale 52 commande et dirige l'exécution des instructions ou portions de code logiciel du ou des programmes de l'invention, les instructions ou portions de code logiciel étant stockées dans l'un des moyens de stockage précités. Lors de la mise sous tension du dispositif 50, le ou les programmes qui sont stockés dans une mémoire non volatile, par exemple le disque dur 58 ou la mémoire morte 53, sont transférés dans la mémoire vive 54 qui contient alors le code exécutable du ou des programmes de l'invention, ainsi que des registres pour mémoriser les variables et paramètres nécessaires à la mise en oeuvre de l'invention. On notera également que le dispositif mettant en oeuvre l'invention ou incorporant celle-ci est réalisable aussi sous la forme d'un appareil programmé. Par exemple, un tel dispositif peut alors contenir le code du ou des programmes informatiques sous une forme figée dans un circuit intégré à application spécifique (ASIC). Le dispositif décrit ici et, particulièrement, l'unité centrale 52, sont susceptibles de mettre en oeuvre tout ou partie des traitements décrits en lien avec les figures 4 à 9, pour mettre en oeuvre les procédés objets de la présente invention et constituer les dispositifs objets de la présente invention.

Les exemples qui précèdent ne sont que des modes de réalisation de l'invention qui ne s'y limite pas.

Présentation des instructions SIMD mises en oeuvre dans le mode de réalisation illustratif de la présente invention. simd not (op) Opérateur « non » bit à bit. simd and (op1, op2) Opérateur « et » bit à bit. simd andc (op1, op2) Opérateur « et contraire » bit à bit. Equivalent à simd and (op1, simd not(op2)). simd or (op1, op2) Opérateur «ou » bit à bit. simd xor (op1, op2) Opérateur « ou exclusif » bit à bit. simd const n (value) Crée une constante, utilisant des champs de bits de taille n, chaque champ contenant la valeur donnée. simd srli (op, value) Décalage logique vers la droite, utilisant le nombre de bits indiqués. simd srl n (op1, op2) Décalage logique vers la droite, utilisant des champs de bits de taille n, où les champs du premier opérande sont décalés du nombre de bits indiqué dans le champ correspondant du deuxième opérande. simd add n hi h2(op1, op2) Additionne les deux opérandes, en utilisant des champs de bits de taille n et en utilisant des opérandes de demi-taille. hi indique quelle demi partie (haute ou basse, représentées par h ou 1) est utilisée pour chaque champ du 25 premier opérande. h2 joue le même rôle pour le deuxième opérande. simd sub n (op', ope) Soustrait les deux opérandes, en utilisant des champs de bits de taille n.

Claims

REVENDICATIONS1. Procédé de traitement d'un flux binaire (2) comprenant des valeurs de codage (30) d'événements d'un document structuré (1), le procédé comprenant les étapes consistant à : - récupérer (E410) une pluralité (value) de valeurs de codage (30) d'événements consécutives dudit flux binaire (2) ; - prédire (E400) la taille binaire (20, value size) desdites valeurs de codage récupérées (30) ; - réaligner (E426), à l'aide desdites tailles binaires prédites (20, value size), les valeurs de codage (30) de ladite pluralité récupérée (value) pour correspondre à un alignement binaire donné ; - valider (E430, E434) la prédiction d'au moins une partie des tailles binaires (20) ; - traiter (E460) les événements correspondant aux tailles binaires dont la prédiction est validée.
2. Procédé de traitement selon la revendication précédente, comprenant les étapes consistant à : - prédire (E432) des valeurs de codage récupérées de sorte à former une pluralité prédite (predicted) de valeurs de codage (21), lesdites valeurs de codage (21) de la pluralité prédite (predicted) étant selon ledit alignement binaire donné ; et - vérifier (E430, E434) la prédiction des valeurs de codage par comparaison des pluralités prédite (21, predicted) et réalignée (30, bytes) de sorte à valider la prédiction d'au moins une partie des tailles binaires (20).
3. Procédé de traitement selon la revendication 2, comprenant l'association (E150), à au moins une table de décodage (10) dudit flux binaire (2), d'une séquence de prédictions (17) dont les entrées comprennent au moins une valeur de codage (21) d'événement et une taille binaire (20) associée à cette valeur de codage ;et dans lequel lesdites prédictions (E400, E430) des valeurs de codage et des tailles binaires sont récupérées de ladite séquence de prédictions (17) associée à la table de décodage (10) courante.
4. Procédé de traitement selon la revendication précédente, comprenant une étape de construction (E150) de ladite séquence de prédictions (17) à partir d'au moins une prédiction simple (14, 15, 16) associée à au moins une entrée (11) des tables de décodage (10), ladite prédiction simple renseignant une autre entrée de table de décodage.
5. Procédé de traitement selon la revendication précédente, dans lequel ladite construction (E150) comprend le parcours (E320) d'une pluralité d'entrées des tables de décodage (10) en navigant à l'aide des prédictions simples (14, 15, 16) associées auxdites entrées parcoures, et l'ajout (E310) desdites prédictions simples parcourues à ladite séquence de prédictions.
6. Procédé de traitement selon l'une des revendications 3 à 5, comprenant la mise à jour (E520) de ladite séquence de prédictions (17) en fonction de ladite vérification (E430, E434).
7. Procédé de traitement selon l'une des revendications 3 à 6, dans lequel ledit traitement comprend le décodage (E460) de la première valeur de codage récupérée dont la prédiction est erronée, à l'aide d'une information de lien (22) associée à une entrée de ladite séquence de prédictions (17).
8. Procédé de traitement selon l'une des revendications 3 à 7, dans lequel ladite séquence de prédictions (17) comprend un nombre d'entrées qui est un multiple du nombre de valeurs contenues, selon ledit alignement binaire de la pluralité prédite, dans un opérande d'instruction unique à multiples données (SIMD).
9. Procédé de traitement selon l'une des revendications 2 à 8, dans lequel ladite vérification (E430, E434) comprend l'application d'un masque de prédiction (predict mask) de sorte à ne pas prendre en compte au moins une valeur de codage lors de ladite comparaison.
10. Procédé de traitement selon l'une des revendications précédentes, dans lequel le réalignement (E426) des valeurs de codage (30)met en oeuvre au moins une instruction unique à multiples données (SIMD) de décalage de bits.
11. Procédé de traitement selon la revendication précédente, comprenant la concaténation des tailles binaires prédites (20) dans un premier registre (value size) d'instruction unique à multiples données (SIMD).
12. Procédé de traitement selon l'une des revendications 10 et 11, dans lequel ledit réalignement (E426) met en oeuvre une pluralité d'instructions uniques à multiples données (SIMD) aptes à réaliser un alignement progressif des valeurs de codage récupérées, par décalage itératif de sous-groupes de valeurs de codage successives.
13. Procédé de traitement selon la revendication précédente, dans lequel on divise par deux les sous-groupes d'une itération à l'autre.
14. Procédé de traitement selon la revendication 1, dans lequel ladite validation (E430) comprend la comparaison d'au moins une partie (value) du flux binaire récupéré avec une structure prédéfinie, et en cas de comparaison positive, on utilise une séquence de prédictions (17) associée à ladite structure prédéfinie pour prédire les tailles binaires (20, value size).
15. Dispositif de traitement (50) d'un flux binaire (2) comprenant des valeurs de codage (30) d'événements d'un document structuré (1), le dispositif comprenant : - un moyen apte à récupérer (E410) une pluralité (value) de valeurs de codage (30) d'événements consécutives dudit flux binaire (2) ; - un moyen de prédiction pour prédire (E400) la taille binaire (20, value size) desdites valeurs de codage récupérées (30) ; - un moyen de réalignement apte à réaligner (E426), à l'aide desdites tailles binaires prédites (20, value size), les valeurs de codage (30) de ladite pluralité récupérée (value) pour correspondre à un alignement binaire donné ; - un moyen de validation apte à valider (E430, E434) la prédiction d'au moins une partie des tailles binaires (20) ;- un module de traitement pour traiter (E460) les événements correspondant aux tailles binaires dont la prédiction est validée.
16. Dispositif de traitement selon la revendication 15, dans lequel : - le moyen de prédiction est également apte à prédire (E432) des valeurs de codage récupérées de sorte à former une pluralité prédite (predicted) de valeurs de codage (21), lesdites valeurs de codage (21) de la pluralité prédite (predicted) étant selon ledit alignement binaire donné; et - le moyen de validation est apte à vérifier (E430, E434) la prédiction des valeurs de codage par comparaison des pluralités prédite (21, predicted) et réalignée (30, bytes) de sorte à valider la prédiction d'au moins une partie des tailles binaires (20).
17. Dispositif de traitement selon la revendication 16, comprenant des instructions uniques à données multiples et des registres associés pour stocker simultanément des informations (20, 21, 30) relatives à une pluralité de valeurs de codage successives à traiter.
18. Dispositif de traitement selon la revendication 16 ou 17, comprenant des tables de décodage (10) auxquelles sont associées des séquences de prédictions (17) dont les entrées comprennent au moins une valeur de codage (21) d'événement et une taille binaire (20) associée à cette valeur de codage.
19. Dispositif de traitement selon la revendication précédente, comprenant des prédictions simples (14, 15, 16) associées à des entrées (11) des tables de décodage (10) et renseignant une autre entrée de table de décodage, et des moyens de construction d'une telle séquence de prédictions à partir des prédictions simples.
20. Moyen de stockage d'informations, lisible par un système informatique, comprenant des instructions pour un programme informatique adapté à mettre en oeuvre le procédé conforme à l'une quelconque des revendications 1 à 14 lorsque le programme est chargé et exécuté par le système informatique.
21. Produit programme d'ordinateur lisible par un microprocesseur, comprenant des portions de code logiciel adaptées à mettre en oeuvre le procédé selon l'une quelconque des revendications 1 à 14, lorsqu'il est chargé et exécuté par le microprocesseur.