This is an old revision of the document!
A tömörítő eljárások lényege: olyan változó szóhosszúságú kódot választunk, hogy a sokszor előforduló szimbólumokhoz rövidebb, míg a ritkábbakhoz hosszabb kódot rendelünk.
Shannon-Fano eljárás
Egyszerű adattömörítési eljárás, amelynek lényege az, hogy:
- A továbbítandó szimbólumokat valószínűség szerint rendezzük.
- 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.
- Az eljárást addig folytatjuk, míg el nem fogynak szimbólumok.
Példa
| Szimbólum | Valószínűség | Kód | Szóhossz |
|---|---|---|---|
| X1 | 0.25 | 00 | 2 |
| X2 | 0.25 | 01 | 2 |
| X3 | 0.125 | 100 | 3 |
| X4 | 0.125 | 101 | 3 |
| X5 | 0.0625 | 1100 | 4 |
| X6 | 0.0625 | 1101 | 4 |
| X7 | 0.0625 | 1110 | 4 |
| X8 | 0.0625 | 1111 | 4 |
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]$$
Mekkora az átlagos szóhosszúság?
Az átlagos szóhosszúságot így számoljuk ki: \( L = \sum\limits_{i=1}^{n} p_i \cdot \mu_i \) ahol n szimbólumunk van és \( p_i \) az i. szimbólum valószínűsége szorozva az i. szimbólum \( \mu_i \) bithosszával.
$$ L = \frac{2}{4} \cdot 2 + \frac{2}{8} \cdot 3 + \frac{4}{16} \cdot 4 = 2.75. \, \, [bit] $$