Brevet FR2751492A1 — publié le 19980123

Procédé et dispositif de compression et de décompression de messages La présente invention concerne d'une manière générale la compression de données. La présente invention est plus particulièrement applicable à la compression de messages destinés à être affichés sur l'écran d'un appareil tel qu'un terminal de télécommunications, notamment un téléphone portable, ces messages étant formés de mots formés eux-mêmes de10 caractères, ces caractères étant eux-mêmes codés, pour leur stockage dans des moyens de traitement de données internes à cet appareil, selon un code binaire tel que le code ASCII par exemple. Dans une telle application, la compression de messages permet essentiellement de réduire la taille de15 mémoire nécessaire au stockage de ces messages, et donc de réduire la taille des circuits internes à un tel appareil. Diverses méthodes de compression de données sont connues et décrites par exemple dans le livre intitulé "Compression de données - Méthodes, algorithmes, programmes détaillés" (Pascal PLUME - Editions Eyrolles). Parmi ces méthodes on peut citer la méthode dite de HUFFMAN qui opère sur des caractères et qui consiste à coder sur une longueur binaire relativement courte (par rapport à un codage binaire classique tel que par exemple le codage25 ASCII) des caractères qui ont une occurrence relativement élevée, et au contraire sur une longueur binaire plus élevée des caractères qui ont une occurrence plus faible, la table de codage ainsi obtenue étant transmise au dispositif destiné à effectuer l'opération inverse de décompression.30 Une telle méthode n'est pas adaptée à la compression de messages, notamment en termes de taux de compression, compte tenu du fait que lesdits mots ou lesdits messages comportent la plupart du temps des séquences répétitives de caractères.35 Pour éviter cet inconvénient on peut utiliser une méthode telle que la méthode dite de LEMPEL-ZIV-WELCH qui 2 2751492 caractères en les remplaçant par leur rang dans une table de codage appelée dictionnaire, créée dynamiquement au fur et à mesure de la lecture du texte à compresser, et recréée de façon similaire au moment de la décompression. Une telle méthode, connue aussi sous l'expression anglo-saxonne de "on line textual substitution",présente un meilleur taux de compression que la méthode citée précédemment. Elle a cependant pour principal inconvénient de nécessiter un temps de décompression relativement long. Un besoin particulier existe donc pour la compression de messages, notamment de messages en nombre relativement important, de taille relativement courte, et utilisant un vocabulaire relativement restreint, tels que par exemple des messages destinés à être affichés sur l'écran d'un appareil15 tel qu'un terminal de télécommunications, notamment un téléphone portable, ce besoin consistant notamment en une méthode qui soit suffisamment performante en temps de décompression, tout en restant suffisamment économique en termes de taux de compression.20 La présente invention a ainsi pour objet un procédé de compression de messages, notamment de messages destinés à être affichés sur un terminal de télécommunications, notamment un téléphone portable, ce procédé étant essentiellement caractérisé en ce que, lesdits messages25 étant formés de mots formés eux-mêmes de caractères, il comporte la constitution de deux tables de codage, l'une, dite table de codage pour la compression de mots, faisant correspondre à chaque mot compressé représenté par son rang de classement dans cette table, un mot dit semi-compressé30 formé d'une séquence de caractères compresses correspondant à ce mot, et l'autre, dite table de codage pour la compression de caractères, faisant correspondre à chaque caractère compressé représenté par son rang de classement dans cette table, un caractère non compressé.35 La présente invention a également pour objet un procédé correspondant de décompression de messages, ce 3 2751492 procédé étant essentiellement caractérisé en ce qu'il comporte un adressage,respectivement par des mots compresses et des caractères compressés, de deux tables de codage, l'une, dite table de codage pour la compression de mots, 5 faisant correspondre à chaque mot compressé représenté par son rang de classement dans cette table, un mot dit semi- compressé formé d'une séquence de caractères compresses correspondant à ce mot, et l'autre, dite table de codage pour la compression de caractères, faisant correspondre à chaque caractère compressé représenté par son rang de classement dans cette table, un caractère non compressé. La présente invention a également pour objet un dispositif correspondant de décompression de messages, ce dispositif étant essentiellement caractérisé en ce qu'il15 comporte une mémoire contenant deux tables de codage, l'une, dite table de codage pour la compression de mots, faisant correspondre à chaque mot compressé représenté par son rang de classement dans cette table, un mot dit semi-compressé formé d'une séquence de caractères compresses correspondant20 à ce mot, et l'autre, dite table de codage pour la compression de caractères, faisant correspondre à chaque caractère compressé représenté par son rang de classement dans cette table, un caractère non compressé, et des moyens d'adressage de ces deux tables, respectivement par des mots25 compresses et par des caractères compresses. D'autres objets et caractéristiques de la présente invention apparaîtront à la lecture de la description suivante d'un exemple de réalisation, faite en relation avec les dessins ci-annexés dans lesquels:30 -la figure 1 est un organigramme destiné à illustrer les différentes étapes d'un exemple de réalisation d'un procédé de compression suivant l'invention, - la figure 2 est un organigramme destiné à illustrer les différentes étapes d'un exemple de réalisation d'un procédé de décompression correspondant, 4 2751492 -la figure 3 illustre schématiquement un exemple de réalisation d'un dispositif de décompression correspondant. Le procédé de compression illustré sur la figure 1 comporte des étapes, notées repectivement 1 et 2, de constitution de tables de codage appelées respectivement table de codage pour la compression de mots et table de codage pour la compression de caractères, dans lesquelles sont rangés respectivement, sous forme codée, les mots constitutifs des messages considérés, et les caractères10 constitutifs de ces mots, chaque caractère ou mot étant défini par son rang de classement dans une telle table, et ce rang de classement, une fois codé, en l'occurrence en binaire, représentant la forme compressée de ce mot ou de ce caractère.15 Une table de codage pour la compression de caractères contient en l'occurrence des caractères sous une forme non compressée, par exemple selon un code binaire tel que le code ASCII. Une table de codage pour la compression de mots contient en l'occurrence des mots sous une forme dite semicompressée, un mot semi-compressé étant constitué par une séquence de caractères compressés correspondant aux caractères successifs formant ce mot. Dans l'exemple illustré, il est en outre préalablement prévu des étapes, repectivement 3 et 4, de tri des caractères et des mots par fréquence d'apparition dans lesdits mots et dans lesdits messages, et lesdites tables de codage comportent elle-mêmes plusieurs tables appelées respectivement alphabets et dictionnaires, les caractères30 (respectivement les mots) les plus fréquemment utilisés étant destinés à être rangés dans un alphabet (respectivement un dictionnaire) de plus petite taille, c'est-à-dire dont les rangs peuvent être codés au moyen de moins de bits.35 L'étape 1 de constitution des alphabets consiste alors par exemple à ranger les 8 caractères les plus utilisés dans 2751492 un premier alphabet dont les rangs sont codés en binaire au moyen de 3 bits, et les autres caractères, par exemple au nombre de 128, dans un deuxième alphabet dont les rangs sont codés en binaire au moyen de 7 bits. L'étape 2 de constitution des dictionnaires consiste alors par exemple à ranger les 8 mots les plus utilisés dans un premier dictionnaire dont les rangs sont codés en binaire au moyen de 3 bits, les 64 mots suivants (par ordre de fréquence d'utilisation décroissante) dans un deuxième10 dictionnaire dont les rangs sont codés en binaire au moyen de 6 bits, et les autres mots, par exemple au nombre de 1024, dans un troisième dictionnaire dont les rangs sont codés en binaire au moyen de 10 bits. Le code binaire indiquant le rang dans un alphabet ou dans un dictionnaire est alors précédé d'un code destiné à indiquer duquel de ces alphabets, ou de ces dictionnaires, il s'agit.Dans l'exemple considéré, le numéro d'alphabet peut ainsi être indiqué au moyen d'un code binaire à un seul élément binaire, et le numéro de dictionnaire au moyen d'un code binaire à deux éléments binaires. En outre, les espaces séparateurs de mots dans lesdits messages sont considérés comme des mots pour la mise en oeuvre de ce procédé, ce qui permet d'optimiser le taux de compression.25 La formation d'un message compressé (étape 5) est alors obtenue en remplaçant chaque mot constitutif de ce message par le mot compressé correspondant, à savoir le code binaire du rang de ce mot dans le dictionnaire correspondant, étant entendu que le contenu dudit30 dictionnaire audit rang est lui-même formé par le mot dit semi- compressé constitué par la séquence des codes binaires des rangs, dans lesdits alphabets, des caractères constitutifs de ce mot. En outre, dans l'exemple considéré, les messages compresses étant destinés à être stockés de manière contiguë dans une mémoire prévue dans le dispositif chargé 6 2751492 d'effectuer l'opération inverse de décompression, et ces messages ayant une taille variable, il est nécessaire de prévoir un mécanisme permettant de déterminer le début et la fin de chaque message compressé dans ladite mémoire.Dans l'exemple considéré, ce mécanisme comporte une étape 6 de constitution d'une table dite table d'adresses de débuts de messages compressés, destinée à indiquer les adresses de début desdits messages compressés dans ladite mémoire. De même, les mots semi-compressés étant, dans l'exemple considéré, destinés à être stockés de manière contiguë dans cette mémoire, et la taille de ces mots semi- compressés étant variable, il est nécessaire de prévoir un mécanisme permettant de déterminer le début et la fin de chaque mot semi- compressé dans ladite mémoire.15 Par ailleurs, dans l'exemple considéré, afin d'optimiser encore le taux de compression, le procédé de compression comporte en outre une étape notée 7 de recherche d'inclusion de mots, appelés sous-mots, au sein de mots plus grands appelés mots racines.Seuls les mots racines sont20 rangés dans les dictionnaires, la numérotation des rangs dans ces dictionnaires étant alors modifiée de manière à définir également des rangs pour ces sous-mots, et ledit mécanisme permettant de déterminer le début et la fin de chaque mot semi- compressé dans ladite mémoire devant alors25 permettre de déterminer le début et la fin de chaque mot semi-compressé, qu'il s'agisse d'un mot racine ou d'un sous- mot. Dans l'exemple considéré, ce dernier mécanisme comporte une étape 8 de constitution d'une table dite table d'adresses de débuts de mots semi-compressés, destinée à indiquer les adresses de début de ces mots (qu'il s'agisse de mots racines ou de sous-mots) dans ladite mémoire, et d'une table dite table de tailles de mots semi-compressés, destinée à indiquer la taille de ces mots (qu'il s'agisse de35 mots racines ou de sous mots)dans ladite mémoire. 7 2751492 Il est en outre prévu une telle table d'adresses de débuts de mots semicompressés et une telle table de tailles de mots semi-compressés pour chacun desdits premier, deuxième, et troisième dictionnaire. En outre, dans l'exemple considéré, les étapes 3 de tri des caractères et 1 de constitution des alphabets sont avantageusement prévues après les étapes 4 (tri des mots) et 7 (recherche de sous-mots), afin de n'effectuer un tri des caractères que sur les mots racines. Un exemple de procédé de décompression correspondant est illustré sur la figure 2. Au cours d'une première étape de ce procédé, notée 10, on lit la table d'adresses de débuts de messages compressés à une adresse déterminée à partir d'une information (supposée fournie) identifiant le message à décompresser, ainsi qu'à une adresse correspondant au message compressé situé de manière contiguë en mémoire. Au cours d'une deuxième étape, notée 11, on lit, à l'adresse de début de message compressé ainsi obtenue, le mot compressé correspondant au premier mot du message à décompresser. Le résultat de cette nouvelle lecture permet, au cours d'une troisième étape, notée 12, d'adresser d'une part la table d'adresses de débuts de mots semi-compressés, pour25 obtenir l'adresse de début du mot semi-compressé correspondant au premier mot du message à décompresser, et d'autre part la table de tailles de mots semi-compressés, pour obtenir la taille de ce mot semi-compressé. L'obtention de l'adresse de début de ce mot semi- compressé permet ainsi, au cours d'une quatrième étape, notée 13, d'adresser le dictionnaire correspondant, et d'obtenir ainsi le premier caractère compressé constitutif de ce mot. La lecture de ce premier caractère compressé permet à son tour, au cours d'une cinquième étape, notée 14, d'adresser l'alphabet correspondant, et d'obtenir ainsi le 8 2751492 premier caractère non compressé correspondant, qui peut alors être transmis vers un registre destiné à stocker le message décompressé à afficher (étape 15). L'adresse courante est alors remplacée par l'adresse du caractère compressé suivant du mot semi- compressé considéré, et tant que cette adresse courante reste inférieure à la somme de l'adresse de début du mot semi- compressé considéré et de la taille de ce mot semi-compressé (ce qui correspond à l'étape de test notée 16), ce procédé de lecture des caractères non compresses constitutifs du mot considéré se poursuit, les caractères non compressés ainsi obtenus étant transmis vers ledit registre destiné à stocker le message décompressé à afficher. Lorsque l'adresse courante devient supérieure à la somme de l'adresse de début du mot semi-compressé considéré et de la taille de ce mot semi-compressé, on passe au mot semi-compressé suivant, et ainsi de suite tant que l'adresse à l'intérieur de la zone des messages compresses reste inférieure à l'adresse de début du message compressé stocké de manière contiguë en mémoire (ce qui correspond à l'étape de test notée 17). Dans cette description, il a été supposé qu'à chaque adresse considérée de la mémoire était stocké le nombre exact d'éléments binaires correspondant à l'information25 recherchée (qu'il s'agisse d'une adresse de début de message compressé, d'un mot compressé, d'une adresse de début de mot semi-compressé, d'une taille de mot semi-compressé, d'un caractère non compressé, ou d'un caractère compressé).Les adaptations à apporter, le cas échéant, relèveraient30 cependant simplement des techniques, classiques pour l'homme du métier, et donc non redécrites ici, d'organisation et d'adressage d'une mémoire. La figure 3 illustre schématiquement un dispositif de décompression correspondant. 9 2751492 Ce dispositif comporte une mémoire notée 20 comportant, dans l'exemple considéré, les zones de données suivantes: -Tl:Table d'adresses de débuts de messages compressés -T2:Table d'adresses de débuts de mots semi-compressés du premier dictionnaire -T3:Table d'adresses de débuts de mots semi-compressés du deuxième dictionnaire - T4:Table d'adresses de débuts de mots semi-compressés du troisième dictionnaire -T5:Table de tailles de mots semi-compressés du premier dictionnaire -T6:Table de tailles de mots semi-compressés du deuxième dictionnaire -T7:Table de tailles de mots semi- compressés du troisième dictionnaire -T8:premier alphabet -T9:deuxième alphabet -TlO:zone de messages compressés -Tll:premier dictionnaire -T12:deuxième dictionnaire -T13:troisième dictionnaire. Ce dispositif comporte en outre des moyens, 21, d'adressage de cette mémoire, ces moyens recevant une information d'entrée, notée I, permettant d'identifier le message à décompresser, et ces moyens générant, à partir de cette information d'entrée,les différentes adresses nécessaires au déroulement du procédé de décompression tel que décrit plus haut.30 Ce dispositif comporte en outre un registre, 22,destiné à stocker le message décompressé à afficher, noté M, avant transmission à un dispositif d'affichage(non illustré). L'ensemble formé par les éléments 20, 21, 22 peut étre inclus dans un ensemble plus général de traitement de données, notamment un microprocesseur, inclus lui- même dans 2751492 l'appareil considéré, tel que notamment un terminal de télécommunications, notamment un téléphone portable. 11 2751492 REVENDICATIONS 1 Procédé de compression de messages, notamment de messages destinés à être affichés sur un terminal de télécommunications, notamment un téléphone portable, 5 caractérisé en ce que, lesdits messages étant formés de mots formés eux-mêmes de caractères, il comporte la constitution (1, 2) de deux tables de codage, l'une, dite table de codage pour la compression de mots, faisant correspondre à chaque mot compressé représenté par son rang de classement dans cette table, un mot dit semi-compressé formé d'une séquence de caractères compressés correspondant à ce mot, et l'autre, dite table de codage pour la compression de caractères, faisant correspondre à chaque caractère compressé représenté par son rang de classement dans cette table, un caractère15 non compressé. 2 Procédé selon la revendication 1, caractérisé en ce que, ladite table pour la compression de mots comporte elle- même au moins deux tables appelées dictionnaires ayant chacune des capacités de stockage différentes, et en ce20 qu'il comporte en outre un tri (4) des mots constitutifs desdits messages par fréquence d'apparition dans lesdits mots, les mots apparaissant le plus fréquemment étant destinés à être rangés dans un dictionnaire de plus faible capacité.25 3 Procédé selon l'une des revendications 1 et 2, caractérisé en ce que, ladite table pour la compression de caractères comporte elle-même deux tables appelées alphabets, ayant chacune des capacités de stockage différentes, et en ce qu'il comporte en outre un tri (3) des30 caractères constitutifs desdits mots par fréquence d'apparition dans lesdits mots, les caractères apparaissant le plus fréquemment étant destinés à être rangés dans un alphabet de plus faible capacité. 4 Procédé selon l'une des revendications 1 à 3, caractérisé en ce que les espaces séparateurs de mots dans 12 2751492 lesdits messages sont considérés comme des mots pour la mise en oeuvre de ce procédé. Procédé selon l'une des revendications 1 à 4, caractérisé en ce que les messages compressés étant destinés à être stockés de manière contiguë dans une mémoire, et ayant en outre une taille variable, il comporte en outre la constitution (6) d'une table d'adresses de début de messages compressés, destinée à indiquer les adresses de début desdits messages compressés dans ladite mémoire.10 6 Procédé selon l'une des revendications 1 à 5, caractérisé en ce qu'il comporte en outre une recherche (7) de mots, appelés sous-mots, inclus dans des mots plus longs appelés mots racines,et en ce que, seuls les mots racines étant rangés dans ladite table de codage pour la compression de mots, et des rangs de classement dans cette table étant également définis pour ces sous-mots, il est en outre prévu la constitution (8) d'une table d'adresses de début de mots semi-compressés et d'une table de tailles de mots semi- compressés, destinées respectivement à indiquer, pour chaque20 rang de classement dans ladite table de codage, l'adresse de début, et la taille, du mot semi-compressé correspondant, qu'il s'agisse d'un mot racine ou d'un sous-mot. 7 Procédé de décompression de messages, notamment de messages destinés à être affichés sur un terminal de télécommunications, notamment un téléphone portable, caractérisé en ce que, lesdits messages étant formés de mots formés eux- mêmes de caractères, il comporte un adressage (13, 14),respectivement par des mots compressés et par des caractères compresses, de deux tables de codage, l'une, dite table de codage pour la compression de mots, faisant correspondre à chaque mot compressé représenté par son rang de classement dans cette table, un mot dit semi-compressé formé d'une séquence de caractères compressés correpondant à ce mot, et l'autre, dite table de codage pour la compression35 de caractères, faisant correspondre à chaque caractère 13 2751492 compressé représenté par son rang de classement dans cette table, un caractère non compressé. 8 Procédé selon la revendication 7, caractérisé en ce que les messages compressés étant stockés de manière contiguë dans une mémoire, et ayant en outre une taille variable, il comporte en outre un adressage (10) d'une table d'adresses de début de messages compresses, destinée à indiquer les adresses de début desdits messages compresses dans ladite mémoire.10 9 Procédé selon l'une des revendications 7 et 8, caractérisé en ce que, seuls des mots dits mots-racines incluant d'autres mots plus courts appelés sous-mots étant rangés dans ladite table de codage pour la compression de mots, et des rangs de classement dans cette table étant15 également définis pour ces sous-mots, il comporte en outre un adressage d'une table d'adresses de débuts de mots semi- compressés et d'une table de tailles de mots semi- compressés, destinées respectivement à indiquer, pour chaque rang de classement dans ladite table de codage, l'adresse de20 début, et la taille, du mot semi-compressé correspondant, qu'il s'agisse d'un mot racine ou d'un sous-mot. Dispositif de décompression de messages, notamment de messages destinés à être affichés sur un terminal de télécommunications, notamment un téléphone portable,25 caractérisé en ce que, lesdits messages étant formés de mots formés eux-mêmes de caractères, il comporte une mémoire (20) contenant deux tables de codage, l'une (T12, T13), dite table de codage pour la compression de mots, faisant correspondre à chaque mot compressé représenté par son rang de classement dans cette table, un mot dit semi-compressé formé d'une séquence de caractères compressés correspondant à ce mot, et l'autre (T8, T9), dite table de codage pour la compression de caractères, faisant correspondre à chaque caractère compressé représenté par son rang de classement dans cette35 table, un caractère non compressé, et des moyens (21) 14 2751492 d'adressage de ces deux tables, respectivement par des mots compressés et par des caractères compresses. 11 Dispositif selon la revendication 10, caractérisé en ce que les messages compressés étant stockés de manière contiguë dans ladite mémoire (20), et ayant en outre une taille variable, ladite mémoire comporte en outre une table (Tl) d'adresses de début de messages compresses, destinée à indiquer les adresses de début desdits messages compresses dans cette mémoire, et en ce que ce dispositif comporte en10 outre des moyens (21) d'adressage de cette table d'adresses de débuts de messages compresses. 12 Dispositif selon l'une des revendications 10 et 11, caractérisé en ce que, seuls des mots dits mots- racines incluant d'autres mots plus courts appelés sous-mots étant rangés dans ladite table de codage pour la compression de mots, et des rangs de classement dans cette table étant également définis pour ces sous-mots, ladite mémoire (20) comporte en outre une table (T2, T3, T4)d'adresses de débuts de mots semi-compressés et une table (T5, T6, T7) de tailles20 de mots semi-compressés, destinées respectivement à indiquer, pour chaque rang de classement dans ladite table de codage, l'adresse de début, et la taille, du mot semi- compressé correspondant, qu'il s'agisse d'un mot racine ou d'un sous-mot, et en ce que ce dispositif comporte en outre25 des moyens (21) pour réaliser un adressage de cette table d'adresses de débuts de mots semi-compressés et de cette table de tailles de mots semi-compressés.