2.6 Arithmetische Komprimierung (1982)

Nachteil von Huffman: nur ganzzahlige Codelängen.
Jetzt: ordne den Symbolen disjunkte Teile des Intervalls [0..1[ zu:

P(x) unten oben

a 0.14 0.00 0.14

b 0.04 0.14 0.18

c 0.07 0.18 0.25

d 0.11 0.25 0.36

e 0.44 0.36 0.80

f 0.04 0.80 0.84

g 0.06 0.84 0.90

h 0.10 0.90 1.00

unten   := 0.0;
oben    := 1.0;
bereich := 1.0;

repeat
  
   x := get_char();
   
   unten := unten + bereich * untere_grenze(x);
   oben  := unten + bereich * obere_grenze(x);
   bereich := oben - unten

until x = EOF;

putstring(unten); /* Nachricht */

Beispiel für ``Chef''

unten oben bereich

c 0.18 0.25 0.07

h 0.243 0.25 0.007

e 0.24552 0.2486 0.00308

f 0.247984 0.2481072 0.0001232

Nachricht: 0.247984 (18-Bit Unsigned Integer)
(Huffman: 1011 1111 0 11100 = 14 Bit)

arithmetische Dekomprimierung

getstring(y);
repeat
   x := suche_passendes_intervall(y);
   put_char(x);
   bereich := obere_grenze(x) - untere_grenze(x);
   y := (y - untere_grenze(x))/bereich;
until x = EOF

Beispiel für Nachricht y = 0.247984

Intervall Symbol bereich (y - untere Grenze)/bereich

0.18-0.25 c 0.07 0.9712

0.90-1.00 h 0.10 0.7120

0.36-0.80 e 0.44 0.8000

0.80-0.84 f 0.04 0.0000

Rechenintensiver als Huffman.
Zur Implementation verwendet man Integer-Arithmetik.
Identische, führende Ziffern bei unterer und oberer Schranke können bereits ausgegeben und dann entfernt werden.

'hhhhhh' arithmetisch komprimiert ergibt 0.9 + 0.1 * 0.9 + 0.9 * 0.01 + 0.9 * 0.001 + ... = 0.999999 = 20 Bit Integer

'hhhhhh' Huffman komprimiert ergibt 1111 1111 1111 1111 1111 1111 = 24 Bit

Beispiel: Zwei Zeichen haben die Wahrscheinlichkeiten 0.9 bzw. 0.1

unten oben

a 0.0 0.9

b 0.9 1.0

Codierung von aaaaaaab ergibt:

unten oben bereich

a 0.0 0.9 0.9

a 0.0 0.81 0.81

a 0.0 0.729 0.729

a 0.0 0.6561 0.6561

a 0.0 0.59049 0.59040

a 0.0 0.531441 0.531441

a 0.0 0.4782969 0.4782969

b 0.4304672 0.4782969 0.0478297

Wähle als Nachricht eine Zahl aus dem letzten Intervall, z.B. 0.45. Also werden 8 Zeichen mit 6 Bit übertragen.

Mark Nelson:

100.000 mal '0' ergibt arithmetisch komprimiert 3 Bytes!
nach Huffman 100.000 Bits = 12500 Bytes)