Brevet FR3053858A1 — publié le 20180112

Procédé d'encodage de données d'un histogramme La présente invention concerne un procédé d'encodage de données d'un histogramme, l'histogramme étant un tableau comportant des couples chacun formé d'un indice entier associé à une valeur, le procédé comportant les étapes de codage d'un message binaire comportant des représentations binaires des valeurs, et de compression du message binaire par un algorithme de compression. Dans le domaine du traitement informatique de données, il est fréquent de s'appuyer sur un histogramme comme mode de représentation des données. Un histogramme est alors un tableau de données comportant des couples chacun formé d'un indice entier associé à une valeur. Un histogramme sert à effectuer des regroupements entre les valeurs, typiquement avec une échelle linéaire ou logarithmique, afin de gagner en espace et de pouvoir dégager des distributions. Les données représentées par un histogramme sont typiquement des données provenant d'un système de mesure. L'histogramme a donc potentiellement besoin d'être véhiculé à travers un réseau depuis le système de mesure vers un système de stockage, afin d'y être stocké par la suite. Pour cela une solution consiste à véhiculer une représentation binaire de l'histogramme. Afin de minimiser l'espace nécessaire au stockage et la bande passante nécessaire sur le réseau, la taille de la représentation binaire de l'histogramme doit être minimisée. Il convient également de minimiser les ressources nécessaires à la conversion de l'histogramme vers sa représentation binaire et celles nécessaires à la conversion de la représentation binaire de l'histogramme vers l'histogramme. Dans l'état de la technique, une solution consiste à appliquer un algorithme de compression GZip sur une représentation binaire de l'histogramme. Néanmoins, cette solution ne donne pas entièrement satisfaction et le fichier obtenu s'avère de taille relativement importante. Un but de l'invention est donc de proposer un procédé d'encodage de données d'un histogramme minimisant les ressources et la taille du fichier obtenu. A cet effet l'invention a pour objet un procédé d'encodage de données d'un histogramme du type précité, caractérisé en ce que le codage du message binaire comprend le codage de chaque valeur par une représentation binaire avec un nombre de bits variable en fonction de la valeur codée ; et en ce que la compression n'est réalisée que si la taille du message binaire est supérieure à une taille prédéterminée. Suivant des modes particuliers de réalisation, le procédé d'encodage de données d'un histogramme comporte l'une ou plusieurs des caractéristiques suivantes : 3053858 2 - seules les valeurs dont les indices associés sont compris entre l'indice de la première valeur non nulle et l'indice de la dernière valeur non nulle de l'histogramme sont codées. - le procédé comporte une étape où l'indice de la première valeur non nulle est 5 codé en représentation binaire et ajouté dans le message binaire, la représentation binaire de l'indice de la première valeur non nulle présentant un nombre de bits variable en fonction de l'indice codé. - le procédé comporte une étape de codage dans le message binaire d'une information représentative du nombre de valeurs codées, l'information étant codée en 10 représentation binaire, la représentation binaire présentant un nombre de bits variable en fonction de l'information codée. - l'information représentative du nombre de valeurs codées est choisie dans le groupe consistant en l'indice de la dernière valeur non nulle, et le nombre de valeurs de l'histogramme dont les indices sont compris entre l'indice de la première valeur non nulle 15 et l'indice de la dernière valeur non nulle de l'histogramme. - le procédé comporte une étape de codage d'une information, dans le message binaire, indiquant si le message binaire a été compressé ou non à l'étape de compression. - l'algorithme de compression utilisé à l'étape de compression est l'algorithme 20 GZip. - le codage, à l'étape de codage du message binaire, est mis en oeuvre par une librairie choisie dans le groupe comportant MsgPack, Protobuf, et Boopickle. - le procédé comporte une étape d'ajout d'informations de décodage dans le message binaire. 25 - les représentations binaires des valeurs sont les écritures en base 2 de ces valeurs. - les représentations binaires ne sont constituées que des octets nécessaires à représenter les valeurs codées. - le procédé comporte le décodage du message binaire. 30 L'invention concerne aussi une installation d'encodage de données d'un histogramme caractérisée en ce qu'elle comporte des moyens de mise en oeuvre du procédé décrit plus haut. L'invention sera mieux comprise à la lecture de la description qui va suivre, donnée à titre d'exemple et faite en se référant aux dessins annexés, sur lesquels : 35 - la figure 1 est une vue schématique d'une installation de recueil et d'exploitation de données mettant en oeuvre des histogrammes ; 3053858 3 - la figure 2 est un organigramme général d'un procédé d'encodage de données d'un histogramme selon l'invention, et ; - la figure 3 est un organigramme d'un exemple de procédé de décodage d'un histogramme codé selon le procédé d'encodage de l'invention. 5 Sur la figure 1, est illustré un dispositif propre à mettre en oeuvre le procédé d'encodage de données d'un histogramme selon l'invention. L'installation illustrée sur la figure 1 comporte un système de mesure, tel qu'un serveur 10 propre à répondre à des requêtes et propre à recueillir, à transmettre et à analyser les temps de traitement des requêtes faites auprès de ce serveur et les temps de 10 réponse. L'installation comporte ainsi une première unité de traitement 11 reliée au serveur 10 et propre, pour chaque requête, à recueillir et à mémoriser le temps de traitement et de réponse. Cette unité 11 est reliée à une entité réceptrice 12 au travers du réseau internet 13. L'unité 11 est propre à former des histogrammes. Ces histogrammes comprennent 15 des classes correspondant à des intervalles de temps de réponse à une requête, la valeur de chaque classe étant égale au nombre de requêtes dont le temps de réponse est dans l'intervalle correspondant, pour une durée de fonctionnement déterminée du serveur. L'unité 11 est propre à compresser l'histogramme ainsi formé et à le transmettre à l'entité 12 qui est propre à les décompresser et à assurer l'analyse des histogrammes 20 reçus pour en déduire l'état de fonctionnement du serveur 10. La première unité de traitement 11 comporte un processeur 14, une mémoire 16 comportant un programme 17 apte à mettre en oeuvre le procédé, un système de stockage 18 et une interface graphique 20. En variante, la première unité de traitement 11 ne comporte pas d'interface graphique. 25 Le processeur 14 de la première unité de traitement 11 est configuré pour recevoir les données du serveur 10 et notamment le temps de réponse pour chaque requête reçue par le serveur. Le programme 17 est apte à agencer les données sous la forme d'un histogramme H, un histogramme étant un tableau de données comportant des couples, chacun formé d'un indice entier associé à une valeur, par exemple, entière. 30 Par exemple, si les classes correspondent à des intervalles de temps de 10 ms, et qu'aucune réponse à une requête n'est obtenue en moins de 30 ms, 323 réponses étant obtenues entre 30 et 40 ms, 728 réponses étant obtenues entre 50 et 60 ms, l'histogramme créé prend la forme suivante (1,0) (2,0) (3,0) (4,323) (5,728), (6,137). Une fois l'histogramme H construit, l'utilisateur est en mesure d'utiliser 35 l'histogramme H afin d'effectuer toute opération du choix de l'utilisateur. L'usage final des 3053858 4 données par l'utilisateur est, par exemple, le regroupement des valeurs suivant une échelle, typiquement linéaire ou logarithmique. L'interface graphique 20 et le processeur 14 de la première unité de traitement 11 permettent à l'utilisateur de mettre en oeuvre l'opération choisie. 5 La première unité de traitement 11, par l'intermédiaire de son processeur 14 et du programme 17, est configurée pour créer l'histogramme H et assurer le codage de l'histogramme H en un message binaire compressé B. Le programme 17 est apte à mettre en oeuvre le codage et la compression. L'entité réceptrice 12 comporte une deuxième unité de traitement 24. L'unité de 10 traitement 24 comprend un processeur 26, une mémoire 28 comportant un programme 29 apte à mettre en oeuvre le décodage, un système de stockage 30 et une interface graphique 32. En variante, la deuxième unité de traitement 24 ne comporte pas d'interface graphique. Le message binaire B envoyé par la première unité de traitement 11 est alors, par 15 exemple, stocké dans le système de stockage 30 de la deuxième unité de traitement 24. La deuxième unité de traitement 24 est configurée pour réaliser le décodage du message binaire B pour reconstruire l'histogramme H. Le programme 29 est apte à mettre en oeuvre le décodage. Une fois l'histogramme H reconstruit, l'utilisateur est en mesure d'utiliser 20 l'histogramme H afin d'effectuer toute opération du choix de l'utilisateur. L'interface graphique 32 et le processeur 26 de la deuxième unité de traitement 24 permettent à l'utilisateur de mettre en oeuvre l'opération choisie. Le procédé d'encodage des données d'un histogramme H selon l'invention va maintenant être décrit en regard des figures 2 et 3. 25 Au cours de cette description, un exemple illustrant le procédé d'encodage selon l'invention est détaillé. Le procédé d'encodage comporte une première phase 100 de codage et transmission d'un message binaire B représentant un histogramme H, illustrée sur la figure 2, et une deuxième phase 102 de décodage du message binaire B en 30 l'histogramme H, illustrée sur la figure 3. La première phase 100 du procédé comprend avantageusement une construction d'un histogramme H, un codage du message binaire B à partir de l'histogramme H et un envoi du message binaire B. De manière générale, le programme 17 de la première unité de traitement 11 met 35 en oeuvre les étapes de la première phase 100. 3053858 5 La première phase 100 du procédé comporte d'abord une première étape 110 de construction de l'histogramme H. Le serveur 10 collecte et envoie les données à la première unité de traitement 11. Le programme 17 agence les données sous la forme de l'histogramme H. 5 La première phase 100 du procédé comporte ensuite une étape 112 de concaténation des valeurs de l'histogramme H dans une liste de concaténation. L'histogramme H comporte typiquement une première valeur non nulle et une dernière valeur non nulle. Afin de réduire la taille de la liste de concaténation, seules les valeurs comprises entre la première valeur non nulle incluse dans l'histogramme et la 10 dernière valeur non nulle incluse sont concaténées et forment les éléments de la liste de concaténation. Dans la liste de concaténation, les valeurs sont ordonnées suivant un ordre prédéterminé. Par exemple, les valeurs sont ordonnées par indice croissant de la gauche vers la droite. 15 A titre d'exemple détaillé, si l'histogramme comporte les couples [(1, 0), (2,0), (3,0), (4,5634), (5,7), (6, 257), (7,0)]. La liste de concaténation associée à l'étape 112 pour cet histogramme est (5634, 7, 257). Le choix a été fait d'ordonner les valeurs par ordre d'indice croissant, de la gauche vers la droite. Au cours d'une étape 114 d'ajout d'informations caractérisant l'histogramme, 20 l'indice de la première valeur non nulle de l'histogramme H est ajouté à la liste de concaténation. Cet indice, égal à 4 dans l'exemple, est, par exemple, ajouté au début de la liste de concaténation. Avantageusement, cette étape 114 comporte l'ajout, à la liste de concaténation, d'une information permettant de déterminer le nombre de valeurs concaténée à l'étape 25 112. Une telle information est, par exemple, l'indice de la dernière valeur non nulle, ici égal à 6, ou le nombre de valeurs de l'histogramme H dont les indices sont compris entre l'indice de la première valeur non nulle et l'indice de la dernière valeur non nulle, qui est ici égal à 3. Par exemple, cette information est ajoutée à la liste de concaténation 30 immédiatement après l'indice de la première valeur non nulle. Concernant l'exemple détaillé, à l'étape 114, la liste de concaténation de l'histogramme de l'exemple précédent est (4, 6, 5634, 7, 257). Le choix a été fait d'ajouter l'indice de la première valeur non nulle au début de la liste de concaténation, et d'ajouter l'indice de la dernière valeur non nulle. 35 Chacune de ces valeurs sont alors codées en binaire avec un codage dont le nombre de bits dépend de la valeur. 3053858 6 Une représentation binaire d'un nombre en format simple précision, respectivement double précision, est usuellement codée en base 2 et sur quatre octets, respectivement sur huit octets, ceci correspondant à une représentation binaire standard pour le nombre simple précision, respectivement double précision. Ces quatre octets, 5 respectivement huit octets, définissent une plage de valeurs à laquelle appartient le nombre. Néanmoins, les nombres ne nécessitent pas tous quatre octets en simple précision ou huit octets en double précision pour être écrits en base 2, leurs écritures sur ces octets comportent donc éventuellement des octets excédentaires vides. On définit ainsi, la représentation binaire minimale d'un nombre comme la 10 représentation binaire, en base 2 de ce nombre, comportant : un nombre prédéfini de bits d'entête décrivant la plage de valeur à laquelle appartient le nombre ; le nombre associé à la représentation binaire codé sur un nombre minimal d'octets, c'est-à-dire sur uniquement les octets nécessaires à son écriture en 15 base 2, typiquement sans octet excédentaire vide en début de représentation binaire standard pour le nombre simple ou double précision. Par la suite, pour des raisons de clarté, les représentations binaires dans l'exemple détaillé ne comprendront pas les bits d'entête décrivant la plage de valeur à laquelle appartient chaque nombre codé. 20 Au cours d'une étape 116, la liste de concaténation est codée en un message binaire B comportant seulement les représentations binaires minimales des valeurs de la liste de concaténation. L'étape 116 est mise en oeuvre par toute librairie adaptée et, par exemple, par les librairies MsgPack, Protobuf, et Boopickle. Lors de cette étape, il est plus pertinent de 25 choisir une librairie qui favorise les nombres positifs comme le fait Boopickle. Concernant l'exemple détaillé, au cours de l'étape 116, la liste de concaténation est codée en un message binaire dans lequel chaque nombre est écrit en présentation binaire minimale. La liste de concaténation correspond à [00000100 1 00000110 1 00010110 00000010 1 00000111 1 00000001 00000001], pour des raisons de clarté le 30 caractère « 1 » sépare ici et dans la suite les représentations binaires associées à des nombres codés différents. Etant donné que les représentations binaires minimales comportent des nombres d'octets variables, le message binaire comporte avantageusement des informations concernant le nombre d'éléments de la liste de concaténation et le nombre d'octets 35 constituants chaque représentation binaire minimale de ces éléments. 3053858 7 Afin de permettre le décodage du message binaire, la première phase 100 du procédé comporte ainsi une étape 118 d'ajout d'informations de décodage. Au cours de l'étape 118, le nombre d'éléments de la liste de concaténation et les nombres d'octets constituant chaque représentation binaire minimale de ces éléments 5 sont codés et ajoutés au message binaire B. Le nombre d'éléments est, par exemple, codé sur quatre octets suivant sa représentation binaire en base 2. Les nombres d'octets constituant chaque représentation binaire minimale sont, par exemple, codés sur un octet suivant leurs représentations binaires en base deux. 10 Ces nombres, une fois codés, sont ajoutés par exemple au début du message binaire. Concernant l'exemple détaillé, à l'étape 118, le nombre d'éléments, c'est-à-dire ici 5, est codé sur quatre octets suivant sa représentation binaire en base 2 ; les nombres d'octets sont codés sur un octet suivant leurs représentations binaires en base 2. 15 Le message binaire précédent est donc [00000000 00000000 00000000 00000101 00000001 00000001 00000010 00000001 00000010 00000100 00000110 00010110 00000010100000111 1 00000001 00000001]. A une étape 119, un test est effectué sur la taille du message binaire. Celle-ci est comparée à une référence R. 20 Si le message binaire B présente une taille supérieure à la taille de référence R, une étape 120A de compression du message binaire B est mise en oeuvre. La compression du message binaire B à l'étape 120A est mise en oeuvre par tout algorithme de compression adapté. Par exemple, la compression est mise en oeuvre par l'algorithme GZip. L'algorithme GZip est bien connu dans l'état de la technique et ne sera 25 pas décrit plus en détail. Dans tous les cas, une étape 120B de codage d'une information permettant de savoir si la compression a été réalisée est ensuite mise en oeuvre. L'information est codée en représentation binaire et ajoutée au message binaire B, par exemple, au début du message binaire B. 30 Cette information, une fois codée, est par exemple un unique bit valant 1 si la compression a été réalisée ou 0 si la compression n'a pas été réalisée. Concernant l'exemple détaillé, si, au cours de l'étape 119, le message binaire actuel ne présente pas une taille suffisante pour appliquer l'algorithme de compression, l'étape 120A n'est pas réalisée et le programme ajoute au message binaire, à l'étape 35 120B, l'information explicitant que la compression n'a pas été réalisée, ici cette information est, par exemple, le bit 0. Le message binaire précédent est alors [0 3053858 8 00000000 00000000 00000000 00000101 100000001 100000001 1 00000010 100000001 1 00000010 1 00000100 1 00000110 1 00010110 00000010 1 00000111 1 00000001 00000001]. La première phase 100 du procédé comporte enfin, avantageusement, une étape 5 122 de transmission du message binaire B. Au cours de cette étape 122, la première unité de traitement 11 envoie le message binaire B sur le réseau 13 vers l'entité réceptrice 12. L'entité réceptrice 12 communique le message binaire B à la deuxième unité de traitement 24. Le message binaire B est alors, par exemple, stocké dans le système de stockage 10 30 de la deuxième unité de traitement 24. Le procédé d'encodage des données d'un histogramme selon l'invention comporte une deuxième phase 102 de décodage illustrée à la figure 3. La deuxième phase 102 comprend le décodage du message binaire B et la reconstruction de l'histogramme H. 15 Le programme 29 de la deuxième unité de traitement 24 met en oeuvre les étapes de la première phase 102. La deuxième phase 102 comporte tout d'abord une étape 140 de lecture de l'information permettant de savoir si la compression à l'étape 120A a été réalisée, au cours de laquelle cette information est décodée et lue. 20 Un test sur cette information est effectué à l'étape 141. Si un algorithme de compression a bien été appliqué à l'étape 120 sur le message binaire B, l'algorithme de décompression associé est appliqué sur le message binaire B à l'étape 142. Si aucun algorithme de compression n'a été appliqué à l'étape 120A, aucune opération n'est alors appliquée sur le message binaire. 25 Une étape 143 de récupération des informations de décodage est ensuite avantageusement mise en oeuvre. Tout d'abord, l'information du nombre d'éléments de la liste de concaténation est décodée et lu. Cette information permet au programme 29 de récupérer et de décoder l'information des nombres d'octets constituant chaque représentation binaire minimale 30 des éléments de la liste de concaténation. A partir des informations récupérées à l'étape 143, le programme 29, au cours d'une étape 144 de décodage, alloue chaque octet du message binaire B à un élément de la liste de concaténation et détermine les représentations binaires minimales de chaque élément de cette liste. 3053858 9 Les représentations binaires minimales sont ensuite décodées. Plus précisément, le programme 29 écrit en base décimale chaque élément, à partir des représentations binaires minimales, et construit la liste de concaténation. La deuxième phase 102 comporte ensuite une étape 146 de reconstruction de 5 l'histogramme H, au cours de laquelle le programme 29 récupère, depuis la liste de concaténation, l'indice de la première valeur non nulle. L'histogramme H est ensuite reconstruit en formant les couples de l'histogramme H. Ces couples sont formés d'indice entier associé à une valeur de la liste de concaténation. 10 Plus précisément, les couples dont les indices sont strictement inférieurs à l'indice de la première valeur non nulle sont reconstruits tout d'abord. Pour cela, le programme 29 leur associe une valeur nulle. Etant donné que la liste de concaténation est ordonnée, le programme 29 reconstruit les couples dont les indices sont compris entre, l'indice de la première valeur 15 non nulle et l'indice de la dernière valeur non nulle, en suivant l'ordre prédéterminé de la liste de concaténation. En option, le programme 29 construit des couples dont l'indice est strictement supérieur à l'indice de la dernière valeur non nulle. Pour cela, le programme 29 leur associe une valeur nulle. 20 Une fois l'histogramme H reconstruit, l'utilisateur est de nouveau en mesure d'utiliser l'histogramme H afin d'effectuer toute opération du choix de l'utilisateur. En variante, la première phase 100 ne comporte pas l'étape 110. La première unité de traitement 11 reçoit alors des données déjà agencées sous forme d'histogramme. 25 En variante, la première unité de traitement 11 est apte à réaliser le décodage du message binaire B à la place de la deuxième unité de traitement 24. Dans une telle variante, au cours de l'étape 122, le message binaire B est stocké dans le système de stockage 18 de la première unité de traitement 11 au lieu d'être envoyé vers l'entité réceptrice 12. La deuxième phase 102 de décodage est ensuite mise en oeuvre par le 30 programme 17 comme décrit précédemment. On comprend que le procédé d'encodage décrit ci-dessus permet d'obtenir un message binaire de petite taille. De plus un tel procédé permet d'optimiser les ressources qui lui sont nécessaires. Par exemple, la compression des données est ainsi réalisée en fonction de la taille du 35 message. REVENDICATIONS1.- Procédé d'encodage de données d'un histogramme, l'histogramme étant un tableau comportant des couples chacun formé d'un indice entier associé à une valeur, le procédé comportant les étapes suivantes : - codage (116) d'un message binaire comportant des représentations binaires des valeurs, et - compression (120A) du message binaire par un algorithme de compression, caractérisé en ce que le codage du message binaire comprend le codage de chaque valeur par une représentation binaire avec un nombre de bits variable en fonction de la valeur codée ; et en ce que la compression (120A) n'est réalisée que si la taille du message binaire est supérieure à une taille prédéterminée. 2.- Procédé d'encodage selon la revendication 1, dans lequel seules les valeurs dont les indices associés sont compris entre l'indice de la première valeur non nulle et l'indice de la dernière valeur non nulle de l'histogramme sont codées. 3.- Procédé d'encodage selon la revendication 1 ou 2, comportant une étape (114) où l'indice de la première valeur non nulle est codé en représentation binaire et ajouté dans le message binaire, la représentation binaire de l'indice de la première valeur non nulle présentant un nombre de bits variable en fonction de l'indice codé. 4.- Procédé d'encodage selon l'une quelconque des revendications précédentes, comportant une étape (114) de codage dans le message binaire d'une information représentative du nombre de valeurs codées, l'information étant codée en représentation binaire, la représentation binaire présentant un nombre de bits variable en fonction de l'information codée. 5.- Procédé d'encodage selon la revendication 4, dans lequel l'information représentative du nombre de valeurs codées est choisie dans le groupe consistant en l'indice de la dernière valeur non nulle, et le nombre de valeurs de l'histogramme dont les indices sont compris entre l'indice de la première valeur non nulle et l'indice de la dernière valeur non nulle de l'histogramme. 3053858 11 6.- Procédé d'encodage selon l'une quelconque des revendications précédentes, comprenant une étape (120B) de codage d'une information, dans le message binaire, indiquant si le message binaire a été compressé ou non à l'étape (120A) de compression. 5 7.- Procédé d'encodage selon l'une quelconque des revendications précédentes, dans lequel l'algorithme de compression utilisé à l'étape de compression (120A) est l'algorithme GZip. 8.- Procédé d'encodage selon l'une quelconque des revendications précédentes, 10 dans lequel le codage, à l'étape (116) de codage du message binaire, est mis en oeuvre par une librairie choisie dans le groupe comportant Msg Pack, Protobuf, et Boopickle. 9.- Procédé d'encodage selon l'une quelconque des revendications précédentes, comportant une étape (118) d'ajout d'informations de décodage dans le message binaire. 15 10.- Procédé d'encodage selon l'une quelconque des revendications précédentes, dans lequel les représentations binaires des valeurs sont les écritures en base 2 de ces valeurs. 20 11.- Procédé d'encodage selon l'une quelconque des revendications précédentes, caractérisé en ce que les représentations binaires ne sont constituées que des octets nécessaires à représenter les valeurs codées. 12.- Procédé d'encodage selon l'une quelconque des revendications précédentes, 25 comportant le décodage (102) du message binaire. 13.- Installation d'encodage de données d'un histogramme, caractérisé en ce qu'elle comporte des moyens de mise en oeuvre du procédé selon l'une quelconque des revendications précédentes. 30