Labb 3

Huffmankodning

Problem

Du ska implementera ett program som komprimerar filer med hjälp av Huffmankodning. Du ska läsa in originalfilen en byte i taget; på det sättet kommer ditt program att fungera för alla typer av filer.

Utförande

En bra beskrivning av Huffmankodning finns här: https://www.cs.duke.edu/csed/poop/huff/info/

Du ska naturligtvis testa ditt program. Ett bra sätt är att placera testkod i main-metoden i de klasser som ska testas. Klassen BitFileReader.java är ett exempel som visar hur du kan göra. Klassen innehåller kod för att läsa en bit i taget från en fil och dessutom finns det testkod i main-metoden.

Bithantering

Bithanteringen har inte nödvändigtvis något med Huffmankodning att göra. Därför bör denna del av programmet vara generell nog att kunna användas av andra program.

Implementera en klass BitFileWriter, som kan skriva enskilda bitar (ettor och nollor) till en fil. Här finns en kort tutorial som visar hur man läser och skriver bytes i Java: https://docs.oracle.com/javase/tutorial/essential/io/bytestreams.html. För att spara data så utrymmessnålt som möjligt måste varje bit som skrivs till fil med BitFileWriter represeteras av en enda bit i filen, och inte av ett helt tecken. Den minsta dataenhet som går att skriva till en fil är en byte. BitFileWriter måste därför samla på sig ett flertal bitar innan den kan skriva något till en verklig fil. Titta noga på koden i BitFileReader för inspiration.

Vid komprimering av en fil skall programmet skapa två filer; en fil som innehåller den komprimerade versionen av källfilen, och en kodfil som innehåller en beskrivning av det använda Huffmanträdet. Det är också möjligt att spara båda dessa filer tillsammans som endast en fil, men det är inte nödvändigt i den här labben.

Eftersom man förmodligen vill kunna komprimera flera olika filer så bör namnen på samtliga filer som komprimeringsprogrammet skapar (kodfil, komprimerad fil) skilja sig från originalfilen, lämpligen genom att programmet lägger till ändelser på orginalfilnamnet.

Vid dekomprimering skall programmet med hjälp av den komprimerade filen och kodfilen skapa en fil som är innehållsmässigt identisk med källfilen.

Programmet skall uppfylla följande:

• Klassen BitFileWriter skall ha ett klart definierat gränssnitt. Inga metoder utanför gränssnittet får användas i resten av koden.
• Det ska finnas tester för ovanstående gränssnitt.
• BitFileWriter skall förstås inte utföra någon del av Huffmankodningen.
• Programmet skall klara av att komprimera godtyckliga filer. Detta löser du genom att läsa in och koda en byte i taget.
• Alla mellansteg (producerade filer) skall finnas kvar, så att de kan jämföras.

Tips och exempel

I Unix finns ett program som heter hexdump som kan användas vid felsökning. Programmet skriver ut enskilda bytes från en fil så att man på ett enkelt sätt kan se exakt vad filen innehåller. Nedan följer ett exempel på hur programmet fungerar. 

sni@my> echo abcdefghijklmnopqrstuvwxyzåäö > test.txt
sni@my> hexdump -C test.txt
00000000 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f 70 |abcdefghijklmnop|
00000010 71 72 73 74 75 76 77 78 79 7a c3 a5 c3 a4 c3 b6 |qrstuvwxyz......|
00000020 0a                                              |.|
00000021
sni@my>

Den första raden skapar en fil som heter test.txt som innehåller alla bokstäver i alfabetet. I kolumnen längst till höger återfinns innehållet i filen utskrivet med vanliga tecken.

Programmet diff kan användas för att jämföra om två filer är innehållsmässigt lika. Om filerna är olika skriver diff ut ett meddelande som beskriver skillnaden mellan filerna. Om filerna är lika avslutas diff utan utskrifter.

Programmet ls -l visar, bland annat, storleken på alla filer i en katalog.

För att veta när den kodade filen är slut så bör du ha en särskild slutsymbol, som förstås måste kodas på ett sätt som skiljer sig från samtliga andra bytes i filen.

Använd gärna ett enkelt textformat för att lagra kodfilen. I stället för att lagra trädet så kan du lagra information om antalet förekomster av olika bokstäver. En fil med innehållet "ABCBCB" ger då upphov till en kodfil som är en text-fil med två tal per rad (A kodas som en byte med värdet 65, etc):

65 1
66 3
67 2

Med hjälp av den här informationen så kan man ju återskapa huffmanträdet.