Comment coder un bloc de 8 octets en utilisant uniquement des chiffres (caractères numériques) ?

Question

J'ai besoin d'encoder des flux de 8 octets de telle sorte que le flux encodé ne contienne que des chiffres (de zéro à neuf). Existe-t-il un mécanisme d'encodage standard pour faire cela ? S'il existe plusieurs façons de le faire, laquelle est la plus efficace en termes de longueur de la chaîne encodée (la plus courte étant la meilleure) ?

Answer 1

Traitez les 8 octets comme un nombre entier non signé de 64 bits, convertissez-les en décimales et complétez-les à gauche avec des zéros. Cela devrait donner la chaîne la plus courte possible, car elle utilise tous les chiffres disponibles dans toutes les positions, sauf celle de départ.

Si vos données ne sont pas uniformément réparties, il existe d'autres solutions, comme le codage de Huffman, qui permet de représenter les modèles de données les plus courants par des chaînes plus courtes. L'une des solutions consiste à utiliser le premier chiffre pour coder la longueur de la chaîne. Tous les chiffres sauf 1 en première position peuvent être traités comme un spécificateur de longueur. Ainsi, la longueur maximale de 20 chiffres ne sera jamais dépassée. (Le 20e chiffre ne peut être que 0 ou 1, le plus grand nombre de 64 bits est 18 446 744 073 709 551 615). L'interprétation exacte du mappage des autres chiffres en longueurs doit être basée sur la distribution de vos motifs. Si vous avez 10 motifs qui se produisent TRÈS souvent, vous pourriez par exemple réserver "0" pour signifier qu'un chiffre représente une séquence complète.

Tout codage plus compliqué de ce type nécessitera toutefois un code d'emballage/désemballage plus complexe et peut-être même des tables de consultation, de sorte que l'effort n'en vaut peut-être pas la peine.

Answer 2

La réponse à la question de l'efficacité dépendra d'un lot sur la gamme typique de valeurs dans les blocs de 8 octets. Prenons l'exemple de l'UTF-8 et de l'UTF-16 d'Unicode. L'UTF-8 est très efficace pour coder des textes écrits principalement en scripts occidentaux, car la plupart des caractères de ces scripts sont dans la plage 0x00 à 0x7F que l'UTF-8 peut stocker dans un seul octet. Mais il n'est pas très efficace pour encoder des textes écrits principalement en scripts orientaux ; UTF-16 ou UTF-32 est un meilleur choix dans ce cas.

Si vous avez une lecture sur les différents UTF ils peuvent inspirer une solution. Fondamentalement, ils fonctionnent en permettant à un grand nombre de valeurs d'être directement encodées dans un octet, mais en ayant un drapeau (le bit de poids fort, je pense, dans le cas du premier octet de l'UTF-8) indiquant que cet octet ne dit pas tout et que l'octet suivant (ou deux, ou trois, ou quatre) est nécessaire. Le point de départ est un octet pour l'UTF-8, un mot pour l'UTF-16, mais les concepts sont similaires.

Maintenant, vous travaillez avec un dramatiquement une plus petite gamme de valeurs (0-9 plutôt que 0-255), et évidemment je ne recommande pas d'essayer d'utiliser directement UTF, juste le concept. Par exemple, disons que la plupart de vos valeurs (directement ou avec un certain massage) sont inférieures à 9000, un certain nombre sont inférieures à 9000000, et seules de rares valeurs vous emmènent au-delà. Vous pourriez adopter l'approche UTF et dire que les blocs (vos valeurs de 8 octets) sont divisés en segments de quatre chiffres, et que vous aurez toujours au moins un segment (quatre chiffres) par bloc encodé. Si la valeur du premier segment (aaaa) est comprise entre 0000 et 8999 (inclus), il s'agit d'un segment "terminal" - c'est la valeur réelle. Mais si elle est de 9aaa, cela signifie qu'il y a un deuxième segment et que vous devez regarder aaabbbb (bbbb étant la valeur du segment suivant). Si que est comprise entre 0000000 et 8999999 (inclus), c'est un terminal ; mais si c'est 9aabbbb, cela signifie qu'il faut regarder aabbbbcccc (cccc étant le segment suivant) ; etc. I pensez à qui nous donnerait ça :

00000000000000000000-00000000000000008999 ->  4 digits (xxxx)
00000000000000009000-00000000000008999999 ->  8 digits (9xxxxxxx)
00000000000009000000-00000000008999999999 -> 12 digits (99xxxxxxxxxx)
00000000009000000000-00000008999999999999 -> 16 digits (999xxxxxxxxxxxxx)
00000009000000000000-00008999999999999999 -> 20 digits (9999xxxxxxxxxxxxxxxx)
00009000000000000000-08999999999999999999 -> 24 digits (99999xxxxxxxxxxxxxxxxxxx)
09000000000000000000-18446744073709551615 -> 28 digits (999999xxxxxxxxxxxxxxxxxxxxxx)
Or special case, just use 26 digits for the last one:  (999999xxxxxxxxxxxxxxxxxxxx)

Dans le meilleur des cas, il s'agit de quatre chiffres et dans le pire, de 28 ou 26, selon que l'on veut ou non mettre en majuscule le dernier segment du bloc. C'est beaucoup mieux (probablement) que d'utiliser 20 chiffres pour chaque bloc.

C'est complètement improvisé et probablement pas aussi efficace que ça pourrait l'être, mais vous voyez l'idée. C'est très facile à désérialiser, et probablement pas si difficile à sérialiser.

Vous pouvez voir pourquoi j'ai commencé par le commentaire sur vos valeurs typiques. Si elles sont typiquement supérieures à 10.000.000.000.000.000.000, la méthode ci-dessus n'est pas un moyen efficace de les coder directement. Mais des techniques similaires peuvent être utilisées si vos valeurs typiques se situent dans la partie supérieure plutôt que dans la partie inférieure, en massant un peu la valeur avant l'encodage.

Answer 3

Le résultat qui a la longueur la plus courte est à convertir directement en décimal. La valeur la plus élevée est alors 18446744073709551615 mais la conversion peut être difficile sans la possibilité d'utiliser des entiers de longueur arbitraire.

Le plus long est de le convertir en octal en un seul morceau. Il en résulte une longueur maximale de 22, avec une valeur de 1777777777777777777777 . La conversion ne nécessite que des décalages, et peut être effectuée assez facilement.

Le plus long est ensuite de le convertir en octal ou en décimal par octet. On obtient ainsi une longueur de 24, avec 8 répétitions de 377 o 255 respectivement. La conversion dans les deux sens est triviale, et est laissée comme un exercice pour le lecteur.