Hva er Huffman koding?

Huffman koding - også kjent som Huffman koding, eller Huffman komprimering - er en algoritme, eller et sett med regler, for tapsfri datakomprimering utviklet av David Albert Hoffman i 1952. Lossless data komprimering innebærer koding av data for å spare lagringsplass eller sendetid på en slik måte at all informasjonen i dataene kan gjenopprettes perfekt ved dekompresjon.

Statistiske Coding

Huffman-koding er en statistisk koding metode. Hvor ofte hvert symbol oppstår i filen blir komprimert bestemmer hvordan det symbolet er representert. I hvilken som helst fil, noen symboler eller tegn, forekommer oftere enn andre. I Huffman-koding, jo oftere et symbol skjer, jo færre binære sifre, eller "bits", blir brukt for å representere et symbol.

ASCII versus Huffman koding

I American Standard kode for Information Interchange (ASCII) koding, som brukes av noen programmeringsspråk, er hvert tegn kodes med en fast lengde koden ved hjelp av 7 eller 8 biter per tegn. De vanligste tegn, for eksempel alfanumeriske tegn og tegnsetting, bruker 7 biter per tegn. Huffman koding, på den annen side, tildeler kortere koder for ofte brukte tegn og lengre koder for mindre brukte tegn til å redusere størrelsen på filen blir komprimert.

Binary Huffman treet

Huffman koding hovedsak innebærer å bygge en enkelt binært tre fra en gruppe, eller skog, trær. I utgangspunktet er alle trær har en enkelt node, med et tegn og tegn vekt, basert på det antall ganger tegnet forekommer i en fil. Jo oftere et tegn opptrer, jo høyere er dets vekt. Trærne, eller noder, er sortert etter vekt og de to laveste vektet trær er kombinert i ett tre, redusere det totale antall trær med én. Denne prosessen gjentas inntil bare en binær Huffman tre rester, med et enkelt element ved sin rot. Huffman-koding bruker de to minste nodene i hvert trinn for å fremstille et globalt optimal koding treet. Av denne grunn er det kjent som en "grådig" algoritme.

Huffman kode

For å generere en Huffman-kode, finne verdien du ønsker i det binære Huffman treet og traversere treet bakover. Denne prosessen bygger det binære Huffman streng. Hver gang du tar en venstre arm med "0" bit, og hver gang du tar en høyre gren, utgang en "en" bit til du kommer til toppen av treet, så den første biten i strengen vises utgangs på toppen.