Informatika 9-12. évfolyam | Sulinet Tudásbázis

Tananyag választó:

LZW működése

Tegyük fel, hogy példánkban az input képpont négy különböző értéket vehet fel. Tehát az alap kódtábla legyen a következő:
<math display="block" xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <mtable> <mtr> <mtd> <mn>0</mn> </mtd> <mtd> <mi>a</mi> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mi>b</mi> </mtd> </mtr> <mtr> <mtd> <mn>2</mn> </mtd> <mtd> <mi>c</mi> </mtd> </mtr> <mtr> <mtd> <mn>3</mn> </mtd> <mtd> <mi>d</mi> </mtd> </mtr> </mtable> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math>
Input jelsorozat: 01012101010000000

LZW algoritmus (Lempel-Ziv-Welch)

Az algoritmus kiszűri az ismétlődő karakterláncokat, és ezeket azonosító kódra cseréli. Ebből következik, hogy az LZW kód csak akkor hatékony, ha a karakterláncok ismétlődése nagy. A kódtábla generálása dinamikus, dekódoláskor pedig egy alap kódtáblából építi fel a teljes kódtáblát.
Pl. egy 8 bit/pixel színmélységű kép esetén az alaptábla 2 a 8-adikon, azaz 256 bejegyzést tartalmaz. A kódolás folyamán karakterláncként fogjuk fel a pixelsorozatokat, és megvizsgáljuk, hogy az adott sorozat benne van-e a kódtáblában.

LZW kódtábla előállítása

LZW dekódoló

A kódolás során keletkező dinamikus táblában előállítunk menetközben felesleges kódokat is, de mivel csak az alap kódtáblát tároljuk, ezért ez nem okoz gondot.
Dinamikus kódtábla:
<math display="block" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow>
<mtable columnalign="left">
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mn>01</mn>
</mrow>
</mtd>
<mtd columnalign="left">
<mi>e</mi>
</mtd>
</mtr>
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mn>10</mn>
</mrow>
</mtd>
<mtd columnalign="left">
<mi>f</mi>
</mtd>
</mtr>
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mn>012</mn>
</mrow>
</mtd>
<mtd columnalign="left">
<mi>g</mi>
</mtd>
</mtr>
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mn>21</mn>
</mrow>
</mtd>
<mtd columnalign="left">
<mi>h</mi>
</mtd>
</mtr>
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mn>101</mn>
</mrow>
</mtd>
<mtd columnalign="left">
<mi>i</mi>
</mtd>
</mtr>
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mn>1010</mn>
</mrow>
</mtd>
<mtd columnalign="left">
<mi>j</mi>
</mtd>
</mtr>
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mn>00</mn>
</mrow>
</mtd>
<mtd columnalign="left">
<mi>k</mi>
</mtd>
</mtr>
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mn>000</mn>
</mrow>
</mtd>
<mtd columnalign="left">
<mi>l</mi>
</mtd>
</mtr>
<mtr columnalign="left">
<mtd columnalign="left">
<mrow>
<mn>0000</mn>
</mrow>
</mtd>
<mtd columnalign="left">
<mi>m</mi>
</mtd>
</mtr>

</mtable>
</mrow>
<annotation encoding="MathType-MTEF">
</annotation>
</semantics></math>
Ezek után adódik az output kódsorozat: abecfiakla

Hierarchikus tömörítés

A hierarchikus tömörítés a képet kétdimenziós területnek tekinti, és rekurzívan osztja fel négy részre. Ha az így kapott területek inhomogének, akkor továbbosztjuk, ha homogének, akkor megjegyezzük a színértéket. Az osztásnál mindig ugyanazt a körüljárási irányt követjük. A végeredményt legegyszerűbben egy négyágú fa adatszerkezettel ábrázoljuk.

Hierarchikus tömörítés

Négyes fa adatszerkezet