Mukautuva Huffman-algoritmi

Mukautuva Huffman-koodaus (kutsutaan myös dynaamiseksi Huffman-koodaukseksi ) on Huffman -koodaukseen perustuva adaptiivinen menetelmä . Sen avulla voit rakentaa koodikaavion suoratoistotilassa (ilman alustavaa tietojen skannausta) ilman alkuperäisen jakelun alkutietoa, mikä mahdollistaa tietojen pakkaamisen yhdellä kertaa. Tämän menetelmän etuna on kyky koodata lennossa.

Algoritmit

Tälle menetelmälle on useita toteutuksia, joista merkittävimmät ovat "FGK" (FGK: Voller, Gallagher ja Knuth ) ja Witterin algoritmi.

FGK-algoritmi

Sen avulla voit säätää Huffman-puuta dynaamisesti ilman alkutaajuuksia. FGD Huffman -puussa on erityinen ulompi solmu, nimeltään 0-solmu , jota käytetään saapuvien merkkien tunnistamiseen. Toisin sanoen aina kun uusi merkki kohdataan, sen polku puussa alkaa nollasolmusta. Tärkeintä on, että sinun on tarvittaessa katkaistava ja tasapainotettava FGD Huffman -puu ja päivitettävä siihen liittyvien solmujen taajuus. Symbolin taajuuden kasvaessa myös sen kaikkien vanhempien taajuutta on lisättävä. Tämä saavutetaan solmujen, alipuiden tai molempien peräkkäisellä permutaatiolla.

FGD-puun tärkeä ominaisuus on veljeys (tai kilpailu) -periaate: jokaisella solmulla on kaksi lasta (solmuja ilman lapsia kutsutaan lehtiksi) ja painot ovat laskevassa järjestyksessä. Tämän ominaisuuden ansiosta puu voidaan tallentaa tavalliseen taulukkoon, mikä lisää suorituskykyä. [1] [2]

Witterin algoritmi

Koodi esitetään puurakenteena, jossa jokaisella solmulla on paino ja yksilöllinen numero.

Numerot laskevat ja oikealta vasemmalle.

Painojen on täytettävä veljeyden periaate. Siten, jos A on B:n vanhempi ja C on B:n lapsi, niin .

Paino on vain tähän mennessä havaittujen merkkien määrä.

Joukko solmuja, joilla on sama paino, on lohko .

Saadaksemme koodin jokaiselle solmulle binääripuun tapauksessa voisimme yksinkertaisesti kulkea kaikki polut juuresta solmuun kirjoittamalla esimerkiksi "1", jos menemme oikealle, ja "0", jos menemme mene vasemmalle.

Tämä algoritmi käyttää myös erityistä lehteä (solmu ilman jälkeläisiä), NYT (englanniksi ei vielä lähetetty - ei vielä lähetetty merkki), josta "kasvaa" uusia, ennen näkemättömiä merkkejä.

Enkooderi ja dekooderi alkavat vain juurisolmusta, jolla on suurin paino. Alussa tämä on NYT-solmumme.

Kun välitämme NYT-merkin, meidän on ensin välitettävä itse solmun koodi ja sitten tiedot.

Jokaiselle puussa jo olevalle symbolille meidän on välitettävä vain päätesolmujen (lehtien) koodi.

Jokaiselle lähetetylle merkille lähetin ja vastaanotin suorittavat päivitystoimenpiteen:

1. Jos nykyistä symbolia ei löydy, lisää NYT:hen kaksi alisolmua: yksi seuraavalle NYT:lle ja toinen symbolille. Lisää uuden arkin ja vanhan NYT:n painoa ja siirry vaiheeseen 4. Jos nykyinen symboli ei ole NYT, siirry symboliarkkiin.
2. Jos tällä solmulla ei ole lohkon suurinta painoa, vaihda se suurimman numeron omaavaan solmuun, ellei tämä solmu ole pääsolmu [3]
3. Nykyisen solmun painon lisääminen
4. Jos se ei ole juurisolmu, siirry pääsolmuun ja siirry sitten vaiheeseen 2. Jos se on juurisolmu, lopeta.

Huomautus: Solmujen vaihtaminen tarkoittaa painojen ja vastaavien symbolien, ei numeroiden, korvaamista.