Huffman-kódolás algoritmus elméleti rész
Az elméleti rész
Huffman algoritmus
Az egyik első algoritmusok hatékony kódolása információ által javasolt Huffman 1952. Ez az algoritmus vált bázis egy csomó adat tömörítő programok. Például, a Huffman kódolást alkalmazunk a ARJ tömörítő programok. ZIP. RAR. A tömörítési algoritmusok JPEG Grafikus képek veszteségeket. valamint az integrált a modern fax.
Hatékony kódolás Huffman, hogy bemutassa a legvalószínűbb (gyakori) betűk bináris kódokat legrövidebb és a legkevésbé valószínű -, annál nagyobb hosszúságú kódok (ha minden kódszó hosszasan kimerítették). Ez úgy történik, hogy az átlagos hossza a kódot a levélben az eredeti üzenet minimális volt.
Megkezdése előtt a kódoló ismerni kell az előfordulási valószínűsége minden egyes levél melyik lesz az üzenet. Alapján a valószínűségi táblázatot gyártani Huffman kódot fa, amely kódolja a leveleket.
Épület egy Huffman kódfában
Annak illusztrálására, úgy a Huffman algoritmus grafikus utat építeni egy fa kódolás. Mielőtt be néhány alkalmazott meghatározások leírni a Huffman algoritmus ezzel a módszerrel.
Count - egy sor, több csomópontot és több ívek irányított egyik csomóponttól a másikig.
Fa - egy grafikont a következő tulajdonságokkal rendelkezik:- bármelyike a csomópontok nem tartalmaz több, mint egy ív;
- csak egy csomópont nem része semmilyen ív (ez a csomópont neve a gyökér a fa);
- mozog az íveket a gyökér, akkor kap minden csomópont.
fa levél - csomópont, amely nem hagy ív. Egy pár fa összekapcsolt csomópontokból ív, amelyikről kiderül, az úgynevezett a szülő. a másik - a gyermek.
Két csomópont nevezik testvérek. ha ugyanaz a szülő.
Binary Tree - egy fa, amely minden csomópont csak a levelek, levelek pontosan két ív.
Fa Huffman-kódolás - bináris fa, ahol minden egyes csomópont a súlyt. és ahol a szülő súly teljes tömege a gyerekeit.
Egy algoritmust építése a fa Huffman a következő:- input ábécé betűit alkotják a listát a szabad csomópontok jövő kódoló fa. Minden csomópont ebben a listában tömege megegyezik a valószínűségét, hogy a megfelelő betűt az üzenetet.
- Válogatott két szabad csomópontja a legalacsonyabb súlyokat. Ha több mint két csomópont a legalacsonyabb szabad súlyokkal, akkor megtesz minden pár.
- Hoz létre a szülő egy tömege azonos a teljes súlyt.
- Szülő hozzá a listát a szabad csomópontok, és a két gyerek eltávolítják a listából.
- Egy ív kinyúló szülőcsomópont, társított bit 1, egy másik - 0.
- 2., 3., 4., 5. ismételjük, amíg a lista a szabad csomópontok nem marad csak egy csomópont. Ez a csomópont lesz a gyökér a fa. Súlya kiderül, hogy az egyik - a teljes valószínűsége minden betűjét az üzenetet.
Most térjünk át a kódot fát fentről lefelé, majd ezt követően írásban bináris számjegy megfelelő ívű, akkor is kaphat kódokat bemeneti ábécé.
Vegyük például az építőiparban a Huffman-kódolás fa egy 1. táblázatban megadott nyolc az ábécé betűit.
Épület egy fa levelei kezd a listán (lásd. Ábra. 1), és hajtsa végre a következő lépéseket.
Ábra. 1. A listát a szabad szárcsomóknál.
Az első lépésben a két levél a fa vannak kiválasztva a legalacsonyabb testtömeget Z7 és Z8. Ezek az aiap csomóponthoz, amelynek tömege van beállítva 0,04 0,02 = 0,06. Ezután Z7 és Z8 csomópontok eltávolítják a szabad listán. Csomópont Z7 0 felel meg ága szülőcsomópont Z8 - 1. Kódolási fa ágai az első lépés után ábrán látható. 2.
Ábra. 2. Huffman-kódolás fa az első lépés után.
A második lépésben „Flyweight” pár Z6 lap és szabad csomópont (Z7 + Z8). Számukra létrehoztunk egy szülő tömegű 0,16. Csomópont Z6 0 felel meg ága szülőcsomópont (Z7 + Z8) - ága 1. Ebben a lépésben, a kódolófa a következők (lásd 3. ábra ..).
Ábra. 3. A Huffman-kódolás fa után a második lépés.
A harmadik lépésben a legkisebb valószínűséggel a Z5. Z4. a Z3 és szabad csomópont (Z6 + Z7 + Z8). Így, ebben a lépésben létre lehet hozni egy szülő és Z5 (Z6 + Z7 + Z8) tömegű 0,26. megérkezik egy fa kódolás, ábrán látható. 4. Felhívjuk figyelmét, hogy ebben a helyzetben van több lehetőség a kapcsolat csomópontok a legalacsonyabb súlyokat. Ráadásul mindezek a lehetőségek helyes, bár ez vezethet a különböző készletek kódok, amelyek azonban ugyanaz lesz a hatékonysága egy adott valószínűség-eloszlás.
Ábra. 4. Huffman-kódolás fa a harmadik lépés után.
A negyedik lépés „pehelysúlyú” egy pár levél a Z3 és Z4. Huffman-kódolás fa ábrán látható. 5.
Ábra. 5. Huffman-kódolás fa után a negyedik lépés.
Az ötödik lépésben válassza oldalak a legalacsonyabb testtömeget az 0,22 és 0,20. Huffman-kódolás fa után az ötödik lépésben ábrán látható. 6.
Ábra. 6. Huffman-kódolás fa után az ötödik lépésben.
A hatodik lépést a három szabad csomópont súlyokkal 0,42. 0,32 és 0,26. A választás a legkisebb súlya 0,32 és 0,26. Huffman-kódolás fa után hatodik lépésben ábrán látható. 7.
Ábra. 7. Huffman-kódolás fa után a hatodik lépésben.
A hetedik lépés az, hogy egyesíti a két fennmaradó szabad csúcsot, majd a végterméket kapjuk Huffman-kódolás fa ábrán látható. 8.
Ábra. 8. A végleges fa Huffman-kódolással.
Alapján az épített fa betűk képviselik kódok fényvisszaverő útvonal a gyökér csomóponttól a levél megfelel a kívánt betű. Ebben a példában, a bemeneti ábécé vannak kódolva, mint a 2. táblázatban látható.
3. táblázat azt mutatja, hogy a kódok is kap egy előtag, és a legvalószínűbb, hogy megfelelnek a betűket a legtöbb rövid kódokat.
A gyakorlati megvalósítása az algoritmus
Ahhoz, hogy a hatékonyság növelése a tömörítés szükséges építési kódfában használt adatokat a valószínűségét betűk ebben a fájlban helyett átlagában nagyszámú szövegeket. Ennek megfelelően, a szükséges statisztikai előfordulásának levelek tömörített fájl, amely beszerezhető előzetes áthaladás a fájlt.
Ahhoz, hogy gyorsítsák fel a munkát készíteni, hogy a bekövetkezés valószínűsége pi nem betűket. és előfordulási gyakorisága (előfordulások száma) ni betűk a fájlt. Ez nagyban egyszerűsíti és felgyorsítja az algoritmus (nem kell lassítani lebegőpontos műveletek és osztály műveletek). Ebben a megközelítésben az algoritmus nem változik, mivel a frekvencia egyenesen arányos a valószínűségeket. Meg kell jegyezni, hogy a súlya a gyökér csomópont a fa kódoló ebben az esetben egyenlő a teljes betűk száma a fájl feldolgozása folyamatban van.
interaktív tanulási
Ha már ismeri az elméleti része a munka, azt javasoljuk, hogy a gyakorlatban az építési Huffman kód fák segítségével egy interaktív tanulási rendszert. Ehhez csak megy ez a link.