Veszteségmentes bittömörítés

A számítógépek minden adatot binárisan ábrázolnak, így a szövegektől a képeken át a videókig minden fájltípus végső soron bitek sorozatából áll. Függetlenül attól, hogy a bitek dokumentumokat vagy GIF-eket ábrázolnak, a számítógépek képesek egy bizonyos, Huffman-kódolásnak nevezett bittömörítési technikát alkalmazni.

Nézzük meg egy egyszerű szöveges példán keresztül, hogyan is működik a Huffman-kódolás! Ebben a példanyelvben mindössze négy különböző karakter van, mégis hihetetlenül fontos számunkra: ez a DNS ábrázolására használt nyelv, amely az A, C, G és T karakterek sorozataiból áll.

Például az E.coli DNS-szekvencia 4,6 millió karaktere így kezdődik:

Mivel négy karaktert kell ábrázolnunk, a számítógép minden karaktert 2 bittel fog ábrázolni, például:

Alább láthatod, hogyan írnánk ki a fenti 13 karaktert 26 bit felhasználásával. Figyeld meg, hogy az egyes bitek kódjai között nincs szükség helykihagyásra.

Viszont ennél jobbat is tudunk! A fenti rövid példában a „t” betű gyakrabban fordul elő, mint a többi betű (a „t” 7-szer, a „c” 3-szor, az „a” kétszer, a „g” pedig csak egyszer). Ha rövidebb kódot adnánk a „t”-nek, akkor az esetek 54%-ában (13 karakterből 7-szer) kevesebb helyet használna fel. Például használhatjuk a következő kódokat:

Ekkor a 13 karakterünk a következőképpen lenne kódolva:

Ez mindössze 22 bit, négy bittel kevesebb, mint az eredeti kódolásunk. Lehet, hogy ez nem tűnik soknak, de képzeld el, mi lenne akkor, ha egy ilyen optimalizálást alkalmaznánk a DNS összes, 4,6 millió karakterére!

Lehet, hogy szöget ütöttek a fejedbe ezek a különböző hosszúságú, új bináris kódok. Lehetséges-e még mindig megbízhatóan dekódolni őket? Lehetséges, abban az esetben, ha megfelelő kódokat használunk.

Pontosan ez a Huffman-kódolás szépsége: az algoritmus lehetővé teszi, hogy egy adott szekvenciához olyan bináris kódokat találjunk, amelyek biztosítják az adatok egyértelmű és megbízható rekonstruálhatóságát.

Sok fájlformátum használ valamilyen Huffman-kódolást a fájl méretének csökkentésére. A faxkészülékek a Huffman-kódolást az RLE használata után a fekete-fehér futamokon használják. A PNG-képek tömörítéskor az LZ77 algoritmust használják, amely hasonló a tanult szövegtömörítési technikához, de ezzel együtt az eredményeken Huffman-kódolást végez.

🙋🏽🙋🏻‍♀️🙋🏿‍♂️Kérdésed van a témával kapcsolatban? Szívesen válaszolunk, csak kérdezz alább, a „Kérdések” részben!