Differences

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

--- tanszek:oktatas:infrendalapjai_architekturak:informacio_feldolgozas:toemoerites [2024/11/12 19:12] – [Huffman kódolás] 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 53: / Line 54: @@
 ^Karakter^Gyakoriság^
-|A|7|
+|A|9|
 |B|3|
 |C|1|
@@ Line 59: / Line 60: @@
 |E|1|
 |F|1|
-|G|2|
+|G|1|
 |H|1|
@@ Line 115: / Line 116: @@
 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.