Hur komprimerar jag data med Huffman-kodning?
Ett binärt träd är ett dataformat där varje datablad är en nod som kan ha upp till en förälder och två barn.
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å ofta mycket mer än åtta bitar ('z' kan vara "00100011010"), men eftersom de förekommer så sällan skapar Huffman-kodning i stort sett en mycket mindre fil än originalet.
Del 1 av 2: kodning
- 1Räkna frekvensen för varje tecken i filen som ska kodas. Inkludera en dummy karaktär för att markera slutet på filen - detta kommer att vara viktigt senare. För närvarande kallar du det EOF (filens slut) och markerar det som frekvensen 1.
- Om du till exempel 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.
- 2Lagra tecken som trädnoder och placera 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 karaktärs frekvens som dess prioritet.
- Ett binärt träd är ett dataformat där varje datablad är en nod som kan ha upp till en förälder och två barn. Det ritas ofta som ett grenande träd, därav namnet.
- En kö är en passande namngiven 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 prioritetsordning, så att det första som kommer ut är det mest brådskande, det som har den minsta prioriteten, snarare än det första som kommer.
- I exemplet " ab ab cab " skulle din prioritetskö se ut så här: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Lagra tecken som trädnoder och placera dem i en prioritetskö. - 3Börja bygga ditt träd. Ta bort (eller dequeue) de två mest brådskande sakerna från prioritetskön. Skapa en ny trädnod för att vara förälder för dessa två noder, lagra den första noden som sitt vänstra barn och den andra som sitt högra barn. Den nya nodens prioritet bör vara summan av barnets prioriteringar. Stäng sedan den nya noden i prioritetskön.
- Prioritetskön ser nu ut så här: {'': 2, ny nod: 2, 'a': 3, 'b': 3}
- 4Slutför byggandet av ditt träd: upprepa steget ovan 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 är träd.
- När du är klar kommer den sista noden i kön att vara roten till det kodande trädet, med alla andra noder som förgrenar sig från det.
- De mest använda karaktärerna kommer att vara bladen närmast trädets topp, medan de sällan använda karaktärerna kommer att placeras längst ner på trädet, längre bort från roten.
- 5Skapa en kodningskarta. Gå genom trädet för att nå varje karaktär. Varje gång du besöker en nods vänstra barn är det ett "0". Varje gång du besöker en nods rätt barn är det ett '1'. När du kommer till en karaktär, lagra karaktären med sekvensen 0 och 1 som det tog för att komma dit. Denna sekvens är vad karaktären kommer att kodas som i den komprimerade filen. Lagra karaktärerna och deras sekvenser på en karta.
- Börja till exempel från roten. Besök rotens vänstra barn och besök sedan nodens vänstra barn. Eftersom noden du befinner dig nu inte har några barn har du nått en karaktär. Detta är ' '. Eftersom du gick åt vänster två gånger för att komma hit är kodningen för '' "00".
- För det här trädet ser kartan ut så här: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Placera dessa noder i en prioritetskö med varje karaktärs frekvens som dess prioritet. - 6Inkludera kodningskartan i rubriken i utdatafilen. Detta gör att filen kan avkodas.
- 7Koda filen. För varje tecken i filen som ska kodas, skriv den binära sekvensen du har lagrat på kartan. När du har kodat filen, se till att lägga till EOF till 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-kodningsalgoritmen inte använder 8-bitarsformatet har kodade filer ofta inte 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, vilket 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 detta och sedan stoppa och ignorera allt annat som har lagts till efter.
Del 2 av 2: avkodning
- 1Lä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 du använde för att koda filen. De två träden ska vara identiska.
När du är klar kommer den sista noden i kön att vara roten till det kodande trädet, med alla andra noder som förgrenar sig från det. - 2Läs i en binär siffra åt gången. Korsa trädet när du läser: om du läser i en '0', gå till vänster barn av noden du befinner dig i, 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 en karaktär. Skriv tecknet i den avkodade filen.
- På grund av hur karaktärerna 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 kodning av en annan karaktär. Kodningen för varje karaktär är helt unik. Detta gör avkodningen mycket enklare.
- 3Upprepa tills du når EOF. Grattis! Du har avkodat filen.
Relaterade artiklar
