Sådan komprimeres data ved hjælp af Huffman-kodning: 10 trin

Huffman`s algoritme bruges til at komprimere eller kode data. Normalt gemmes hvert tegn i en tekstfil som otte bits (cifre, enten 0 eller 1), der kortlægges til det tegn ved hjælp af en kodning kaldet ASCII. En Huffman-kodet fil bryder ned den stive 8-bit-struktur, så de mest almindeligt anvendte tegn opbevares på blot et par bits (`A` kunne være "10" eller "1000" snarere end ASCII, hvilket er "01100001"). De mindst almindelige tegn, så vil ofte tage meget mere end 8 bits (`z` kan være "00100011010"), Men fordi de forekommer så sjældent, skaber Huffman, i det hele taget en meget mindre fil end originalen.

Trin

Del 1 af 2:

Indkodning

1. Tæl frekvensen af hvert tegn i den fil, der skal kodes. Medtag en dummy karakter for at markere slutningen af filen - det vil være vigtigt senere. For nu skal du kalde det EOF (slutningen af filen) og markere det som en frekvens på 1.

For eksempel, hvis du vil kode for en tekstfil læsning "ab ab ab cab," Du ville have `A` med frekvens 3, `b` med frekvens 3, `` (rum) med frekvens 2, `C` med frekvens 1 og EOF med frekvens 1.

Billedet med titlen Komprimer data ved hjælp af Huffman kodning Trin 2

2. Opbevar tegn som trænoder og sæt dem i en prioritetskø. Du vil bygge et stort binærtræ med hver karakter som et blad, så du skal gemme tegnene i et format, så de kan blive noder af træet. Placer disse noder i en prioritetskø med hver tegns frekvens som dens nodes prioritet.

Et binært træ er et dataformat, hvor hvert stykke data er en knude, der kan have op til en forælder og to børn. Det er ofte trukket som et forgreningstræ, dermed navnet.

En kø er en passende navngivet dataindsamling, hvor den første ting at gå ind i køen er også den første ting at komme ud (som venter i kø). I en prioritet Kø, dataene gemmes i rækkefølge af deres prioritet, så den første ting at komme ud er den mest presserende ting, sagen med den mindste prioritet, snarere end den første ting, der er blevet temmet.

I "ab ab ab cab" Eksempel, din prioritetskø vil se sådan ud: {C `: 1, EOF: 1,` `: 2,` A `: 3,` B `: 3}

Billedet med titlen Komprimer data ved hjælp af Huffman kodning Trin 3

3. Begynd at bygge dit træ. Fjern (Or DEQUEUE) de to mest presserende ting fra prioritetskøen. Opret en ny træknude for at være forældrene til disse to noder, opbevare den første knude som dets venstre barn og det andet som dets højre barn. Den nye nodes prioritet bør være summen af prioriteterne i sit barn. Så enqueue denne nye node i prioriteringskøen.

Prioritetskøen ser nu ud som denne: {``: 2, ny node: 2, `A`: 3, `b`: 3}

BILLEDE Titled Komprimer data ved hjælp af Huffman kodning Trin 4

4. Afslutning af dit træ: Gentag ovenstående trin, indtil der kun er en node i køen. Bemærk, at i tillæg til de noder, du har oprettet for tegnene og deres frekvenser, vil du også være dequinging, dreje til træer og genpåfører forældre noder, noder, der allerede er selv træer.

Når du er færdig, vil den sidste node i køen være den rod af det kodende træ, med alle de andre noder forgrenet fra det.

De mest anvendte tegn vil være bladene tættest på toppen af træet, mens de sjældent brugte tegn vil blive placeret i bunden af træet, længere væk fra roden.

Billedet med titlen Komprimer data ved hjælp af Huffman kodning Trin 5

5. Opret AN kodning af kort. Gå gennem træet for at nå hver karakter. Hver gang du besøger et node venstre barn, er det en `0`. Hver gang du besøger et knudepunkts højre barn, er det en `1`. Når du kommer til et tegn, skal du gemme karakteren med sekvensen af 0s og 1s at det tog for at komme derhen. Denne sekvens er, hvad tegnet vil blive kodet som i den komprimerede fil. Gem tegnene og deres sekvenser i et kort.

For eksempel start ved roden. Besøg rodens venstre barn, og så besøg det node venstre barn. Da noden du nu ikke har nogen børn, har du nået et tegn. Dette er ` `. Da du gik tilbage to gange for at komme her, er kodningen for `` ` "00".

For dette træ vil kortet se sådan ud: {``:"00", `en`:"10", `b`:"11", `C`:"010", EOF:"011"}.

BILLEDE Titled Komprimer data ved hjælp af Huffman kodning Trin 6

6. I outputfilen skal du inkludere kodningskortet som et overskrift. Dette vil gøre det muligt for filen at blive afkodet.

BILLEDE Titled Komprimer data ved hjælp af Huffman kodning trin 7

7. Kode for filen. For hvert tegn i filen, der skal kodes, skal du skrive den binære sekvens, du har gemt på kortet. Når du er færdig med at kodning af filen, skal du sørge for at tilføje EOF til slutningen.

For filen "ab ab ab cab", Den kodede fil vil se sådan ud: "1011001011000101011011".

Filer gemmes som bytes (8 bits eller 8 binære cifre). Fordi Huffman kodende algoritme ikke bruger 8-bit-formatet, vil kodede filer ofte ikke have længder, der er multipler på 8. De resterende cifre vil blive udfyldt med 0s. I dette tilfælde vil to 0`er blive tilføjet i slutningen af filen, som ligner et andet rum. Dette kunne være et problem: Hvordan ville dekoderen vide, hvornår man skal stoppe med at læse? Men fordi vi inkluderede en end-of-fil karakter, vil dekoderen komme til dette og derefter stoppe og ignorere alt andet, der er blevet tilføjet på efter.

Del 2 af 2:

Afkodning

1. Læs i en Huffman-kodet fil. Først skal du læse overskriften, som skal være kodningskortet. Brug dette til at opbygge et dekodningstræ på samme måde, du har bygget det træ, du plejede at kode for filen. De to træer skal være identiske.

Billedet med titlen Komprimer data ved hjælp af Huffman kodning Trin 9

2. Læs i det binære etcifret ad gangen. Traverse træet som du læser: Hvis du læser i en `0`, skal du gå til venstre barn i noden, du er på, og hvis du læser i en `1`, skal du gå til det rigtige barn. Når du når et blad (en node uden børn), er du ankommet til et tegn. Skriv tegnet i den afkodede fil.

På grund af den måde, tegnene opbevares i træet, har koderne for hver karakter en præfiks egenskab, således at ingen tegns binære kodning nogensinde kan forekomme i starten af en anden tegns kodning. Kodningen for hver karakter er helt unik. Dette gør afkodning meget lettere.

BILLEDE Titled Komprimer data ved hjælp af Huffman kodning Trin 10

3. Gentag, indtil du når EOF. Tillykke! Du har afkodet filen.

Tips

Del på sociale netværk :

Sådan komprimerer du data ved hjælp af huffman-kodning

Trin

Tips