Codage de plage - Range coding
Le codage par plage (ou codage par plage ) est une méthode de codage entropique définie par G. Nigel N. Martin dans un article de 1979, qui a effectivement redécouvert le code arithmétique FIFO introduit pour la première fois par Richard Clark Pasco en 1976. Étant donné un flux de symboles et leurs probabilités, un codeur de distance produit un flux de bits peu encombrant pour représenter ces symboles et, étant donné le flux et les probabilités, un décodeur de distance inverse le processus.
Le codage de plage est très similaire au codage arithmétique , sauf que le codage est effectué avec des chiffres dans n'importe quelle base, au lieu de bits, et il est donc plus rapide lors de l'utilisation de bases plus grandes (par exemple un octet ) à faible coût en efficacité de compression. Après l'expiration du premier brevet de codage arithmétique (1978), le codage par plage est apparu clairement exempt de toute charge de brevet. Cela a particulièrement suscité l'intérêt pour la technique dans la communauté open source . Depuis lors, les brevets sur diverses techniques de codage arithmétique bien connues ont également expiré.
Comment fonctionne le codage de plage
Le codage par plage code conceptuellement tous les symboles du message en un seul nombre, contrairement au codage de Huffman qui attribue à chaque symbole un motif binaire et concatène tous les motifs binaires ensemble. Ainsi, le codage par plage peut atteindre des taux de compression plus élevés que la limite inférieure d'un bit par symbole sur le codage de Huffman et il ne souffre pas des inefficacités que fait Huffman lorsqu'il traite des probabilités qui ne sont pas une puissance exacte de deux .
Le concept central derrière le codage par plage est le suivant : étant donné une plage d' entiers suffisamment large et une estimation de probabilité pour les symboles, la plage initiale peut facilement être divisée en sous-plages dont les tailles sont proportionnelles à la probabilité du symbole qu'elles représentent. Chaque symbole du message peut ensuite être codé à son tour, en réduisant la plage actuelle à la seule sous-plage qui correspond au prochain symbole à coder. Le décodeur doit avoir la même estimation de probabilité que le codeur utilisé, qui peut soit être envoyé à l'avance, dérivé de données déjà transférées, soit faire partie du compresseur et du décompresseur.
Lorsque tous les symboles ont été codés, il suffit d'identifier la sous-gamme pour communiquer l'intégralité du message (en supposant bien sûr que le décodeur est en quelque sorte averti lorsqu'il a extrait l'intégralité du message). Un seul entier est en fait suffisant pour identifier la sous-plage, et il peut même ne pas être nécessaire de transmettre l'entier entier ; s'il existe une séquence de chiffres telle que chaque entier commençant par ce préfixe tombe dans la sous-plage, alors le préfixe seul est tout ce qui est nécessaire pour identifier la sous-plage et ainsi transmettre le message.
Exemple
Supposons que nous voulions encoder le message "AABA<EOM>", où <EOM> est le symbole de fin de message. Pour cet exemple, on suppose que le décodeur sait que nous avons l'intention de coder exactement cinq symboles dans le système de numération en base 10 (permettant 10 5 combinaisons différentes de symboles avec la plage [0, 100000)) en utilisant la distribution de probabilité {A: . 60 ; B : 0,20 ; <EOM> : .20}. L'encodeur décompose la plage [0, 100000) en trois sous-plages :
A: [ 0, 60000) B: [ 60000, 80000) <EOM>: [ 80000, 100000)
Puisque notre premier symbole est un A, il réduit notre plage initiale à [0, 60000). Le deuxième choix de symbole nous laisse avec trois sous-gammes de cette gamme. Nous les montrons en suivant le 'A' déjà encodé :
AA: [ 0, 36000) AB: [ 36000, 48000) A<EOM>: [ 48000, 60000)
Avec deux symboles encodés, notre plage est maintenant [0, 360000) et notre troisième symbole conduit aux choix suivants :
AAA: [ 0, 21600) AAB: [ 21600, 28800) AA<EOM>: [ 28800, 36000)
Cette fois, c'est le deuxième de nos trois choix qui représente le message que nous voulons encoder, et notre plage devient [21600, 28800). Il peut sembler plus difficile de déterminer nos sous-plages dans ce cas, mais ce n'est pas le cas : nous pouvons simplement soustraire la limite inférieure de la limite supérieure pour déterminer qu'il y a 7 200 nombres dans notre plage ; que les 4320 premiers d'entre eux représentent 0,60 du total, les 1440 suivants représentent les 0,20 suivants et les 1440 restants représentent les 0,20 restants du total. L'ajout de la borne inférieure nous donne nos plages :
AABA: [21600, 25920) AABB: [25920, 27360) AAB<EOM>: [27360, 28800)
Enfin, avec notre plage réduite à [21600, 25920), nous n'avons plus qu'un symbole à encoder. En utilisant la même technique que précédemment pour diviser la plage entre la limite inférieure et la limite supérieure, nous trouvons que les trois sous-plages sont :
AABAA: [21600, 24192) AABAB: [24192, 25056) AABA<EOM>: [25056, 25920)
Et puisque <EOM> est notre symbole final, notre plage finale est [25056, 25920). Parce que tous les entiers à cinq chiffres commençant par "251" se trouvent dans notre plage finale, c'est l'un des préfixes à trois chiffres que nous pourrions transmettre qui transmettrait sans ambiguïté notre message d'origine. (Le fait qu'il y ait en fait huit de ces préfixes en tout implique que nous avons encore des inefficacités. Ils ont été introduits par notre utilisation de la base 10 plutôt que de la base 2. )
Le problème central peut sembler être la sélection d'une plage initiale suffisamment grande pour que, quel que soit le nombre de symboles que nous devons encoder, nous ayons toujours une plage actuelle suffisamment grande pour se diviser en sous-plages non nulles. En pratique, cependant, ce n'est pas un problème, car au lieu de commencer avec une plage très large et de la réduire progressivement, l'encodeur fonctionne avec une plage de nombres plus petite à un moment donné. Une fois qu'un certain nombre de chiffres ont été codés, les chiffres les plus à gauche ne changeront pas. Dans l'exemple après avoir codé seulement trois symboles, nous savions déjà que notre résultat final commencerait par "2". Plus de chiffres sont décalés vers la droite au fur et à mesure que les chiffres de gauche sont envoyés. Ceci est illustré dans le code suivant :
int low = 0;
int range = 100000;
void Run()
{
Encode(0, 6, 10); // A
Encode(0, 6, 10); // A
Encode(6, 2, 10); // B
Encode(0, 6, 10); // A
Encode(8, 2, 10); // <EOM>
// emit final digits - see below
while (range < 10000)
EmitDigit();
low += 10000;
EmitDigit();
}
void EmitDigit()
{
Console.Write(low / 10000);
low = (low % 10000) * 10;
range *= 10;
}
void Encode(int start, int size, int total)
{
// adjust the range based on the symbol interval
range /= total;
low += start * range;
range *= size;
// check if left-most digit is same throughout range
while (low / 10000 == (low + range) / 10000)
EmitDigit();
// readjust range - see reason for this below
if (range < 1000)
{
EmitDigit();
EmitDigit();
range = 100000 - low;
}
}
Pour finir, nous devrons peut-être émettre quelques chiffres supplémentaires. Le chiffre supérieur de lowest probablement trop petit, nous devons donc l'incrémenter, mais nous devons nous assurer de ne pas l'incrémenter au-delà de low+range. Nous devons donc d'abord nous assurer qu'il rangeest assez grand.
// emit final digits
while (range < 10000)
EmitDigit();
low += 10000;
EmitDigit();
Un problème qui peut se produire avec la Encodefonction ci - dessus est que rangepourrait devenir très petites mais lowet low+rangeont encore différents premiers chiffres. Cela pourrait entraîner une précision insuffisante de l'intervalle pour distinguer tous les symboles de l'alphabet. Lorsque cela se produit, nous devons modifier un peu, afficher les deux premiers chiffres même si nous sommes peut-être décalés d'un, et réajuster la plage pour nous donner autant de place que possible. Le décodeur suivra les mêmes étapes afin qu'il sache quand il doit le faire pour rester synchronisé.
// this goes just before the end of Encode() above
if (range < 1000)
{
EmitDigit();
EmitDigit();
range = 100000 - low;
}
La base 10 a été utilisée dans cet exemple, mais une implémentation réelle utiliserait simplement le binaire, avec la plage complète du type de données entier natif. Au lieu de 10000et 1000vous utiliseriez probablement des constantes hexadécimales telles que 0x1000000et 0x10000. Au lieu d'émettre un chiffre à la fois, vous émettriez un octet à la fois et utiliseriez une opération de décalage d'octet au lieu de multiplier par 10.
Le décodage utilise exactement le même algorithme avec en plus le suivi de la codevaleur actuelle constituée des chiffres lus par le compresseur. Au lieu d'émettre le chiffre supérieur de lowvous, jetez-le simplement, mais vous décalez également le chiffre supérieur codeet insérez un nouveau chiffre lu par le compresseur. Utilisez AppendDigitci-dessous au lieu de EmitDigit.
int code = 0;
int low = 0;
int range = 1;
void InitializeDecoder()
{
AppendDigit(); // with this example code, only 1 of these is actually needed
AppendDigit();
AppendDigit();
AppendDigit();
AppendDigit();
}
void AppendDigit()
{
code = (code % 10000) * 10 + ReadNextDigit();
low = (low % 10000) * 10;
range *= 10;
}
void Decode(int start, int size, int total) // Decode is same as Encode with EmitDigit replaced by AppendDigit
{
// adjust the range based on the symbol interval
range /= total;
low += start * range;
range *= size;
// check if left-most digit is same throughout range
while (low / 10000 == (low + range) / 10000)
AppendDigit();
// readjust range - see reason for this below
if (range < 1000)
{
AppendDigit();
AppendDigit();
range = 100000 - low;
}
}
Afin de déterminer les intervalles de probabilité à appliquer, le décodeur doit examiner la valeur actuelle de codel'intervalle [faible, faible + plage) et décider quel symbole cela représente.
void Run()
{
int start = 0;
int size;
int total = 10;
InitializeDecoder(); // need to get range/total >0
while (start < 8) // stop when receive EOM
{
int v = GetValue(total); // code is in what symbol range?
switch (v) // convert value to symbol
{
case 0:
case 1:
case 2:
case 3:
case 4:
case 5: start=0; size=6; Console.Write("A"); break;
case 6:
case 7: start=6; size=2; Console.Write("B"); break;
default: start=8; size=2; Console.WriteLine("");
}
Decode(start, size, total);
}
}
int GetValue(int total)
{
return (code - low) / (range / total);
}
Pour l'exemple AABA<EOM> ci-dessus, cela renverrait une valeur comprise entre 0 et 9. Les valeurs 0 à 5 représenteraient A, 6 et 7 représenteraient B, et 8 et 9 représenteraient <EOM>.
Relation avec le codage arithmétique
Le codage arithmétique est le même que le codage par intervalles, mais avec les nombres entiers considérés comme étant les numérateurs des fractions . Ces fractions ont un dénominateur commun implicite, tel que toutes les fractions se situent dans la plage [0,1). En conséquence, le code arithmétique résultant est interprété comme commençant par un "0" implicite. Comme il ne s'agit que d'interprétations différentes des mêmes méthodes de codage et que les codes arithmétiques et de plage résultants sont identiques, chaque codeur arithmétique est son codeur de plage correspondant, et vice versa. En d'autres termes, le codage arithmétique et le codage par plage ne sont que deux façons légèrement différentes de comprendre la même chose.
En pratique, cependant, les codeurs dits de gamme ont tendance à être implémentés à peu près comme décrit dans l'article de Martin, tandis que les codeurs arithmétiques ont plus généralement tendance à ne pas être appelés encodeurs de gamme. Une caractéristique souvent notée de ces codeurs de plage est la tendance à effectuer une renormalisation octet à la fois, plutôt qu'un bit à la fois (comme c'est généralement le cas). En d'autres termes, les codeurs de plage ont tendance à utiliser des octets comme chiffres de codage, plutôt que des bits. Bien que cela réduise la quantité de compression qui peut être obtenue d'une très petite quantité, c'est plus rapide que lors de la renormalisation pour chaque bit.
Voir également
- Codage arithmétique
- Systèmes numériques asymétriques
- Compression de données
- Codage entropique
- Codage de Huffman
- Format d'électrophysiologie multi-échelle
- Codage Shannon-Fano
Les références
- ^ un b G. Nigel N. Martin, Range encoding: Un algorithme pour supprimer la redondance d'un message numérisé , Video & Data Recording Conference, Southampton , Royaume-Uni, 24-27 juillet 1979.
- ^ "Algorithmes de codage source pour une compression rapide des données" Richard Clark Pasco, Stanford, CA 1976
- ^ " Sur les frais généraux des codeurs de gamme ", Timothy B. Terriberry, Note technique 2008
- ^ Brevet américain 4,122,440 - (IBM) déposé le 4 mars 1977, accordé le 24 octobre 1978 (maintenant expiré)