Harjoitustyö 1: Haikugeneraattori

Huom! Kohdassa "Bigram-malli" viimeinen lause päivitetty!

Toteutettava ohjelma

Harjoitustyön tarkoituksena on tehdä haikuja syöteaineistosta tuottava ohjelma. Haikujen tuottamiseen käytetään ehdollisiin todennäköisyyksiin perustuvaa bigram-mallia. Toteutuskielen olla ANSI-standardin mukainen C++. Standard Libraryn valmiita tietorakenteita ja algoritmeja saa tässä harjoitustyössä käyttää täysin vapaasti.

Haiku

Haiku on Japanilainen runotyppi jonka muodostamiseen on olemassa muutamia erilaisia sääntöjä. Tämän harjoitustyön osalta rajaamme alaa siten, että haiku on kolmesta rivistä muodostunut runo, jossa ensimmäisen rivin sana(t) sisältävät yhteensä tarkalleen viisi tavua, toisen rivin sanat seitsemän ja kolmannen rivin sanat taas viisi tavua. Tätä sanotaan ns. 5-7-5 säännöksi. Esimerkiksi:

Sinä ja minä
Olimme ystäviä
Ala-asteella

Bigram-malli

Bigram-malli on yksinkertainen todennäköisyyksiin perustuva malli jonka perus ideana on laskea todennäköisyydet sanojen esiintymisjärjestyksille syötteenä annetun tekstin perusteella. Jokaista sanaa Wi-1 kohden on olemassa jokin sana Wi ja näiden sanojen välillä on esiintymistodennäköisyys on P(Wi|Wi-1), bigram-mallissa lasketaan siis ensimmäisen asteen Markovin oletuksen mukainen todennäköisyys sanojen esiintymisjärjetykselle annetussa syöteaineistossa. Esimerkiksi P(olen|minä) = 0,12 tarkoittaa, että annetun syöteaineiston perustella sana "olen" esiintyy sanan "minä" jälkeen todennäköisyydellä 0,12. Lausekokonaisuuden viimeisellä sanalla ei ole seuraajaa. Lausekokonaisuus loppuu pisteesee tai pilkkuun.

Ohjelman toiminta

Haikugeneraattori lukee syötteenä annettua valmiiksi käsiteltyä tekstiä ja laskee syötteen sanojen esiintymisjärjestyksille bigram-mallin mukaiset ehdolliset todennäköisyydet. Tämän jälkeen haikugeneraattori saa syötteenään kolme sanaa. Syötetyt sanat ovat tuotettavan haikun kolmen säkeen aloitus sanat; ensimmäinen sana aloittaa ensimmäisen (viiden tavun) rivin, toinen sana toisen rivin (seitsemän tavua) jne. Mikäli jotain annetuista sanoista ei löydy ollenkaan opetusaineistosta, tulostetaan virheilmoitus.

Haiku tulee tuottaa ahnetta valintaa käyttäen siten, että jokaisen sanan seuraajaksi valitaan aina todennäköisin seuraaja niin kauan, että haikun viiden tai seitsemän tavun raja (rivistä riippuen) tulee täytettyä. Mikäli ahne valinta päätyy liian pitkään tavutukseen (esim. si-nä ja su-san-na -> 6 tavua) palataan edelliseen vaiheeseen jossa tavujen määrää ei vielä oltu ylitetty ja valitaan ahneesti seuraavaksi todennäköisin vaihtoehto (esim. si-nä ja mi-nä -> 5 tavua). Haikun ensimmäisen ja viimeisen rivin tulee olla täsmälleen viiden tavun mittaisia ja toisen rivin täsmälleen seitsemän tavun mittainen.

Mikäli jollain annetuista sanoista ei saada aikaan oikean mittaista riviä (joko bigram-malli ei sisällä tarpeeksi sanoja tai se ei sisällä sopivia sanoja) niin tulostetaan virheilmoitus (kts. tulostus). Mikäli joillekkin sanoille Wi ja Wi-1, P(Wi|Wi-1)=0 ei sanojen välillä ole mitään yhteyttä eivätkä ne saa täten myöskään esiintyä peräkkäin samalla rivillä missään olosuhteissa. Mikäli kahdella sanalla Wk ja Wj, P(Wk|Wi) = P(Wj|Wi) niin tulostetaan sanoista se joka on ensimmäisenä aakkosjärjestyksessä. Mikäli jostain annetusta sanasta ei saada generoitua haluttua riviä haikusta ollenkaan niin tulostetaan rivin tilalta virheilmoitus.

Syötteet

Haikugeneraattori saa alussa syötteenään lauseita joiden kaikki sanat on kirjoitettu pienillä kirjaimilla ja valmiiksi tavutettu. Tavuviivojen lisäksi lauseet sisältävät välimerkkejä "." (piste) ja "," (pilkku). Opetusaineisto loppuu merkkiin "#" (risuaita). Esimerkki syötteestä:

mat-ti ja mai-ja me-ni-vät kaup-paan. mat-ti os-ti mak-ka-raa ja mai-ja os-ti mai-to-a. mai-ja joi mai-don he-ti, mat-ti sääs-tää mak-ka-raa il-lak-si.#

Risuaita "#" annetaan tavutetussa syöteaineistossa heti pisteen jälkeen ilman tyhjiä merkkejä. Kaikki pisteet ja pilkut annetaan syötteessä normaaliin tapaan.

Haikugeneraattorin saatua syötteet voidaan sitä pyytää tuottamaan haikuja. Haikujen tuottamiseksi haikugeneraattorille syötetään kolme (tavuttamatonta) pinenllä kirjoitettua ja välilyönneillä eroiteltua sanaa, joita se käyttää haikun kolmen säkeen ensimmäisinä sanoina. Ohjelman suoritus lopetetaan syöttämällä toinen "#" (risuaita) viimeisen säkeenaloittavan sanan perään (ilman välimerkkejä). Esimerkiksi:

matti maija säästää#

Haikugeneraattorin tulee pystyä tuottamaan monta haikua samasta aineistosta mutta bigram-malli, jonka perusteella haikut generoidaan, tehdään ohjelman ajon aikana vain kerran.

Tulosteet

Haikugeneraattori tulostaa tuottamansa haikun kolmelle erilliselle riville (kts. haiku) ilman tavuviivoja. Jokaisen haikun väliin tulee tulostaa tyhjä rivi. Haikujen tuottaminen syöteaineistosta on yksiselitteistä eli samalla syöteaineistolla saadaan aina sama tulos.

Esimerkiksi edellisen esimerkin mukainen tuloste olisi:

matti ja maija
maija joi maidon heti
säästää makkaraa

Virhetilanteissa tulostetaan jompi kumpi seuraavista virheen luonteesta riippuen. Mahdolliset virhetilanteet on määritelty edellä.

Virheellisiin syötteisiin ei ohjelman toiminnassa tarvitse varautua.

Pidempi mallisyöte ja -tuloste

Selostus

Tästä harjoitustyöstä koodin lisäksi täytyy tehdä lyhyt selostus. Tarkemmat ohjeet selostuksen laatimiseen löytyy sivulta http://www.cs.tut.fi/~ai/selostus.html

Palautus

Itse palautus tapahtuu sähköpostitse osoitteeseen ai@cs.tut.fi,subjectina ai palautus 1, ja itse tiedostot tar-paketoituna ja mime-koodattuna, esimerkiksi näin:

tar cf - t999999.h t999999.cc Makefile | mimencode | elm -s"ai palautus " ai@cs.tut.fi

Onnistuneesta harjoitustyön palautuksesta tulee nopeasti automaattinen vastaus. Tämä vastaus siis tarkoittaa, että harjoitustyö on saapunut perille, ei suinkaan hyväksymistä. Harjoitustyö tarkastetaan vasta deadlinen mentyä umpeen.