Adaptív Huffman algoritmus

Az adaptív Huffman-kódolás (más néven dinamikus Huffman-kódolás ) egy Huffman-kódoláson alapuló adaptív módszer . Lehetővé teszi egy kódséma felépítését streaming módban (az adatok előzetes szkennelése nélkül), az eredeti disztribúció kezdeti ismerete nélkül, amely lehetővé teszi az adatok tömörítését egyetlen lépésben. Ennek a módszernek az az előnye, hogy menet közben is kódolható.

Algoritmusok

Ennek a módszernek számos megvalósítása létezik, a legfigyelemreméltóbb az "FGK" (FGK: Voller, Gallagher és Knuth ) és a Witter-algoritmus.

FGK algoritmus

Lehetővé teszi a Huffman-fa dinamikus beállítását kezdeti frekvenciák nélkül. Az FGD Huffman-fának van egy speciális külső csomópontja, az úgynevezett 0-csomópont , amely a bejövő karakterek azonosítására szolgál. Ez azt jelenti, hogy amikor egy új karakterrel találkozunk, annak útvonala a fában a nulla csomóponttól kezdődik. A legfontosabb dolog az, hogy szükség esetén le kell vágni és ki kell egyensúlyozni az FGD Huffman fát, és frissíteni kell a kapcsolódó csomópontok gyakoriságát. Egy szimbólum gyakoriságának növekedésével az összes szülőjének gyakoriságát is növelni kell. Ez a csomópontok, részfák vagy mindkettő egymás utáni permutációjával érhető el.

Az FGD fa fontos jellemzője a testvériség (vagy rivalizálás) elve: minden csomópontnak két gyermeke van (a gyermek nélküli csomópontokat leveleknek nevezzük), és a súlyok csökkenő sorrendben vannak. Ennek a tulajdonságnak köszönhetően a fa szabályos tömbben tárolható, ami növeli a teljesítményt. [1] [2]

Witter-algoritmus

A kód egy fastruktúraként jelenik meg, amelyben minden csomóponthoz tartozik egy súly és egy egyedi szám.

A számok lefelé mennek, és jobbról balra.

A súlyoknak meg kell felelniük a testvériség elvének. Így ha A B szülője, C pedig B gyermeke, akkor .

A súly csak az eddig talált karakterek száma.

Az azonos súlyú csomópontok halmaza egy blokk .

Az egyes csomópontok kódjának megszerzéséhez egy bináris fa esetében egyszerűen bejárhatjuk az összes utat a gyökértől a csomópontig, például "1"-et írva, ha jobbra megyünk, és "0"-t, ha jobbra megyünk. menj balra.

Ezenkívül ez az algoritmus egy speciális levelet (csomópont utódok nélkül), NYT-t (az angol még nem továbbított - még nem továbbított karakterből) használ, amelyből új, korábban nem látott karakterek „nőnek ki”.

A kódoló és a dekódoló csak a legnagyobb súlyú gyökércsomóponttól indul. Kezdetben ez a mi NYT-csomópontunk.

Amikor átadjuk a NYT karaktert, először magának a csomópontnak a kódját kell átadnunk, majd az adatokat.

Minden egyes szimbólumhoz, amely már benne van a fában, csak a végcsomópontok (levelek) kódját kell átadnunk.

Az adó és a vevő minden egyes elküldött karakternél frissítési eljárást hajt végre:

1. Ha az aktuális szimbólum nem található, adjon hozzá két gyermek csomópontot a NYT-hez: az egyik a következő NYT-hez, a másik a szimbólumhoz. Növelje az új lap és a régi NYT súlyát, és folytassa a 4. lépéssel. Ha az aktuális szimbólum nem NYT, lépjen a szimbólumlapra.
2. Ha ennek a csomópontnak nincs a legnagyobb súlya a blokkban, cserélje ki a legnagyobb számú csomópontra, kivéve, ha ez a csomópont szülő [3]
3. Az aktuális csomópont súlyának növelése
4. Ha nem a gyökércsomópont, lépjen a szülőcsomópontra, majd folytassa a 2. lépéssel. Ha ez a gyökér, fejezze be.

Megjegyzés: A csomópontok cseréje a súlyok és a megfelelő szimbólumok cseréjét jelenti, nem a számokat.