Huffmans algoritme brukes til å komprimere eller kode data. Normalt lagres hvert tegn i en tekstfil som åtte bits (sifre, enten 0 eller 1) som tilordnes det tegnet ved hjelp av en koding kalt ASCII. En Huffman-kodet fil bryter ned den stive 8-biters strukturen slik at de mest brukte tegnene lagres i bare noen få biter ('a' kan være "10" eller "1000" i stedet for ASCII, som er "01100001"). De minst vanlige tegnene vil da ofte ta mye mer enn 8 biter ('z' kan være "00100011010"), men fordi de forekommer så sjelden, skaper Huffman -koding i det hele tatt en mye mindre fil enn originalen.
Trinn
Del 1 av 2: Koding
Trinn 1. Tell frekvensen til hvert tegn i filen som skal kodes
Inkluder et dummy -tegn for å markere slutten av filen - dette vil være viktig senere. For øyeblikket, kall det EOF (slutten av filen) og merk den som en frekvens på 1.
For eksempel, hvis du vil kode en tekstfil som leser "ab ab cab", vil du ha 'a' med frekvens 3, 'b' med frekvens 3, '' (mellomrom) med frekvens 2, 'c' med frekvens 1 og EOF med frekvens 1
Trinn 2. Lagre tegn som trenoder og sett dem i en prioritetskø
Du skal bygge et stort binært tre med hvert tegn som et blad, så du bør lagre tegnene i et format slik at de kan bli noder til treet. Plasser disse nodene i en prioritetskø med hvert tegns frekvens som nodens prioritet.
- Et binært tre er et dataformat hvor hvert data er en node som kan ha opptil én forelder og to barn. Det er ofte tegnet som et forgrenet tre, derav navnet.
- En kø er en passende navn for datasamling der det første som går inn i køen også er det første som kommer ut (som å vente i kø). I en prioritetskø lagres dataene i rekkefølge etter prioritet, slik at det første som kommer ut er det mest presserende, det som har den minste prioriteten, i stedet for det første som blir spurt.
- I eksempelet "ab ab cab" ser prioritetskøen din slik ut: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Trinn 3. Begynn å bygge treet ditt
Fjern (eller fjern) de to mest presserende tingene fra prioritetskøen. Opprett en ny trenode for å være overordnet til disse to nodene, lagre den første noden som venstre barn og den andre som sitt høyre barn. Prioriteten til den nye noden bør være summen av barnets prioriteringer. Sett deretter denne nye noden i prioritetskøen.
Prioritetskøen ser nå slik ut: {'': 2, ny node: 2, 'a': 3, 'b': 3}
Trinn 4. Fullfør bygningen av treet ditt:
gjenta trinnet ovenfor til det bare er en node i køen. Vær oppmerksom på at i tillegg til nodene du opprettet for tegnene og frekvensene deres, vil du også dequeuing, bli til trær og re-enqueueing overordnede noder, noder som allerede er trær selv.
- Når du er ferdig, vil den siste noden i køen være roten til kodetreet, med alle de andre nodene som forgrener seg fra det.
- De mest brukte tegnene vil være bladene nærmest toppen av treet, mens de sjelden brukte tegnene vil bli plassert nederst på treet, lenger borte fra roten.
Trinn 5. Lag et kodingskart. Gå gjennom treet for å nå hver karakter. Hver gang du besøker en nodes venstre barn, er det en '0'. Hver gang du besøker en nodes rette barn, er det en '1'. Når du kommer til et tegn, lagrer du tegnet med sekvensen på 0 og 1 som det tok for å komme dit. Denne sekvensen er hva tegnet vil bli kodet som i den komprimerte filen. Lagre karakterene og sekvensene deres på et kart.
- For eksempel, begynn ved roten. Besøk rotens venstre barn, og besøk deretter nodens venstre barn. Siden noden du befinner deg på nå ikke har noen barn, har du nådd et tegn. Dette er ' '. Siden du gikk til venstre to ganger for å komme hit, er kodingen for '' "00".
- For dette treet vil kartet se slik ut: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Trinn 6. I utdatafilen, inkluder kodingskartet som en overskrift
Dette gjør at filen kan dekodes.
Trinn 7. Kode filen
For hvert tegn i filen som skal kodes, skriver du den binære sekvensen du har lagret på kartet. Når du er ferdig med å kode filen, må du legge til EOF til slutten.
- For filen "ab ab cab" vil den kodede filen se slik ut: "1011001011000101011011".
- Filer lagres som byte (8 bits eller 8 binære sifre). Fordi Huffman Encoding-algoritmen ikke bruker 8-biters format, vil kodede filer ofte ikke ha lengder som er multipler av 8. De resterende sifrene fylles ut med 0s. I dette tilfellet vil to 0 -er bli lagt til på slutten av filen, som ser ut som et annet mellomrom. Dette kan være et problem: Hvordan vet dekoderen når den skal slutte å lese? Men fordi vi inkluderte et end-of-file-tegn, vil dekoderen komme til dette og deretter stoppe, ignorere alt annet som er lagt til etterpå.
Del 2 av 2: Dekoding
Trinn 1. Les i en Huffman-kodet fil
Les først overskriften, som skal være kodingskartet. Bruk dette til å bygge et dekodingstre på samme måte som du bygde treet du brukte til å kode filen. De to trærne skal være identiske.
Trinn 2. Les det binære ett siffer om gangen
Kryss treet mens du leser: Hvis du leser i en '0', går du til venstre barn på noden du er på, og hvis du leser i en '1', går du til det riktige barnet. Når du når et blad (en node uten barn), har du kommet til et tegn. Skriv tegnet inn i den avkodede filen.
På grunn av måten tegnene er lagret på i treet, har kodene for hvert tegn en prefiksegenskap, slik at ingen tegns binære koding noen gang kan forekomme ved starten av et annet tegns koding. Kodingen for hvert tegn er helt unik. Dette gjør dekoding mye enklere
Trinn 3. Gjenta til du når EOF
Gratulerer! Du har dekodet filen.
