Huffman's algoritme wordt gebruikt om gegevens te comprimeren of te coderen. Normaal gesproken wordt elk teken in een tekstbestand opgeslagen als acht bits (cijfers, 0 of 1) die naar dat teken verwijzen met behulp van een codering die ASCII wordt genoemd. Een Huffman-gecodeerd bestand breekt de rigide 8-bits structuur af, zodat de meest gebruikte tekens in slechts een paar bits worden opgeslagen ('a' kan "10" of "1000" zijn in plaats van de ASCII, dat is "01100001"). De minst voorkomende tekens nemen dan vaak veel meer dan 8 bits in beslag ('z' kan "00100011010" zijn), maar omdat ze zo zelden voorkomen, creëert Huffman-codering over het algemeen een veel kleiner bestand dan het origineel.
Stappen
Deel 1 van 2: Codering
Stap 1. Tel de frequentie van elk teken in het te coderen bestand
Voeg een dummy-teken toe om het einde van het bestand te markeren -- dit is later belangrijk. Noem het voorlopig de EOF (einde van het bestand) en markeer het als een frequentie van 1.
Als u bijvoorbeeld een tekstbestand met de tekst 'ab ab cab' wilt coderen, heeft u 'a' met frequentie 3, 'b' met frequentie 3, ' ' (spatie) met frequentie 2, 'c' met frequentie 1, en EOF met frequentie 1
Stap 2. Sla karakters op als boomknooppunten en plaats ze in een prioriteitswachtrij
Je gaat een grote binaire boom bouwen met elk karakter als een blad, dus je moet de karakters in een zodanig formaat opslaan dat ze knooppunten van de boom kunnen worden. Plaats deze knooppunten in een prioriteitswachtrij met de frequentie van elk teken als de prioriteit van het knooppunt.
- Een binaire boom is een gegevensindeling waarbij elk stuk gegevens een knooppunt is dat maximaal één ouder en twee kinderen kan hebben. Het wordt vaak getekend als een vertakte boom, vandaar de naam.
- Een wachtrij is een gegevensverzameling met de toepasselijke naam waarbij het eerste dat in de wachtrij gaat, ook het eerste is dat eruit komt (zoals wachten in de rij). In een prioriteitswachtrij worden de gegevens opgeslagen in volgorde van hun prioriteit, zodat het eerste dat naar buiten komt het meest urgent is, het ding met de minste prioriteit, in plaats van het eerste dat in de wachtrij wordt geplaatst.
- In het voorbeeld "ab ab cab" ziet uw prioriteitswachtrij er als volgt uit: {'c':1, EOF:1, ' ':2, 'a':3, 'b':3}
Stap 3. Begin met het bouwen van je boom
Verwijder (of uit de wachtrij) de twee meest urgente dingen uit de prioriteitswachtrij. Maak een nieuw boomknooppunt als ouder van deze twee knooppunten, waarbij het eerste knooppunt wordt opgeslagen als het linkerkind en het tweede als het rechterkind. De prioriteit van het nieuwe knooppunt moet de som zijn van de prioriteiten van het onderliggende knooppunt. Zet dit nieuwe knooppunt vervolgens in de wachtrij met prioriteit.
De prioriteitswachtrij ziet er nu als volgt uit: {' ':2, nieuwe node:2, 'a':3, 'b':3}
Stap 4. Voltooi het bouwen van je boom:
herhaal de bovenstaande stap totdat er slechts één knooppunt in de wachtrij staat. Merk op dat naast de knooppunten die u voor de karakters en hun frequenties hebt gemaakt, u ook de wachtrij zult verwijderen, in bomen zult veranderen en de bovenliggende knooppunten opnieuw in de wachtrij zult plaatsen, knooppunten die zelf al bomen zijn.
- Als je klaar bent, is het laatste knooppunt in de wachtrij de wortel van de coderingsboom, met alle andere knooppunten die ervan vertakken.
- De meest gebruikte karakters zijn de bladeren die zich het dichtst bij de top van de boom bevinden, terwijl de zelden gebruikte karakters onderaan de boom worden geplaatst, verder weg van de wortel.
Stap 5. Maak een coderingskaart. Loop door de boom om elk personage te bereiken. Elke keer dat u het linkerkind van een knoop bezoekt, is dat een '0'. Elke keer dat u het juiste kind van een knoop bezoekt, is dat een '1'. Wanneer je bij een personage komt, sla het personage dan op met de reeks nullen en enen die nodig waren om daar te komen. Deze volgorde is wat het teken zal worden gecodeerd zoals in het gecomprimeerde bestand. Bewaar de personages en hun volgorde op een kaart.
- Begin bijvoorbeeld bij de wortel. Bezoek het linkerkind van de wortel en bezoek dan het linkerkind van dat knooppunt. Omdat het knooppunt waar je je nu bevindt geen kinderen heeft, heb je een personage bereikt. Dit is ' '. Omdat je twee keer naar links bent gelopen om hier te komen, is de codering voor '' '00'.
- Voor deze boom ziet de kaart er als volgt uit: {' ':"00", 'a':"10", 'b':"11", 'c':"010", EOF:"011"}.
Stap 6. Neem in het uitvoerbestand de coderingskaart op als koptekst
Hierdoor kan het bestand worden gedecodeerd.
Stap 7. Codeer het bestand
Voor elk teken in het bestand dat moet worden gecodeerd, schrijft u de binaire reeks die u op de kaart hebt opgeslagen. Als u klaar bent met het coderen van het bestand, moet u de EOF aan het einde toevoegen.
- Voor het bestand "ab ab cab" ziet het gecodeerde bestand er als volgt uit: "1011001011000101011011".
- Bestanden worden opgeslagen als bytes (8 bits of 8 binaire cijfers). Omdat het Huffman Encoding-algoritme geen 8-bits formaat gebruikt, hebben gecodeerde bestanden vaak geen lengtes van veelvouden van 8. De overige cijfers worden ingevuld met nullen. In dit geval zouden twee nullen worden toegevoegd aan het einde van het bestand, dat eruitziet als een andere spatie. Dit kan een probleem zijn: hoe weet de decoder wanneer hij moet stoppen met lezen? Omdat we echter een end-of-file-teken hebben toegevoegd, komt de decoder hiernaar toe en stopt dan, en negeert al het andere dat daarna is toegevoegd.
Deel 2 van 2: Decodering
Stap 1. Lees een Huffman-gecodeerd bestand in
Lees eerst de koptekst, die de coderingskaart zou moeten zijn. Gebruik dit om een decoderingsboom te bouwen op dezelfde manier waarop u de boom bouwde die u gebruikte om het bestand te coderen. De twee bomen moeten identiek zijn.
Stap 2. Lees het binaire cijfer één voor één in
Doorkruis de boom terwijl u leest: als u een '0' inleest, ga dan naar het linker kind van het knooppunt waar u zich bevindt, en als u in een '1' leest, ga dan naar het rechter kind. Wanneer je een blad bereikt (een knoop zonder kinderen), ben je bij een personage aangekomen. Schrijf het teken in het gedecodeerde bestand.
Vanwege de manier waarop de tekens in de boomstructuur zijn opgeslagen, hebben de codes voor elk teken een prefixeigenschap, zodat de binaire codering van een teken nooit kan plaatsvinden aan het begin van de codering van een ander teken. De codering voor elk karakter is volledig uniek. Dit maakt het decoderen veel gemakkelijker
Stap 3. Herhaal dit totdat je de EOF hebt bereikt
Gefeliciteerd! Je hebt het bestand gedecodeerd.
