Tämä ohjelma perustuu ajatukseen, että tulevien kirjaimien (foneemien, ...) ennustaminen antaa olennaista tietoa kielen morfologisesta rakenteesta.
Toteutus perustuu puhtaasti yhteen tietorakenteeseen, prefiksipuuhun. Käytännössä kyseinen tietorakenne on kohtuullisen tilatehokas tapa pitää muistissa jonkin aineistotekstin jokainen alamerkkijono (käytännössä alamerkkijonojen pituus rajoitetaan esim. 6 merkkiin tilan säästämiseksi) sekä se, kuinka monta kertaa kyseinen merkkijono esiintyy tekstissä.
Prefiksipuun perusteella voi laskea tehokkaasti (a) todennäköisyyksiä eri seuraaville merkeille aiempien merkkien (ts. merkkihistorian) perusteella; (b) todennäköisyyshajoamia seuraavan merkin eri vaihtoehtojen välillä.
Varsinainen algoritmi koostuu näiden kahden arvon vaihtelun seuraamisesta: tod.näk.hajoaman sekä sen, kuinka todennäköisenä toteutunutta merkkiä pidettiin. Kun kumpi tahansa näistä arvoista putoaa puoleen edellisen merkin vastaavasta arvosta, katsotaan siinä kohtaa olevan morfeemin raja.
Lähdekoodi on nähtävissä täällä: http://sange.fi/~atehwa/ptmorph/prefixtree.ss
[kategoria: ohjelmointi] [kategoria: kieli]