Statistical Coders French

 

Compression: Algorithmes: Codage statistique

Introduction

Les codeurs statistiques sont l’épine dorsale de la compression. Nous avons besoin d’un modèle simple pour un compresseur:

(RAW) ENTRÉE -> COMPRESSEUR -> SORTIE (TRANSMISSION)

(TRANSMISSION) ENTREE -> DECOMPRESSEUR -> SORTIE (RAW)

L’idée de base est: le compresseur devine quelle entrée sera, et écrit moins de bits sur la sortie si elle devine correctement. Notez que le décompresseur DOIT être capable de faire la même conjecture que le compresseur, afin de décoder correctement la transmission, puisque la transmission est différente selon la prédiction.

Actuellement, cependant, nous ne nous occupons que du «codeur statistique». Il s’agit d’un algorithme qui code ou décode un caractère, avec un nombre de bits proportionnel au -log2 (probabilité prédite). Notez qu’il peut arrondir le nombre de bits vers le haut ou encoder avec extra – aussi longtemps qu’il essaie d’atteindre cet objectif, il est un codeur statistique.

Par exemple, si les données RAW peuvent être de quatre caractères: a, b, c ou d, et le codeur statistique est informé (par le reste du compresseur) que 50% du temps se produit, b se produit 25% du temps, c se produit 25% du temps, et d se produit presque jamais, alors nous voudrions coder comme suit:

1 bit pour a (-log2 (.5) = 1)

2 bits pour b est c (-log2 (.25) = 2)

par exemple:

a : 0

b : 10

c : 11

Notez qu’il existe de nombreuses autres possibilités (c’est-à-dire {1,01,00}, {1,00,01}, {0,11,10} – tout ce qui compte, c’est que la longueur des codes soit aussi bonne que possible

Vous pouvez penser à « RAW » IO comme un codeur statistique qui prédit chaque symbole avec une probabilité égale. Ainsi, il y a 256 valeurs pour un octet, et chacune a une probabilité égale, p = 1/256, donc -log2 (1/256) = 8 bits.

Dans le texte typique (comme celui-ci) le caractère ESPACE et ‘e’ se produisent très souvent, donc ils doivent être écrits en peu de bits (3) alors que ‘q’ se produit souvent, donc il devrait être écrit en plus de bits (12).

Une autre façon de considérer l’objectif d’un codeur statistique est d’imaginer que l’entrée n’a que deux symboles A et B (ceci est parfaitement général, car n’importe quel octet peut être décomposé en ses bits). Soit p (A) la probabilité réelle de A. Comme il n’y a que deux symboles, p (A) + p (B) = 1, donc p (B) = 1 – p (A). Soit L (a) = nombre de bits utilisés pour écrire a, et L (b) = nombre de bits utilisés pour écrire b (notez que ce ne sont PAS des entiers). Ainsi, notre objectif est de minimiser la fonction

L = L(A)*p (A) + L (B)*p(B)

p(A) = L (B) = 0 n’est pas valide, c’est-à-dire que le code doit être décodable Ni L (A) = L (B) = 0,5)

On peut montrer que les valeurs qui minimisent L sont:

L(A) = -log2(p (A))

L(B) = -log2(p (B)) = -log2(1 – p(A))

L = -log2(p (A))*p(A) -log2(1 – p(A))*(1 – p(A))

Ainsi L ne dépend que de p(A) (ou p(B) si vous préférez).

Vous pouvez vous demander : comment L peut-il être un non-entier? Eh bien, une réponse est: « codage arithmétique », dont nous allons parler plus tard. Une autre réponse, plus facile est: « blocage ».

Le blocage consiste à combiner deux symboles adjacents afin de permettre des longueurs de code fractionnaires. Par exemple, soit A et B les seuls symboles d’entrée (entrée binaire). Si l’ensemble de codage est:

AA: 0

AB: 10

BA: 110

BB: 111

Ensuite, A est écrit en (environ) 0,7 bits, et B est écrit en environ 1.4 bits.

Il a été montré que si N symboles sont bloqués ensemble, l’inefficacité de codage due à des longueurs de code entier est bornée par:

(Longueur supplémentaire par symbole) <= 1/N bits

D’accord. C’est la fin de l’introduction au codage statistique. Après cela, nous passons par le codage de Shannon-Fano, le codage de Huffman, puis le codage arithmétique.

ADDENDA :

Le but du codage statistique est de coder des symboles avec leur entropie Shannon-order0. Voir mes nouvelles postings sur l’entropie.

Algorithmes de codage

Rappelez-vous mon exemple:

a : 0

b : 10

c : 11

Vous pouvez demander comment un tel code a été atteint. Il est facile de faire conceptuellement pour un petit alphabet, mais comment pouvons-nous le faire pour un grand alphabet? Évidemment, nous voulons un algorithme itératif ou récursif à usage général.

Ce processus est requis pour tous les préfixes de longueur entière.

Un préfixe code est un tel qu’aucune partie d’un code n’est le préfixe d’un autre. Ceci est nécessaire pour le décodage simple. Par exemple:

a : 0

b : 01

c : 10

N’est PAS un code sans préfixe. Si le décodeur a vu la chaîne « 0010 », il ne saurait pas si c’était « a, b, a » ou « a, a, c ».

Un autre exemple de NON préfixe-code :

a: 0

b : 01

c : 11

la chaîne « 00111 » DOIT être « a, b, c », mais le décodeur ne peut pas dire tout de suite s’il commence par « a, a » ou « a, b » – c’est-à-dire qu’un code ne peut être décodé qu’après examen ultérieur. Ce type de décodage doit être évité.

a : 0

b : 10

c : 11

IS est un préfixe-code. Aucune chaîne n’est ambiguë. « 0010 » signifie « a, a, b » et « 00111 » signifie « a, b, c » et le décodeur peut le dire immédiatement.

Maintenant nous voulons créer un de ces préfixes-codes. Comment faisons-nous ça? Nous divisons le processus en deux étapes:

1. Déterminer la longueur des codes. Si Li est la longueur du ith code Let Ei = Li – (- log2 (Pi)) où Pi est la probabilité du ith code Ei est la longueur Extra écrite pour chaque symbole, c’est-à-dire la longueur qui est écrite qui n’est pas nécessaire. Nous aimerions choisir les longueurs de façon à minimiser la somme de Pi*Ei. Cela devrait être logique car Pi est le taux d’occurrence de i, et Ei est la longueur excédentaire, donc la somme de Pi*Ei est la longueur de sortie totale qui est plus longue que nécessaire.

2. Créez un préfixe-code pour ces longueurs de code.

L’étape 1 est réalisée avec le codage Shannon-Fano ou le codage Huffman. Ceux-ci sont discutés plus tard. En ce qui concerne l’étape 2, ces longueurs pourraient être générées de n’importe quelle manière.

Inégalité Kraft

Il s’avère qu’un code de préfixe n’existe que pour les codes SI:

K = Somme(i = 0 à N ) de 2^(- Li) <= 1

C’est l’inégalité Kraft. La preuve de cette affirmation dépasse le cadre du présent document. Notons cependant que Li = -log2 (Pi) + Ei

ainsi 2^(-Li) = 2^(–log2(Pi) – Ei) = 2^(log2(Pi)) * 2^(-Ei) = Pi / 2^(Ei)

ainsi K = somme( i = 0 to N ) of Pi / 2^(Ei)

Image le cas simple où Ei = E pour tous i

ainsi K = somme( i = 0 to N ) de Pi / 2^(E) = [ somme( i = 0 to N ) de Pi ] / 2^E

mais[ somme( i = 0 à N ) de Pi ] = 1

ainsi K = 1 / 2^E

Ainsi, l’inégalité Kraft dit 1/ 2^E <= 1 1 = 2^0

2^(-E) <= 2^(0)

-E <= 0

E >= 0

Le résultat est: L’inégalité Kraft dit qu’un code est décodable IF ET SEULEMENT si les longueurs de code sont supérieures ou égales à celles déterminées par l’entropie.

Cela devrait faire bon sens.

Génération d’un code sans préfixe

Deux méthodes seront présentées ici. L’un est simple et intuitif, l’un est pratique et de pointe.

Le premier est très simple. Il suffit de créer un arbre binaire de symboles, de sorte que la profondeur dans l’arbre est la longueur du code.

Par exemple :
L(a) = 1
L(b) = 2
L(c) = 2

Then we make the tree:

a / root b \ / X \ c Maintenant, traverse l’arbre. Chaque branche est un bit. Chaque branche descendante est un bit zéro. La création de cet arbre est un algorithme relativement simple.

La seconde méthode est rapide et crée un code alphabétique. Je shant discuter ici, mais vous pouvez regarder mon code source Huffman pour le vérifier.

Code Shannon-Fano

Le codage Shannon-Fano est une méthode pour créer les longueurs de code d’un préfixe-code.

L’idée de base entre le codage Huffman & S-F est:

Parce que chaque bit de la sortie réserve la même quantité d’espace, chaque bit devrait avoir la même probabilité.

Pensons à un code comme un arbre binaire comme décrit ci-dessus. La déclaration ci-dessus est la même que de dire que, à chaque noeud de l’arbre, la branche ci-dessus et la branche ci-dessous devraient avoir la même probabilité de se produire.

Par exemple, dans un octet normal de 8 bits, nous avons un arbre totalement symétrique. Certaines des branches sont prises souvent, et certaines sont prises presque jamais. Par exemple, dans le texte, la branche supérieure de la racine est presque jamais prise (c’est-à-dire les caractères ASCII ne vont pas plus de 127).

Ainsi, tous les algorithmes de génération de longueur de code sont un moyen d’étaler des caractères sur un arbre binaire de sorte que les probabilités soient égales entre chaque branche.

Imaginez que nous connaissions un nombre d’occurrences pour chaque symbole: c’est-à-dire si la chaîne d’entrée est (aabbaac), alors le nombre d’occurrences est:

C(a) = 4

C(b) = 2

C(c) = 1

Ensuite, nous voulons l’arbre:

       a / 4 / root b \ / 3 2 \ / X \ 1 \ c

Le nombre sur chaque branche indique la somme des nombres de fréquences dans le « sous-arbre » : c’est-à-dire l’arbre avec ce noeud comme racine.

Nous pouvons voir que dans chaque branche, les comptes ne sont PAS égaux, bien qu’ils soient aussi proches que possible de l’égalité. Cela signifie qu’un code de longueur entière pour cette chaîne est sous-optimal. Chaque fois que les dénombrements sont inégaux, alors le code n’est pas aussi bon que l’entropie.

Comment faire un arbre comme ça? C’est facile.

Prenez tous les caractères, chacun a un compte associé à lui, et les mettre dans les nœuds qui sont liés à rien. Appelez cet ensemble S0. Soit C(S0) = la somme de tous les comptages dans S0.

Prenez le nœud avec le nombre le plus élevé et placez-le dans l’ensemble S1. Maintenant, C(S0) est plus faible.

Continuez jusqu’à ce que C(S1) >= C(S0). Maintenant, nous avons divisé les données ainsi:

[S1] / C(S1) / root \ C(S0) \ [S0]

Maintenant, prenez [S1] comme point de départ et divisez-le en [S2] et [S1]. Faites la même chose pour [S0], faisant [S3] et [S0]. Continuez à faire ceci jusqu’à ce qu’un ensemble ait seulement un membre, auquel point il est un noeud de feuille.

Je vais faire un exemple sur l’ensemble:

C(a) = 4

C(b) = 2

C(c) = 1

C(d) = 1

S0 = {a, b, c, d}, C(S0) = 8

Tirer un

S1 = {a} C(S1) = 4; S0 = {b, c, d} C(S0) = 4

Les comptes sont égaux, arrêter la construction S1

S1 n’a qu’un seul membre, arrêtez de travailler sur S1

S0 = {b, c, d} C(S0) = 4

Retirer b pour faire S2

S2 = {b} C(S2) = 2; S0 = {c, d} C(S0) = 2

Les comptes sont égaux, arrêter de construire S2

S2 n’a qu’un seul membre, arrêtez de travailler sur S2

S0 = {c,d} C(S0) = 2

Soit S2 = {c}, et S0 = {d} et nous sommes finis.

a / 4 / root b \ / 4 2 \ / X c \ / 2 1 \ / X \ 1 \ d

Quel est le code idéal pour cet ensemble.

C’est ce qu’on appelle le codage Shannon-Fano.

Huffman Codage

Il a été trouvé que le codage de Shannon-Fano est légèrement sous-optimal dans certains cas.

Ainsi, le code Huffman est le meilleur qui peut être avec des codes de longueur entière.

> OOPS !!! J’ai eu la mauvaise description de codage Huffman! <

Ici, il est, à peu près: au lieu d’une passe avant comme Shannon-Fano, un passe en arrière est faite. À Shannon-Fano, nous avons créé un arbre en commençant par tous les caractères à la racine, puis en les divisant en deux groupes et en recourant vers le bas. Dans Huffman, nous commençons par tous les caractères «Hors de l’arbre», sur le côté « droit », c’est-à-dire au-delà des feuilles. Nous saisissons ensuite quelques personnages pour devenir les feuilles les plus à droite. Ensuite, nous saisissons un peu plus et faire les noeuds parents, et retrouver notre chemin de retour à la racine. Cependant, dans la pratique, cela se fait différemment:

Prenez une liste de tous vos personnages, mettez-les dans des nœuds feuilles, et donnez à chaque nœud un nombre égal au nombre de caractères dans le nœud. Ces nœuds n’ont actuellement ni parents ni enfants (ils n’auront jamais d’enfants). Maintenant, oubliez que ce sont des personnages, et juste appeler les nœuds avec des comptes. Les classer de sorte que ceux qui ont les comptes les plus bas sont les premiers. Maintenant, saisissez les deux noeuds de comptage le plus bas, créez un nouveau nœud comme parent de ces deux et définissez le nombre du nouveau nœud égal à la somme de ses comptes enfants. (Vous voyez comment nous récurrent vers l’arrière dans la construction de l’arbre). Maintenant, ajoutez ce nouveau nœud à la liste triée des noeuds, dans sa position triée correcte. Les deux noeuds qui ont été faits en enfants ne sont plus dans la liste (c’est-à-dire que la liste devient plus courte par un noeud). Répétez jusqu’à ce que la liste a un seul membre – c’est la racine!

Maintenant un exemple, celui que nous avons déjà fait avec Shannon-Fano:

[a] : 4

[b] : 2

[c] : 1

[d] : 1

Je vais utiliser [] pour indiquer un nœud, donc [[x], [[y], [z]]] est un nœud avec deux enfants, l’un est une feuille [x] et l’autre a deux enfants , [Y] et [z]. [X]: N signifie que le compte de ce noeud est N.

Initialiser le codage: transformer les caractères en nœuds feuilles et trier:

[c] : 1

[d] : 1

[b] : 2

[a] : 4

Prenez deux plus bas: [c] & [d], et créez un nouveau noeud: [[c], [d]] : 2

Le remettre dans un ordre trié [b] : 2

[[C],[d]]: 2

[a]: 4

Prenez les deux plus basses: [b] & [[c],[d]], et faites un nouveau nœud : [[b],[[c], [d]]] : 4

[a] : 4

[[b],[[c],[d]]] : 4

Maintenant, nous sommes évidemment fait: il suffit de saisir les deux plus bas et de faire un nouveau nœud:

[[a],[[b],[[c],[d]]]] : 8

Il ne reste qu’un nœud, c’est la racine.

Maintenant je vais dessiner l’arbre afin que vous puissiez voir ce que signifie cette notation:

draw the tree so you can see what this notation means:

a / 4 / root b \ / 4 2 \ / X c \ / 2 1 \ / X \ 1 \ d

Le même que Shannon-Fano codage créé. (C’est un facile parce que les probabilités sont des puissances inverses de deux)

Codage Arithmétique Théorique (Introduction)

OK allons y. Mettez vos bottes.

Le codage arithmétique (arithcoding) est une méthode d’écriture d’un code dans une longueur non entière. Cela nous permet de coder très près de l’entropie idéale.

Rappelez-vous que le blocage de caractères ensemble peut entraîner le codage de longueurs non entières. Par exemple :

pA) = 2/3

p(B) = 1/3

Puis le code :

0 = AA

10 = AB

11 = B

Écrit A & B avec les longueurs de code idéales.

En pratique, le blocage nécessaire pour obtenir un comportement optimal peut être arbitrairement important. En outre, le blocage idéal (comme ci-dessus) est un problème difficile à résoudre en temps réel. Nous avons donc besoin d’arithcodage.

Arithcoding est basé sur ce principe: Les Numéros Réels sont très semblables aux Fichiers de Données. Permet de penser à cela et de le comprendre. Si vous avez un nombre réel, spécifié jusqu’à N chiffres, il ya encore un nombre infini de façons d’étendre hors de lui. De même pour un fichier. De plus, pour un nombre réel de N chiffres, il y a des nombres exp (N) avec ce nombre de chiffres. De même pour les fichiers. Par analogie, on peut penser à un fichier comme un nombre réel.

Par exemple, si nous connaissons la longueur de l’entrée, L (en bits), il ya 2 ^ L entrées possibles. Nous pouvons penser à chaque fichier d’entrée comme un nombre binaire (c’est ce que c’est). Par exemple: l’entrée 0101100 est équivalente au nombre binaire 0101100 (duh!). Mais, nous voulons que l’encodeur soit indépendant de la longueur, donc nous voulons utiliser la propriété d’extensibilité des nombres réels, comme mentionné ci-dessus. Donc au lieu de penser le nombre binaire comme un entier, nous penserons qu’il s’agit de la fraction binaire 0.0101100 – c’est-à-dire un point décimal est ajouté à l’extrême gauche. Maintenant, nous pouvons étendre le fichier: à 0,01011001 ou 0,01011000 sans empiéter sur d’autres nombres réels: c’est-à-dire chaque numéro doit spécifier un seul fichier.

Contrairement aux nombres réels mathématiques, on apprend combien de chiffres de précision sont dans le nombre, c’est-à-dire 0,00 n’est pas identique à 0,000 parce que le nombre de chiffres est différent; Ils spécifient des fichiers différents.

Temps pour un diagramme :

——————————————————– 8/8 1 111 +———————————– 7/8 0 110 1 +——————————————- 6/8 0 1 101 +———————————– 5/8 0 100 1 +—————————————————- 4/8 0 1 011 +———————————– 3/8 0 010 1 +——————————————- 2/8 0 1 001 +———————————– 1/8 0 000 ——————————————————– 0/8

Regardons cela de gauche à droite. Nous commençons par un intervalle à l’extrême gauche, entre les deux lignes pointillées les plus éloignées. Nous passons au premier signe ‘+’. À ce stade, nous entrons un peu dans le fichier. Cela nous indique si nous devons aller vers le haut ou vers le bas. Maintenant, nous avons coupé l’intervalle en deux, et aller d’un côté. Nous continuons à faire cela à chaque avantage. Une fois que vous avez fait cela 3 fois, aller tout le chemin à droite. Nous sommes maintenant dans un intervalle qui correspond aux 3 bits entrés. Les fractions à l’extrême droite sont équivalentes aux données entrées. Chaque triplet de données correspond à la fraction en dessous.

Il est facile de confirmer que ces fractions sont identiques à la fraction binaire des données entrées:

—– 8/8 0,111 —– 7/8 0,110 —– 6/8 0,101 —– 5/8 0,100 —– 4/8 0,011 —– 3/8 0,010 —– 2/8 0,001 —– 1/8 0,000 —– 0/8

Il est clair que ceci est équivalent à l’extrême droite du diagramme ci-dessus. De nouveau, chaque fraction binaire correspond à la fraction en dessous. Nous l’écrivons ainsi, car chaque fraction binaire correspond à l’intervalle entre les fractions au-dessus et au-dessous.

Par exemple, 010 correspond à l’intervalle (2/8, 3/8).

Cela est pratique, car toute extension de 010 sera également dans l’intervalle (2/8, 3/8): par exemple, 0100 est dans l’intervalle (4/16, 5/16) et 0101 est dans l’intervalle (5/16, 6/16): les deux étant en (2/8, 3/8).

Ok, maintenant nous avons considéré l’entrée comme une fraction binaire, pensons à la façon dont nous le compressions.

C’est vraiment très simple :

1. Premièrement, nous devons penser à la façon dont nous écrire un intervalle. Ceci est fait en écrivant n’importe quelle valeur dans cet intervalle. Nous décidons arbitrairement que le bord inférieur de l’intervalle sera dans cet intervalle, et le bord supérieur sera dans le suivant. Ainsi, pour indiquer 0.000, nous pourrions écrire 0/8 ou 1/16 ou .000000001. Nous choisissons toujours le chemin le plus court, et nous l’écrivons sous forme de fraction binaire, puisque les données informatiques sont en nombres binaires et non rationnels.

2. Deuxièmement, nous devons réaliser que les intervalles plus grands sont écrits en moins de bits. Par exemple, si A donne l’intervalle (0, 1/2) et B donne l’intervalle (1/2, 3/4) et C donne l’intervalle (3/4, 1) alors nous pouvons spécifier ces intervalles comme :

A : 0.0 – 0.1 B : 0.10 – 0.11 C : 0.11 – 1.00

Et nous pouvons les écrire comme la valeur la plus courte dans l’intervalle:

A : 0.0 : 0 B : 0.10 : 10 C : 0.11 : 11

Ne vous inquiétez pas que 1.00 est invalide (n’oubliez pas que nous utilisons toujours 0.X pour indiquer le fichier X) parce que le haut de l’intervalle est inutilisé.

En fait, vous pouvez intuitivement voir que si l’intervalle est de taille R, il peut être spécifié dans approximativement log2((1/R)) bits. Notez que cela pourrait être un entier non, et c’est très bien.

Juste pour la pratique, regardons les intervalles pour le jeu de code, (A,B,C) ci-dessus:

————————————————- 1 C CC ———————————- 15/16 B CB ———————————- 7/8 C A CA ——————————————— 3/4 C BC ———————————- 11/16 B BB ———————————- 5/8 B A BA ——————————————— 1/2 C AC ———————————- 1/8 B AB ———————————- 1/4 A A AA ————————————————- 0

Le processus est le même que précédemment: commencez par l’intervalle complet à gauche (0, 1): lorsque vous arrivez à une branche, lisez à partir de l’entrée, et prenez la branche qui correspond aux données que vous lisez. Faites de même à la deuxième branche. Une fois que vous avez lu deux, vous avez maintenant l’intervalle pour spécifier ces deux entrées. Considérez ceci comme divisant / affinant successivement l’intervalle de travail.

 Pour les entrées plus longues, vous conserverez subdivisant encore et encore.

Par exemple, pour écrire BA, vous aurez l’intervalle ( 1/2, 5/8 ) qui peut être écrit sous forme de fraction binaire 0.100 : NOT 0.1: 0.1 spécifie (B ou C) dans le premier choix: 0.10 spécifie B dans la première Choix: vous devez écrire 0.100 pour spécifier BA. Similaire 0.1010 est BB et 0.1011 BC.

Comme on sait qu’un intervalle de taille R est écrit en l = -log2 (R) bits, il est simple de voir que si R = p (la probabilité de ce caractère) alors l = -log2 (p) bits, ce qui est l’idéal. Ainsi, tout ce que nous avons à faire pour coder les données est de déterminer p, alors nous pouvons faire un processus de division de l’intervalle qui codera les données IDEALEMENT!

 Ainsi, on voit que l’exemple ci-dessus (avec A,B,C) fournira un codage idéal si et seulement si P(A) = 1/2, P(B) = 1/4 et P(C) = 1/4 Et A, B et C n’ont pas de corrélation (c.-à-d. Après A, les probabilités du caractère suivant sont les mêmes qu’après un B, même qu’après un C, ie aucun caractère n’implique rien au sujet d’un autre).

Codage arithmétique pratique avec renormalisation

La discussion ci-dessus est très agréable: mais comment faites-vous? La méthode de division d’intervalle ci-dessus fonctionnera très bien, sauf pour un problème: sur les fichiers de données volumineux, l’intervalle deviendra TRÈS petit. Trop petit pour garder un mot machine.

En fait, si vous ne vous souciez pas de la vitesse, vous pouvez utiliser la méthode ci-dessus. Cependant, la plupart d’entre nous comme la vitesse. Ainsi, nous devons conserver l’intervalle dans un mot machine entier.

Cela signifie que pour un mot de 32 bits, vous ne pouvez pas spécifier plus de précictions que 2^ (- 32).

Cependant, considérons un code plat pour l’octet: c’est-à-dire qu’un octet a des valeurs 0 -> 255 et que vous écrivez chacune avec une probabilité égale 1/256. Après un événement de codage, l’intervalle est 1/256, après un autre octet, l’intervalle est 1/65536, après 3 octets l’intervalle est 1/2^ (24) et après 4 octets l’intervalle est 2^ (- 32). YIKES! En 4 octets d’entrée nous avons utilisé notre mot machine! Nous souhaitons compresser des fichiers de plus de 4 octets !!

 Ainsi, nous avons besoin d’un moyen de garder notre intervalle d’être trop petit.

 Le secret est : Renormalisation.

Pensons-y de cette façon :

 Nous commençons par une borne basse, L, et une borne supérieure, H, pour notre gamme. En images, L est le bas du graphique et H le sommet. Maintenant, en passant par la récursion de codage (c’est-à-dire la subdivision de la plage), L et H se rapprochent et se rapprochent. Lorsque nous avons terminé, nous écrivons un nombre entre les deux (disons (L + H) / 2) et nous avons terminé. Mais, si nous représentons L et H comme une fraction binaire, comme ci-dessus, alors nous pouvons écrire des bits que nous allons: une fois que quelques-uns des bits les plus à gauche de L et H sont les mêmes, alors ils ne peuvent jamais changer.

 Par exemple: si nous voulons coder du “modèle” de:

 

————————————————- 1 B ———————————- 1/2 A ————————————————- 0

 

Et l’entrée est “ABAA” alors les codes procèdent comme suit :

 

L H Chars seen ———————————— 0.0000 0.1111 none 0.0000 0.0111 A 0.0011 0.0111 AB 0.0011 0.0101 ABA 0.0011 0.0100 ABAA

 

Une marche rapide de cette table, pour plus de clarté :

 On commence par L = 0,0000 et H = 0,1111, c’est la condition d’initialisation correspondant à la gamme complète. Ensuite, nous voyons un A, et couper la gamme en deux, en gardant la moitié inférieure. Évidemment, L ne change pas. H doit être / 2, ce qui est le même que >> 1, donc le nouveau H est 0.0111 Une autre façon de voir cela est: H a vraiment commencé à 1.0000, avec 0.0000 … 0001 soustraire. Ainsi, 1/2 = 0,1000, mais il faut soustraire 0,0000 … 00001, ce qui donne 0,0111. Maintenant, nous voyons un B, donc nous devons diviser par deux la portée vers le haut. H reste la même, et L est augmenté de moitié (H-L), ce qui est 0,0011 … Le reste suit comme cela a été fait.

 Maintenant nous pourrions écrire 0.0011 et être fait. Cependant, nous pourrions produire le premier 0 juste après le premier A: une fois que L est 0,0000 et H est 0,0111 alors on peut sortir un bit 0 et décaler les deux jusqu’à 0,000 et 0,111 ;

Nous changeons toujours un zéro en L et un un en H, donc L serait 0.0000 et H serait 0.1111 après ces changements.

 La raison pour laquelle nous changeons un 1 en H est que H n’est pas vraiment 0.1111, c’est vraiment 1.00000, mais puisque nous ne pouvons pas traiter cela, nous le traitons comme 0.11111111111111 …. qui

est équivalent à 0.9999999999 …

que nous connaissons De Math est égal à 1 (en base-dix). (Ceci doit être équivalent à Un, car s’il n’était pas égal, alors il y aurait un nombre différent qui pourrait s’insérer entre les deux).

 

Ainsi, un codeur arithmétique algorithmique simple dans les registres à 16 bits serait:

 

 Void A_Simple_Arithcoder (void) {uword L, H; L = 0 H = (1<<16) – 1; /* Il y a une décimale implicite au 16e bit, juste à gauche du mot machine */ tandis que(pluscontribution) {obtenir entrée rétrécissement L rétrécissement H /* L et H sont rétrécis basés sur des probabilités cumulatives de symboles. C’est ce qu’on appelle « l’étape de codage » */ si ( L & (1<<15) == H & (1<<15)) {sortiebit (L & (1<<15)); /* Si les bits supérieurs sont identiques, les décaler */ L <<= 1; H <<= 1; H ++; /* Décaler un dans le lieu le moins significatif de H */ } } }

 Soit dit en passant, l’étape de codage est :

Soit Sp = la probabilité de symbole Sl = la somme de toutes les probabilités de symboles, dont l’indice est inférieur au courant

R = H – L L += R * Sl H -= R * (1 – (Sl + Sp))

 Cela devrait être assez évident. En multipliant par R, on calcule simplement les probabilités dans la plage de L et H pour que Sl = 0 -> L et Sl+Sp = L -> H

 Maintenant nous sommes tous prêts à écrire un arithcoder sauf pour une chose: Sortie. Sortie est le « pire cas » pour un arithcoder de ce style (ou tout style). Cela se produit environ une fois tous les 1000 octets, mais nous devons être en mesure de le gérer, ou notre arithcoder va mourir.

 Sous-écoulement est le cas lorsque L = 0,01 … et H = 0,10 …: c’est-à-dire qu’ils se chevauchent le point milieu: L = 0,011111111 et H = 0,100000001 est le pire cas. Le problème ici est que, quelle que soit la distance divisée, les chiffres supérieurs de L et H ne seront jamais égaux tant que L et H sont égaux !!!! ( Ce n’est pas vrai si vous avez un registre de machine infiniment grand).

 Ainsi, nous devons reconnaître que L et H sont dans le cas du Sous écoulement, et faire quelque chose à ce sujet.

 

 La meilleure façon de comprendre cela est de revenir à notre précédent arithcoder et de changer la base conceptuelle. Chaque fois que le premier chiffre de L et H sont tous les deux 0, cela signifie L <1/2 et H <1/2 : lorsque nous les augmentons, ce que nous avons réellement fait est «rétréci notre étendue» de (0,1) à (0,1 / 2 : 

par exemple:

Soit Rl = la borne basse de la plage, soit Rh = la borne haute de la plage, soit Al = arithcoder basse, absolue, soit Ah = arithcoder haute, absolue Rl = 0, Rh = 1, Al = 0, Ah = 1 Procédez avec arithcodage , Shrink Al et Ah, ne vous inquiétez pas à renormalisation. Nos anciens amis L et H peuvent être trouvés à partir de: L = (Al – Rl) / (Rh – Rl) H = (Ah – Rl) / (Rh – Rl) qui est juste l ‘échelle de Al et Ah dans le Rl – Rh Cadre. C’est-à-dire que Al et Ah sont pris dans l’intervalle (Rl, Rh) alors que L et H sont dans l’intervalle (0,1) maintenant, si L < 1/2 et H < 1/2 puis Rh = Rl) / 2 + Rl en d’autres termes, si Al et Ah sont tous les deux dans la moitié inférieure de l’intervalle Rl-Rh, coupez alors l’intervalle Rl-Rh en deux, en choisissant la moitié inférieure de façon similaire, si L > 1/2 et H> 1/2 soit Rl = ( Rh – Rl ) / 2 + Rl choisissant la moitié supérieure.

 Ceci est identique à notre « codeur arithmétique simple ».

 Ce point de vue facilitera la compréhension de la solution au problème de sous-flux (qui a échappé à cet auteur depuis un certain temps), ce que l’on appelle la méthode « bit-plus-suivre ».

 C’est vraiment très simple une fois que vous savez comment le faire. Quand L & H était inférieur à 1/2, nous avons coupé la gamme en deux et avons pris le bas. Quand L & H étaient au-dessus de 1/2, nous avons coupé la gamme en deux et avons pris le dessus. Donc, quand L & H sont dans le milieu, nous avons juste coupé la gamme en deux et prendre le milieu! Comme suit:

 Si (1/4 <= L <3/4 && 1/4 <= H < 3/4) {L – = 1/4; H -= 1/4; L *= 2; H *= 2; }

 Il devrait être clair que ce segment de code réduit la plage médiane 1/2 jusqu’à la plage complète.

Maintenant, le seul problème est : comment dire le décodeur que nous avons fait cela? Modifions à nouveau notre base conceptuelle.

 Un fichier de données ressemble à une série de commandes. Le décodeur lit ces commandes et sait comment les interpréter et faire quelque chose d’utile avec eux. En codage arithmétique, nous avons deux commandes que nous pouvons envoyer au décodeur:

 0 = moitié moindre

 1 = moitié supérieure

 Puisque nous sommes en binaire, ce sont les seules commandes que nous recevons. Vous devez arrêter et penser une seconde pour être sûr que son point de vue est équivalent à notre Simple_ArithCoder qui a sorti le bit le plus à gauche des fractions binaires de L & H chaque fois qu’ils sont devenus les mêmes.

 Alors, comment envoyons-nous une commande « demi-milieu »? Eh bien, il semblerait que nous ne pouvons pas – et en effet, nous ne pouvons pas! – mais nous pouvons envoyer une commande « demi-milieu » si elle est suivie par une des autres commandes. Voyons quelques exemples:

 Que se passe-t-il si nous faisons un « demi-milieu » suivi d’un “moitie-bas”: le résultat est:

 

1 ———- 3/4 ——– initiale -> Moitié au milieu -> -> « Moitié au milieu » -> 1/2 —— gamme 1/4 ——– 1/4 —— 0 ———-

 

Le résultat net est une fourchette de (1/4, 1/2) – mais c’est la même chose que de faire un « demi-bas » suivi d’un « demi-haut » !!

Maintenant, que se passe-t-il si nous faisons un « demi-milieu » suivi d’une « moitié en deux »:

1 ———- 3/4 ——– 3/4 —— initiale -> demi-milieu -> ->

« Moitié en haut » -> 1/2 —— plage 1/4 ——– 0 ———-

 Le résultat net est une plage de (1/2, 3/4) – mais c’est la même chose que de faire une « moitié supérieure » suivie d’une « moitié inférieure » !!

 Rappelez-vous maintenant

 0 = moitié moindre

 1 = moitié supérieure

 Ainsi nous pouvons écrire algorithmiquement:

 (« demi-milieu ») puis (opération B) = (opération B) alors (opération NOT B)

 Maintenant, que faire si nous devons faire un « demi-milieu » plusieurs fois avant une opération normale? Eh bien, cela nécessite des applications multiples de l’opération! B. (Ce qui est facile à confirmer, il suffit de penser à des plages de moitié, comme ci-dessus).

 Nous avons donc cette image:

 N applications de (« demi-milieu ») alors (opération B)

 = (Opération B) puis N applications de (opération !B)

 Ainsi, chaque fois que nous voulons faire un « demi-milieu », nous incrémentons un compteur, que j’appellerai BPF, qui nous indique combien de bits opposés à la sortie.

 Maintenant, nous allons revisiter notre Simple_Arithcoder, et nous ajouterons BitPlusFollow.

Void A_Simple_Arithcoder_Number1 (void) {uword L,H; Int b,bpf; Bpf = 0; L = 0 H = (1<<16) – 1; /* Il y a une décimale implicite au 16e bit, juste à gauche du mot machine

* / tandis que(plus sortie) {obtenir entrée rétrécissement L rétrécissement H /* L et H sont rétrécis basés sur des probabilités cumulatives de symboles. C’est ce qu’on appelle l’étape de codage * / if (L & (1<<15) == H & (1<<15)) {b = L & (1<<15); Outputbit (b); If (bpf) {tandis que (bpf–) {outputbit (!b); }} /* Si les bits supérieurs sont identiques, les décaler * / L << = 1; H << = 1; H ++; = / 0 (x) = (x) = (x) = 0 xx (x) = 0 x1 + 01 et les deux premiers bits de H sont 10 puis ils chevauchent le milieu et nous avons besoin de faire un “demi-milieu” */ bpf ++; / * Cela fait que le – = 1/4 * / L & = (1<<14) -1; H | = (1<<14); L << = 1; H << = 1; H ++; ……

C’est une façon de le faire, en utilisant une approche très peu orientée. Regardons d’une autre façon:

Void A_Simple_Arithcoder_Number2 (void) {ulong One, moitié, Quart,troisquarts; Ulong L, H; Int b, bpf; Bpf = 0; Un = (1 << 16); Demi = un / 2; Trimestre = moitié / 2; Trois trimestres = demi + trimestre; L = 0 H = un à 1; tandis que(Plus d’entrées) {obtenir entrées) & rétrécir L, H si (L> = Demi) {b = 1 outputbit (b); si (bpf) {tandis que (bpf–) {outputbit (! B); }} L – = moitié; H – = moitié; L *= 2; H *= 2; H ++; } autrement si(H < moitié) (b = 0 outputbit (b); si (bpf) {tandis que (bpf–) {outputbit (!b); }} L *= 2; H *= 2; H ++; } autrement si(L> = Quart && H < Trois quarts) {bpf ++; /* Ceci fait le – = 1/4 */ L – = trimestre; H – = trimestre; L *= 2; H *= 2; H ++; } } }

Eh bien, c’est tout. Il y a quelques choses à noter :

 1. Notez que nous utilisons <= et >= pour le bas de la plage, mais < et > pour le haut de la plage. Il est essentiel que vous choisissiez une frontière pour être “in” et une pour être “out” – ils ne peuvent pas tous les deux être “dans” la gamme.

 2. Notons que X + = X est équivalent à X *= 2 et X << = 1 et que la méthode de X + = X est la plus rapide sur la plupart des architectures.

 3. Notons que H est REALEMENT (H + 1), et que H < One toujours, et qu’un bit 1 est décalé dans H au lieu d’un bit 0 (c’est-à-dire H ++)

 

 

Allez ici pour quelques autres notes sur le calcul arithcoding / decoding de nombres finis:

Email on integer coding  

Charles Bloom / cb sur mon domaine

Back to the Index

 

John Miller
Follow us

John Miller

John has worked in investment banking for 10 years and is the main author at 7 Binary Options. He holds a Master's degree in Economics.
John Miller
Follow us

Leave a Reply

Your email address will not be published. Required fields are marked *