Labor 1: Huffmanni algoritm (itv0020)

Allikas: Lambda
Süsteemprogrammeerimine keeles C

Praktikumid

Laborid

Selle laboratoorse töö eesmärk on tutvuda üldotstarbeliste pakkimisalgoritmidega

Only the fool would take trouble to verify that this sentence was composed of ten a's, three b's, four c's, four d's, forty-six e's, sixteen f's, four g's, thirteen h's, fifteen i's, two k's, nine l's, four m's, twenty-five n's, twenty-four o's, five p's, sixteen r's, forty-one s's, thirty-seven t's, ten u's, eight v's, eight w's, four x's, eleven y's, twenty-seven commas, twenty-three apostrophes, seven hyphens, and, last but not least, a single ! - Sentences about Self-Reference

Ülesanne

Teie ülesandeks on kirjutada programm, mis pakib Hufmanni algoritmi abil faile kokku ja lahti.

Huffmanni algoritmi juhendvideo, mis seletab ära kuidas pakkimise algoritm töötab.

Meetod on ise on ka SIIN ära toodud. Kui seal toodud ülesanded ükshaaval lahendada, on lõpplahendus vaid koodijuppide omavahelise kokkukeevitamise kaugusel.

Kokkupakkimine lühidalt:

  • Koguge tähemärkide esinemissageduse statistika
  • Moodustage pakkimise kodeeringut tekitav puu
  • Looge puu abil igale tähemärgile vastav kood
  • Kirjutage puu tulemusfaili
  • Kirjutage koodide abil faili sisu tulemusfaili

Lahtipakkimine lühidalt:

  • Taastage kodeeringut hoidev puu
  • Taastage puu abil faili sisu

Lisaks on tarvis leida meetod andmete biti kaupa väljakirjutamiseks olukorras, kus operatsioonisüsteem toetab vaid baidi kaupa kirjutamist (st on vaja tekitada väike bittide kirjutamise library).

Programmi funktsionaalsuse näitena võtame näiteks programmi gzip, mis ilma parameetriteta käivitamisel andmed kokku pakib. Kasutades -d parameetrit, pakib gzip andmed taas lahti. Tavaolukorras funktsioneerib ta filtrina: loeb stdin'ist ja kirjutab stdout'i. gzip suudab kasutada ka faile, kuid seda funktsionaalsust pole kohustuslik implementeerida.

Programmi võid testida Calgary pakkimiskorpusel. Programm võiks saavutada tekstifailide (book*, prog*) pakkimise vähemalt 30%. Teiste failide (pildid, heli), pakkimisel peaks programm suutma kokku ja lahti pakkida, kuid suuruse kahanemine ei ole ilmtingimata kohustuslik.


Esitamine

Programm tuleb Jaagup Irvele tähtajaks ette näidata. Kui programm on valmis:

  1. Pane see dijkstra.cs.ttu.ee kataloogi ~/CLABOR/lab1
  2. Testi seda hoolega. Võib-olla on abi järgmisest csh programmist (eeldusel, et sinu programmi nimi on compr, proovib ta pakkida ja lahti pakkida iga kataloogis olevat faili, võrreldes lahtipakitud faile originaaliga)
foreach f ( lab1_test/* )
   compr $f tmp1 && compr -d tmp1 tmp2 && cmp $f tmp2 && echo $f ok
end
  1. Kirjelda oma programm failis ~/CLABOR/lab1/README (mida ta teeb, kuidas kompileerub, kuidas jooksutada)
  2. Näita oma programmikood enne tähtaega ette.

NB: Failid peavad kuni sessi lõpuni seal kataloogis püsima.

Programmi argumendid

Iga faili puhul peab töötama käsk: 

prog < file | prog -d >file1

ühtlasi peab tulemus originaaliga identne olema. Isegi kui fail on tühi või hiiglaslikult suur, peab programm töötama. Erandlikel puhkudel (mälu täis, sisend/väljundviga lahtipakitav fail on vigane) peab programm rahulikult veakoodi väljastama ja väljuma, ta ei tohi crashida.

Juhul kui standardsisendi ja standardväljundi kasutamine tundub üle jõu käiv, võite kirjutada programmi töötama failidega: 

prog infile huffile
prog -d huffile outfile
diff infile outfile # diff programm võrdleb kaht faili omavahel

Probleemid

Mis on tähemärkide tüüp?

Vaikimisi on char märgiga tüüp. See tähendab, et kõrgeim (8s) bitt tähistab märki (1 miinuse puhul, 0 muidu). Kui char-i intiks teisendad, lähevad tähemärgid, mis on üle 127 negatiivseks. Kui kirjutad tabch, kus ch on charina deklareeritud, teed ränga vea, mida kompileerija ei avasta. Selle vältimiseks peaksid ch deklareerima int-ina. Nii on kõigi tähemärkide koodid positiivsed. Teine põhjus, miks int on parem valik, on see, et funktsioon int getc(FILE*) võib anda 257 erinevat väärtust (-1 kuni 255), mis kõik ühte baiti ära ei mahu. On omamoodi irooniline, et C-s on (ruumi kokkuhoiuks) võimalik kasutada char tüüpi, kuid samas ei saa seda kasutada charide sisselugemisel.

Vale väljumiskood

Unixis tagastavad kõik programmil väljumisel ühe baidi, mida nimetatakse exit code või exit status. Üldtähendus on selline, et niisama väljumisel antakse tagasi 0 ning mingit tüüpi vea korral nullist erinev väärtus. Shellis saab tagastatavat väätust kontrollida muutuja $? abil. 

more foo.c; echo $?

Samuti && || käsu abil 

cmp foo.c bar.c && echo Files equal || echo Files differ

Selle väärtuse määramiseks on kaks viisi: esiteks exit() funktsiooni argumendina, teiseks on võimalik int main() funktsiooni poolt tagastatav väärtus. Kui seda ei määrata, valib kompileerija kuidas käitutakse: enamasti on selleks suvaline rämpsnumber.

Kataloogiprobleemid.

Programmi testimise viis ei ole määratud. Võimalik, et käivitan programmi sinu kodukataloogis, võimalik, et oma kodukataloogis või siis et kompileerin ise kokku ja panen käima. Kui jooksvas kataloogis peavad veel mingid failid olema, kirjuta see README alla. Ajutiste failide tarbeks kasuta standardseid funktsioone tmpfile() või tmpnam() ja mitte mõni kindlaksmääratud nimega fail parajasti aktiivses kataloogis (võimalik, et mul ei ole võimalik teie kodukataloogi kirjutada). Kui sa ei kasuta stdin ja stdout streame ja teed failid funktsiooni fopen() abil lahti, peaksid kontrollima, kas nad ka tegelikult tulid lahti. Kui sääraseid vigu leidub, ei saa ma programmi testida isegi juhul, kui algoritmi implementatsioon on korrektne.

Pakitud fail on arhitektuurist sõltuv.

Sinu programmi peaks olema võimalik kompileerida erinevate kompilaatoritega ja käivitada erinevate masinate peal. Tulemused peaksid olema ühilduvad: ühes arvutis pakitud fail peaks tulema lahti ka teistes arvutites. Et seda võimaldada, tuleb lugeda ja kirjutada baithaaval ja baidimassiividega opereerides. Mitte integeride, mitte pointerite, mitte struktuuridega. Näiteks: 

putc(ch,outf); /* OK */
fwrite(outf,1,buflen,buff); /* OK kui buff on charide massiiv*/
fwrite(outf,sizeof(long),1,filelen); /* sõltub masinast ! */
putw(filelen,outf); /* sõltub masinast ! */
putbits(filelen,32); /* OK, kui putbits on OK */

Võib eeldada, et long on vähemasti 32 bitti, aga int ja char võivad pisemad olla.

Väike sissejuhatus pakkimiskunsti

Esimene kokkupuude pakkimisega jätab pahatihti mulje maagiast: failid vähendavad äkitselt oma suurust ja kuskilt ilmub tasuta vaba ruumi.

Praeguse töö eesmärk on implementeerida üks kindel algoritm ja mitte tutvuda kogu selle taga oleva teooriaga. Samas on osa sellest taustast kasulik niisamagi teada.

Antud töö puhul huvitume üldotstarbelisest kadudeta pakkimisest.

  • Üldotstarbelisus tähendab, et ta peaks sööma iga sisendit (vastanduvalt näiteks video või heli pakkimisel kasutatavatele erialgoritmidele). Sisendilt ei eeldata mingit kindlat struktuuri (mõningad andmebaasipakkimistehnikad).
  • Kadudeta tähendab, et algne info on võimalik saada tagasi täpselt (Vastupididselt siis fraktaalsetele meetoditele, mille abil saavutame algse faili lähendi, mis ainult tundub sarnane)
  • Pakkimine...

Seda on tegelikult üsna keeruline defineerida. Me ei saa eeldada, et antud algoritm kahandab suvalist sisendit. Tegelikult on nii, et kõik pakkimismeetodid väendavad mingite sisendite puhul andmete pikkust märgatavalt, samas kui mõnede teiste puhul hoopis suurendavad seda.

Harjutus: Tõesta ülaltoodud väide (suhteliselt lihtne). Ja selgita, miks enamik inimesi, kes PKZIPi kasutavad, sellest ei hooli.

Enamikul pakkimismeetodeid põhineb kahel põhimetoodikal:

Statistiline pakkimine

Mõningad tähed esinevad tekstis tihemini kui teised. Idee on selles, et tihedamini esitatavad tähed võtaksid vähem ruumi, kui haruldased. Need põhinevad Shannoni töödel andmeedastuse kohta. Kõige tuntum neist algoritmidest on Hufmanni oma.

Asendav pakkimine (LZ perekond)

Pakkimisalgoritm sisaldab sõnaraamatut mõnedest levinumatest sõnadest (tähemärgijadadest). Kui ta mõne sellise sõnaraamatust välja loeb, asendab ta selle mingi viitega. Idee on põhimõtte poolest vanem kui arvutid. 1977-78 esitasid Lempel ja Ziv kaks algoritmi (erineva sõnastikukasutusega), mida nimetatakse LZ77 ja LZ78. Kaasaegseid variatsioone nimetatakse sarnaselt LZS, LZW, LZP jne.

Levinumad programmid kasutavad mitut meetodit korraga. Harilikult kasutatakse kõigepealt mõnd Lempel-Ziv-i et globaalsed kordused välja korjata, seejärel käiakse tulemusest Hufmanni algoritmiga üle. Kui on meeles programm nimega LZH, siis see sai oma nime täpselt sedamoodi käitumise eest. Enamik programmidest teab mitut meetodit, mille hulgast valitakse pärast faili alguse analüüsi. Kui meetodist pole abi, säilitatakse fail nii nagu ta on. Näiteks on PKZIPil ja ARJil mõlemal üks lemmikvõte ja paar eriolukordade tarbeks mõeldud meetodit.

Lingid

Pärit leheküljelt "http://lambda.ee/w/index.php?title=Labor_1:_Huffmanni_algoritm_(itv0020)&oldid=9603"