Differences

This shows you the differences between two versions of the page.

--- tanszek:oktatas:infrendalapjai_architekturak:informacio_feldolgozas:toemoerites [2024/11/12 12:49] – knehez
+++ tanszek:oktatas:infrendalapjai_architekturak:informacio_feldolgozas:toemoerites [2024/11/15 18:01] (current) – knehez
@@ Line 1: / Line 1: @@
+===== Adattömörítő eljárások =====
 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.
@@ Line 37: / Line 38: @@
 $$ 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?
+===== Huffman kódolás =====
-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.
+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.
-$$ L = \frac{2}{4} \cdot 2 + \frac{2}{8} \cdot 3 + \frac{4}{16} \cdot 4 = 2.75. \, \, [bit] $$
+=== A Huffman-kódolás lépései ===
+  - Számoljuk ki az egyes karakterek előfordulási gyakoriságát az adatban.
+  - Építsünk bináris fát a gyakorisági adatok alapján.
+  - 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.
+=== Huffman-kódolási példa ===
+Kódoljuk a következő szöveget: ''BACADAEAFABBAAAGAH''
+== Gyakoriságok meghatározása ===
+^Karakter^Gyakoriság^
+|A|9|
+|B|3|
+|C|1|
+|D|1|
+|E|1|
+|F|1|
+|G|1|
+|H|1|
+Készítsük el a bináris fa leveleit úgy, hogy zárójelben feltüntetjük a gyakoriságokat:
+{{:tanszek:oktatas:infrendalapjai_architekturak:informacio_feldolgozas:pasted:20241112-131521.png}}
+Válasszuk ki a két legkisebb gyakoriságú levelet és vonjuk össze az alábbiak szerint:
+{{:tanszek:oktatas:infrendalapjai_architekturak:informacio_feldolgozas:pasted:20241112-131623.png}}
+Vonjuk össze a F és G leveleket is ugyanígy:
+{{:tanszek:oktatas:infrendalapjai_architekturak:informacio_feldolgozas:pasted:20241112-190312.png}}
+Vonjuk össze a D és E leveleket is ugyanígy:
+{{:tanszek:oktatas:infrendalapjai_architekturak:informacio_feldolgozas:pasted:20241112-190334.png}}
+Most a középső két levél tartalmazza legkisebb gyakoriságot, ezért vonjuk őket össze:
+{{:tanszek:oktatas:infrendalapjai_architekturak:informacio_feldolgozas:pasted:20241112-190444.png}}
+Most a B és a jobb oldali 2-vel jelölt levél tartalmazza legkisebb gyakoriságot, ezért ezeket vonjuk össze:
+{{:tanszek:oktatas:infrendalapjai_architekturak:informacio_feldolgozas:pasted:20241112-190541.png}}
+Most vonjuk össze az utolsó két megmaradt levelet:
+{{:tanszek:oktatas:infrendalapjai_architekturak:informacio_feldolgozas:pasted:20241112-190619.png}}
+A végén ez a fa lesz az eredmény:
+{{:tanszek:oktatas:infrendalapjai_architekturak:informacio_feldolgozas:pasted:20241112-190643.png}}
+=== Bináris kód hozzárendelés a fa leveleihez ===
+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.
+^Karakter^Bináris kód^
+|A|0|
+|B|100|
+|C|1100|
+|D|1110|
+|E|1111|
+|F|1010|
+|G|1011|
+|H|1101|
+Az eredmény a következő lesz:
+<code>BACADAEAFABBAAAGAH -> 100|0|1100|0|1110|0|....|1101</code>
+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.
+===== LZW kódolás =====
+Ennél a módszernél, nem kell tudni a forrásadatokban szereplő szimbólum gyakoriságokat. Menet közben gyűjtünk információt a forrásszimbólumokról. Az LZW kódolás az úgynevezett adaptív kódok csoportjába tartozik.
+=== Algoritmusa ===
+Kiindulásként a kódtáblázat tartalmazza a forrás összes előforduló elemét.
+A kódoláskor az éppen aktuális pozíciótól kezdve addig olvassuk be a soron következő szimbólumokat egy bufferbe (**b**), amíg a sorozat szerepel a szótárban. Ha a soron következő karakter (**c**) az első olyan elem, amelyre **bc** már nem szerepel a szótárban, akkor **b** indexe lesz a soron következő kód a szótárban és a szótárt **bc**-vel bővítjük és **c** karaktertől folytatjuk a kódolást.
+Ezt a tömör leírást egy példa alapján tesszük érthetővé.
+=== Példa ===
+Kódoljuk a következő sorozatot LZW kódolással:
+''dabbacdabbacdabbacdabbacdeecdeecdee''
+Megvizsgálva az adatforrást, látható hogy csak 5 különböző szimbólumból áll: (a,b,c,d,e). A szótárt kezdetben ezzel az 5 elemmel töltjük fel.
+   - A kódoló először **d** karaktert veszi.
+   - A **d** benne van a szótárban, így hozzáilleszti a következő, az **a** karaktert.
+   - A **da** már nem szerepel jelenleg a szótárban, ezért:
+     - **d** 4-es indexét lejegyzi
+     - felveszi a szótárba **da** részszöveget a 6. bejegyzésbe és megy tovább **a**-val folytatva.
+   - Az **a** szerepel a szótárban, ezért hozzáveszi a következő **b** elemet, és mivel **ab** nem szerepel a szótárban, így a indexét az 1-et lejegyzi, majd **ab**-t 7. elemként a szótárhoz illeszti az algoritmus. A kódolás végén a következő indexek jelennek meg:
+''4,1,2,2,1,3,6,8,10,12,9,11,7,16,4,5,5,11,21,23,5''
+^index^bejegyzés^
+|1|a|
+|2|b|
+|3|c|
+|4|d|
+|5|e|
+|6|da|
+|7|ab|
+|8|bb|
+|9|ba|
+|10|ac|
+|11|cd|
+|12|dab|
+|13|bba|
+|14|acd|
+|15|dabb|
+|16|bac|
+|17|cda|
+|18|abb|
+|19|bacd|
+|20|de|
+|21|ee|
+|22|ec|
+|23|cde|
+|24|eec|
+|25|cdee|
+A Unix **compress** parancsa és a **GIF** (Graphics Interchange Format) képtömörítő eljárás is az **LZW** algoritmust alkalmazza.
+===== RLE kódolá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''
+=== Kódolva ===
+''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.