5.4. Tehtävä: LZW-pakkaus
Tästä sivusta:
Pistearvo: 200p
Bonus: +5 % omista pisteistä aikaisesta palautuksesta.
Intro
Tehtävässä kirjoitetaan ohjelma, joka pakkaa Lempel-Ziv-Welch pakkausalgoritmilla annettua tekstiä. Käy aluksi lukemassa Wikipedian artikkeli LZW-pakkauksesta (vanha versio - uusimmasta versiosta joku on editoinut algoritmin pseudokoodin jne. pois). Tätä tehtävää varten ei tarvitse kuitenkaan ymmärtää tarkalleen miten pakkausalgoritmi toimii. On riittävää, että pystyt annetun luokan LZWReader ja mm. wikipediasta löytyvän pseudokoodin perusteella toteuttamaan luokan LZWWriter.
Don't Panic [1]
Algoritmi on oikeasti suhteellisen yksinkertainen toteuttaa. Aluksi kannattanee kokeilla wikipedian koodausesimerkkiä paperilla. Sitten voi vilkaista valmista luokkaa LZWReader ja verrata sitä pseudokoodiin. Tämän jälkeen toteutuksen pitäisi olla aika helppo rakentaa.
[1] Adams D., The Hitch-Hikers Guide to the Galaxy, Pan Books, United Kingdom, 1979
Oppimis- ja kertaustavoitteet
- Koodin lukeminen.
- Pseudokoodin implementointi.
- Tavumuotoisten tietovirtojen käyttö. (toteutustasolla)
Toteutusohjeet
Aloita tehtävä lukemalla mainittu wikipedian artikkeli ja tutkimalla luokkaa LZWReader. Päättele mitkä asiat luokan toiminnassa vastaavat artikkelin pseudokoodin eri osia.
Wikipedia-artikkelin ensimmäinen kappale "Description of the algorithm" antaa yleiskuvan algoritmista ja selittää kooditaulun alustuksen. Kappaleessa "Algorithm" on pseudokoodi sekä kirjoitus, että purkualgoritmille ja myöhemmin tulevassa kappaleessa Example selitetään kuinka algoritmi käyttää eri vaiheissa eri määrän bittejä merkkijonoja vastaavien koodien esittämiseen.
Kun ymmärrät luokan LZWReader-toteutuksen voit aloittaa LZWWriter:in toteutuksen. LZWWriterin write-metodin toteutus tulee olemaan lyhyempi ja yksinkertaisempi kuin LZWReader:in read, koska write-metodiin ei tarvitse tehdä minkäänlaista erillistä puskuria.
Toteutettava algoritmi on lopulta varsin yksinkertainen. Tehtävän pääpaino on enemmänkin koodin ja dokumentaation lukemisessa.
Toteutuksen erityispiirteet TÄRKEÄÄ!
Toteutus noudattaa artikkelissa kuvattua algoritmia varsin tarkasti. Allaolevat asiat ovat kuitenkin juuri tälle tehtävälle spesifejä ja selviävät myös luokkaa LZWReader lukemalla.
Koodikirjan alustaminen
- Algoritmi osaa koodata ja dekoodata merkistön 256 ensimmäistä merkkiä.
- Merkistön merkki '\0' (nollatavu) on sijoitettu koodille 256, muut merkit ovat alkuperäisillä paikoillaan.
- Vapaaksi jäänyttä koodia 0 käytetään kertomaan että tietovirta on päättynyt. (BitStream lähettää sen automaattisesti suljettaessa) Älä laita koodia 0 koodikirjaan.
Kuinka kirjoitetaan eri levyisiä merkkejä?
- Eri levyisten (biteissä) symbolien kirjoittaminen ja lukeminen on jätetty luokan BitStream vaivaksi. Reader ja Writer voivat muuttaa bittileveyttä metodilla set_code_length(length)
Pseudokoodista toteutukseksi
Pseudokoodin suoritus jakautuu init-metodiin, write-metodiin sekä close-metodiin.
- Pseudokoodin kaksi ensimmäistä riviä, jotka alustavat koodikirjan ja asettavat kentän w (lähettämättömien merkkien puskuri) tyhjäksi merkkijonoksi "", kuuluvat init:iin.
- For silmukassa tapahtuva syötteen käsittely toteutuu käytännössä monen write-kutsun aikana. Huomaa että puskurin w arvon täytyy säilyä kutsusta toiseen. Puskurissa on tallessa ne merkit joita writen loppuessa ei vielä ehditty koodata.
- Lopuksi pseudokoodin rivi, joka lähettää merkkijonon päättyessä puskurin w sisältämän datan kuuluu close-metodin tehtäviin. Riville "display output" ei ole varsinaista vastinetta.
Vinkkejä
- VINKKI Voit testata luokkaasi myös pakkaamalla jotakin aineistoa ja purkamalla tuloksen LZWReader:illa. Luo tiedosto kirjoittamista varten. Anna se parametrina luodessasi LZWWriter-olion. Luo testimerkkijono ja anna se parametrina write-metodille. Write huolehtii sen pakkamisesta tiedostoon. Sulje virta. Avaa nyt tiedosto lukemista varten ja luo LZWReader olio tällä tiedostolla. read-metodin pitäisi palauttaa alkuperäinen testimerkkijono.
- VINKKI Voit kokeilla koodiasi kehitysvaiheessa vaikkapa wikipedian esimerkillä "TOBEORNOTTOBEORTOBEORNOT". Koska merkki 0 on meidän merkistössämme paikalla 256 niin kaikki uudet koodit tulevat meidän taulussamme yhden numeron verran korkeammille paikoille. Muuten kooditaulun pitäisi vastata k.o. esimerkkiä.
- VINKKI Älä unohda sulkea LZWWriteria testeissäsi, koska sulkeminen hoitaa viimeisen merkin lähettämisen.
- VINKKI Huomaa että pakkaus tapahtuu tietovirtaan, joten metodia write-kutsutaan lukuisia kertoja. Joidenkin muuttujien pitää siis säilyä metodikutsusta toiseen.
- VINKKI Huomaa että väärin pakattukin tietovirta voi olla purettavissa täysin oikein. Vaikka et pakkaisi lainkaan (lähetät vain yhden merkin mittaisten pätkien koodeja) niin tietovirta on kyllä purettavissa - se ei vaan ole pakattu lainkaan. Tämän vuoksi pelkkä pakkaaminen ja purkaminen ei yksinään takaa että pakkaus olisi tehty oikein.
Valmiiksi annettu koodi
- LZW_writer.py: Palautetaan Täydennettävä tehtäväpohja.
- LZW_reader.py: (Ei palauteta) Edellisen vastakappale, jota voit käyttää toteutuksesi testaamiseen.
- bit_stream.py: (Ei palauteta) Vaihtelevan levyisten koodien lukemiseen ja tulostukseen tarkoitettu luokka. Tarvitset tätä luokkaa LZWWriter-luokkaa toteutettaessa.
- test_file2.lzw: (Ei palauteta) Rikkinäinen pakkaustiedosto, jos tarvitsee testaukseen. Löytyy myös A Plussasta.
- test.py: Palautetaan
Rakenna itse testiluokka
Test, joka testaa LZWWriterin toimintaa. Palauta luomasi test.py-tiedosto.