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

Tömörítési kódolás

Hol van a tömörítés határa? Készítette: Brit Cruise.

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.

Videóátirat

Amikor digitálisan ábrázolunk információt, például egy képet, akkor azt apró részekre kell felosztanunk. Ez lehetővé teszi azt, hogy egy képet színek jelsorozataként küldjünk el. Ezeket a színeket egyedi számokkal jelöljük valamilyen kód alapján. Vegyük az alábbi feladatot! Alíz és Bob üzenetek tudnak bináris formában továbbítani és fogadni. (morze jelek) Bitenként 1 pennyt kérnek rendszerhasználati díjként. Megjelenik egy régi ügyfelük, aki üzenetet akar küldeni. Az üzenet 1000 jelből áll. Az üzenet jelentése teljesen ismeretlen. Ezt általában szabványos 2-bites kódban küldték el, ami 2000 bites tarifát jelent. De Alíz és Bob korábban elemezték az ügyfél üzeneteit, és megállapították, hogy az üzenetben eltérő az egyes jelek előfordulási valószínűsége. Fel tudják-e használni ezeket az ismert valószínűségeket az átvitel tömörítésére, hogy így növeljék a hasznukat? Mi az optimális kódolási stratégia? David Huffman híres optimális stratégiáját 1952-ben jelentette meg. Azon alapult, hogy alulról épített egy bináris fát. Kiindulásként felsoroljuk az összes jelet, ezeket csomópontnak hívjuk. Kiválasztjuk a két legvalószínűtlenebb csomópontot, ebben az esetben B-t és C-t, összevonjuk azokat egy csomóponttá, és összeadjuk a valószínűségüket. Ezután megint kiválasztjuk a két legvalószínűtlenebb csomópontot, és addig folytatjuk az összevonásokat, amíg a tetején egyetlen csomópont marad. Végül megjelöljük a fa éleit tetszőleges sorrendben 0-val és 1-gyel. Minden betű kódja az útvonal a fa tetejétől az adott betűig. Az A csupán egy él, azaz 1. Ezt Huffman kódolásnak hívják, és az ilyen típusú példákra nem fogsz hatékonyabb megoldást találni. Próbáld meg! Például, ha a D kódját lerövidíted 0-ra akkor a 011 üzenet jelenthet DAA-t, de jelenthet B-t is. Ahhoz, hogy működjön, a betűk közé betűközt kell illeszteni, ami lenullázza, amit megspórolsz az átvitelnél. Mennyire tömöríti ez az eljárás az üzenetet az eredeti 2000 bithez képest? Ehhez ki kell számolni a betűnként szükséges bitek átlagos számát. Megszorozzuk az egyes kódok hosszát az előfordulás valószínűségével, ezeket összeadjuk, ami 1,75 bit/jel átlagos hosszat eredményez. Ez azt jelenti, hogy Huffman kódolással az üzenetet várhatóan 2000 bitről 1750 bitre tudjuk tömöríteni. Claude Shannon volt az első, aki azt állította, hogy a tömörítés határa megegyezik az üzenet forrásának entrópiájával. Ahogy csökken a forrás entrópiája vagy bizonytalansága ismert statisztikai struktúra alapján, úgy növekszik a tömöríthetőség. (morze jelek) Ha az entrópia növekszik a megjósolhatatlanság miatt, a tömöríthetőség is csökken. (morze jelek) Ha az entrópián túl akarunk tömöríteni, törvényszerűen veszítünk az üzenet információtartalmából.