Adaptiv Huffman-kodning - Adaptive Huffman coding

Adaptiv Huffman-kodning (også kaldet Dynamic Huffman-kodning ) er en adaptiv kodningsteknik baseret på Huffman-kodning . Det tillader opbygning af koden, når symbolerne transmitteres, uden indledende kendskab til kildedistribution, der muliggør kodning og tilpasning til enpasning til skiftende data i data.

Fordelen ved enpasningsprocedure er, at kilden kan kodes i realtid, selvom den bliver mere følsom over for transmissionsfejl, da bare et enkelt tab ødelægger hele koden.

Algoritmer

Der er en række implementeringer af denne metode, de mest bemærkelsesværdige er FGK ( Faller - Gallager - Knuth ) og Vitter- algoritme.

FGK algoritme

Det er en online kodningsteknik baseret på Huffman-kodning. Uden indledende kendskab til forekomstfrekvenser tillader det dynamisk at justere Huffmans træ, når data transmitteres. I et FGK Huffman-træ bruges en speciel ekstern knude, kaldet 0-knude , til at identificere et nyt kommende tegn. Når der er stødt på nye data, skal du sende stien til 0-noden efterfulgt af dataene. For en fremtidig karakter skal du blot output stien til dataene i det aktuelle Huffmans træ. Vigtigst er det, at vi er nødt til at justere FGK Huffman-træet, hvis det er nødvendigt, og endelig opdatere hyppigheden af ​​relaterede noder. Efterhånden som frekvensen af ​​et datum øges, kan søskendeegenskaberne for Huffmans træ blive brudt. Justeringen udløses af denne grund. Det opnås ved fortløbende swappings af noder, subtrees eller begge dele. Dataknudepunktet byttes med den højest ordnede knude af den samme frekvens i Huffmans træ (eller undertrådet rodfæstet ved den højest ordnede knude). Alle forfædres noder i noden skal også behandles på samme måde.

Da FGK-algoritmen har nogle ulemper ved bytte af node eller subtree, foreslog Vitter en anden algoritme for at forbedre den.

Vitter-algoritme

Nogle vigtige terminologier og begrænsninger: -

  • Implicit nummerering  : Det betyder simpelthen, at noder nummereres i stigende rækkefølge efter niveau og fra venstre mod højre. dvs. noder på bundniveau vil have et lavt implicit antal sammenlignet med noder på det øverste niveau og noder på samme niveau er nummereret i stigende rækkefølge fra venstre til højre.
  • Invariant  : For hver vægt w går alle blade af vægt foran alle interne noder med vægt w.
  • Blokke  : Noder af samme vægt og samme type (dvs. enten bladknude eller intern knude) danner en blok.
  • Leder  : Højest nummererede knude i en blok.

Blokke er sammenkoblet ved at øge rækkefølgen af ​​deres vægte.

En bladblok går altid forud for den interne blok af samme vægt og opretholder således invarianten.

NYT (Ikke overført endnu) er en særlig knude og bruges til at repræsentere symboler, der 'endnu ikke er overført' .

Image
Slide_And_Increment (bladnode) glidning starter. P er en bladknude.
Image
Slide_And_Increment (bladnode) glidende trin 2. Da P er bladnode, glider den foran de næste bloknoder med samme vægt.
Image
Slide_And_Increment (bladnode) glidende trin 3. Her øger vi den aktuelle vægt med 1.
Image
Slide_And_Increment (bladnode) glidende trin 4. Metoden slutter. P er den nye forælder.
Image
Slide_And_Increment (intern node) glidning starter. P er en intern knude.
Image
Slide_And_Increment (intern node) glidende trin 2. Knude P glider foran næste blok af blade noder med vægt wt + 1.
Image
Slide_And_Increment (intern node) glidende trin 3. Nu øger vi vægten til 9. Således opretholdes invarianten, da den aktuelle node er en intern node og skal forekomme foran bladnoder med samme vægt, da vi har øget vægten.
Image
Slide_And_Increment (intern node) glidende trin 4. Nu peger 'P' på den tidligere forælder (som i tilfældet med intern node ifølge algoritme) 
algorithm for adding a symbol is
    leaf_to_increment := NULL
    p := pointer to the leaf node containing the next symbol

    if (p is NYT) then
        Extend p by adding two children
        Left child becomes new NYT and right child is the new symbol leaf node
        p := parent of new symbol leaf node
        leaf_to_increment := Right Child of p
    else
        Swap p with leader of its block
        if (new p is sibling to NYT) then
            leaf_to_increment := p
            p := parent of p

    while (p ≠ NULL) do
        Slide_And_Increment(p)

    if (leaf_to_increment != NULL) then
        Slide_And_Increment(leaf_to_increment)

function Slide_And_Increment(p) is
    previous_p := parent of p

    if (p is an internal node) then
        Slide p in the tree higher than the leaf nodes of weight wt + 1
        increase weight of p by 1
        p := previous_p
    else
        Slide p in the tree higher than the internal nodes of weight wt
        increase weight of p by 1
        p := new parent of p.

Koder og dekoder starter kun med rodnoden, som har det maksimale antal. I starten er det vores første NYT-knude.

Når vi sender et NYT-symbol, er vi nødt til at sende kode til NYT-noden og derefter til dens generiske kode.

For hvert symbol, der allerede findes i træet, behøver vi kun at sende kode til dets bladknude.

Eksempel

Adaptiv Huffman Vitter.jpg

Kodning af "abb" giver 01100001 001100010 11.

Trin 1:

Start med et tomt træ.

For "a" skal du sende sin binære kode.

Trin 2:

NYT gyder to underknudepunkter: 254 og 255, begge med vægt 0. Forøg vægten for rod og 255. Kode for "a", der er knyttet til node 255, er 1.

For "b" send 0 (for NYT-node) derefter dens binære kode.

Trin 3:

NYT gyder to underknudepunkter: 252 for NYT og 253 for bladknude, begge med vægt 0. Forøg vægten til 253, 254 og rod. For at opretholde Vitter's invariant, at alle blade af vægt w går forud for (i den implicitte nummerering) alle interne noder af vægt w, skal grenen, der starter med node 254, byttes (i form af symboler og vægte, men ikke nummerbestilling) med node 255. Koden for "b" er 11.

For det andet "b" send 11.

Af hensyn til forklaringen følger dette trin ikke ligefrem Vitters algoritme, men effekterne er ækvivalente.

Trin 4:

Gå til bladknude 253. Bemærk, at vi har to blokke med vægt 1. Knude 253 og 254 er en blok (bestående af blade), node 255 er en anden blok (bestående af interne noder). For node 253 er det største tal i dens blok 254, så skift vægte og symboler for knudepunkter 253 og 254. Nu skal node 254 og grenen, der starter fra node 255, tilfredsstille SlideAndIncrement-tilstanden og skal derfor byttes. Endelig øges node 255 og 256's vægt.

Fremtidig kode for "b" er 1, og for "a" er nu 01, hvilket afspejler deres frekvens.

Referencer

  • Vitters originale papir: JS Vitter, " Design og analyse af dynamiske Huffman-koder ", Journal of the ACM, 34 (4), oktober 1987, s. 825–845.
  • JS Vitter, "ALGORITHM 673 Dynamic Huffman Coding", ACM-transaktioner på matematisk software, 15 (2), juni 1989, s. 158-167. Vises også i ACM's samlede algoritmer.
  • Donald E. Knuth, "Dynamic Huffman Coding", Journal of Algorithm, 6 (2), 1985, s. 163-180.

eksterne links