If you're seeing this message, it means we're having trouble loading external resources on our website.

Ha webszűrőt használsz, győződj meg róla, hogy a *.kastatic.org és a *.kasandbox.org nincsenek blokkolva.

Fő tartalom

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.

A Huffman-kódolási algoritmus

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:
agcttttcattct
Mivel négy karaktert kell ábrázolnunk, a számítógép minden karaktert 2 bittel fog ábrázolni, például:
karakterbináris kód
a00
c01
g10
t11
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.
100 111 111 111 000 000 000 000
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:
karakterbináris kód
a010
c00
g011
t1
Ekkor a 13 karakterünk a következőképpen lenne kódolva:
100 110 011 110 000 000 000
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!

A Huffman-dekódolás

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.
Próbáld ki!
Dekódold az alábbi biteket az optimalizált bináris kódok segítségével!
111 001
karakterbináris kód
a010
c00
g011
t1
Győződj meg róla, hogy a bal oldali első résznél kezded, és hogy a kódokat balról jobbra haladva illeszted egymáshoz. Milyen DNS sztringet kaptál?
Válassz egyet:

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.

A Huffman-kódolás alkalmazásai

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!

Szeretnél részt venni a beszélgetésben?

Még nincs hozzászólás.
Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.