Hur man komprimerar data med Huffman -kodning: 10 steg

Innehållsförteckning:

Hur man komprimerar data med Huffman -kodning: 10 steg
Hur man komprimerar data med Huffman -kodning: 10 steg

Video: Hur man komprimerar data med Huffman -kodning: 10 steg

Video: Hur man komprimerar data med Huffman -kodning: 10 steg
Video: 11 tips från Elaine Eksvärd: Så blir du omtyckt - Nyhetsmorgon (TV4) 2024, Mars
Anonim

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 mappar till det tecknet med hjälp av en kodning som kallas ASCII. En Huffman-kodad fil bryter ner den styva 8-bitarsstrukturen så att de vanligaste tecknen lagras i bara några bitar ('a' kan vara "10" eller "1000" snarare än ASCII, vilket är "01100001"). De minst vanliga tecknen tar därför ofta mycket mer än 8 bitar ('z' kan vara "00100011010"), men eftersom de förekommer så sällan skapar Huffman -kodning i det stora hela en mycket mindre fil än originalet.

Steg

Del 1 av 2: Kodning

Komprimera data med hjälp av Huffman -kodning Steg 1
Komprimera data med hjälp av Huffman -kodning Steg 1

Steg 1. Räkna frekvensen för varje tecken i filen som ska kodas

Inkludera ett dummy -tecken för att markera slutet på filen - det kommer att vara viktigt senare. Kalla det för närvarande EOF (slutet av filen) och markera det som med en frekvens på 1.

Till exempel, om du vill koda en textfil som läser "ab ab cab", skulle du ha 'a' med frekvens 3, 'b' med frekvens 3, '' (mellanslag) med frekvens 2, 'c' med frekvens 1 och EOF med frekvens 1

Komprimera data med hjälp av Huffman -kodning Steg 2
Komprimera data med hjälp av Huffman -kodning Steg 2

Steg 2. Lagra tecken som trädnoder och lägg 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 tecknen i ett format så att de kan bli noder i trädet. Placera dessa noder i en prioritetskö med varje teckens 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 grenande träd, därav namnet.
  • En kö är en träffande datainsamling där det första som går in i kön också är det första som kommer ut (som att vänta i kö). I en prioritetskö lagras data i ordning efter deras prioritet, så att det första som kommer ut är det som är mest angeläget, det som har den minsta prioriteten, snarare än det första som uppmanas.
  • I exemplet "ab ab cab" ser din prioritetskö ut så här: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Komprimera data med hjälp av Huffman -kodning Steg 3
Komprimera data med hjälp av Huffman -kodning Steg 3

Steg 3. Börja bygga ditt träd

Ta bort (eller ta bort) de två mest brådskande sakerna från prioritetskön. Skapa en ny trädnod för att vara förälder till dessa två noder, lagra den första noden som dess vänstra barn och den andra som sitt högra barn. Den nya nodens prioritet bör vara summan av barnets prioriteringar. Ge sedan den nya noden i prioritetskön.

Prioritetskön ser nu ut så här: {'': 2, ny nod: 2, 'a': 3, 'b': 3}

Komprimera data med hjälp av Huffman -kodning Steg 4
Komprimera data med hjälp av Huffman -kodning Steg 4

Steg 4. Slutför att bygga ditt träd:

upprepa ovanstående steg tills det bara finns en nod i kön. Observera att förutom de noder du skapade för karaktärerna och deras frekvenser kommer du också att dequeuing, förvandlas till träd och re-enqueueing överordnade noder, noder som redan själva är träd.

  • När du är klar kommer den sista noden i kön att vara roten till kodningsträdet, med alla andra noder som förgrenas från det.
  • De mest använda tecknen är 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.
Komprimera data med hjälp av Huffman -kodning Steg 5
Komprimera data med hjälp av Huffman -kodning Steg 5

Steg 5. Skapa en kodningskarta. Gå genom trädet för att nå varje karaktär. Varje gång du besöker en nodes vänstra barn är det ett '0'. Varje gång du besöker en nods rätta barn är det ett '1'. När du kommer till ett tecken, lagra tecknet med sekvensen 0 och 1 som det tog för att komma dit. Denna sekvens är vad tecknet kommer att kodas som i den komprimerade filen. Spara karaktärerna och deras sekvenser på 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 befinner dig vid nu inte har några barn har du nått en karaktär. Detta är ' '. Eftersom du gick vänster två gånger för att komma hit är kodningen för '' "00".
  • För det här trädet kommer kartan att se ut så här: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Komprimera data med hjälp av Huffman -kodning Steg 6
Komprimera data med hjälp av Huffman -kodning Steg 6

Steg 6. Inkludera kodningskartan som en rubrik i utdatafilen

Detta gör att filen kan avkodas.

Komprimera data med hjälp av Huffman -kodning Steg 7
Komprimera data med hjälp av Huffman -kodning Steg 7

Steg 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 har kodat filen, se till att lägga till EOF i slutet.

  • För filen "ab ab cab" kommer den kodade filen att se ut så här: "1011001011000101011011".
  • Filer lagras som byte (8 bitar eller 8 binära siffror). Eftersom Huffman Encoding-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å 0: or läggas till i slutet av filen, vilket ser ut som ett annat utrymme. Detta kan vara ett problem: hur skulle avkodaren veta när den ska sluta läsa? Men eftersom vi inkluderade ett slutet av filtecken kommer avkodaren att komma till detta och sedan sluta, ignorera allt annat som har lagts till efter.

Del 2 av 2: Avkodning

Komprimera data med hjälp av Huffman -kodning Steg 8
Komprimera data med hjälp av Huffman -kodning Steg 8

Steg 1. Läs in 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 trädet som du använde för att koda filen. De två träden ska vara identiska.

Komprimera data med hjälp av Huffman -kodning Steg 9
Komprimera data med hjälp av Huffman -kodning Steg 9

Steg 2. Läs in den binära en siffra i taget

Korsa trädet medan du läser: om du läser i ett '0' går du till det vänstra barnet på noden du befinner dig i, och om du läser i ett '1' går du till det rätta barnet. När du når ett blad (en nod utan barn) har du kommit fram till en karaktär. Skriv tecknet i den avkodade filen.

På grund av hur tecknen lagras i trädet har koderna för varje tecken en prefixegenskap, 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 karaktär är helt unik. Detta gör avkodningen mycket enklare

Komprimera data med hjälp av Huffman -kodning Steg 10
Komprimera data med hjälp av Huffman -kodning Steg 10

Steg 3. Upprepa tills du når EOF

Grattis! Du har avkodat filen.

Rekommenderad: