Huffman kód

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. január 8-án felülvizsgált verziótól ; az ellenőrzések 27 szerkesztést igényelnek .

A Huffman algoritmus egy mohó algoritmus egy ábécé optimális előtagkódolására minimális redundanciával . 1952 -ben fejlesztette ki David Huffman , az MIT végzős hallgatója , miközben dolgozatát írta . Jelenleg sok adattömörítő programban használják .

A Shannon-Fano algoritmussal ellentétben a Huffman algoritmus mindig optimális marad a kettőnél több karaktert tartalmazó m 2 másodlagos ábécék esetében.

Ez a kódolási módszer két fő lépésből áll:

Optimális kódfa felépítése.
Kód-szimbólum leképezés készítése a felépített fa alapján.

A klasszikus Huffman-algoritmus

Az algoritmus gondolata a következő: ismerve a karakterek előfordulási valószínűségét az üzenetben, leírható az egész számú bitből álló változó hosszúságú kódok felépítésének eljárása. A karakterekhez nagyobb valószínűséggel rövidebb kódokat rendelnek. A Huffman-kódok előtag tulajdonsággal rendelkeznek (azaz egyetlen kódszó sem egy másik előtagja), amely lehetővé teszi azok egyértelmű dekódolását.

A klasszikus Huffman-algoritmus bemenetként egy táblázatot kap az üzenetben szereplő karakterek gyakoriságáról . Ezen túlmenően a táblázat alapján egy Huffman kódoló fa (H-fa) készül. [egy]

A bemeneti ábécé karakterei a szabad csomópontok listáját alkotják. Minden levélnek van súlya, amely egyenlő lehet a tömörítendő karakter előfordulási valószínűségével vagy számával az üzenetben.
Két szabad facsomópont kerül kiválasztásra a legkisebb súllyal.
Szülőjük összsúlyával megegyező súllyal jön létre.
A szülő hozzáadódik a szabad csomópontok listájához, és a két gyermeke törlődik ebből a listából.
A szülőből kimenő egyik ív 1. bitre, a másik 0. bitre van állítva. A gyökérből érkező ágak bitértékei nem függenek a gyerekek súlyától.
A másodiktól kezdődő lépéseket addig ismételjük, amíg csak egy szabad csomópont marad a szabad csomópontok listájában. A fa gyökerének fogják tekinteni.

Tegyük fel, hogy van a következő abszolút gyakorisági táblázatunk:

Szimbólum	DE	B	NÁL NÉL	G	D
Abszolút Frekvencia	tizenöt	7	6	6	5

Ez a folyamat felfogható úgy, mint egy fa felépítése, amelynek gyökere a szimbólum az utolsó lépés szimbólumainak kombinálásával kapott kombinált szimbólumok valószínűségeinek összegével, n 0 leszármazottja az előző lépés szimbólumai, és így tovább .

Az üzenetben szereplő karakterek kódjának meghatározásához az aktuális karakternek megfelelő fa levelétől a gyökeréig kell mennünk, és biteket halmozva haladunk a fa ágai között (az útvonal első ága a legkisebb jelentőségű bitnek felel meg). Az így kapott bitsorozat az adott karakter kódja, fordított sorrendben írva.

Egy adott karaktertáblázat esetében a Huffman-kódok így fognak kinézni.

Szimbólum	DE	B	NÁL NÉL	G	D
A kód	0	100	101	110	111

Mivel a kapott kódok egyike sem a másik előtagja, a folyamból történő kiolvasáskor egyértelműen dekódolhatók. Ezenkívül az A üzenet leggyakoribb szimbóluma a legkevesebb bittel, a legritkább D szimbólum pedig a legnagyobb bittel van kódolva.

Ebben az esetben a táblázatban megadott szimbólumokból álló üzenet teljes hossza 87 bit lesz (átlagosan 2,2308 bit szimbólumonként). Egységes kódolás esetén az üzenet teljes hossza 117 bit lenne (karakterenként pontosan 3 bit). Megjegyzendő, hogy a meghatározott frekvenciájú szimbólumokat egymástól függetlenül generáló forrás entrópiája ~2,1858 bit/szimbólum, vagyis az ilyen forráshoz szerkesztett Huffman-kód redundanciája , ami a szimbólumonkénti bitek átlagos száma és a bitek átlagos száma közötti különbséget jelenti. entrópia, kisebb, mint 0,05 bit egy szimbólumon.

A klasszikus Huffman-algoritmusnak számos jelentős hátránya van. Először is, a tömörített üzenet tartalmának visszaállításához a dekódolónak ismernie kell a kódoló által használt frekvenciatáblázatot. Ezért a tömörített üzenet hossza megnő az adatok előtt elküldendő gyakorisági táblázat hosszával, ami meggátolja az üzenet tömörítésére irányuló erőfeszítéseket. Ezen túlmenően ahhoz, hogy a tényleges kódolás megkezdése előtt teljes frekvenciastatisztikával rendelkezzen, az üzeneten két alkalommal kell átmenni: az egyik az üzenetmodell felépítéséhez (frekvenciatábla és a H-fa), a másik pedig a tényleges kódoláshoz. Másodszor, a kódolási redundancia csak azokban az esetekben szűnik meg, amikor a kódolt szimbólumok valószínűsége 2 inverz hatványa. Harmadszor, 1-nél nem nagyobb entrópiájú forrás esetén (például bináris forrás esetén) a Huffman-kód közvetlen alkalmazása. értelmetlen.

Adaptív tömörítés

Az adaptív tömörítés lehetővé teszi, hogy ne vigye át vele együtt az üzenetmodellt, és csak egy lépésre korlátozódjon az üzeneten mind a kódolás, mind a dekódolás során.

Az adaptív Huffman kódolási algoritmus létrehozása során a legnagyobb nehézségek a modell következő karakterrel történő frissítésére szolgáló eljárás kidolgozásakor merülnek fel. Elméletileg a Huffman kódolófa teljes felépítését egyszerűen be lehetne illeszteni ebbe az eljárásba, azonban egy ilyen tömörítési algoritmusnak elfogadhatatlanul alacsony a teljesítménye, mivel egy H-fa felépítése túl sok munka, és ésszerűtlen megtenni a feldolgozás során. minden karakter. Szerencsére van mód egy már meglévő H-fa módosítására, hogy tükrözze egy új karakter feldolgozását. A legismertebb újraépítő algoritmusok a Voller-Gallagher-Knuth (FGK) és a Witter algoritmus.

A fa következő karakter olvasásakor történő újraépítésére szolgáló összes algoritmus két műveletet tartalmaz:

Az első a fa csomópontjainak súlyának növelése. Először eggyel növeljük az olvasott karakternek megfelelő lap súlyát. Ezután növeljük a szülő súlyát, hogy az összhangba kerüljön a gyerekek új súlyaival. Ez a folyamat addig folytatódik, amíg el nem érjük a fa gyökerét. A súlynövekmény átlagos száma megegyezik a karakter kódolásához szükséges bitek átlagos számával.

A második műveletre - a fa csomópontjainak permutációjára - akkor van szükség, ha egy csomópont súlyának növekedése a rendezési tulajdonság megsértéséhez vezet, vagyis amikor a csomópont megnövekedett súlya nagyobb, mint a következő csomópont súlya. rendelés. Ha folytatjuk a súlynövekedés feldolgozását a fa gyökere felé haladva, akkor a fa már nem lesz Huffman fa.

A kódolási fa sorrendjének megtartása érdekében az algoritmus a következőképpen működik. Legyen az új megnövelt csomópontsúly W+1. Ezután kezdjük el a listán a súlynövelés irányába haladni, amíg meg nem találjuk az utolsó W súllyal rendelkező csomópontot. Rendezzük át egymás között a listában az aktuális és talált csomópontokat, így visszaállítjuk a fában a sorrendet (jelen esetben a szülőket). mindegyik csomópont is megváltozik). Ezzel befejeződik a csereművelet.

A permutáció után tovább folytatódik a csomópontok tömegének növelése. A következő csomópont, amelynek súlyát növeli az algoritmus, annak a csomópontnak az új szülője, amelynek súlyának növekedése okozta a permutációt.

Kanonikus Huffman kódok

A hagyományos Huffman-tömörítési algoritmus problémája a nem-determinizmus. Hasonló szekvenciák esetén különböző fák fordulhatnak elő, és egy fa megfelelő szerializálás nélkül különböző sorozatoknak felelhet meg. A kanonikus Huffman-kódok használatának elkerülése érdekében.

Ez az algoritmus nem épít Huffman fát [2] .

Két szakaszból áll:

A kód hosszának kiszámítása valamilyen karakterhez
Kód összeállítása.

Hosszszámítás

Számítsa ki az egyes karakterek gyakoriságát
Rendezd őket lexikográfiai sorrendbe!
Írjuk be az egyes betűk gyakoriságát a tömbbe.
A bal oldalon hozzárendelünk egy azonos hosszúságú tömböt, de a jobb oldali tömbből származó sorozatszámokkal. A bal oldali tömb a jobb oldal elemeire mutató mutatók listájaként jön létre.
A bal oldalon egy nem növekvő piramist készítünk . De a kupac nem a tömbelemek, hanem a hivatkozott tömbelem értéke alapján lesz.
A bal szélső elem a jobb oldali tömb legalacsonyabb gyakoriságú karakterére mutat. Így lehet eltávolítani:
1. Ne érintse meg a jobb felét
2. A tömb első elemét lecseréljük a bal oldali tömb jobb szélső elemére, állítólag eltolva az elválasztási határt.
3. Ellenőrizzük a piramis helyességének feltételeit, ha valami nincs rendben, akkor meg kell ismételni a „hipizálást”.
4. A tömb bal oldalának első elemét eltávolítjuk, és a korábban eltávolított elemet egyesítjük. Frekvenciáik összegét a bal és jobb oldali tömb határára írjuk.
5. A bal oldalon a törölt elem helyére a tömb indexét írjuk, ahol az utolsó lépésben hozzáadtuk a gyakoriságok összegét.
6. Tekintettel arra, hogy két elemet kombináltak, meg kell változtatni a tömb ezen elemeinek értékét, hivatkozva arra a szülőre, ahová kerültek.
Ismételjük, nem marad 1 elem a kupacban.
A tömb jobb oldalán 2 karaktert kombináló elemekre mutató hivatkozásokat kaptunk. Ezért a tömbön linkeken keresztül megyünk végig, növelve a merítés szintjét.
A linkekre leadott kattintások száma a Huffman kód hossza lesz.

Kódösszeállítás

Rendezd az elemeket lexikográfiai sorrendbe!
Készítsünk blokkokból álló táblázatot a legnagyobb kódhosszal kezdve. Minden blokk azonos kódhosszúságú elemeket tartalmaz.
A táblázat legelső karaktere nullákkal van kódolva.
Minden blokkban a karakterek lexikográfiai sorrendben lesznek.
A blokkban lévő kódok binárisak és 1-gyel különböznek egymástól.
Amikor a következő blokkra lép, a legutóbbi karakter kódbitjei levágásra kerülnek, és hozzáadódik 1.

Biggram modell

A Huffman-algoritmusnak van egy változata, amely kontextust használ. Ebben az esetben a kontextus mérete eggyel egyenlő (bigram - két karakter, trigram - három és így tovább). Ez a módszer egy előtag kód létrehozására magasabb rendű modellekhez, már nem memória nélküli forrás. Az (előző művelet) művelet eredményét használja az előző betűhöz az aktuális betűvel együtt. Egy függőségi mélységű Markov-láncra épül . [3] $r=1$

Algoritmus

A táblázatot négyzet formájában állítjuk össze - a valószínűségi eloszlást a biggramokban. A kiindulási séma azonnal kiszámításra kerül, aminek segítségével csak az első betű kerül kódolásra. A táblázat sorai például az előző betűk, az oszlopok pedig az aktuálisak.
Valószínűségeket számítanak ki a kontextusok kódfáihoz.
A hosszkontextusok a fennmaradó kódfák felépítésére szolgálnak, amelyek segítségével az összes többi karakter (az első kivételével) kódolásra kerül. $r=1$
A kódolás megtörténik, az első karakter kódolása a kezdő séma szerint történik, az összes következő karakter a kontextusok kódfái alapján kódolásra kerül (az előző karakter).

A dekódolás hasonló módon történik: a kezdő kódsémából megkapjuk az első kontextust, majd a megfelelő kódfára lépünk. Ezenkívül a dekódolónak szüksége van egy valószínűségi eloszlási táblázatra.

Példa

Tegyük fel, hogy a kódolandó üzenet az "abcabcabc" . A szimbólumgyakorisági táblázatot előre ismerjük (más adatok, például szótári statisztikák alapján).

	a	b	c	Összeg
a	${\tfrac {3}{16}}$	${\tfrac {1}{16}}$	${\tfrac {1}{16}}$	${\tfrac {5}{16}}$
b	${\tfrac {1}{8))$	${\tfrac {1}{16}}$	${\tfrac {1}{8))$	${\tfrac {5}{16}}$
c	${\tfrac {1}{8))$	${\tfrac {1}{8))$	${\tfrac {1}{8))$	${\tfrac {6}{16}}$

Van egy kiindulási sémánk: . Rendezd csökkenő sorrendbe: és építs fel egy Huffman kódfát. $(a={\tfrac {5}{16}},b={\tfrac {5}{16}},c={\tfrac {6}{16}})$ $(c={\tfrac {6}{16}},a={\tfrac {5}{16}},b={\tfrac {5}{16}})$

Az " a " kontextushoz a következőket találjuk:

$p(a/a)=p(a,a)/p(a)={\tfrac {3}{16}}\div {\tfrac {5}{16}}={\tfrac {3 }{5}}$ ,
$p(b/a)=p(b,a)/p(a)={\tfrac {1}{16}}\div {\tfrac {5}{16}}={\tfrac {1 }{5}}$ ,
$p(c/a)=p(c,a)/p(a)={\tfrac {1}{16}}\div {\tfrac {5}{16}}={\tfrac {1 }{5}}$ .

A " b " kontextushoz a következőket találjuk:

$p(a/b)=p(a,b)/p(b)={\tfrac {1}{8}}\div {\tfrac {5}{16}}={\tfrac {2 }{5}}$ ,
$p(b/b)=p(b,b)/p(b)={\tfrac {1}{16}}\div {\tfrac {5}{16}}={\tfrac {1 }{5}}$ ,
$p(c/b)=p(c,b)/p(b)={\tfrac {1}{8}}\div {\tfrac {5}{16}}={\tfrac {2 }{5}}$ .

A " c " kontextushoz a következőket találjuk:

$p(a/c)=p(a,c)/p(c)={\tfrac {1}{8}}\div {\tfrac {6}{16}}={\tfrac {1 }{3}}$ ,
$p(b/c)=p(b,c)/p(c)={\tfrac {1}{8}}\div {\tfrac {6}{16}}={\tfrac {1 }{3}}$ ,
$p(c/c)=p(c,c)/p(c)={\tfrac {1}{8}}\div {\tfrac {6}{16}}={\tfrac {1 }{3}}$ .

Megjegyzés: itt p(x, y) nem egyenlő p(y, x) -vel .

Minden kontextushoz kódfát készítünk. Kódolást végzünk, és van egy kódolt üzenetünk: (00, 10, 01, 11, 10, 01, 11, 10, 01).

00 - a kezdő séma "a" betűjének kódjából ,
10 - a "b" betű kódjából az "a" kontextushoz ,
01 - a "c" betű kódjából a "b" kontextushoz ,
11 - az "a" betű kódjából a "c" kontextushoz .

Túlcsordulás

Ahogy a tömörítési algoritmus fut, a Huffman-kódolófa csomópontjainak súlya folyamatosan növekszik. Az első probléma akkor merül fel, amikor a fa gyökerének súlya kezd meghaladni annak a cellának a kapacitását, amelyben azt tárolják. Ez jellemzően 16 bites érték, ezért nem lehet nagyobb 65535-nél. A második nagyobb figyelmet érdemlő probléma jóval korábban felmerülhet, amikor a leghosszabb Huffman-kód mérete meghaladja annak a cellának a kapacitását, amelyet a kód továbbítására használnak. a kimeneti folyam. A dekódolót nem érdekli, mennyi ideig dekódolja a kódot, mivel fentről lefelé mozog a kódolási fa mentén, és egy-egy bitet választ a bemeneti adatfolyamból. A kódolónak ezzel szemben a fa levelétől kell indulnia, és fel kell haladnia a gyökérig, összegyűjtve a továbbítandó biteket. Ez általában egy egész típusú változónál történik, és amikor a Huffman-kód hossza meghaladja az egész típus bitben kifejezett méretét, túlcsordulás következik be.

Bizonyítható, hogy az azonos bemeneti ábécéjú üzenetek Huffman-kódja akkor lesz maximális hosszúságú, ha a szimbólumfrekvenciák a Fibonacci-sorozatot alkotják . A Fibonacci-számokkal Fib(18)-ig terjedő szimbólumgyakoriságú üzenetek nagyszerű módja annak, hogy teszteljük a Huffman tömörítőprogramok működését.

Egy Huffman-fa csomópontsúlyainak skálázása

A fentiek figyelembe vételével a Huffman-fa frissítésének algoritmusát a következőképpen kell módosítani: a súly növekedésével ellenőrizni kell, hogy eléri-e a megengedett maximumot. Ha elértük a maximumot, akkor "méreteznünk" kell a súlyt, általában úgy, hogy a levelek tömegét elosztjuk egy egész számmal, például 2-vel, majd újraszámoljuk az összes többi csomópont súlyát.

A súly felezésénél azonban probléma adódik azzal a ténnyel, hogy a művelet elvégzése után a fa megváltoztathatja alakját. Ez azzal magyarázható, hogy egész számok osztásakor a tört részt eldobjuk.

A méretezés után megfelelően szervezett Huffman-fa alakja jelentősen eltérhet az eredetitől. Ennek az az oka, hogy a méretezés a statisztikák pontosságának elvesztését eredményezi. De az új statisztikák összegyűjtésével ezeknek a „hibáknak” a következményei gyakorlatilag eltűnnek. A súlyozás meglehetősen költséges művelet, mivel a teljes kódolási fa újraépítéséhez vezet. De mivel viszonylag ritkán van rá igény, akkor kibírhatja.

Méretezési előnyök

A fa csomópontjainak súlyának bizonyos időközönkénti skálázása váratlan eredményt ad. Noha a méretezés során csökken a statisztikai pontosság, a tesztek azt mutatják, hogy a méretezés jobb tömörítési teljesítményt eredményez, mintha a skálázás késleltetett lenne. Ez azzal magyarázható, hogy a tömöríthető folyam jelenlegi szimbólumai jobban "hasonlítanak" közeli elődeikhez, mint a jóval korábban előfordulókhoz. A méretezés eredményeként csökken a "régi" szimbólumok befolyása a statisztikákra, és nő a "legutóbbi" szimbólumok befolyása rá. Ezt nagyon nehéz számszerűsíteni, de elvileg a skálázás pozitív hatással van az információtömörítés mértékére. A tömörítési folyamat különböző pontjain végzett méretezési kísérletek azt mutatják, hogy a tömörítés mértéke erősen függ a súly méretezésének pillanatától, de nincs szabály az optimális méretezési nyomaték kiválasztására bármilyen típusú információ tömörítésére összpontosító program esetében.

Alkalmazás

A Huffman kódolást széles körben használják adattömörítésben, beleértve a fotó- és videótömörítést ( JPEG , MPEG ), a népszerű archiválókban ( PKZIP , LZH stb.), HTTP-ben ( Deflate ), MNP5 és MNP7 adatátviteli protokollokban és másokban.

Módosítások

2013-ban javasolták a Huffman-algoritmus olyan módosítását, amely lehetővé teszi a karakterek töredékszámú bitszámú kódolását - ANS [4] [5] . Ezen a módosításon alapul a Zstandard (Zstd, Facebook, 2015–2016) [6] és az LZFSE (Apple, OS X 10.11, iOS 9, 2016) [7] [8] [9] [10] tömörítési algoritmusok valósulnak meg .

Jegyzetek

↑ D. Masztryukov. Monitor 7-8.93 Archiválva : 2018. május 17. a Wayback Machine -nél
↑ Az algoritmust példákkal részletezi: Managing Gigabytes by Witten, Moffat, Bell, 68. oldal.
↑ Shmuel T. Klein és Dana Shapira. Huffman kódolás nem rendezett frekvenciákkal (2008). Hozzáférés dátuma: 2016. január 2. Az eredetiből archiválva : 2016. március 4. (határozatlan)
↑ Archivált másolat . Letöltve: 2016. január 2. Az eredetiből archiválva : 2016. március 5.. (határozatlan)
↑ Archivált másolat . Letöltve: 2016. január 2. Az eredetiből archiválva : 2016. szeptember 11.. (határozatlan)
↑ A Facebook közzétette a Zstandard 1.0 tömörítési algoritmus megvalósítását Archiválva : 2016. szeptember 2. a Wayback Machine -en / Opennet.ru, 2016.01.09.
↑ Az Apple megnyitotta az LZFSE veszteségmentes tömörítési algoritmus megvalósítását
↑ Az Apple nyílt forráskódú LZFSE új tömörítési algoritmust . Letöltve: 2016. szeptember 1. Archiválva az eredetiből: 2016. szeptember 11. (határozatlan)
↑ Adattömörítés
↑ GitHub - lzfse/lzfse: LZFSE tömörítési könyvtár és parancssori eszköz . Letöltve: 2016. szeptember 1. Az eredetiből archiválva : 2020. november 28. (határozatlan)

Irodalom

Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmusok: felépítés és elemzés = Introduction to Algorithms. - 2. kiadás — M .: Williams , 2006. — 1296 p. — ISBN 0-07-013151-1 .
D. Salomon. Adatok, képek és hangok tömörítése. - M . : Technosfera, 2004. - 368 p. - 3000 példányban. — ISBN 5-94836-027-X .
Ian H. Witten, Alistair Moffat, Timothy C. Bell. Gigabyte-ok kezelése: dokumentumok és képek tömörítése és indexelése. - 1999. - 551 p. — ISBN 1558605703 .
Levitin A. V. 9. fejezet. Mohó módszerek: A Huffman algoritmus // Algoritmusok. Bevezetés a fejlesztésbe és elemzésbe - M . : Williams , 2006. - S. 392-398. — 576 p. — ISBN 978-5-8459-0987-9

Markov A. A. Bevezetés a kódoláselméletbe. — M .: Nauka, 1982. — 192 p.

Linkek

Tömörítési módszerek

Elmélet

Információ	Saját Kölcsönös Entrópia Feltételes entrópia Bonyolultság Redundancia
Egységek	Bit Nat Rágcsál Hartley Hartley képlet

Veszteségmentes

Entrópia tömörítés	Aszimmetrikus számrendszerek Huffman algoritmus Adaptív Huffman algoritmus Shannon-Fano algoritmus Shannon algoritmusa Aritmetikai kódolás ( intervallum ) Golomb kódok Delta Univerzális kód Elias fibonacci
Szótári módszerek	RLE Kienged LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
Egyéb	RLE CTW BWT MTF PPM DMC

Hang

Elmélet	Konvolúció PCM Aliasing Mintavétel Kotelnyikov tétele
Mód	LPC LAR LSP WLPC CELP ACELP Törvény μ-törvény ADPCM MDCT Fourier transzformáció Pszichoakusztikus modell
Egyéb	Audio kompresszor Beszédtömörítés Sáv kódolás

Képek

Feltételek	színtér Pixel Telítettségi részmintavétel Tömörítési műtermékek
Mód	RLE DPCM fraktál hullámocska EZW SPIHT LP PrEP PCL
Egyéb	Bitráta Szabványos tesztkép PSNR Kvantálás

Videó

Feltételek	Videó jellemzői Keret Keret típusok Videó minőség
Mód	Mozgáskompenzáció PrEP Kvantálás hullámocska
Egyéb	Videokodek Sebesség-torzítás elmélet CBR ABR VBR