DATS 2300202012

Prev Up Next

Hei alle sammen!

 

forrige uke så så vi på Huffman koding som en form for komprimering, og vi fortsetter med teamet komprimering denne uken. Vi skal se på LZW-koding, og hashing (og dermed hashmaps)

 

Huffman-trær ble brukt til å lage optimale prefix-koder for komprimering av symboler (og dette er pensum i kurset). Symboler betyr her bokstaver (f.eks ABCDR for å kode ABRACADABRA), eller binære tegn (som typisk vises som � og andre rare symboler) om du åpner en binærfil i en teksteditor. Hvert av disse symbolene består av 8 bit (som er lengden til en char), og det Huffman-koding gjør er å erstatte disse 8 bit lange tegnene med bit-koder som er kortere (kanskje bare to til fire bit bit) for symboler som forekommer ofte. For symboler som forekommer sjeldent kan vi ha mye lengere bit-koder, men det gjør ikke så mye fordi de forekommer sjeldent. Det geniale med Huffmans metode er måten han lager disse prefix-kodene/bit-kodene. Se forrige ukes forelesnings-videoer for detaljene.  

 

LZW-komprimering bruker en annen fremgangsmåte. Istedenfor å erstatte hvert symbol med en kortere kode, så forsøker LZW å kode flere symboler etter hverandre (ett "ord") med en enkelt kode. Hver gang LZW ser en ukjent symbolkombinasjon, så lager algoritmen en ny kode for denne kombinasjonen. Det geniale med LZW-koding er at man ikke trenger å sende med ordboken med koder for å dekode. Alt man trenger for å dekode er kodene for enkelt-symbolene. 

 

 

 

Forelesning

I ukens tirsdagsforelesning gikk vi gjennom eksamens-relaterte ting, samt emneevaluering. Vi gikk også gjennom hashmap både i teori og i kode. Et hashmap består essensielt sett av et array, hvor hvert element i arrayet består av en lenket liste (eller i noen tilfeller lagrer man den "listen" i arrayet selv, også kalt "åpen addressering" i kompendiet). Dette gjør at dersom man har korte lister så får man konstant tid ved både innlegging og ved uttak/søking i listen. Dette gjør hashmap til en veldig effektiv datastruktur. Men: dersom hash-funksjonen er dyr (f.eks. å beregne hashen av en DVD-film) så er konstant tid fortsatt veldig dyrt (nettopp fordi det tar lang tid å hashe dataene). Kildekoden ligger på github som vanlig