Discussion :

[progfou]

Bonjour tout le monde,

Un titre obscur, mais je ne sais pas comment décrire mon problème...
Dans l'idée, j'ai un message (un paquet IP, par exemple) qui transporte une série d'informations.
J'ai un échange entre deux systèmes, et en gros :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
serveur
Envoi un numéro de trame absolu (32 bits)
client
numéro de la dernière trame reçue (32 bits)
20 derniers numéros relatifs (8bits, par exemple)

Dans l'idée, en imaginant que le client recoive les trames 0,1,100,110, il renverra :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

110,10,99,1

Cet algorithme est très simple et permet de reconstruire la série de numéros.
Mais existe-t-il des algorithmes plus efficaces (en taille de données, par exemple) ?
Si je peux transporter 30 numéros au lieu de 20 par exemple, dans la même taille de trame, ça m'intéresse. L'essentiel c'est de ne pas avoir une usine à gaz.

Merci !

[Graffito]

Bonjour,

La méthode de compactage usuelle pour un entier n qui est généralement petit mais qui exceptionnelement peut prendre des valeurs plus grande consiste à utiliser une taille variable.

Par exemple, on pourra reserver le bit de poids fort des octets pour indiquer si n est codé sur "un octet de plus".

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
Ainsi si n<128, 1 Octet = { n }
Sinon si n<128x128, 2 octets = { 80 or (n and 7F), (n shl 7) and 7F } 
Sinon si n<128x128x128 3 octets = { 80 or (n and 7F),80 or ((n shl 7) and 7FF), (n shl 14) and 7F}

Dans ton cas, si les séquences sont respectées dans la très grande majorité des cas (c'est à dire si la trame n+1 suit la trame n), on peut peut-être mettre un entier de 32 bits devant la série. Chaque bit B[n] correspondra à un élément de la séquence et indiquera si le codage est implicite (le numéro de la trame est égale à Trame[n]-1 et il n'est pas codé dans la série) ou implicite (le numéro de trame est codé dans la série).

[progfou]

Dans ton cas, si les séquences sont respectées dans la très grande majorité des cas (c'est à dire si la trame n+1 suit la trame n), on peut peut-être mettre un entier de 32 bits devant la série. Chaque bit B[n] correspondra à un élément de la séquence et indiquera si le codage est implicite (le numéro de la trame est égale à Trame[n]-1 et il n'est pas codé dans la série) ou implicite (le numéro de trame est codé dans la série).

OK, dans l'idée je comprends, mais je ne vois pas bien ce qu'est B[n] ?
En imaginant une suite comme celle-ci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

0-1-2-3-4-7-8-9

Comment codes-tu cela dans ton exemple ?

[souviron34]

je ne comprend pas tout à fait tout, mais pour transporter plus plus efficacement tu as les algos de compression, dont le plus "bête" est d'utiliser juste le bon nombre de bits : transporter 1 demande 1 bit.. etc..

[Grilled ]

[forthx]

je ne comprend pas tout à fait tout, mais pour transporter plus plus efficacement tu as les algos de compression, dont le plus "bête" est d'utiliser juste le bon nombre de bits : transporter 1 demande 1 bit.. etc..

Mais si tu code des valeurs a bits variable, il faut pouvoir determiner quel bit appartien a quel valeur. En general on utilise en plus une table de correspondance (dictionaire). Ca devien efficace pour recoder (compresser) des informations ayant un peu de volume et codées en taille fixe. Sur 32 bits par exemple, la solution proposé par Graffito a l'air plus adapté. L'ideal etant sans doute de voir statistiquement le nombre de bits utilisé dans la majoritée des cas et s'en servire comme taille de base. (ex: si 90% des valeures ne depassent pas 8 bit on utilisera un bloc de 9 bits. 8+extention).

Dans tout les cas rien ne garantie que tu pourra transporter 20 + N numeros avec N fixe. Dans le pire des cas tu ne pourra en transporter que 19! (si la taille maximum est toujours atteinte, comme tu rajoute des bits pour indiquer la taille des numeros, tu depassera).

[souviron34]

comme c'est un delta, il y a (peut-être) une valeur max..

Par exemple dans le cas indiqué 110. Et donc on peut coder sur 7 bits et non pas 32, ou 8 si c'est 255.


Mais si on a plus faiblle on peut fortement diminuer..

20 ou 30 tiennent sur 5 bits, le nombre de bits d'encodage tient sur 5 aussi, et donc avec 10 bits on a passé toute l'info nécessaire (et on peut même se passer du 20 ou 30 en ne passant que le nombre de bits d'encodage et en divisant la longueur restante par ce nombre)

[Graffito]

En imaginant une suite comme celle-ci :
0-1-2-3-4-7-8-9
Comment codes-tu cela dans ton exemple ?

Au départ, on code un entier (sur 2, 3 ou 4 octets si le nombre maximum d'éléments de la suite est 16, 24 ou 32) avec comme premiers bits "10010000".

• Le premier bit à 1 indique que "9" sera codé explicitement (c'est toujours le cas du premier élément de la série).
• Les 2 bits à 0 suivants indiquent qu'on n'a pas besoin de coder explicitement les 2 suivants et qu'on va les déduire de l'élément précédent de la série (9-1=>8, puis 8-1=>7 ) .
• le bit à 1 au milieu indique que l'élément suivant (le "4") sera codé explicitement.
• les 4 derniers bits à zéro indiquent qu'on n'a pas besoin de coder explicitement les 4 suivants (3-2-1-0) qui sont en séquence depuis le "4".

Ensuite, viennent les codages explicites des éléments ne respectant pas la séquence, soit "9" et "4"

La trame sera donc composée d'un entier avec "10010000...." suivi des 2 éléments rompant la séquence, soit "9" , puis "4".

A toi de décider si le codage du "4" se fait en relatif par rapport à l'élément précédent (le "7") ou en absolu (par rapport à 0).

[progfou]

OK, ça me plaît bien ça .
Dans l'idéal ça consomme quasiment rien... .