Tömörítés : Algoritmusok : Statisztikai Programozóknak

Posted on

Szerző: Charles Bloom

Bevezetés

Statisztikai kódolók vagy a gerincét tömörítés. Az első megköveteli egy egyszerű modell kompresszor:

( NYERS ) BEMENET -> KOMPRESSZOR -> OUTPUT ( SEBESSÉGVÁLTÓ )

( SEBESSÉGVÁLTÓ ) BEMENET -> KICSOMAGOLÓ -> OUTPUT ( NYERS )

Az alapgondolat : a kompresszor kitalálja, mit bemenet, írja kevesebb bitet a kimenet, ha helyesen tippelt. Vegye figyelembe, hogy a kicsomagoló, képesnek KELL lennie arra, hogy ugyanazt gondolom, mint a kompresszor, annak érdekében, hogy helyesen dekódolni az adás, mivel az átviteli más, attól függően, hogy a jóslat.

Jelenleg azonban csak az érintett a “statisztikai kóder”. Ez egy olyan algoritmus, amely kódolja vagy dekódolja egy karakter, egy bitek száma arányos a -log2(becsült valószínűség). Vegye figyelembe, hogy ez lehet kerek a bitek száma vagy kódolás extra – mindaddig, amíg ezt próbálja elérni, ez egy statisztikai programozó.

Például, ha a NYERS adatokat lehet egy négy karakterek : a,b,c vagy a d gombbal, valamint a statisztikai coder azt mondta (a többi kompresszor) elvárható, hogy akkor jelentkezik, 50% – ában, b fordul elő, 25% – ában, c fordul elő, 25% – a, d fordul elő, szinte soha, akkor szeretnénk, hogy a kód a következőképpen:

1 picit a (-log2(.5) = 1)
2 bit a b & c (-log2(.25) = 2)

például:

a : 0
b : 10
c : 11

megjegyzendő, hogy sok egyéb lehetőségek (pl. {1,01,00},{1,00,01},{0,11,10}) – csak az számít, hogy a hossza a kódok lesz olyan jó, mint lehetséges
Lehet, hogy a “NYERS” IO, mint egy statisztikai coder, amely szerint minden szimbólum azonos a valószínűsége. Így vannak 256 értékek egy byte, minden adott egy egyenlő a valószínűsége, p = 1/256,- log2(1/256) = 8 bit.

A tipikus szöveg (mint ez), a SZÓKÖZ karaktert, majd az ” e “fordul elő nagyon gyakran, így kell írni néhány bit (3), míg a” q ” fordul elő gyakran, szóval nem lesz írva több bit (12).

Egy másik módja annak, hogy nézd meg a cél, hogy a statisztikai coder: képzeld el, hogy a bemeneti csak két szimbólumok, illetve A B (ez teljesen általános, mivel minden byte bontható a bit). Legyen p(A) a tényleges valószínűsége A. Mert csak ez a két szimbólum, p(A) + p(B) = 1, p(B) = 1 – p(A). Hagyd, hogy L(a) = # bit használt írni, L(b) = # bit használt írni b (megjegyzendő, hogy ezek NEM egész szám). Így a cél az, hogy minimalizálja a funkció

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

p(A) & p(B) adott, L(A) & L(B) korlátozza az a tény, hogy a kód dekódolható (azaz L(A)=L(B)=0 NEM érvényes, sem az L(A)=L(B)=0.5)

Látható, hogy az értékek, amelyek minimálisra csökkentik a L a következők:

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))

Így L csak attól függ, p(A) (vagy p(B), ha úgy tetszik).

Lehet, hogy csoda : hogy lehet, hogy L nem egész szám? Nos, az egyik válasz az, hogy : “az aritmetikai kódolás”, amely fogunk beszélni később. Egy másik, egyszerűbb a válasz : “blokkoló”.

Blokkolás, ha kombináljuk a két szomszédos szimbólum együtt annak érdekében, hogy lehetővé teszi a relatív kód hosszúságú. Például, hogy Egy B az egyetlen bemeneti jelek (bináris bemenet). Ha a kódolás beállítása:

AA : 0
AB : 10
BA : 110
BB : 111

Aztán van írva (a) 0.7 bit, a B-ben írt arról, 1.4 bit.

Kimutatták, hogy ha N szimbólumok blokkolva vannak együtt, a kódolás inefficieny miatt egész kód hossz határol :

(Extra hosszúságú, egy szimbólum) <= 1/N bit

Ok. Ez a vége a intro statisztikai kódolás. Ezt követően menjünk át a Shannon-Fano kódolás, Huffman kódolás, majd az Aritmetikai kódolás.

KIEGÉSZÍTÉS :
A cél, hogy a statisztikai kód kód szimbólumok a Shannon-order0-entrópia. Kérjük, tekintse meg a hír hozzászólásokat az entrópia.


Kódolási Algoritmusok

Emlékszem, a példa:

a : 0
b : 10
c : 11
Lehet kérni, hogy egy ilyen kód megérkezett. Könnyű, hogy fogalmilag egy kis abc, azonban, hogyan lehetne egy nagy ábécé? Nyilvánvalóan azt akarjuk, hogy egy általános célú iteratív vagy rekurzív algoritmus.

Ez a folyamat szükséges, hogy minden egész szám hosszúságú prefix-kódok.

Egy prefix kód egy olyan, hogy nem része egy kód az előtag a másik. Ez szükséges ahhoz, hogy egyszerű dekódolás. Például:

a : 0
b : 01
c : 10
NEM prefix-szabad kód. Ha a dekóder látta, hogy a string “0010” nem tudom, hogy ez volt “a,b,a” vagy “a,a,c” .

Egy másik példa egy NEM prefix kód :

a : 0
b : 01
c : 11
a string “00111” KELL “a,b,c” azonban a dekóder nem mondja meg azonnal, ha kezdődik, mint az “a” vagy “b” – azaz egy kódot nem lehet dekódolni, amíg után később is vizsgálják. Ez a fajta dekódolás el kell kerülni.

a : 0
b : 10
c : 11
Egy prefix kód. Nem string egyértelmű. “0010”: “a,a,b”, illetve “00111”: “a,b,c”, illetve a dekóder lehet mondani, ez azonnal.

Most már kívánom, hogy hozzon létre egy ilyen előtag-kódok. Hogyan csináljuk? Megtörjük a folyamat két lépésből áll:

1. Határozza meg a hossza a kódokat. ha Li a hossza, az i-edik kód Hadd Ei = Li – (- log2 (Pi) ), ahol Pi a valószínűsége, hogy az i-edik kód Ei az Extra hosszúságú írva minden szimbólum, azaz a hosszát, ami meg van írva, ami nem szükséges. Szeretnénk felvenni a hossz, hogy minimalizálják az összeg a Pi*Ei . Ez logikus, mert a Pi a occurance aránya én, Ei a felesleges hossz, így az összeg a Pi*Ei a teljes kimeneti hossza, amely hosszabb, mint szükséges.

2. Hozzon létre egy prefix kód azoknak a kód hossza.

1. lépés teljesítve a Shannon-Fano kódolás, vagy a Huffman kódolás. Ezek szó később. Amennyire Lépés 2 illeti, ilyen messzire lehet keletkezett.

Kraft Egyenlőtlenség

Kiderült, hogy egy prefix-kód csak azért létezik, hogy a kódokat:

K = Sum( i = 0, N), 2^(-Li) <= 1

Ez a Kraft egyenlőtlenség. Bizonyítéka ez a megállapítás túlmutat a papírt. Azonban vedd figyelembe, hogy Li = -log2(Pi) + Ei

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

Így K = Sum( i = 0, N ) a Pi / 2^(Ei)

Kép az egyszerű esetben, ahol Ei = E én

Így K = Sum( i = 0, N ) a Pi / 2^(E) = [ Sum( i = 0, N ) a Pi ] / 2^E

de [ Sum( i = 0, N ) a Pi ] = 1

Így K = 1 / 2^E

Szóval a Kraft egyenlőtlenség áll, 1/ 2^E <= 1 1 = 2^0

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

-E <= 0

E >= 0

Az eredmény : A Kraft egyenlőtlenség azt mondja, hogy egy kód decodeable HA PEDIG CSAK akkor, a kód hossza nagyobb vagy egyenlő, mint az határozza meg, hogy az entrópia.

Ez kell, hogy jó értelemben.

Generál egy Prefix-Ingyenes Kód

Két módszer kerül bemutatásra. Egy egyszerű, intuitív, gyakorlatias, élvonalbeli.

Az első nagyon egyszerű. Csak hozzon létre egy bináris fa, a szimbólumok, mint például, hogy a mélység a fa a kód hossza.

Például :
L(a) = 1
L(b) = 2
L(c) = 2

Aztán, hogy a fa:

  
      a
    /
root      b
    \   /
      X
        \ 
          c


Most traverse a fa. Minden fel-ág egy kicsit. Minden le ág nulla kicsit. A teremtés, ez a fa egy viszonylag egyszerű algoritmus.

A második módszer gyors, de létrehoz egy abc-sorrendben-a megrendelt kódot. Én bűzcsomag megvitatására, de lehet, hogy nézd meg a Huffman forráskód, hogy ellenőrizze.


Shannon-Fano Kódolás

Shannon-Fano kódolás egy módszer, amellyel az a kód hossza egy prefix kód.

Az alap ötlet között Huffman & S-F kódolás :
mert minden kimeneti fenntartja ugyanarra a térre, minden kicsit kellett volna azonos a valószínűsége.

Gondoljunk egy kód, mint egy bináris fa, mint a fent leírt. A fenti kijelentés, az ugyanaz, mintha azt mondanánk, hogy minden csomópont a fa, a fenti ág, az alábbi ág kellett volna, hogy az azonos valószínűséggel előforduló.

Például egy normál 8 bites byte, egy teljesen szimmetrikus fa. Néhány ágat hozott gyakran, néhány venni, szinte soha. Például, a szöveg, a felső ág a gyökér szinte soha nem vett (azaz ASCII karakterek ne menj át 127).

Így minden kód-hossza generáló algoritmusok egy módon terjed karakterek több, mint egy bináris fa olyan, hogy a siker egyenlő át minden ág.

Képzeld el, hogy tudjuk, egy occurance számít minden szimbólum : azaz, ha a bemeneti string (aabbaac), akkor a occurance számít:
C(a) = 4
C(b) = 2
C(c) = 1
Akkor azt szeretnénk, hogy a fa:

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

A számot minden ága jelzi, hogy az összeg gyakorisága számít a “részfa” : azaz a fa, hogy a csomópont, mint a gyökér.
Láthatjuk, hogy az egyes ága, a grófok NEM egyenlő, akkor is, ha azok közel azonos lehetséges. Ez azt jelenti, hogy egy egész szám-hossz kód szöveg szub-optimális. Ha az értéke egyenlő, akkor a kód nem olyan jó, mint az entrópia.

Honnan tudjuk, hogy egy ilyen fa? Ez könnyű.

Minden karakter, mindegyik egy szám tartozik, a csomópontok, amelyek kapcsolódnak a semmi. Hívja ezt a set S0. Hadd C(S0) = összessége számít S0.

Vidd a csomópont a legmagasabb szám, tedd bele a set S1. Most C(S0) alacsonyabb.

Addig folytatjuk, amíg a C(S1) >= C(S0). Most már osztott az adatok imigyen:

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

Most, [S1], mint a kiindulási pont, osztott be [S2] , [S1]. Ugyanezt [S0] , hogy a [S3] , [S0] . Addig folytatjuk, amíg A készlet csak egy-egy tag, ekkor egy levél csomópont.

Én nem egy példa a forgatáson:

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

húzza ki a

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

számít egyenlő, ne épület S1

S1 csak egy tagja van, abba S1

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

húzza ki a b, hogy S2

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

számít egyenlő, ne épület S2

S2 csak egy tagja van, abba S2

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

hagyd, S2 = {c} , S0 = {d}, aztán végeztünk.

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

Ami az ideális kód beállítása.
Ez az úgynevezett Shannon-Fano kódolás.


Huffman Kódolás

Megállapították, hogy a Shannon-Fano kódolás kissé szub-optimális egyes esetekben.

Így a Huffman-kód a legjobb, amely már az egész hosszúságú kódokat.

> Hopá!!! A leírás a Huffman kódolás! <

Itt van, nagyjából : ahelyett, hogy egy előre-passz, mint a Shannon-Fano, egy visszafelé át készült. A Shannon-Fano létrehoztunk egy fa kezdve az összes karakter, a gyökér, akkor megszegi őket két csoportra, recursing le. A Huffman, kezdjük az összes karakter, a “Ki a fa” , a “jó” oldalon, azaz a múlt a levelek. Akkor hozz egy kis karakter lesz a legtöbb levelek. Akkor vegyünk még, hogy a szülő csomópont, megtalálni az utat vissza a root. A gyakorlatban azonban vége kicsit másképp :

Egy listát az összes karakter, tedd a levél csomópontok, minden csomópont egy szám egyenlő a gróf a karakter. Ezek a csomópontok jelenleg nincs szülők vagy a gyermekek (soha nem lesz gyereke). Most felejtsük el, hogy ezek a karakterek, csak hívja őket csomópontok számít. Valahogy őket úgy, hogy azok a legkisebb is számít! Fogd meg a két legkisebb szám csomópontok, hogy egy új csomópont, mint a szülőnek a kettő közül, valamint beállíthatjuk, hogy a gróf az új csomópont összegével egyenlő a gyermek számít. (látod, mennyire vagyunk recursing visszafelé felépíteni a fát). Most, az új csomópont a rendezett lista a csomópontok, a helyes sorrendje helyzetben. A két csomópont, amelyet a gyerekek már nincsenek a listán (azaz a lista egyre rövidebb egy csomópont). Ismételje addig, amíg a lista csak egy tag – ez a gyökér!

Most egy példát, az egyik már a Shannon-Fano:

[a] : 4
[b] : 2
[c] : 1
[d] : 1
Majd használja a [] jelzi, egy csomópont, tehát [[x],[[y],[z]]] egy csomópont két gyerekkel, az egyik egy levél [x] lehetőséget , majd egy két gyermeke van saját, [y] , [z]. [x] : N azt jelenti, hogy a gróf, hogy csomópont N.

Inicializálja a kódolás: viszont a karakter a levél csomópontok & sort :

[c] : 1
[d] : 1
[b] : 2
[a] : 4
Fogd meg két legalacsonyabb : [c] & [d] , majd egy új csomópont : [[c],[d]] : 2
tedd vissza rendezetten [b] : 2
[[c],[d]] : 2
[a] : 4
fogd meg a két legalacsonyabb : [b] & [[c],[d]] , hogy egy új csomópont : [[b],[[c],[d]]] : 4
[a] : 4
[[b],[[c],[d]]] : 4
Most már nyilvánvaló : csak fogd a két legalacsonyabb pedig, hogy egy új csomópont:

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

Csak egy csomópont bal, ez a root.

Most rajzolok a fát, hogy lássa, mit ez a jelölés azt jelenti, hogy:

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

Ugyanaz, mint a Shannon-Fano kódolás létre. (ez könnyű, mert a valószínűségek inverz hatáskörét két)


Elméleti Aritmetikai Kódolás (Bevezetés)

Oké, itt vagyunk. Tedd a mocsári csizma.

Aritmetikai Kódolás (arithcoding) egy módszer, írok egy kódot nem egész hossza. Ez lehetővé teszi számunkra, hogy a kód nagyon közel az ideális entrópia.

Emlékezzünk vissza, hogy blokkolja a karakterek együtt eredményezheti, hogy a kódolás nem egész szám hosszúságú. Például:


Р(А) = 2/3


p(B) = 1/3



akkor a kód :


0 = AA


10 = AB


11 = B


Írja A & B ideális hosszúságú kód.

A gyakorlatban, a blokkoló szükség, hogy optimális viselkedés lehet tetszőlegesen nagy. Is, ideális-blokkoló (mint fent) egy nehéz problémát kell megoldanunk valós időben. Így kell arithcoding.

Arithcoding az ezen elv alapján : Valós Számok nagyon hasonló Adatokat. Gondoljuk ezt megérteni. Ha van egy valós szám, megadott fel, hogy N számjegy, akkor még mindig végtelen számú módon kiterjeszteni. Hasonlóképpen egy fájlt. Is, egy valós szám N számjegy, exp(N) számok ezzel a számjegyek száma. Hasonlóképpen a fájlokat. Ennek analógiájára, hogy kitalálunk egy fájlt, mint egy valós szám.

Például, ha tudjuk, hogy a hossza a bemeneti, L (bit), 2^L lehetséges bemenetek. Mi jut minden egyes bemeneti fájlt, mint egy bináris szám (ez a baj). Például : a bemeneti 0101100 egyenértékű, hogy a bináris szám 0101100 (naná!). De azt akarjuk, hogy a kódoló, hogy a hossz-független, így szeretnénk használni, a bővíthetőség ingatlan valós számok, mint a fent említett. Szóval ahelyett, hogy arra gondolsz, hogy a bináris szám, mint egy egész szám, akkor gondolj rá úgy, mint a bináris frakció 0.0101100 – azaz egy tizedes ponttal egészül ki, hogy a bal szélen. Most már tudjuk kiterjeszteni a fájlt : 0.01011001 vagy 0.01011000 anélkül, hogy összeütközésbe más valós számok, azaz : minden szám egyedileg kell adnia egy fájlt.

Ellentétben a matematikai valós számok, tudjuk, hány számjegy pontosságú a szám, azaz 0.00, nem ugyanaz, mint 0.000 mert a számjegyek száma más; ezek határozzák meg a különböző fájlokat.

Ideje egy ábra:

-------------------------------------------------------- 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

Nézzük csak meg ezt a balról jobbra. Kezdjük egy intervallum a bal szélen, a két legtávolabbi szaggatott vonalak. Tovább az első ‘+’ jel. Ezen a ponton bemeneti egy kicsit a fájlt. Ez azt mondja, hogy menni felfelé vagy lefelé. Most, vágjuk az intervallum ketté, egyik oldalon. Ezt fogjuk csinálni minden egyes plusz. Egyszer tette ezt 3-szor, az a helyes. Most egy intervallum, amely megfelel a 3 bit lettek megadva. A frakciók a jobb szélen, vagy ezzel egyenértékű, hogy a bevitt adatokat. Egyes adatok triplett megfelel a töredéke alatt.

Könnyen megerősítik, hogy ezek a frakciók ugyanaz, mint a bináris-töredéke a bevitt adatok:

----- 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

Egyértelmű, hogy ez egyenértékű a jobb szélen a fenti ábra is. Újra, minden bináris frakció megfelel a töredéke alatt. Írjuk így, mert minden bináris frakció megegyezik az intervallum között a frakciók, alul, felül.

Például, 010 megegyezik az intervallum ( 2/8 , 3/8 ).

Ez kényelmes, mert minden kiterjesztése 010 is az intervallum ( 2/8 , 3/8 ) : például 0100 ez az intervallum ( 4/16 , 5/16 ) 0101 az intervallum ( 5/16 , 6/16 ) : mindkettő a ( 2/8 , 3/8 ).

Ok, most már úgy vélte, hogy a bemenet egy bináris frakció, gondoljuk át, hogyan szeretnénk tömöríteni.

Ez nagyon egyszerű :

1. először is, meg kell gondolni, hogyan fog írni egy intervallum. Ezt írásban BÁRMELY érték be az időközt. Mi önkényesen dönt arról, hogy az alsó széle az intervallum belsejében, hogy az intervallum, a felső széle lesz a következő. Így jelzi 0.000 írhatnánk ki 0/8, vagy 1/16 vagy .000000001 . Mindig válassza ki a legrövidebb utat, majd írni, mint egy bináris tört, mivel a számítógépes adatok bináris, nem racionális számok.

2. Másodszor, el kell ismernünk, hogy nagyobb időközönként vannak írva kevesebb bit. Például, ha Egy ad a várakozási idő ( 0 , 1/2 ), valamint B ad az intervallum ( 1/2 , 3/4-es), illetve a C ad az intervallum ( 3/4 , 1 ), akkor megadhatja, hogy ezeket időközönként, mint :

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

mi lehet írni őket, mint a legrövidebb érték be a szünetben :

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

Ne aggódj, hogy 1.00 érvénytelen (ne feledje, hogy mindig használja a 0.X jelzi, az X fájl), mert a tetején az intervallum nem használt.

Sőt, ösztönösen látom, hogy ha az intervallum mérete R, meg lehet határozni, hogy körülbelül log2((1/R)) bit. Vegye figyelembe, hogy ez nem egész szám, ami rendben is van.

Csak a gyakorlatban, nézzük meg időközönként a kód beállítása, (A,B,C) fenti :

------------------------------------------------- 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

A folyamat ugyanaz, mint korábban : kezdjük a teljes
intervallum bal (0,1) : ha egy ág,
olvassa el az input, az ág, amely megfelel
az adatok, olvasd el. Ugyanezt a második ág.
Egyszer azt olvastam, hogy két, most van az intervallum, hogy
adja meg a két bemenet. Hiszem, hogy ez egymás után
elosztjuk/finomítás a dolgozó-intervallum.

Tovább bemenet, folyamatosan tovább osztják vége
aztán vége.


Például, hogy írjon BA volna az intervallum
( 1/2 , 5/8 ), ami lehet írni, mint bináris frakció 0.100 :
NEM 0.1 : 0.1 meghatározza (B vagy C) az első választás : 
0.10 meghatározza a B az első választás : hogy kell írni
0.100, hogy meghatározza BA. Similary 0.1010 a BB 0.1011 a BC.

Mivel tudjuk, hogy egy intervallum mérete R van írva l = -log2(R)
bit, egyszerű látni, hogy ha R = p (a valószínűsége
ez a karakter), akkor l = -log2(p) bit, amely az ideális.
Ezért csak annyit kell tennünk, hogy a kód adatait kell kitalálni, p, akkor
lehet, hogy egy folyamat elosztjuk az intervallum, amely kód
az adatok IDEÁLIS!


Tehát, azt látjuk, hogy a fenti példában (A,B,C) biztosítja
ideális kódolás, ha P(A) = 1/2, P(B) = 1/4, P(C) = 1/4
pedig A,B & C nincs összefüggés (azaz, miután Egy, a valószínűségek
a következő karakter ugyanaz, mint a után B, akárcsak után egy C;
azaz nincs karakter azt jelenti, valamit egy másik).

Gyakorlati Aritmetikai Kódolás a Renormálás 

A fenti vita mind nagyon szép, de hogyan csinálod ?
Az intervallum-osztály módszer fenti nagyszerűen működik, kivéve
egy probléma : a nagy adat fájlok, az intervallum lesz NAGYON
kicsi. Túl kicsi ahhoz, hogy ne egy gép szót.

Sőt, ha nem érdekel a sebesség, akkor használja a fenti
módszer. Azonban a legtöbben, mint a sebesség. Így kell tartanunk
az intervallum egy egész gép szót.

Ez azt jelenti, hogy egy 32 bites szó, nem adja meg többet
precicision, hogy 2^(-32).

Azonban, fontolja meg egy lapos kód, byte : azaz egy byte-nak
értékek 0 -> 255 te írsz minden egyenlő valószínűséggel, 1/256.
Aztán egy kódolási esemény, az intervallum 1/256 után
egy másik byte, az intervallum 1/65536 után 3 bájt az intervallum
1/2^(24) után 4 byte-intervallum 2^(-32).
A MINDENIT! A 4 byte bemeneti használtuk fel a gép a szót!
Szeretnénk tömöríti a fájlokat több mint 4 bájt!!

Ezért szükségünk van egy módja annak, hogy tartsa az intervallum attól, hogy túl kicsi.

A titok : Renormálás.

Gondoljuk meg :

kezdjük egy alacsony kötött, L, valamint egy felső határ, H a tartományban.
Képszerűen, L az alsó grafikon, H a tetején. Most, mint
keresztül megyünk a kódolás rekurzió (én.e tovább osztják, a tartomány) L
H közelebb, közelebb. Ha végeztünk, akkor írj a
szám a kettő között (mondjuk (L+H)/2) végeztünk. De, ha
képviseli L, H, mint egy bináris frakció, mint a fenti, akkor tudunk írni
ki a biteket vagyunk : ha néhány maradt-a legtöbb bit L H a
azonos, akkor soha nem változik.

például :
ha azt akarjuk, hogy a kód a "modell":

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

a bemenet "ABAA", akkor a kódok eljárni, mint:

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

Egy gyors séta az asztalnál, extra világosság :

kezdjük azzal, L = 0.0000 H = 0.1111 , ez az inicializálás
állapota megfelelő, a teljes tartományban.
Aztán még Egy, aztán kivágták a tartomány fele, miközben az alsó fele.
Nyilvánvaló, hogy L nem változik. H kell /2 , ami ugyanaz, mint a >> 1,
szóval az új H 0.0111 egy Másik módja annak, hogy lásd ezt: H tényleg elkezdődött
a 1.0000 , a 0.0000…0001 vonjuk le. Így, 1/2 = 0.1000 , de
meg kell vonjuk le 0.0000….00001 , amely 0.0111
Most már látjuk, hogy a B, tehát meg kell felezni a tartomány felfelé. H ugyanaz marad,
pedig L-kal nőtt a fele (H-L) , ami 0.0011 …
A többi követi, mint ez volt.

most írhatnánk ki 0.0011 meg lehet tenni. Azonban lehet,
van kimenet az első 0, miután az A : ha L
0.0000, H 0.0111 akkor tudjuk kimenet 0 kicsit, majd a shift
mindkét akár 0.000, 0.111 ;

Mi mindig a shift egy nulla a L egy be H, L lenne
0.0000, H lenne 0.1111 után ezek a változások.

Az oka, hogy a shift 1-be H ez H nem igazán 0.1111 ,
nagyon 1.00000 , de mivel ezt nem lehet elviselni, kezelni,
mint 0.11111111111111 …. ami egyenértékű 0.9999999999 …
ami tudjuk, hogy a Matematika egyenlő 1 (alap-ten). (ez kell
egyenértékű Egy, mert ha nem egyenlő, akkor ott
lenne egy másik szám, amely alkalmas a kettő között).

Így egy egyszerű algoritmikus arith-coder a 16 bites regiszterek:

void A_Simple_Arithcoder(void)
{
uword L,H;

L = 0
H = (1<<16) - 1; /* there is an implicit decimal place at the 16th bit,
                   just to the left of the machine word */

while ( MoreInput )
  {
  get input

  shrink L
  shrink H
  /* L and H are shrunk based on symbol cumulative probabilities.
       this is called the "coding step" */

  if ( L & (1<<15) == H & (1<<15) )
    {
    outputbit ( L & (1<<15) );

    /* if the top bits are the same, shift them out */

    L <<= 1;
    H <<= 1;
  
    H ++;

    /* shift a one into the least-significant place of H */
    }
  }

}

Mellesleg, a kódolási lépés :

let Sp = a jel valószínűség
let Sl = az összeg az összes szimbólum valószínűsége, akinek index
alacsonyabb, mint a jelenlegi

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

Ez elég nyilvánvaló. Szaporodnak R csak a mérleg
valószínűségek be a tartományban, L, H, így Sl = 0 -> L
pedig Sl+Sp = L -> H

Most már készen állunk, hogy írjon egy arithcoder, egy dolgot kivéve :
UnderFlow. UnderFlow a "legrosszabb esetben" egy arithcoder a
ez a stílus (vagy bármilyen stílus). Megtörténik egyszer minden 1000 byte,
de tudnunk kell kezelni, vagy a arithcoder meg fog halni.

Underflow az az eset, amikor L = 0.01 ... H = 0.10 ... : azaz ők
stradle a középpont : L = 0.011111111 H = 0.100000001 a
legrosszabb esetben. A probléma itt az, hogy nem számít, mennyi a tartomány
osztott, a felső számjegye L, H soha nem lesz egyenlő, míg L, H
egyenlő !!!! ( ez nem igaz, ha van egy végtelenül nagy
gép nyilvántartás).

Így, el kell ismerni, hogy a L, H a underflow ügyben,
tenni valamit ellene.

A legjobb módja annak, hogy megértsük ezt, hogy visszatérjen az előző arithcoder
majd módosítsa a fogalmi alapon. Amikor az első számjegy a L, H
mindkét 0 , ez azt jelenti, L < 1/2, H < 1/2 : amikor skála őket,
mi igazán tettek az "összement a tartomány" (0,1) (0,1/2) :

például:

let Rl = az alacsony köteles a range
let Rh = a magas köteles a range
let Al = arithcoder alacsony , abszolút
let, Ah = arithcoder magas, abszolút

Rl = 0 , Rh = 1 , Al = 0, Ah = 1

Folytassa arithcoding, pszichiáter Al, Ah, ne aggódj
abour renormálás.

A régi barátok L, H megtalálható a :
L = ( Al - Rl ) / ( Rh - Rl )
H = ( Ah - Rl ) / ( Rh - Rl )

ami csak méretezés Al, Ah a Rl-Rh keret. azaz Al, Ah
veszik, hogy az intervallum (Rl,Rh), míg a L, H a az intervallum
(0,1)

most, ha L < 1/2, H < 1/2, akkor hagyd, hogy Rh = ( Rh - Rl ) a / 2 + Rl

más szóval, ha Al, Ah, mind az alsó fele
a Rl-Rh intervallum, majd vágjuk a Rl-Rh intervallum fél, kiválasztása
az alsó fele

hasonlóképpen, ha L > 1/2, H > 1/2 hadd Rl = ( Rh - Rl) a / 2 + Rl

válassza ki a felső fele.

Ez azonos az "egyszerű számtani encoder".

Ez a nézőpont könnyebb lesz megérteni, hogy a megoldás
a underflow probléma (ami elkerülte a szerző egy ideje)
amely az úgynevezett "kis plusz" módszer.

Ez tényleg elég egyszerű, ha tudod, hogyan kell csinálni. Ha L & H
voltak kisebb, mint 1/2 , levágjuk a tartomány fele vette az alján. Ha
L & H felett 1/2, levágjuk a tartomány fele került a tetejére.
Szóval, ha L & H közepén, hagyjuk már ezt a tartományt fél
középen! A következőképpen:

( 1/4 <= L < 3/4 && 1/4 <= H < 3/4 )

{

L -= 1/4; H -= 1/4;

L *= 2; H *= 2;

}

Világossá kell tenni, hogy ez a kód szegmens mérleg a középső 1/2 tartomány akár a teljes tartományban. Most már csak az a probléma : hogyan mondd meg a dekódoló, hogy mi tette ezt? Nézzük újra változtatni a fogalmi alapon. Egy adatfájl, mint egy sor parancsot. A dekóder olvassa ezeket a parancsok, tudja, hogyan kell értelmezni őket & valami hasznos őket. Az aritmetikai kódolás, két parancsot tudunk küldeni, hogy a dekóder:

0 = halve lower
1 = halve upper

Mivel a bináris, csak ezek a parancsok kapunk. Kéne
állj meg egy percre, hogy győződjön meg róla, hogy a nézőpont egyenértékű
a Simple_ArithCoder, amely kiadott a bal szélső bit bináris
frakciók L & H ha ők lettek a régi.

Szóval, hogyan tudjuk küldeni “felezi középső” parancs? Nos, úgy tűnik, hogy
nem tudjuk – sőt, nem tudjuk!!! – de tudunk küldeni egy “felezi középső”
parancs, ha követi egyik a másik parancsok. Tudassa velünk
nézd csak néhány példa:

Mi van, ha tényleg egy “felezi középső” követi “felezi alacsonyabb” : a
eredmény:

1 ----------

                             3/4 --------

initial   -> halve middle ->               -> "halve lower" ->   1/2 ------
range 
                             1/4 --------                        1/4 ------

0 ----------

A nettó eredmény egy sor (1/4 , 1/2) – de ez ugyanaz, mint a “half lower” követi “half upper”!!

Most mi történik, ha egy “halve middle” követi “half upper” :

1 ----------

                             3/4 --------                        3/4 ------

initial   -> halve middle ->               -> "halve upper" ->   1/2 ------
range 
                             1/4 --------                      

0 ----------


A nettó eredmény egy sor (1/2 , 3/4) – de ez ugyanaz, mint csinál
“half upper”, majd egy “half lower”!!

Most már emlékszem,
0 = halve lower (alsó felére csökkentik)

1 = halve upper (felső felére csökkentik)

Így tudjuk írni algoritmikusan :

(“Felezi Közepén”), akkor (a művelet B) = (operation B), akkor (a művelet NEM B)

Most mi van, ha kell egy “Felezi Középső” többször előtt
a normális működés? Nos, ez igényel több alkalmazások
a !B műveletet. (ez könnyű, hogy erősítse meg, gondoljunk csak a tartományok
hogy felére csökken, mint fent).

Így van ez a kép:

N alkalmazások (“Felezi Közepén”), akkor (a művelet B)

= (operation B), akkor N alkalmazások (akció !B)

Úgyhogy, amikor azt akarjuk, hogy “csökkentsük a felére Középső”, csak növekmény egy számláló,
ami felhívom BPF, ami azt mondja nekünk, hogy hány ellenkező bit kimenet.

Most, akkor majd visszatérünk a Simple_Arithcoder, majd a hozzáadás BitPlusFollow.

void A_Simple_Arithcoder_Number1 (void)
{
uword L,H;
int b,bpf;

bpf = 0;

L = 0
H = (1<<16) - 1; /* there is an implicit decimal place at the 16th bit,
                   just to the left of the machine word */

while ( MoreInput )
  {
  get input

  shrink L
  shrink H
  /* L and H are shrunk based on symbol cumulative probabilities.
       this is called the "coding step" */

  if ( L & (1<<15) == H & (1<<15) )
    {
    b = L & (1<<15);
    outputbit ( b );
    if ( bpf )
      {
      while( bpf-- )
        {
        outputbit ( !b );
        }
      }
      

    /* if the top bits are the same, shift them out */

    L <<= 1;
    H <<= 1;
  
    H ++;

    /* shift a one into the least-significant place of H */
    }
  else if ( (L>>13) == 0x1 && (H>>13) == 0x2 )
    {
    /* if the top two bits of L are 01 and the top two bits of H are 10
       then they straddle the middle and we need to do a "halve middle" */

    bpf ++;

    /* this does the -= 1/4 */
    L &= (1<<14)-1;
    H |= (1<<14);

    L <<= 1;
    H <<= 1;
    H ++;
    }
  }

}

Ez egy módszer, segítségével egy nagyon kicsit-orientált megközelítés. Hadd nézd meg egy másik módja:

void A_Simple_Arithcoder_Number2 (void)
{
ulong One,Half,Quarter,ThreeQuarters;
ulong L,H;
int b,bpf;

bpf = 0;

One = (1<<16);
Half = One/2;
Quarter = Half/2;
ThreeQuarters = Half + Quarter;

L = 0
H = One - 1;

while ( MoreInput )
  {
  get input & shrink L,H

  if ( L >= Half )
    {
    b = 1
    outputbit ( b );
    if ( bpf )
      {
      while( bpf-- )
        {
        outputbit ( !b );
        }
      }

    L -= Half;
    H -= Half;
      
    L *= 2;
    H *= 2;
  
    H ++;
    }
  else if ( H < Half )
    {
    b = 0
    outputbit ( b );
    if ( bpf )
      {
      while( bpf-- )
        {
        outputbit ( !b );
        }
      }

    L *= 2;
    H *= 2;
  
    H ++;
    }
  else if ( L >= Quarter && H < ThreeQuarters )
    {
    bpf ++;

    /* this does the -= 1/4 */
    L -= Quarter;
    H -= Quarter;

    L *= 2;
    H *= 2;

    H ++;
    }
  }

}

Nos, erről van szó. Van egy pár dolog amit meg kell jegyeznünk :


1. vegye figyelembe, hogy használjuk,<= and >= az a legolcsóbb, de a < and > 
a felső tartományban. Nagyon fontos, hgy úgy döntött, egy határ, hogy
"in" , egy "out" - mindkettő nem lehet "in" tartomány.


2. vegye figyelembe, hogy X += X egyenértékű X *= 2, X <<= 1, illetve, hogy a módszer
X += X a leggyorsabb a legtöbb architektúrán.


3. Vegye figyelembe, hogy H a (H + 1), valamint azt is, hogy a H < mindig, hogy
1 kicsit eltolódott a H helyett 0 bit (azaz H++ )


Eredetileg egy http://www.cbloom.com/algs/statisti.html. Készítette http://hunsci.com