Institute of Information Science - University of Miskolc

Egyszerű adattömörítési eljárás, amelynek lényege az, hogy:

1. A továbbítandó szimbólumokat valószínűség szerint rendezzük.
2. A szimbólumhalmaz két lehetőség azonos valószínűségű részhalmazra bontjuk. Az egyikhez 0, a másikhoz 1 szimbólummal kezdődő szót rendelünk.
3. Az eljárást addig folytatjuk, míg el nem fogynak szimbólumok.

8 szimbólumot használunk a kódolásnál, amelynek egyes szimbólumai a táblázatban megadott valószínűséggel szerepelnek a küldendő üzenetben. Ezeket előfordulási gyakoriság alapján csökkenő sorrendbe rendeztük, azaz a leggyakoribbak vannak elől. A harmadik oszlopban hozzárendeltük változó hosszúságú kódokat, a gyakoriakhoz hosszabbakat.

A 8 szimbólum teljes eseményrendszert alkot, hiszen egymást kizáró eseményekből áll, valamint a szimbólumok előfordulási valószínűségeik összege 1.

Tömörítsük az X2 X3 X8 X7 X1 üzenetet:

Az eredmény:

011001111111000

A tömörítés nélkül az üzenet hossza 4 * 5 azaz 20 bit lett volna. A tömörítés után 15 bitre csökkent.

Számítsuk ki a kód entrópiáját.

$$ H = - (\frac{2}{4}log\frac{1}{4} + \frac{2}{8} log \frac{1}{8} + \frac{4}{16} log \frac{1}{16}) = 2.75 \,\, [bit]$$

A Huffman kódolás egy veszteségmentes adatkompressziós algoritmus, amely a gyakrabban előforduló szimbólumokhoz rövidebb, míg a ritkábban előfordulókhoz hosszabb kódokat rendel. Ez az előfordulási gyakoriság alapján történik az adatban. Az eljárás optimális, mert a legkisebb átlagos kódhosszt eredményezi.

1. Számoljuk ki az egyes karakterek előfordulási gyakoriságát az adatban.
2. Építsünk bináris fát a gyakorisági adatok alapján.
3. Rendeljünk bináris kódokat minden karakterhez a fa szerkezetét követve, biztosítva, hogy a gyakoribb karakterek rövidebb kódokat kapjanak.

Kódoljuk a következő szöveget: BACADAEAFABBAAAGAH

Készítsük el a bináris fa leveleit úgy, hogy zárójelben feltüntetjük a gyakoriságokat:

Válasszuk ki a két legkisebb gyakoriságú levelet és vonjuk össze az alábbiak szerint:

Vonjuk össze a F és G leveleket is ugyanígy:

Vonjuk össze a D és E leveleket is ugyanígy:

Most a középső két levél tartalmazza legkisebb gyakoriságot, ezért vonjuk őket össze:

Most a B és a jobb oldali 2-vel jelölt levél tartalmazza legkisebb gyakoriságot, ezért ezeket vonjuk össze:

Most vonjuk össze az utolsó két megmaradt levelet:

A végén ez a fa lesz az eredmény:

A bináris fa létrehozása után, rendeljük a levelekhez a kódokat, felülről lefelé haladva balra mozdulva 0-val, jobbra mozdulva 1-el egészítjük ki a kódot.

Az eredmény a következő lesz:

BACADAEAFABBAAAGAH -> 100|0|1100|0|1110|0|....|1101

Hasonló módon készül el a végleges kód, mint a Shannon-Fano kódolás esetén, csak itt a fa készítés segít a bináris hozzárendelés elkészítésében.

megjegyzés: a | karakter természetesen nincs benne az eredményben, itt csak az átláthatóság miatt szerepel, ebben a módszerben sincs és nem is kell elválasztó jelzés.

Run-Length Encoding (RLE) – futáshossz kódolás.

A fentiekhez képes nagyon egyszerű, de mégis a gyakorlatban széleskörben használt kódolás.

Egyszerű tömörítési eljárás, amely a hosszasan ismétlődő azonos karaktereket, biteket egyetlen szimbólummal és egy ismétlésszámmal kódolja. Fekete-fehér képek tömörítésére használták korábban, de a TGA, PCX formátumok, valamint a FAX gépek is használják, textúra tömörítéshez is jó lehet. Példa alapján könnyen érthető.

Kódoljuk a következő karaktereket RLE kódolással:

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWW

12W1B12W3B24W1B14W

Melynek értelmezése: 12 darab W, 1 darab B, 12 darab W, 3 darab B, stb.

Így tehát a Run-Length Encodinggal kódolt szöveg az eredeti 67 karaktert 18-cal írja le. Természetesen a valóságban nem karakterekkel, hanem bináris kóddal használják.