Så här komprimerar du data med huffman som kodar

Huffmans algoritm används för att komprimera eller koda data. Normalt lagras varje tecken i en textfil som åtta bitar (siffror, antingen 0 eller 1) som kartlägger till den tecknet med en kodning som heter ASCII. En Huffman-kodad fil bryter ner den styva 8-bitars strukturen så att de vanligaste tecknen lagras på bara några bitar ("A" kan vara "10" eller "1000" snarare än ASCII, som är "01100001"). De minst vanliga tecknen kommer då ofta att ta upp mycket mer än 8 bitar (`Z` kan vara "00100011010"), men för att de förekommer så sällan, skapar Huffman, på det hela taget en mycket mindre fil än originalet.

Steg

Del 1 av 2:
Kodning
  1. Bild med titeln Komprimera data med hjälp av Huffman som kodar Steg 1
1. Räkna frekvensen för varje tecken i filen som ska kodas. Inkludera en dummy-karaktär för att markera slutet på filen - det här blir viktigt senare. För närvarande, kalla det EF (slutet av filen) och markera det som en frekvens på 1.
  • Till exempel, om du vill koda en textfil läsning "AB AB Cab," Du skulle ha "A" med frekvens 3, `b` med frekvens 3, `` (utrymme) med frekvens 2, `c` med frekvens 1 och EOF med frekvens 1.
  • Bild med titeln Komprimera data med Huffman som kodar Steg 2
    2. Förvara tecken som trädnoder och sätta dem i en prioritetskö. Du kommer att bygga ett stort binärt träd med varje tecken som ett blad, så du bör lagra karaktärerna i ett format så att de kan bli noder av trädet. Placera dessa noder i en prioritetskö med varje karaktärs frekvens som nodens prioritet.
  • Ett binärt träd är ett dataformat där varje data är en nod som kan ha upp till en förälder och två barn. Det är ofta ritat som ett förgrenande träd, därav namnet.
  • En kö är en lämpligt namngiven datainsamling där det första som ska gå in i köen är också det första att komma ut (som att vänta i linje). I en prioritet Kö, data lagras i enlighet med deras prioritet, så att det första som kommer ut är det mest brådskande sak, saken med den minsta prioriteten, snarare än det första som enkänd.
  • I "AB AB Cab" Exempel, din prioritetskö skulle se ut så här: {`c`: 1, EOF: 1, ``: 2, `A`: 3, `B`: 3}
  • Bild med titeln Komprimera data med Huffman som kodar Steg 3
    3. Börja bygga ditt träd. Ta bort (eller dequeue) de två mest brådskande sakerna från prioritetskön. Skapa en ny trädkod för att vara förälder till dessa två noder, lagra den första noden som sitt vänstra barn och den andra som sitt rätt barn. Prioriteringen av den nya noden bör vara summan av barnets prioriteringar. Sedan enqueue den här nya noden i prioritetskön.
  • Prioriterade köen ser nu ut så här: {``: 2, Ny nod: 2, `A`: 3, `B`: 3}
  • Bild med titeln Komprimera data med Huffman som kodar Steg 4
    4. Avsluta Bygga ditt träd: Upprepa ovanstående steg tills det bara finns en nod i köen. Observera att förutom de noder du skapade för tecknen och deras frekvenser, kommer du också att avstänga, vända sig till träd och re-enqueueing modernoder, noder som redan är själva träd.
  • När du är klar kommer den sista noden i köen att vara rot av det kodande trädet, med alla andra noder som förgrenar sig från den.
  • De vanligaste tecknen kommer att vara bladen närmast toppen av trädet, medan de sällan använda tecknen kommer att placeras längst ner på trädet, längre bort från roten.
  • Bild med titeln Komprimera data med Huffman som kodar Steg 5
    5. Skapa en Kodningskartan. Gå genom trädet för att nå varje tecken. Varje gång du besöker en nods vänstra barn, är det en "0". Varje gång du besöker en nods rätt barn, är det en "1". När du kommer till ett tecken, lagra karaktären med sekvensen av 0s och 1s som det tog för att komma dit. Denna sekvens är vad tecknet kommer att kodas som i den komprimerade filen. Förvara tecknen och deras sekvenser i en karta.
  • Till exempel, börja vid roten. Besök rotens vänstra barn, och besök sedan den nodens vänstra barn. Eftersom noden du nu inte har några barn, har du nått en karaktär. Detta är ` `. Sedan du gick kvar två gånger för att komma hit, är kodningen för `` "00".
  • För detta träd kommer kartan att se ut så här: {``:"00", `A`:"10", `B`:"11", `c`:"010", EOF:"011"}.
  • Bild med titeln Komprimera data med Huffman som kodar Steg 6
    6. I utdatafilen, inkludera kodningskartan som en rubrik. Detta gör det möjligt för filen att avkodas.
  • Bild med titeln Komprimera data med Huffman som kodar Steg 7
    7. Koda filen. För varje tecken i filen som ska kodas skriver du den binära sekvensen du har lagrat på kartan. När du är klar med att koda filen, se till att du lägger till EOF till slutet.
  • För filen "AB AB Cab", Den kodade filen kommer att se ut så här: "1011001011000101011011".
  • Filer lagras som byte (8 bitar eller 8 binära siffror). Eftersom Huffman som kodar algoritmen inte använder 8-bitarsformatet, kommer kodade filer ofta inte att ha längder som är multiplar av 8. De återstående siffrorna fylls i med 0s. I det här fallet skulle två 0s läggas till i slutet av filen, som ser ut som ett annat utrymme. Detta kan vara ett problem: Hur skulle avkodaren veta när man ska sluta läsa? Men eftersom vi inkluderade ett slutet av filtecken kommer avkodaren att komma till det här och sedan sluta, ignorera något annat som har lagts till efter.
    • Del 2 av 2:
    Avkodning
    1. Bild med titeln Komprimera data med Huffman som kodar Steg 8
    1. Läs i en Huffman-kodad fil. Läs först rubriken, som ska vara kodningskartan. Använd detta för att bygga ett avkodningsträd på samma sätt som du byggde det träd som du använde för att koda filen. De två träden ska vara identiska.
  • Bild med titeln komprimera data med Huffman som kodar Steg 9
    2. Läs i den binära en siffra i taget. Traverse trädet som du läser: Om du läser i en "0", gå till nodens vänstra barn du är på, och om du läser i en "1", gå till rätt barn. När du når ett blad (en nod utan några barn) har du kommit fram till ett tecken. Skriv tecknet i den avkodade filen.
  • På grund av hur tecknen lagras i trädet har koderna för varje tecken en prefix egendom, så att ingen karaktärs binära kodning någonsin kan inträffa i början av en annan karaktärs kodning. Kodningen för varje tecken är helt unik. Detta gör avkodning mycket enklare.
  • Bild med titeln komprimera data med användning av Huffman som kodar steg 10
    3. Upprepa tills du når EOF. Grattis! Du har avkodat filen.

    • Tips

    Dela på det sociala nätverket:
    Liknande