thuis-Hoe een bestand te openen-Huffman-codering. Huffman-code

Huffman-codering. Huffman-code

Huffman-codering is een eenvoudig algoritme voor het construeren van codes variabele lengte met een minimale gemiddelde lengte. Dit zeer populaire algoritme dient als basis voor veel computertekst- en tekstcompressieprogramma's. grafische informatie. Sommigen van hen gebruiken het Huffman-algoritme rechtstreeks, terwijl anderen het beschouwen als een stap in een compressieproces op meerdere niveaus. De Huffman-methode produceert perfecte compressie (dat wil zeggen, comprimeert de gegevens tot de entropie ervan) als de kansen van de karakters precies gelijk zijn aan negatieve machten van 2. Het algoritme begint de codeboom van onder naar boven op te bouwen en glijdt vervolgens door de boom naar beneden. bouw elke individuele code van rechts naar links (van het minst significante bit tot het meest significante bit). Sinds het werk van D. Huffman in 1952 is dit algoritme het onderwerp geweest van vele onderzoeken. (De laatste uitspraak uit §3.8.1 laat dat zien beste code variabele lengte kan soms worden verkregen zonder dit algoritme.)

Het algoritme begint met het samenstellen van een lijst met alfabetische tekens in aflopende volgorde van hun waarschijnlijkheid. Vervolgens wordt vanaf de wortel een boom gebouwd, waarvan de bladeren deze symbolen zijn. Dit gebeurt in stappen, waarbij elke stap de twee symbolen met de laagste waarschijnlijkheid selecteert, deze bovenaan de gedeeltelijke boom toevoegt, ze uit de lijst verwijdert en ze vervangt door een hulpsymbool dat deze twee symbolen vertegenwoordigt. Aan het hulpsymbool wordt een waarschijnlijkheid toegewezen die gelijk is aan de som van de kansen die bij deze symboolstap zijn geselecteerd. Wanneer de lijst wordt teruggebracht tot één enkel hulpsymbool dat het hele alfabet vertegenwoordigt, wordt de boom compleet verklaard. Het algoritme eindigt door de boom af te dalen en de codes van alle symbolen te construeren.

Dit algoritme wordt het beste geïllustreerd door eenvoudig voorbeeld. Er zijn vijf symbolen met de kansen gegeven in Fig. 1.3a.

Rijst. 1.3. Huffman-codes.

De karakters zijn gekoppeld in de volgende volgorde:

1. wordt gecombineerd met , en beide worden vervangen door het gecombineerde symbool met waarschijnlijkheid 0,2;

2. Er zijn nog vier symbolen over, met een waarschijnlijkheid van 0,4, en ook met een waarschijnlijkheid van 0,2. We selecteren willekeurig en , combineren ze en vervangen ze door een hulpsymbool met waarschijnlijkheid 0,4;

3. Nu zijn er drie symbolen met respectievelijk kansen 0,4, 0,2 en 0,4. We selecteren en combineren symbolen en tot een hulpsymbool met waarschijnlijkheid 0,6;

4. Ten slotte combineren we de twee overgebleven symbolen en vervangen ze door kans 1.

De boom is gebouwd. Het wordt getoond in Afb. 1.3a, “liggend op zijn kant”, met de wortel aan de rechterkant en vijf bladeren aan de linkerkant. Om codes toe te wijzen, wijzen we voor elk paar willekeurig bit 1 toe aan de bovenste tak en bit 0 aan de onderste tak van de boom. Als resultaat krijgen we de volgende codes: 0, 10, 111, 1101 en 1100. De verdeling van bits langs de randen is willekeurig.

De gemiddelde lengte van deze code is bits/symbool. Het is heel belangrijk dat er veel Huffman-codes zijn. Sommige stappen van het algoritme zijn willekeurig gekozen, omdat dat zo was meer karakters met minimale waarschijnlijkheid. In afb. Figuur 1.3b laat zien hoe de karakters op verschillende manieren kunnen worden gecombineerd om een ​​andere Huffman-code te produceren (11, 01, 00, 101 en 100). De gemiddelde lengte is gelijk aan bits/symbool zoals in de vorige code.

Voorbeeld: Gegeven 8 symbolen A, B, C, D, E, F, G en H met kansen 1/30, 1/30, 1/30, 2/30, 3/30, 5/30, 5/30 en 12/ dertig. In afb. 1.4a,b,c tonen drie Huffman-codebomen van hoogte 5 en 6 voor dit alfabet.

Rijst. 1.4. Drie Huffman-bomen voor acht karakters.

De gemiddelde lengte van deze codes (in bits per symbool) is

Voorbeeld: Op afb. Figuur 1.4d toont nog een boom met hoogte 4 voor de acht karakters uit het vorige voorbeeld. Uit de volgende analyse blijkt dat de bijbehorende code met variabele lengte slecht is, ook al is de lengte minder dan 4.

(Analyse) Na het combineren van de symbolen A, B, C, D, E, F en G zijn de resterende symbolen ABEF (met een waarschijnlijkheid van 10/30), CDG (met een waarschijnlijkheid van 8/30) en H (met een waarschijnlijkheid van een waarschijnlijkheid van 12/30). De karakters ABEF en CDG hebben de laagste waarschijnlijkheid, dus moesten ze worden samengevoegd, maar in plaats daarvan werden de karakters CDG en H samengevoegd. De resulterende boom is geen Huffman-boom.

Door enige willekeur in de constructie van de boom kunnen we dus verschillende Huffman-codes met dezelfde gemiddelde lengte verkrijgen. Dit roept de vraag op: “Wat is de beste Huffman-code die voor een bepaald alfabet is samengesteld?” Het antwoord zal eenvoudig zijn, maar niet voor de hand liggend: de beste code is degene met de minste variantie.

Dispersie laat zien hoeveel de lengtes van individuele codes afwijken van hun gemiddelde waarde (dit concept wordt uitgelegd in elk statistiekhandboek). De variantie van code 1.3a is gelijk aan , en voor code 1.3b .

Code 1.3b heeft de voorkeur (dit wordt hieronder toegelicht). Een zorgvuldige blik op de bomen laat zien hoe we degene kunnen kiezen die we nodig hebben. Vijg op de boom 1.3a gaat het symbool samen met het symbool, terwijl in Fig. 1.3b fuseert met . De regel zou zijn: als er meer dan twee knooppunten met de laagste waarschijnlijkheid in de boom zijn, moeten de karakters met de hoogste en laagste waarschijnlijkheid worden gecombineerd; dit vermindert de algehele codevariantie.

Als de encoder gewoon schrijft gecomprimeerd bestand naar schijf, dan doet codevariantie er niet toe. Huffman-codes met lage variantie hebben alleen de voorkeur als de encoder dit gecomprimeerde bestand via communicatielijnen verzendt. In dit geval zorgt een code met een hoge variantie ervoor dat de encoder bits met een variabele snelheid genereert. Normaal gesproken worden gegevens verzonden via communicatiekanalen met constante snelheid, dus de encoder gebruikt een buffer. De bits van het gecomprimeerde bestand worden tijdens het genereren gebufferd en met een constante snelheid in het kanaal ingevoerd voor verzending. Het is gemakkelijk in te zien dat code zonder variantie met een constante snelheid in de buffer wordt ingevoerd, dus er zal een korte buffer nodig zijn, en voor grote codevariantie zal het gebruik van een lange buffer nodig zijn.

In de informatiecompressieliteratuur is soms de volgende uitspraak te vinden: de Huffman-codelengte van een symbool is altijd maximaal . Hoewel deze bewering in veel voorbeelden waar is, is ze in het algemeen niet waar. Ik ben Guy Blalock zeer dankbaar, die mij op dit feit heeft gewezen en mij een voorbeeld heeft gegeven van de code uit de tabel. 1.5. De tweede regel van deze tabel bevat een teken met een codelengte van 3 bits, terwijl .

Tafel 1.5. Huffman-codevoorbeeld.

De lengte van de code van een symbool hangt uiteraard af van de waarschijnlijkheid ervan. Het hangt echter impliciet ook af van de alfabetgrootte. In een groot alfabet zijn de symboolkansen klein, dus Huffman-codes zijn lang. In een klein alfabet wordt het tegenovergestelde beeld waargenomen. Intuïtief is dit logisch omdat voor een klein alfabet slechts een paar codes nodig zijn, dus ze zijn allemaal kort, maar een groot alfabet vereist veel codes, en sommige daarvan moeten lang zijn.

Rijst. 1.6. Huffman-code voor het Engelse alfabet.

In afb. Figuur 1.6 toont de Huffman-code voor alle 26 letters van het Engelse alfabet.

Het geval van een alfabet waarin de symbolen even waarschijnlijk zijn, is bijzonder interessant. In afb. Figuur 1.7 toont Huffman-codes voor een alfabet met 5, 6, 7 en 8 even waarschijnlijke tekens. Als de alfabetgrootte een macht van 2 is, zijn de resultaten eenvoudigweg codes met een vaste lengte. In andere gevallen liggen de codes vrij dicht bij codes met een vaste lengte. Dit betekent dat er geen voordeel is aan het gebruik van codes met variabele lengte. In tafel 1.8 toont de codes, hun gemiddelde lengte en varianties.

Rijst. 1.7. Huffman codeert met gelijke kansen.

Het feit dat gegevens met even waarschijnlijke tekens niet worden gecomprimeerd door de Huffman-methode kan betekenen dat de reeksen van dergelijke tekens volledig willekeurig zijn. Er zijn echter voorbeelden van tekenreeksen waarin alle tekens even waarschijnlijk zijn, maar niet willekeurig, en kunnen worden gecomprimeerd. Een goed voorbeeld is een reeks waarin elk teken in lange reeksen voorkomt. Zo'n string kan worden gecomprimeerd met behulp van de RLE-methode, maar niet met de Huffman-methode. (De lettercombinatie RLE staat voor ‘run-length encoding’, d.w.z. ‘run-length encoding’. Deze eenvoudige methode is op zichzelf niet erg effectief, maar kan worden gebruikt in compressie-algoritmen met veel fasen, zie

Met andere woorden, we zullen beetje bij beetje vanuit de invoerstroom in de codevariabele van links naar de code duwen< base. При этом на каждой итерации будем увеличивать переменную length на 1 (т.е. продвигаться вниз по дереву). Цикл в (2) остановится когда мы определим длину кода (уровень в дереве, на котором находится искомый символ). Остается лишь определить какой именно символ на этом уровне нам нужен.

Stel dat de lus in (2) na verschillende iteraties stopt. In dit geval is de uitdrukking (code - basis) het serienummer van het gewenste knooppunt (symbool) op lengteniveau. Het eerste knooppunt (symbool) dat zich op lengteniveau in de boom bevindt, bevindt zich in de symb-array op index offs. Maar we zijn niet geïnteresseerd in het eerste teken, maar in het genummerde teken (code - basis). Daarom is de index van het gezochte symbool in de symb-array gelijk aan (offs + (code - base)). Met andere woorden: het gewenste symbool symbol=symb + code - base].

Laten we een specifiek voorbeeld geven. Met behulp van het beschreven algoritme decoderen we het bericht Z /.

Z / = "0001 1 00001 00000 1 010 011 1 011 1 010 011 0001 1 0010 010 011 011 1 1 1 010 1 1 1 0010 011 0011 1 0011 0011 011 1 0 1 1"

  1. code = 0, lengte = 1
  2. code = 0< base = 1
    code = 0<< 1 = 0
    code = 0 + 0 = 0
    lengte = 1 + 1 = 2
    code = 0< base = 2
    code = 0<< 1 = 0
    code = 0 + 0 = 0
    lengte = 2 + 1 = 3
    code = 0< base = 2
    code = 0<< 1 = 0
    code = 0 + 1 = 1
    lengte = 3 + 1 = 4
    code = 1 = basis = 1
  3. symbool = symb = 2 + code = 1 - basis = 1] = symb = A
  1. code = 1, lengte = 1
  2. code = 1 = basis = 1
  3. symbool = symb = 7 + code = 1 - basis = 1] = symb = H
  1. code = 0, lengte = 1
  2. code = 0< base = 1
    code = 0<< 1 = 0
    code = 0 + 0 = 0
    lengte = 1 + 1 = 2
    code = 0< base = 2
    code = 0<< 1 = 0
    code = 0 + 0 = 0
    lengte = 2 + 1 = 3
    code = 0< base = 2
    code = 0<< 1 = 0
    code = 0 + 0 = 0
    lengte = 3 + 1 = 4
    code = 0< base = 1
    code = 0<< 1 = 0
    code = 0 + 1 = 1
    lengte = 4 + 1 = 5
    code = 1 > basis = 0
  3. symbool = symb = 0 + code = 1 - basis = 0] = symb = F

Dus hebben we de eerste 3 karakters gedecodeerd: A, H, F. Het is duidelijk dat we met dit algoritme precies het bericht S zullen ontvangen.

Berekening van codelengtes

Om een ​​bericht te coderen, moeten we de tekencodes en hun lengte kennen. Zoals opgemerkt in de vorige sectie, worden canonieke codes volledig bepaald door hun lengte. Onze hoofdtaak is dus het berekenen van de lengte van de codes.

Het blijkt dat voor deze taak in de overgrote meerderheid van de gevallen niet expliciet een Huffman-boom hoeft te worden geconstrueerd. Bovendien zijn algoritmen die een interne (niet expliciete) representatie van de Huffman-boom gebruiken veel efficiënter in termen van snelheid en geheugenkosten.

Tegenwoordig zijn er veel effectieve algoritmen voor het berekenen van codelengtes (,). We zullen ons beperken tot het beschouwen van slechts één ervan. Dit algoritme is vrij eenvoudig, maar desondanks is het erg populair. Het wordt gebruikt in programma's zoals zip, gzip, pkzip, bzip2 en vele andere.

Laten we terugkeren naar het algoritme voor het construeren van de Huffman-boom. Bij elke iteratie voerden we een lineaire zoektocht uit naar de twee knooppunten met het laagste gewicht. Het is duidelijk dat een prioriteitswachtrij zoals een piramide (minimaal) hiervoor geschikter is. Het knooppunt met het minste gewicht heeft de hoogste prioriteit en staat bovenaan de piramide. Laten we dit algoritme presenteren.

    Laten we alle gecodeerde symbolen in de piramide opnemen.

    We zullen achtereenvolgens 2 knooppunten uit de piramide halen (dit zijn de twee knooppunten met het minste gewicht).

    Laten we een nieuw knooppunt vormen en daaraan, als kinderen, twee knooppunten uit de piramide koppelen. In dit geval stellen we het gewicht van het gevormde knooppunt gelijk aan de som van de gewichten van de onderliggende knooppunten.

    Laten we het gevormde knooppunt in de piramide opnemen.

    Als er meer dan één knooppunt in de piramide is, herhaal dan 2-5.

We gaan ervan uit dat voor elk knooppunt een verwijzing naar zijn ouder is opgeslagen. Aan de wortel van de boom stellen we deze pointer gelijk aan NULL. Laten we nu een bladknooppunt (symbool) selecteren en, door de opgeslagen wijzers te volgen, klimmen we in de boom totdat de volgende wijzer NULL wordt. De laatste voorwaarde betekent dat we de wortel van de boom hebben bereikt. Het is duidelijk dat het aantal overgangen van niveau naar niveau gelijk is aan de diepte van het bladknooppunt (symbool), en dus de lengte van zijn code. Door op deze manier alle knooppunten (symbolen) te doorlopen, krijgen we de lengte van hun codes.

Maximale codelengte

In de regel wordt bij het coderen de zogenaamde codeboek (codeboek), een eenvoudige datastructuur, in wezen twee arrays: één met lengtes, de andere met codes. Met andere woorden, de code (als een bitstring) wordt opgeslagen in een geheugenlocatie of register met een vaste grootte (meestal 16, 32 of 64). Om te voorkomen dat er een overflow ontstaat, moeten we er zeker van zijn dat de code in het register past.

Het blijkt dat op een alfabet met N-tekens de maximale codegrootte maximaal (N-1) bits lang kan zijn. Met andere woorden, met N=256 (een gebruikelijke optie) kunnen we een code krijgen van 255 bits lang (hoewel het bestand hiervoor erg groot moet zijn: 2.292654130570773*10^53~=2^177.259)! Het is duidelijk dat een dergelijke code niet in het register past en dat er iets mee gedaan moet worden.

Laten we eerst eens kijken onder welke omstandigheden overstroming optreedt. Laat de frequentie van het i-de symbool gelijk zijn aan het i-de Fibonacci-getal. Bijvoorbeeld: A-1, B-1, C-2, D-3, E-5, F-8, G-13, H-21. Laten we de overeenkomstige Huffman-boom construeren.

WORTEL /\ / \ / \ /\ H / \ / \ /\ G / \ / \ /\ F / \ / \ /\ E / \ / \ /\ D / \ / \ /\ C / \ / \ A B

Zo'n boom heet ontaarden. Om het te kunnen ontvangen, moeten de frequenties van de symbolen minstens evenveel groeien als de Fibonacci-getallen of zelfs sneller. Hoewel het in de praktijk met echte gegevens vrijwel onmogelijk is om zo'n boom te verkrijgen, is het heel eenvoudig om deze kunstmatig te genereren. Met dit gevaar moet in ieder geval rekening worden gehouden.

Dit probleem kan op twee aanvaardbare manieren worden opgelost. De eerste is gebaseerd op een van de eigenschappen van canonieke codes. Feit is dat in een canonieke code (bitstring) geen significante bits anders dan nul kunnen zijn. Met andere woorden: alle andere bits worden mogelijk helemaal niet opgeslagen, omdat ze zijn altijd nul. In het geval van N=256 hoeven we alleen de minst significante 8 bits van elke code op te slaan, ervan uitgaande dat alle andere bits gelijk zijn aan nul. Dit lost het probleem op, maar slechts gedeeltelijk. Dit zal zowel het coderen als het decoderen aanzienlijk compliceren en vertragen. Daarom wordt deze methode in de praktijk zelden gebruikt.

De tweede methode is het kunstmatig beperken van de lengte van de codes (tijdens de constructie of daarna). Deze methode is algemeen aanvaard, dus we zullen er dieper op ingaan.

Er zijn twee soorten algoritmen voor het beperken van de codelengte. Heuristisch (bij benadering) en optimaal. Algoritmen van het tweede type zijn behoorlijk complex om te implementeren en vereisen in de regel meer tijd en geheugen dan de eerste. De effectiviteit van een heuristisch beperkte code wordt bepaald door de afwijking ervan van de optimaal beperkte code. Hoe kleiner dit verschil, hoe beter. Het is vermeldenswaard dat dit verschil voor sommige heuristische algoritmen erg klein is ( , , ), en dat ze heel vaak optimale code genereren (hoewel ze niet garanderen dat dit altijd het geval zal zijn). Bovendien, omdat in de praktijk komt overflow uiterst zelden voor (tenzij er een zeer strikte beperking is op de maximale codelengte); bij een kleine alfabetgrootte is het beter om eenvoudige en snelle heuristische methoden te gebruiken.

We zullen kijken naar een vrij eenvoudig en zeer populair heuristisch algoritme. Het heeft zijn toepassing gevonden in programma's zoals zip, gzip, pkzip, bzip2 en vele andere.

Het probleem van het beperken van de maximale codelengte is gelijk aan het probleem van het beperken van de hoogte van de Huffman-boom. Merk op dat door de constructie elk niet-bladig knooppunt in een Huffman-boom precies twee kinderen heeft. Bij elke iteratie van ons algoritme zullen we de hoogte van de boom met 1 verminderen. Laat L dus de maximale codelengte (boomhoogte) zijn en we willen deze beperken tot L / < L. Laat RN i verder de meest rechtse bladknooppunt op niveau i, en LN i is het meest linkse.

Laten we beginnen te werken vanaf niveau L. Laten we knooppunt RNL verplaatsen naar de plaats van zijn ouder. Omdat knooppunten gaan in paren; we moeten een plaats vinden voor het knooppunt grenzend aan RN L. Om dit te doen, vinden we het niveau j dat het dichtst bij L ligt en dat bladknooppunten bevat, zodat j < (L-1). In plaats van LN j zullen we een niet-bladig knooppunt vormen en hieraan als kinderen het knooppunt LN j en het resterende ongepaarde knooppunt van niveau L koppelen. Pas dezelfde bewerking toe op alle resterende paren knooppunten op niveau L. Het is duidelijk dat we, door de knooppunten op deze manier te herverdelen, de hoogte van onze boom met 1 hebben verkleind. Nu is deze gelijk aan (L-1). Als nu L / < (L-1), dan zullen we hetzelfde doen met niveau (L-1), enz. totdat de vereiste limiet is bereikt.

Laten we terugkeren naar ons voorbeeld, waar L=5. Laten we de maximale codelengte beperken tot L / =4.

WORTEL /\ / \ / \ /\ H C E / \ / \ / \ / \ /\ A D G / \ / \ B F

Het is te zien dat in ons geval RN L = F, j=3, LNj = C. Eerst verplaatsen we het knooppunt RN L = F in de plaats van zijn ouders.

WORTEL /\ / \ / \ /\ H / \ / \ / \ / \ / \ / \ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ C E / \ / \ / \ / \ F A D G B(ongepaarde knoop)

Nu op plaats LN j = C Laten we een niet-bladknooppunt vormen.

WORTEL /\ / \ / \ /\ H E / \ / \ / \ / \ / \ / \ F A D G ? ? B(ongepaarde knoop) C(ongepaarde knoop)

Laten we twee ongepaarde aan het gevormde knooppunt koppelen: B En C.

WORTEL /\ / \ / \ /\ H / \ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ /\ E / \ / \ / \ / \ / \ / \ F A D G B C

Daarom hebben we de maximale codelengte beperkt tot 4. Het is duidelijk dat we door het wijzigen van de codelengtes een beetje aan efficiëntie hebben verloren. Het bericht S, gecodeerd met behulp van een dergelijke code, zal dus een grootte hebben van 92 bits, d.w.z. 3 bits meer vergeleken met minimaal redundante code.

Het is duidelijk dat hoe meer we de maximale codelengte beperken, hoe minder efficiënt de code zal zijn. Laten we eens kijken in hoeverre we de maximale codelengte kunnen beperken. Uiteraard niet korter.

Het berekenen van canonieke codes

Zoals we herhaaldelijk hebben opgemerkt, zijn de lengtes van de codes voldoende om de codes zelf te genereren. Laten we laten zien hoe dit kan worden gedaan. Laten we aannemen dat we de codelengtes al hebben berekend en hebben geteld hoeveel codes van elke lengte we hebben. Laat L de maximale codelengte zijn en T i het aantal codes met lengte i.

Laten we Si berekenen - de initiële waarde van de code met lengte i, voor alle i

SL = 0 (altijd)
S L-1 = (S L + T L) >> 1
S L-2 = (S L-1 + T L-1) >> 1
...
S 1 = 1 (altijd)

Voor ons voorbeeld: L = 5, T 1 .. 5 = (1, 0, 2,3, 2).

S 5 = 00000 bak = 0 dec
S 4 = (S 5 =0 + T 5 =2) >> 1 = (00010 bak >> 1) = 0001 bak = 1 dec
S 3 = (S 4 =1 + T 4 =3) >> 1 = (0100 bak >> 1) = 010 bak = 2 dec
S 2 = (S 3 =2 + T 3 =2) >> 1 = (100 bak >> 1) = 10 bak = 2 dec
S 1 = (S 2 =2 + T 2 =0) >> 1 = (10 bak >> 1) = 1 bak = 1 dec

Het is duidelijk dat S 5, S 4, S 3, S 1 precies karaktercodes zijn B, A, C, H. Wat deze symbolen gemeen hebben is dat ze allemaal op de eerste plaats komen, elk op hun eigen niveau. Met andere woorden: we hebben de initiële codewaarde voor elke lengte (of niveau) gevonden.

Laten we nu codes toewijzen aan de resterende symbolen. De code van het eerste teken op niveau i is Si, het tweede is S i + 1, het derde is S i + 2, enz.

Laten we de resterende codes voor ons voorbeeld opschrijven:

B= S 5 = 00000 bak A= S 4 = 0001 bak C= S 3 = 010 bak H= S 1 = 1 bak
F= S 5 + 1 = 00001 bak D= S 4 + 1 = 0010 bak E= S 3 + 1 = 011 bak
G= S 4 + 2 = 0011 bak

Het is duidelijk dat we precies dezelfde codes hebben verkregen alsof we expliciet de canonieke Huffman-boom hadden gebouwd.

Overdracht van codeboom

Om een ​​gecodeerd bericht te kunnen decoderen, moet de decoder dezelfde codeboom hebben (in een of andere vorm) die werd gebruikt tijdens het coderen. Daarom zijn we gedwongen om, samen met de gecodeerde gegevens, de bijbehorende codeboom op te slaan. Het is duidelijk dat hoe compacter het is, hoe beter.

Er zijn verschillende manieren om dit probleem op te lossen. De meest voor de hand liggende oplossing is om de boom expliciet op te slaan (dat wil zeggen, als een geordende reeks knooppunten en aanwijzers van een of andere soort). Dit is misschien wel de meest verkwistende en ineffectieve manier. In de praktijk wordt er geen gebruik van gemaakt.

U kunt een lijst met symboolfrequenties opslaan (dwz een frequentiewoordenboek). Met zijn hulp kan de decoder de codeboom eenvoudig reconstrueren. Hoewel deze methode minder verspillend is dan de vorige, is deze niet de beste.

Ten slotte kunt u een van de eigenschappen van canonieke codes gebruiken. Zoals eerder opgemerkt, worden canonieke codes volledig gedefinieerd door hun lengte. Met andere woorden: het enige wat de decoder nodig heeft is een lijst met tekencodelengtes. Gezien het feit dat gemiddeld de lengte van één code voor een alfabet van N karakters kan worden gecodeerd in [(log 2 (log 2 N))] bits, verkrijgen we een zeer efficiënt algoritme. We zullen er dieper op ingaan.

Laten we aannemen dat de alfabetgrootte N=256 is en we comprimeren het gewone tekstbestand(ASCII). Hoogstwaarschijnlijk zullen we niet alle N-tekens van ons alfabet in zo'n bestand vinden. Laten we vervolgens de lengte van de code van ontbrekende tekens gelijk stellen aan nul. In dit geval zal de opgeslagen lijst met codelengtes voldoende bevatten groot aantal nullen (codelengtes van ontbrekende tekens) gegroepeerd. Elke groep kan worden gecomprimeerd met behulp van de zogenaamde groepscodering - RLE (Run - Length - Encoding). Dit algoritme is uiterst eenvoudig. In plaats van een reeks van M identieke elementen op een rij, zullen we het eerste element van deze reeks en het aantal herhalingen ervan opslaan, d.w.z. (M-1). Voorbeeld: RLE("AAABBBCDDDDDD")=A3 B2 C0 D6.

Bovendien kan deze werkwijze enigszins worden uitgebreid. Wij kunnen solliciteren RLE-algoritme niet alleen voor groepen met een lengte van nul, maar ook voor alle andere. Deze methode voor het verzenden van een codeboom is algemeen aanvaard en wordt in de meeste moderne implementaties gebruikt.

Implementatie: SHCODEC

Bijlage: biografie van D. Huffman

David Huffman werd in 1925 geboren in Ohio, VS. Huffman behaalde een bachelordiploma in elektrotechniek van Staatsuniversiteit Ohio (Ohio State University) op 18-jarige leeftijd. Vervolgens diende hij in het leger als radarondersteuningsofficier op een torpedobootjager die na de Tweede Wereldoorlog hielp bij het opruimen van mijnen in Japanse en Chinese wateren. Vervolgens behaalde hij een masterdiploma aan de Ohio University en een doctoraat aan het Massachusetts Institute of Technology (MIT). Hoewel Huffman vooral bekend is vanwege het ontwikkelen van een methode voor het construeren van minimaal redundante codes, heeft hij ook belangrijke bijdragen geleverd op vele andere gebieden (vooral elektronica). Hij voor een lange tijd Hoofd van de afdeling Computerwetenschappen aan het MIT. In 1974 nam hij, reeds emeritus hoogleraar, ontslag. Huffman ontving een aantal waardevolle onderscheidingen. 1999 - Richard W. Hamming-medaille van het Institute of Electrical and Electronics Engineers (IEEE) voor uitzonderlijke bijdragen aan de informatietheorie, Louis E. Levy-medaille van het Franklin Institute voor zijn proefschrift over sequentiële schakelcircuits, de W. Wallace McDowell Award, de IEEE Computer Society Award en de IEEE Golden Anniversary Technology Innovation Award in 1998. In oktober 1999 stierf David Huffman op 74-jarige leeftijd aan kanker.

R.L. Milidiu, A.A. Pessoa, ES Laber, "Efficiënte implementatie van het opwarmalgoritme voor de constructie van in lengte beperkte prefixcodes", Proc. van ALENEX (Internationale workshop over algoritme-engineering en experimenten), pp. 1-17, Springer, januari. 1999.

Op dit moment Weinig mensen denken na over hoe bestandscompressie werkt. Vergeleken met eerder gebruik persoonlijke computer het werd veel gemakkelijker. En bijna iedereen die ermee werkt bestandssysteem, maakt gebruik van archieven. Maar weinig mensen denken na over hoe ze werken en volgens welk principe bestandscompressie plaatsvindt. De allereerste versie van dit proces waren Huffman-codes, en deze worden nog steeds gebruikt in verschillende populaire archiveringsprogramma's. Veel gebruikers denken er niet eens over na hoe gemakkelijk het is om een ​​bestand te comprimeren en hoe het werkt. In dit artikel zullen we bekijken hoe compressie plaatsvindt, welke nuances het coderingsproces helpen versnellen en vereenvoudigen, en we zullen ook het principe van het construeren van een coderingsboom begrijpen.

Geschiedenis van het algoritme

Het allereerste algoritme voor efficiënt coderen elektronische informatie werd de code die Huffman halverwege de twintigste eeuw voorstelde, namelijk in 1952. Hij is momenteel de belangrijkste basis element de meeste programma's zijn ontworpen om informatie te comprimeren. Op dit moment zijn enkele van de meest populaire bronnen die deze code gebruiken ZIP-archieven, ARJ, RAR en vele anderen.

Ook dit algoritme Huffman geldt voor anderen grafische objecten. Welnu, alle moderne faxen gebruiken ook codering, uitgevonden in 1952. Ondanks het feit dat er zoveel tijd is verstreken sinds de code is gemaakt, wordt deze nog steeds gebruikt in de nieuwste shells en op apparatuur van oude en moderne typen.

Efficiënt codeerprincipe

Het Huffman-algoritme is gebaseerd op een schema waarmee u de meest waarschijnlijke, meest voorkomende symbolen van het systeem kunt vervangen. En degenen die minder vaak voorkomen, worden vervangen door langere codes. De overgang naar lange Huffman-codes vindt pas plaats nadat het systeem alles heeft gebruikt minimumwaarden. Met deze techniek kunt u de codelengte per teken minimaliseren Originele bericht over het algemeen.

Het belangrijke punt is dat aan het begin van het coderen de kansen van de letters al bekend moeten zijn. Op basis hiervan zal het uiteindelijke bericht worden samengesteld. Op basis van deze gegevens wordt een Huffman-codeboom opgebouwd, op basis waarvan het proces van het coderen van brieven in het archief zal worden uitgevoerd.

Huffman-codevoorbeeld

Laten we, om het algoritme te illustreren, nemen grafische versie het bouwen van een codeboom. Om deze methode effectief te gebruiken, is het de moeite waard om de definitie van enkele van de waarden die nodig zijn voor het concept te verduidelijken deze methode. Een reeks bogen en knooppunten die van knooppunt naar knooppunt zijn gericht, wordt gewoonlijk een grafiek genoemd. De boom zelf is een grafiek met een aantal bepaalde eigenschappen:

  • elk knooppunt kan niet meer dan één van de bogen bevatten;
  • een van de knooppunten moet de wortel van de boom zijn, dat wil zeggen dat deze helemaal geen bogen mag bevatten;
  • Als je vanaf de wortel langs bogen begint te bewegen, zou dit proces je in staat moeten stellen om absoluut elk van de knooppunten te bereiken.

Er is ook zo'n concept opgenomen in de Huffman-codes als een blad van een boom. Het vertegenwoordigt een knooppunt waaruit geen boog mag voortkomen. Als twee knooppunten met elkaar zijn verbonden door een boog, dan is een van hen een ouder en de andere een kind, afhankelijk van uit welk knooppunt de boog komt en waar deze binnenkomt. Als twee knooppunten hetzelfde ouderknooppunt hebben, worden ze gewoonlijk zusterknooppunten genoemd. Als de knooppunten naast de bladeren meerdere bogen hebben, wordt deze boom binair genoemd. Dit is precies wat een Huffman-boom is. Kenmerken van knooppunten van deze constructie is dat het gewicht van elke ouder gelijk is aan de som van de gewichten van al zijn knooppuntkinderen.

Huffman-boomconstructie-algoritme

De constructie van de Huffman-code bestaat uit de letters van het invoeralfabet. Er wordt een lijst gevormd met de knooppunten die vrij zijn in de toekomstige codeboom. Het gewicht van elk knooppunt in deze lijst moet hetzelfde zijn als de waarschijnlijkheid van het voorkomen van de berichtletter die overeenkomt met dat knooppunt. In dit geval wordt uit verschillende vrije knooppunten van de toekomstige boom degene geselecteerd die het minst weegt. Bovendien, als de minimale indicatoren in verschillende knooppunten worden waargenomen, kunt u vrijelijk een van de paren kiezen.

Hierna wordt een ouderknooppunt gemaakt, dat hetzelfde zou moeten wegen als de som van dit paar knooppunten. Hierna wordt de ouder naar de lijst met vrije knooppunten gestuurd en worden de kinderen verwijderd. In dit geval ontvangen de bogen de overeenkomstige indicatoren, enen en nullen. Dit proces wordt net lang genoeg herhaald om slechts één knooppunt over te laten. Daarna worden ze van boven naar beneden uitgeschreven.

Verbetering van de compressie-efficiëntie

Om de compressie-efficiëntie te verbeteren, moet u bij het bouwen van een codeboom alle gegevens gebruiken met betrekking tot de waarschijnlijkheid dat letters verschijnen specifiek bestand, vastgemaakt aan de boom, en zorg ervoor dat ze niet verspreid raken een groot aantal tekstdocumenten. Als u dit bestand eerst doorneemt, kunt u meteen statistieken berekenen over hoe vaak letters van het te comprimeren object voorkomen.

Versnelt het compressieproces

Om het werk van letters te versnellen, is het noodzakelijk om niet uit te voeren op basis van indicatoren van de waarschijnlijkheid van het verschijnen van een bepaalde letter, maar op basis van de frequentie van voorkomen ervan. Hierdoor wordt het algoritme eenvoudiger en gaat het werken ermee aanzienlijk sneller. Het vermijdt ook drijvende-komma- en delingsoperaties.

Bovendien werkt het werken in deze modus dynamische code Huffman, of beter gezegd het algoritme zelf, is niet aan veranderingen onderhevig. Dit komt voornamelijk door het feit dat kansen recht evenredig zijn met frequenties. Het is de moeite waard om speciale aandacht te besteden aan het feit dat het uiteindelijke gewicht van het bestand of het zogenaamde rootknooppunt gelijk zal zijn aan de som van het aantal letters in het te verwerken object.

Conclusie

Huffman-codes zijn een eenvoudig en al lang bestaand algoritme dat nog steeds door velen wordt gebruikt bekende programma's en bedrijven. Dankzij de eenvoud en duidelijkheid kunt u effectieve compressieresultaten bereiken voor bestanden van elke grootte en de ruimte die ze op de opslagschijf innemen aanzienlijk verminderen. Met andere woorden: het Huffman-algoritme is een lang bestudeerd en ontwikkeld schema waarvan de relevantie tot op de dag van vandaag niet is afgenomen.

En dankzij de mogelijkheid om de grootte van bestanden te verkleinen, wordt het overbrengen ervan via het netwerk of andere middelen eenvoudiger, sneller en handiger. Als u met het algoritme werkt, kunt u absoluut alle informatie comprimeren zonder de structuur en kwaliteit ervan te schaden, maar met maximaal effect het verminderen van het bestandsgewicht. Met andere woorden: Huffman-codering is en blijft de meest populaire en huidige methode compressie van bestandsgrootte.

Huffman-codering. Deel 1.
Invoering
Hallo, beste lezer! Dit artikel bespreekt een van de datacompressiemethoden. Deze methode is vrij wijdverspreid en verdient enige aandacht. Dit materiaal is ontworpen voor drie artikelen, waarvan de eerste zal worden gewijd aan het compressie-algoritme, de tweede - software-implementatie algoritme, en de derde is decompressie. Het compressie-algoritme wordt geschreven in C++, het decompressie-algoritme in Assembler.
Voordat we echter verder gaan met het algoritme zelf, moet er eerst een beetje theorie in het artikel worden opgenomen.
Een beetje theorie
Compressie (compressie) is een methode om het gegevensvolume te verminderen met het oog op verdere verzending en opslag.
Decompressie is een methode om gecomprimeerde gegevens in hun oorspronkelijke vorm te herstellen.
Compressie en decompressie kan plaatsvinden zonder kwaliteitsverlies (wanneer de verzonden/opgeslagen informatie in gecomprimeerde vorm na decompressie absoluut identiek is aan het origineel), of met kwaliteitsverlies (wanneer de gegevens na decompressie verschillen van het origineel). Bijvoorbeeld, tekstdocumenten, databases en programma's kunnen alleen worden gecomprimeerd met behulp van een methode zonder kwaliteitsverlies, terwijl afbeeldingen, video's en audiobestanden juist worden gecomprimeerd vanwege het kwaliteitsverlies van de originele gegevens (een typisch voorbeeld van algoritmen is JPEG, MPEG, ADPCM), met soms een onmerkbaar kwaliteitsverlies, zelfs bij compressie 1:4 of 1:10.
De belangrijkste soorten verpakkingen worden onderscheiden:
  • Decimale verpakking is bedoeld voor het verpakken van tekengegevens die alleen uit cijfers bestaan. In plaats van 8 bits per teken te gebruiken, is het redelijk rationeel om slechts 4 bits te gebruiken voor decimale en hexadecimale cijfers, 3 bits voor octaal enzovoort. Bij deze aanpak is al een compressie van minimaal 1:2 voelbaar.
  • Relatieve codering is verliesgevende codering. Het is gebaseerd op het feit dat het volgende data-element verschilt van het vorige in een hoeveelheid die minder geheugenruimte in beslag neemt dan het element zelf. Een typisch voorbeeld is ADPCM (Adaptive Differential Pulse Code Modulation) audiocompressie, die veel wordt gebruikt in digitale telefonie en waarmee audiogegevens kunnen worden gecomprimeerd in een verhouding van 1:2 met een vrijwel onmerkbaar kwaliteitsverlies.
  • Symbolische onderdrukking- een methode voor informatiecompressie waarbij lange reeksen identieke gegevens worden vervangen door kortere.
  • Statistische codering is gebaseerd op het feit dat niet alle gegevensitems met dezelfde frequentie (of waarschijnlijkheid) voorkomen. Met deze aanpak worden codes zo geselecteerd dat het meest voorkomende element overeenkomt met een code met de kortste lengte, en het minst voorkomende element overeenkomt met het langste.
Bovendien zijn de codes zodanig geselecteerd dat tijdens het decoderen het element van de brongegevens ondubbelzinnig kan worden bepaald. Met deze aanpak is alleen bitgeoriënteerde codering mogelijk, waarbij onderscheid wordt gemaakt tussen toegestane en verboden codes. Als bij het decoderen van een bitreeks de code verboden blijkt te zijn, dan is het nodig om er nog een bit van de originele reeks aan toe te voegen en de decodering te herhalen. Voorbeelden van dergelijke codering zijn de algoritmen van Shannon en Huffman, waarvan we de laatste zullen overwegen.
Meer specifiek over het algoritme
Zoals al bekend uit de vorige paragraaf is het Huffman-algoritme gebaseerd op statistische codering. Laten we de implementatie ervan eens nader bekijken.
Laat er een gegevensbron zijn die symbolen verzendt (a_1, a_2, ..., a_n) Met op verschillende niveaus waarschijnlijkheid, dat wil zeggen dat elke a_i zijn eigen waarschijnlijkheid (of frequentie) P_i(a_i) heeft, en er is ten minste één paar a_i en a_j, i\ne j, zodat P_i(a_i) en P_j(a_j) niet gelijk zijn . Hierdoor ontstaat een reeks frequenties (P_1(a_1), P_2(a_2),...,P_n(a_n)), waar heeft het mee te maken \displaystyle \sum_(i=1)^(n) P_i(a_i)=1, aangezien de zender behalve (a_1,a_2,...,a_n).
Onze taak is om dergelijke te selecteren codetekens (b_1, b_2,...,b_n) met lengtes (L_1(b_1),L_2(b_2),...,L_n(b_n)) zodat de gemiddelde lengte van het codesymbool de gemiddelde lengte van het originele symbool niet overschrijdt. In dit geval moet rekening worden gehouden met de voorwaarde dat als P_i(a_i)>P_j(a_j) en i\ne j , dan L_i(b_i)\le L_j(b_j).
Huffman stelde voor een boom te bouwen waarin de knooppunten met de hoogste waarschijnlijkheid het minst ver van de wortel verwijderd zijn. Dit is waar de methode voor het construeren van de boom vandaan komt:
1. Selecteer twee symbolen a_i en a_j , i\ne j , zodat P_i(a_i) en P_j(a_j) uit de hele lijst (P_1(a_1),P_2,...,P_n(a_n)) zijn minimaal.
2. Breng de boomtakken van deze twee elementen met waarschijnlijkheid naar één punt P=P_i(a_i)+P_j(a_j), markeer de ene tak met nul en de andere met één (naar eigen inzicht).
3. Herhaal stap 1 en houd er rekening mee nieuw punt in plaats van a_i en a_j als het aantal resulterende punten groter is dan één. Anders hebben we de wortel van de boom bereikt.
Laten we nu proberen de resulterende theorie te gebruiken en de door de bron verzonden informatie te coderen, aan de hand van het voorbeeld van zeven symbolen.
Laten we de eerste cyclus in detail bekijken. De figuur toont een tabel waarin elk symbool a_i zijn eigen waarschijnlijkheid (frequentie) P_i(a_i) heeft. Volgens punt 1 selecteren we twee symbolen uit de tabel met de laagste waarschijnlijkheid. In ons geval zijn dit a_1 en a_4. Volgens punt 2 reduceren we de boomtakken van a_1 en a_4 tot één punt en markeren we de tak die naar a_1 leidt met één, en de tak die naar a_4 leidt met nul. Boven het nieuwe punt wijzen we de waarschijnlijkheid ervan toe (in in dit geval- 0,03) V verdere actie worden herhaald rekening houdend met het nieuwe punt en zonder rekening te houden met a_1 en a_4.

Na het vele malen herhalen van de bovenstaande stappen wordt de volgende boom opgebouwd:

Aan de hand van de geconstrueerde boom kun je de betekenis van de codes bepalen (b_1,b_2,...,b_n), aflopend van de wortel naar het overeenkomstige element a_i , terwijl nul of één wordt toegevoegd aan de resulterende reeks wanneer elke vertakking wordt doorgegeven (afhankelijk van hoe de specifieke vertakking wordt genoemd). De codetabel ziet er dus als volgt uit:

ib ikL ik (b ik) 1 011111 62 1 13 0110 44 011110 65 010 36 00 27 01110 5

Laten we nu proberen een reeks tekens te coderen.
Laat het symbool a_i (als voorbeeld) overeenkomen met het getal i. Laat er een reeks 12672262 zijn. We moeten de resulterende binaire code verkrijgen.
Voor het coderen kunt u de reeds bestaande tabel met codesymbolen b_i gebruiken, waarbij u er rekening mee houdt dat b_i overeenkomt met het symbool a_i. In dit geval is de code voor nummer 1 de reeks 011111, voor nummer 2 - 1 en voor nummer 6 - 00. We krijgen dus het volgende resultaat:

Gegevens12672262CodelengteOrigineel001010110111010010110 01024 bitsGecodeerd011111100011101100119 bits

Als resultaat van de codering hebben we 5 bits gewonnen en de reeks opgenomen met 19 bits in plaats van 24.
Dit biedt echter geen volledige beoordeling van datacompressie. Laten we terugkeren naar de wiskunde en de mate van codecompressie evalueren. Hiervoor is een entropieschatting nodig.
Entropie- een maatstaf voor de onzekerheid van een situatie (willekeurige variabele) met een eindige of even getal uitkomsten. Wiskundig gezien wordt entropie geformuleerd als de som van de producten van waarschijnlijkheden verschillende omstandigheden systemen op de logaritmen van deze kansen, genomen met het tegenovergestelde teken:

H(X)=-\displaystyle \sum_(i=1)^(n)P_i\cdot log_d (P_i).​

Waar X discreet is willekeurige waarde(in ons geval een codesymbool), en d is een willekeurige grondtal groter dan één. De keuze van de basis is gelijk aan de keuze van een specifieke eenheid voor entropiemeting. Aangezien we te maken hebben met binaire cijfers, dan is het rationeel om d=2 als basis te kiezen.
Entropie voor ons geval kan dus worden weergegeven als:

H(b)=-\displaystyle \sum_(i=1)^(n)P_i(a_i)\cdot log_2 (P_i(a_i)).​

Entropie heeft een opmerkelijke eigenschap: het is gelijk aan de minimaal toegestane gemiddelde lengte van een codesymbool \overlijn(L_(min)) in stukjes. De gemiddelde lengte van een codesymbool zelf wordt berekend met de formule

\overline(L(b))=\displaystyle \sum_(i=1)^(n)P_i(a_i)\cdot L_i(b_i).​

Als we de waarden vervangen door de formules H(b) en \overline(L(b)), krijgen we het volgende resultaat: H(b)=2,048, \overlijn(L(b))=2.100.
De waarden van H(b) en \overline(L(b)) liggen heel dicht bij elkaar, wat duidt op een reële winst in de keuze van het algoritme. Vergelijk nu de gemiddelde lengte van het originele symbool en de gemiddelde lengte van het codesymbool via de relatie:

\frac(\overline(L_(src)))(L(b))=\frac(3)(2,1)=1,429.​

We kregen dus een compressieverhouding van 1:1.429, wat erg goed is.
En laten we tot slot het laatste probleem oplossen: het decoderen van een reeks bits.
Laat er een reeks bits zijn voor onze situatie:

001101100001110001000111111​

Moet bepalen bron, dat wil zeggen, deze reeks decoderen.
Natuurlijk kun je in een dergelijke situatie een codetabel gebruiken, maar dit is behoorlijk lastig, omdat de lengte van codesymbolen niet constant is. Het is veel handiger om een ​​boom af te dalen (beginnend bij de wortel) volgens de volgende regel:
1. Het startpunt is de wortel van de boom.
2. Lezen nieuw stukje. Als het nul is, ga dan langs de tak gemarkeerd met nul, anders - met één.
3. Als het punt dat we hebben bereikt definitief is, hebben we een codesymbool bepaald dat moet worden opgeschreven en terugkeren naar stap 1. Anders moet stap 2 worden herhaald.
Laten we een voorbeeld bekijken van het decoderen van het eerste teken. We zijn op een punt met waarschijnlijkheid 1,00 (de wortel van de boom), lezen het eerste bit van de reeks en gaan langs de tak gemarkeerd met nul naar een punt met waarschijnlijkheid 0,60. Omdat dit punt niet het eindpunt in de boom is, lezen we het volgende bit, dat ook nul is, en gaan we langs de tak gemarkeerd met nul naar het punt a_6, wat het eindpunt is. We hebben het symbool ontcijferd - dit is het getal 6. We schrijven het op en keren terug naar de initiële staat(ga naar de wortel).
De gedecodeerde reeks neemt dus de vorm aan.

Gegevens

001101100001110001000111111 CodelengteGecodebitsOrigineel6223676261233 bits

In dit geval bedroeg de versterking 6 bits met een vrij kleine reekslengte.
De conclusie dringt zich op: het algoritme is eenvoudig. Er moet echter een opmerking worden gemaakt: dit algoritme is goed voor compressie tekst informatie(in werkelijkheid gebruiken we ongeveer 60 van de beschikbare 256 tekens bij het typen van tekst, dat wil zeggen dat de kans dat we andere tekens tegenkomen bijna nul is), maar het is al erg genoeg voor het comprimeren van programma's (aangezien alle tekens in een programma bijna even waarschijnlijk). De efficiëntie van het algoritme hangt dus sterk af van het type gegevens dat wordt gecomprimeerd.
P.S
In dit artikel hebben we gekeken naar het Huffman-coderingsalgoritme, dat is gebaseerd op niet-uniforme codering. Hiermee kunt u de omvang van verzonden of opgeslagen gegevens verkleinen. Het algoritme is gemakkelijk te begrijpen en kan echte winsten opleveren. Bovendien heeft het nog een opmerkelijke eigenschap: het vermogen om informatie on-the-fly te coderen en decoderen, op voorwaarde dat de waarschijnlijkheid van de codewoorden correct wordt bepaald. Hoewel er een wijziging in het algoritme is waarmee u de boomstructuur in realtime kunt wijzigen.
In het volgende deel van het artikel zullen we kijken naar byte-georiënteerde bestandscompressie met behulp van het Huffman-algoritme, geïmplementeerd in C++.
Huffman-codering. Deel 2
Invoering
In het laatste deel hebben we het coderingsalgoritme bekeken en beschreven wiskundig model, voerde codering en decodering uit specifiek voorbeeld, berekende de gemiddelde lengte van het codewoord en bepaalde ook de compressieverhouding. Daarnaast zijn er conclusies getrokken over de voor- en nadelen van dit algoritme.
Daarnaast bleven echter nog twee vragen onopgelost: de implementatie van een programma dat een gegevensbestand comprimeert, en een programma dat een gecomprimeerd bestand decomprimeert. Dit artikel is gewijd aan de eerste vraag. Daarom moet je beginnen met ontwerpen.
Ontwerp
Het eerste dat u hoeft te doen, is de frequentie berekenen waarmee tekens in het bestand voorkomen. Om dit te doen, beschrijven we de volgende structuur:

    // Structuur voor het berekenen van de symboolfrequentie

    typedef struct TFreq

    int ch;

    TTafel * tafel;

    DWORD-frequentie;

    ) Tfreq;

Deze structuur beschrijft elk personage uit 256. ch- het ASCII-teken zelf, frequentie― aantal keren dat een symbool in het bestand voorkomt. Veld tafel— verwijzing naar structuur:

    // Knooppuntdescriptor

    typedef struct TTable

    int ch;

    Tafel * links;

    Tafel * rechts;

    ) TTabel;

Als gezien, TTabel is een knooppuntdescriptor met vertakkingen door nul en één. Met behulp van deze constructies zal in de toekomst de compressieboom worden gebouwd. Laten we nu voor elk symbool zijn eigen frequentie en zijn eigen knooppunt declareren:

    Tfreq Freq [256] ;

Laten we proberen erachter te komen hoe de boom zal worden gebouwd. In de beginfase moet het programma het hele bestand doorlopen en het aantal tekens daarin tellen. Bovendien moet het programma voor elk gevonden symbool een knooppunthandle maken. Hierna bouwt het programma, uitgaande van de gemaakte knooppunten, rekening houdend met de frequentie van symbolen, een boom, waarin de knooppunten worden geplaatst in een bepaalde volgorde en het leggen van verbindingen daartussen.
De geconstrueerde boom is goed voor het decoderen van bestanden. Maar voor bestandscodering is het lastig, omdat niet bekend is in welke richting je vanaf de root moet gaan om bij het vereiste teken te komen. Om dit te doen, is het handiger om een ​​conversietabel van symbool naar code te bouwen. Daarom definiëren we een andere structuur:

    // Codetekendescriptor

    typedef struct TOPcode

    DWORD-opcode;

    DWORD-lens;

    ) TOPcode;

Hier opcode is de codecombinatie van het symbool, en len- de lengte (in bits). En laten we een tabel met 256 van dergelijke structuren declareren:

    TOPcode-opcodes[256];

Als u het gecodeerde symbool kent, kunt u het codewoord uit de tabel bepalen. Laten we nu direct verder gaan met het tellen van de frequenties van symbolen (en niet alleen).
Symboolfrequenties tellen
In principe is deze actie niet moeilijk. Het volstaat om het bestand te openen en het aantal tekens erin te tellen, en de bijbehorende structuren in te vullen. Laten we eens kijken naar de implementatie van deze actie.
Laten we, om dit te doen, globale bestandsdescriptors declareren:

    BESTAND *in, *uit, *assembleren;

in– bestand waaruit niet-gecomprimeerde gegevens worden gelezen.
uit– een bestand waarin gecomprimeerde gegevens worden geschreven.
montage– een bestand waarin de boom wordt opgeslagen in een vorm die handig is om uit te pakken. Omdat de uitpakker in assembler zal worden geschreven, is het heel rationeel om de boom onderdeel van de uitpakker te maken, dat wil zeggen deze in de vorm van instructies in assembler te presenteren.
De eerste stap is het initialiseren van alle structuren met nulwaarden:

    // Symboolfrequenties tellen

    int Telfrequentie(void )

    int ik; // lusvariabele

    int-aantal= 0; // tweede lusvariabele

    DWORD Totaal Aantal= 0; // bestandsgrootte.

    // Initialiseer structuren

    voor (i= 0; ik< 256 ; i++ )

    Freq[i].freq = 0;

    Freq[i].tabel = 0;

    Freq[i].ch = i;

Hierna tellen we het aantal keren dat het symbool in het bestand voorkomt en de bestandsgrootte (uiteraard niet op de meest ideale manier, maar het voorbeeld heeft duidelijkheid nodig):

    // Karakterfrequenties tellen (karakter voor karakter)

    terwijl (! feof (in) ) // totdat het einde van het bestand is bereikt

    i= fgetc (in) ;

    als (i!=EOF) // zo niet het einde van het bestand

    Freq[i].freq++; // frequentie++

    TotaalAantal++; // maat ++

Omdat de code ongelijkmatig is, zal het voor de uitpakker moeilijk zijn om te achterhalen hoeveel tekens er worden gelezen. Daarom is het noodzakelijk om de grootte ervan in de uitpaktabel vast te leggen:

    // “Vertel” de uitpakker de bestandsgrootte

    fprintf(assembl, "coded_file_size: \n dd %8lxh\n \n ", Totaal);

Hierna worden alle gebruikte tekens naar het begin van de array verschoven en worden ongebruikte tekens overschreven (door herschikking).

    // verplaats alle ongebruikte tekens naar het einde

    ik= 0;

    aantal= 256;

    terwijl ik< count) // het einde is nog niet bereikt

    if (Freq[ i].freq == 0 ) // als de frequentie 0 is

    Freq[ i] = Freq[ -- aantal] ; // kopieer vervolgens het item vanaf het einde

    anders

    ik++; // alles is in orde - laten we verder gaan.

En pas na een dergelijke "sortering" wordt geheugen toegewezen aan knooppunten (voor enige besparing).

    // Wijs geheugen toe voor knooppunten

    voor (i= 0; ik< count; i++ )

    Freq[ i].table = nieuwe TTable; // maak een knooppunt

    Freq[ i].tabel - > links= 0 ; // geen verbindingen

    Freq[ i].tabel - > rechts= 0 ; // geen verbindingen

    Freq[ i].tabel - > ch= Freq.ch ; // kopieer het symbool

    Freq[ i].freq = Freq.freq ; // en frequentie

    retourtelling;

We schreven dus een functie voor de initiële initialisatie van het systeem, of, als je naar het algoritme in het eerste deel van het artikel kijkt, ‘we schreven de symbolen op die in een kolom werden gebruikt en kenden er waarschijnlijkheden aan toe’, en ook voor voor elk symbool hebben we een ‘startpunt’ – een knooppunt – gemaakt en geïnitialiseerd. De velden in links En rechts nullen opgeschreven. Als een knooppunt dus het laatste knooppunt in de boom is, is het gemakkelijk te zien links En rechts, gelijk aan nul.
Een boom maken
Dus in de vorige sectie hebben we “de symbolen vastgelegd die in een kolom werden gebruikt en er waarschijnlijkheden aan toegewezen.” In feite hebben we er geen kansen aan toegekend, maar de tellers van de breuk (dat wil zeggen het aantal keren dat tekens in het bestand voorkomen). Nu moeten we een boom bouwen. Maar om dit te doen, moet je vinden minimaal onderdeel op de lijst. Om dit te doen introduceren we een functie waaraan we twee parameters doorgeven: het aantal elementen in de lijst en het element dat moet worden uitgesloten (omdat we in paren zullen zoeken, en het zal erg onaangenaam zijn als we hetzelfde element ontvangen van de functie twee keer):

    // zoek naar het knooppunt met de laagste waarschijnlijkheid.

    int FindLeast(int-aantal, int-index)

    int ik;

    DWORD min= (index== 0 ) ? 10; // element dat we tellen

    // minimaal

    voor (i= 1; ik< count; i++ ) // loop door de array

    als (i!=index) // als het element niet is uitgesloten

    als (Freq[i].freq< Freq[ min] .freq ) // сравниваем

    min=ik; // minder dan het minimum - onthoud

    retour min; // retourneer de minimale index

De zoekopdracht is eenvoudig geïmplementeerd: eerst selecteren we het “minimum” element van de array. Als het uitgesloten element 0 is, nemen we het eerste element als minimum, anders beschouwen we nul als minimum. Terwijl we door de array bewegen, vergelijken we het huidige element met het ‘minimale’ element, en als het kleiner blijkt te zijn, markeren we het als minimaal.
In feite functioneert het bouwen van bomen zelf:

    // Boombouwfunctie

    void PreInit(int-telling)

    int ind1, ind2; // elementindexen

    TTabel * tafel; // pointer naar "nieuw knooppunt"

    terwijl (tel> 1) // loop totdat we de root bereiken

    ind1= VindLeast(telling,- 1) ; // eerste knooppunt

    ind2= VindLeast(telling,ind1) ; // tweede knooppunt

    tabel= nieuwe TTabel; // maak een nieuw knooppunt

    tabel->ch= - 1; // niet definitief

    tabel->links= Freq[ind1].tabel ; // 0 - knooppunt 1

    tabel->rechts= Freq[ind2].tabel ; // 1 - knooppunt 2

    Freq[ind1].ch = - 1; // wijzig het item over

    Freq[ind1].freq + = Freq[ind2].freq ; // frequentie voor het symbool

    Freq[ind1].tabel = tabel; // en schrijf een nieuw knooppunt

    als (ind2! = (-- tellen) ) // als ind2 niet de laatste is

    Freq[ ind2] = Freq[aantal] ; // dan op zijn plaats

    // plaats de laatste in de array

Codesymbooltabel
Dus bouwden we een boom in het geheugen: we namen twee knooppunten in paren, creëerden een nieuw knooppunt, waarin we verwijzingen naar hen schreven, waarna het tweede knooppunt uit de lijst werd verwijderd, en in plaats van het eerste knooppunt, een nieuw knooppunt is geschreven met een tak.
Nu doet zich een ander probleem voor: boomcodering is lastig, omdat je precies moet weten op welk pad een bepaald symbool zich bevindt. Het probleem wordt echter heel eenvoudig opgelost: er wordt een andere tabel gemaakt - een tabel met codesymbolen - en de bitcombinaties van alle gebruikte symbolen worden geschreven. Om dit te doen, volstaat het om de boom één keer recursief te doorkruisen. Om het niet opnieuw te omzeilen, kunt u tegelijkertijd het genereren van een assemblagebestand toevoegen aan de bypass-functie voor verdere decodering van gecomprimeerde gegevens (zie sectie " Ontwerp").
Eigenlijk is de functie zelf niet ingewikkeld. Er moet 0 of 1 aan de codecombinatie worden toegewezen als het knooppunt niet het eindknooppunt is. Voeg anders het codesymbool toe aan de tabel. Genereer naast dit alles een assembler-bestand. Overweeg deze functie:

    void RecurseMake(TTable * tbl, DWORD opcode, int len)

    fprintf (assembl,"opcode%08lx_%04x: \N",opcode,len); //label naar bestand

    if (tbl- > ch! = - 1 ) // eindknooppunt

    BYTE mod= 32 - len;

    Opcodes[tbl->ch].opcode = (opcode>> mod) ; // sla de code op

    Opcodes[tbl- > ch].len = len; // en de lengte ervan (in bits)

    // en maak het bijbehorende label

    fprintf(assembleren, " db %03xh,0ffh,0ffh,0ffh\n \n ",tbl->ch) ;

    anders // knooppunt is niet definitief

    opcode>>= 1 ; // maak ruimte voor een nieuw stukje

    len++; // vergroot de lengte van het codewoord

    \N",opcode,len);

    fprintf (assembl," dw opcode%08lx_%04x \n\n",opcode| 0x80000000 ,len) ;

    RecurseMake(tbl-> links,opcode,len) ;

    RecurseMake(tbl- > right,opcode| 0x80000000,len) ;

    // verwijder het knooppunt (het is niet langer nodig)

    verwijder tbl;

Na het passeren van een knooppunt verwijdert de functie dit onder andere (maakt de aanwijzer vrij). Laten we nu eens kijken wat voor soort parameters aan de functie worden doorgegeven.

  • tbl- een knooppunt dat moet worden omzeild.
  • opcode— huidig ​​codewoord. Het meest significante bit moet altijd gratis zijn.
  • len— lengte van het codewoord.
In principe is de functie niet ingewikkelder dan de ‘klassieke faculteit’ en zou geen problemen moeten veroorzaken.
Bit-uitvoer
Nu hebben we het niet zo prettige deel van ons archiveringshulpmiddel bereikt, namelijk de uitvoer van codetekens naar een bestand. Het probleem is dat de codesymbolen een ongelijke lengte hebben en dat de uitvoer bitsgewijs moet gebeuren. De functie zal hierbij helpen ZetCode. Maar laten we eerst twee variabelen declareren: de bitteller in de byte en de uit te voeren byte:

    // Bitteller

    int UitBits;

    // Uitvoerteken

    BYTE OutChar;

OutBits wordt elke keer dat een bit wordt uitgevoerd met één verhoogd. OutBits==8 geeft aan dat de OutChar in een bestand moet worden opgeslagen.

    ongeldige PutCode(int ch)

    int len;

    int-uitcode;

    // haal de lengte van het codewoord en het codewoord zelf op

    outcode= Opcodes[ch].opcode ; // een codewoord

    len= Opcodes[ch].len ; // lengte (in bits)

    terwijl (len> 0 ) // uitvoer bit voor bit

    // Loop totdat de OutBits-variabele niet volledig bezet is

    terwijl ((OutBits< 8 ) && (len> 0 ) )

    UitChar>>= 1; // maak ruimte vrij

    UitChar| = ((uitcoderen& 1 )<< 7 ) ; // en doe er een beetje in

    coderen>>= 1; //volgend stukje code

    len -- ; // verklein de lengte

  1. UitBits ++ ; // het aantal bits is toegenomen

  2. }

  3. // als alle 8 bits worden gebruikt, sla ze dan op in een bestand

  4. als ( UitBits == 8 )

  5. {

  6. fputc( UitChar, uit ) ; // opslaan in bestand

  7. UitBits = 0 ; // opnieuw instellen

  8. UitChar = 0 ; // opties

  9. }

  10. }

  11. }

Bovendien moet u zoiets als "flush" organiseren, dat wil zeggen na de uitvoer van het laatste codewoord UitChar past niet in het uitvoerbestand, omdat UitBits!=8. Dit brengt nog een kleine functie naar voren:

  1. // De bitbuffer "wissen".

  2. leegte EindePlaat (leegte)

  3. {

  4. // Als er bits in de buffer zitten

  5. als ( UitBits ! = 0 )

Gerelateerde publicaties: