Clarification de l'encodage à octets variables

Question

Je suis très novice dans le monde de l'encodage des octets, alors excusez-moi (et corrigez-moi bien sûr) si j'utilise/exprime des concepts simples de la mauvaise façon. J'essaie de comprendre le codage à octets variables. J'ai lu l'article de Wikipedia (http://en.wikipedia.org/wiki/Variable-width_encoding) aussi bien qu'un book chapter d'un manuel de recherche d'information. Je pense que je comprends comment encoder un nombre entier décimal. Par exemple, si je voulais fournir un codage variable octet pour l'entier 60, je devrais le résultat suivant:

1 0 1 1 1 1 0 0 

(s'il vous plaît laissez-moi savoir si ce qui précède est incorrect). Si je comprends le schéma, alors je ne suis pas complètement sûr de la façon dont l'information est compressée. Est-ce parce qu'habituellement nous utiliserions 32 bits pour représenter un nombre entier, de sorte que représenter 60 aboutirait à 1 1 1 1 0 0 précédé de 26 zéros, gaspillant ainsi cet espace plutôt que de le représenter avec seulement 8 bits à la place?

Merci d'avance pour les clarifications.

Answer 1

La façon dont vous le faites est en réservant l'un des bits pour signifier "Je n'ai pas fini avec la valeur." Habituellement, c'est le bit le plus important.

Lorsque vous lisez un octet, vous traitez les 7 bits inférieurs. Si le bit le plus significatif est 1, alors vous savez qu'il y a encore un octet à lire, et vous répétez le processus, en ajoutant les 7 bits suivants aux 7 bits actuels.

Le format MIDI utilise ce codage exact pour représenter longueurs des événements MIDI, de la manière suivante:

1. ExpectedValue = 0
2. octet = ReadFromFile
3. ExpectedValue = ExpectedValue + (octet ET 0x7f)
4. si l'octet> 127 puis
   1. ExpectedValue = ExpectedValue SHL 7
   2. Aller à 2
5. Fait

Par exemple, serait représenté la valeur 0x80 en utilisant les octets 0x81 0x00. Vous pouvez essayer d'exécuter l'algorithme sur ces deux octets, et vous verrez que vous aurez la bonne valeur.

UTF-8 fonctionne de manière similaire, mais il utilise un schéma légèrement plus complexe pour vous dire combien d'octets vous devriez attendre. Cela permet une correction d'erreur, car vous pouvez facilement savoir si les octets que vous obtenez correspondent à la longueur demandée. Wikipedia describes their structure assez bien.

Answer 2

Vous frappez le clou sur la tête.

Il existe de nombreux schémas de codage, tels que gamma et delta, qui sont des cas particuliers de codage Elias. Ce sont des codes au niveau du bit, par opposition au code au niveau octet que vous avez utilisé, et sont utiles lorsque vous avez un fort biais vers de petits nombres (qui peuvent souvent être obtenus en codant des deltas au lieu de valeurs absolues). Les schémas de codage au niveau du bit sont beaucoup plus difficiles à implémenter que les schémas au niveau octet et la charge supplémentaire de l'UC peut dépasser le gain de temps en réduisant les données à lire, même si la plupart des processeurs modernes ont le bit le plus haut et le bas instructions «binaires» qui améliorent considérablement les performances des codecs de niveau bits. À mesure que les vitesses du processeur continuent de dépasser les vitesses RAM, les schémas au niveau des bits deviennent plus attrayants, bien que la simplicité des codecs au niveau des octets soit également un facteur important.

Answer 3

Oui, vous avez économisé de l'espace en encodant un octet au lieu de 4. En général, vous économiserez de la mémoire si les valeurs que vous encodez sont beaucoup plus petites que la valeur maximale qui correspondrait à votre original encodage en largeur