Institute of Information Science - University of Miskolc

User Tools

Site Tools

Trace:
tanszek:oktatas:infrendalapjai_architekturak:informacio_feldolgozas:toemoerites

Differences

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

Link to this comparison view

Next revision		Previous revision
tanszek:oktatas:infrendalapjai_architekturak:informacio_feldolgozas:toemoerites [2024/11/12 12:48] – created kneheztanszek: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. 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]$$ $$ 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 bithosszával \( \mu_i \). +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. 
 + 
 +=== 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.
  
-$$ L = \frac{2}{4} \cdot 2 + \frac{2}{8} \cdot 3 + \frac{4}{16} \cdot 4 = 2.75. $$ 
tanszek/oktatas/infrendalapjai_architekturak/informacio_feldolgozas/toemoerites.1731415709.txt.gz · Last modified: 2024/11/12 12:48 by knehez