Huffmans algoritme bruges til at komprimere eller kode data. Normalt lagres hvert tegn i en tekstfil som otte bits (cifre, enten 0 eller 1), der tilknyttes det tegn ved hjælp af en kodning kaldet ASCII. En Huffman-kodet fil nedbryder den stive 8-bit struktur, så de mest almindeligt anvendte tegn gemmes i bare et par bits ('a' kan være "10" eller "1000" i stedet for ASCII, som er "01100001"). De mindst almindelige tegn vil derfor ofte optage meget mere end 8 bits ('z' kan være "00100011010"), men fordi de forekommer så sjældent, skaber Huffman -kodning i det hele taget en meget mindre fil end originalen.
Trin
Del 1 af 2: Kodning
Trin 1. Tæl frekvensen af hvert tegn i den fil, der skal kodes
Inkluder et dummy -tegn for at markere slutningen af filen - dette 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 en tekstfil, der læser "ab ab cab", ville du have 'a' med frekvens 3, 'b' med frekvens 3, '' (mellemrum) med frekvens 2, 'c' med frekvens 1 og EOF med frekvens 1
Trin 2. Gem tegn som træknude og sæt dem i en prioritetskø
Du bygger et stort binært træ med hvert tegn som et blad, så du bør gemme tegnene i et format, så de kan blive knudepunkter for træet. Placer disse noder i en prioritetskø med hvert tegns frekvens som nodens 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 tegnet som et forgrenet træ, deraf navnet.
- En kø er en passende navngivet dataindsamling, hvor den første ting at gå ind i køen også er den første ting, der kommer ud (som at vente i kø). I en prioritetskø gemmes dataene i rækkefølge efter deres prioritet, så den første ting, der kommer ud, er den mest presserende ting, den ting med den mindste prioritet, snarere end den første, der bliver spurgt.
- I eksemplet "ab ab cab" ser din prioritetskø således ud: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Trin 3. Begynd at bygge dit træ
Fjern (eller fjern) de to mest presserende ting fra prioritetskøen. Opret en ny træknude, der skal være forælder til disse to noder, og gem den første knude som sit venstre barn og den anden som sit højre barn. Prioriteten for den nye knude bør være summen af barnets prioriteter. Giv derefter denne nye knude i prioritetskøen.
Prioritetskøen ser nu sådan ud: {'': 2, ny node: 2, 'a': 3, 'b': 3}
Trin 4. Afslut med at bygge dit træ:
gentag ovenstående trin, indtil der kun er en knude i køen. Bemærk, at du ud over de noder, du har oprettet for tegnene og deres frekvenser, også vil dequeuing, blive til træer og genoplive forældreknudepunkter, noder, der allerede selv er træer.
- Når du er færdig, er den sidste knude i køen roden til kodningstræet, hvor alle de andre noder forgrener sig fra det.
- De mest anvendte tegn vil være bladene tættest på toppen af træet, mens de sjældent anvendte tegn vil blive placeret i bunden af træet, længere væk fra roden.
Trin 5. Opret et kodningskort. Gå gennem træet for at nå hver karakter. Hver gang du besøger et nodes venstre barn, er det et '0'. Hver gang du besøger en nodes rigtige barn, er det et '1'. Når du kommer til et tegn, skal du gemme tegnet med sekvensen på 0'er og 1'er, som det tog at komme dertil. Denne sekvens er, hvad tegnet vil blive kodet som i den komprimerede fil. Gem tegnene og deres sekvenser på et kort.
- Start for eksempel ved roden. Besøg rodens venstre barn, og besøg derefter nodens venstre barn. Da den knude, du befinder dig i nu, ikke har nogen børn, har du nået en karakter. Dette er ' '. Da du gik til venstre to gange for at komme hertil, er kodningen for '' "00".
- For dette træ vil kortet se sådan ud: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Trin 6. Inkluder kodningskortet i outputfilen som en overskrift
Dette gør det muligt at afkode filen.
Trin 7. Koder 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 kode filen, skal du tilføje EOF til slutningen.
- For filen "ab ab cab" vil den kodede fil se sådan ud: "1011001011000101011011".
- Filer gemmes som bytes (8 bits eller 8 binære cifre). Fordi Huffman Encoding-algoritmen ikke bruger 8-bit-formatet, vil kodede filer ofte ikke have længder, der er multipla af 8. De resterende cifre udfyldes med 0s. I dette tilfælde vil der blive tilføjet to 0'er i slutningen af filen, hvilket ligner et andet mellemrum. Dette kan være et problem: Hvordan ville dekoderen vide, hvornår den skulle stoppe med at læse? Men fordi vi inkluderede en end-of-file-karakter, vil dekoderen komme til dette og derefter stoppe og ignorere alt andet, der er blevet tilføjet efter.
Del 2 af 2: Afkodning
Trin 1. Læs i en Huffman-kodet fil
Læs først overskriften, som skal være kodningskortet. Brug dette til at bygge et afkodningstræ på samme måde som du byggede det træ, du brugte til at kode filen. De to træer skal være identiske.
Trin 2. Læs det binære ét ciffer ad gangen
Krydse træet, mens du læser: Hvis du læser i et '0', skal du gå til venstre barn på den knude, du er på, og hvis du læser i et '1', skal du gå til det rigtige barn. Når du når et blad (en knude uden børn), er du nået frem til en karakter. Skriv tegnet i den afkodede fil.
På grund af den måde, hvorpå tegnene er gemt i træet, har koderne for hvert tegn en præfiks -egenskab, så der ikke nogensinde kan forekomme tegnets binære kodning i starten af et andet tegns kodning. Kodningen for hvert tegn er helt unik. Dette gør afkodning meget lettere
Trin 3. Gentag, indtil du når EOF
Tillykke! Du har afkodet filen.
