Stemmaus (stemming) eli karsinta tai ”typistäminen” on tiedonhakuun liittyvä luonnollisen kielen käsittelyn menetelmä, jossa sanoista poistetaan niiden sanaliitteet (affixes) ja/tai johtimet (derivatives). Käytännössä stemmaus tapahtuu ns. stemmereiden eli karsintaohjelmien avulla, algoritmeja tai sanakirjaa (usein myös molempia) hyödyntäen. Saadut vartalot (stems) indeksoidaan hakuavaimiksi tietokantaan, ja tarvittaessa myös hakukyselyt stemmataan. Menetelmän tavoitteena on kyselyjen ja tekstitietokantojen indeksin keskinäinen yhdenmukaistaminen, mikä edesauttaa relevanttien dokumenttien löytymistä täsmäytysvaiheessa.
Historia 1950- ja 1960-lukujen ensimmäiset automaattiset tekstitiedonhakujärjestelmät olivat ns. viitehakujärjestelmiä, jotka painottuivat tieteellisiin artikkeli- ja kirjallisuusviitteisiin. Englanti oli tieteen kielenä tiedonhaun keskiössä, ja vaikka sen morfologia onkin melko yksinkertainen, hakutermeinä käytettyjen yksittäisten sanojen muodonvaihtelut hankaloittivat usein relevanttien dokumenttien löytämistä. Kielellisen kattavuuden ja tulosten parantamiseksi ryhdyttiin siksi kehittämään erilaisia tietokoneohjelmia.
Varhaisin tällainen menetelmä oli hakutermien katkaiseminen. Se jätti kuitenkin vastuun käyttäjälle, mikä ei ollut kovin luotettava ratkaisu. 1960-luvun lopulla alettiin suunnitella hakutermien ja teksteissä esiintyvien sanojen yhdenmukaistamiseen omaa ohjelmaansa. Ensimmäisen tähän tarkoitukseen soveltuvan stemmerin eli karsintaohjelman kehitti Julie Beth Lovins MIT:ssä vuonna 1968. Ohjelma oli aikaiseen julkaisuajankohtaansa nähden varsin edistynyt ja myöhemmälle tutkimukselle uraauurtava. Muutama vuosi myöhemmin John Dawson kehitteli oman, Lovinsin stemmeriä muistuttavan versionsa (Dawson Stemmer) Cambridgen yliopiston kirjallisuus- ja kielitieteiden keskuksessa. Hän julkaisi algoritminsa 1974.
Myöhemmistä stemmereistä suosituin on varmasti Porterin algoritmi, jonka Martin Porter sai valmiiksi 1980 – niin ikään Cambridgessä. Alkuperäinen ohjelma oli kirjoitettu BCPL-kielellä, mutta se on sittemmin käännetty myös useille muille ohjelmointikielille. Porterin itsensä kehittämän Snowball-ohjelmointikielen myötä algoritmista on muokattu versioita myös muille kuin englannin kielelle.
Tunnettuja karsintaohjelmia ovat lisäksi Paice/Husk ja Krovetz. Ensin mainitun julkaisivat Chris Paice ja Gareth Husk Lancasterin yliopistossa 1990. Ohjelma toteutettiin Pascal-ohjelmointikielellä; käännöksiä on myöhemmin tehty esimerkiksi C-, Java- ja Perl-kielille. Krovetzin karsintaohjelma oli puolestaan Robert Krovetzin käsialaa. Hän esitteli kyseisen, englannin kielen sanakirjaa hyödyntävän karsintaohjelmansa vuonna 1993.
Stemmausmenetelmät Stemmausmenetelmät voidaan jakaa algoritmisiin, sanakirjallisiin ja tilastollisiin. Kaikilla menetelmillä on tiedonhaun kannalta omat hyvät ja huonot puolensa, ja niiden merkitys relevanttien dokumenttien löytämisessä vaihtelee kielikohtaisesti.
Algoritmiset karsintaohjelmat Algoritmiset stemmerit ovat pieniä ja kevyitä ohjelmia, jotka soveltuvat hyvin morfologisesti suppeampien kielien – kuten englannin – nopeaan ja automaattiseen käsittelyyn tiedonhakujärjestelmissä. Ensimmäiset stemmausalgoritmit suunniteltiin nimenomaan englannin kielen tarpeisiin, ja niissä on keskitytty poistamaan sanojen etu- ja/tai loppuliitteitä. Tunnetuimmat algoritmiset karsintaohjelmat lienevät Porterin, Lovinsin ja Paicen/Huskin stemmerit.
Porter Stemmer (1980) Martin Porterin vuonna 1980 julkaisema stemmausalgoritmi on karsintaohjelmista tunnetuin ja suosituin, ja sen pohjalta on myöhemmin kehitelty lukuisia paranneltuja versioita. Alkuperäinen ohjelma koostuu viidestä vaiheesta, jotka sisältävät sääntöjä englannin sanojen päätteiden (suffixes) poistamiseksi. Ensimmäinen vaihe – joka itsessään pitää sisällään kolme eri vaihetta (1a, 1b ja 1c) – käsittelee monikkoja ja menneen ajan partisiippimuotoja; loput neljä vaihetta (2, 3, 4, 5a ja 5b) ovat suoraviivaisempia.
Koska englannissa monimutkaisemmat päätteet koostuvat usein lyhyemmistä ja yksinkertaisemmista päätteistä, ohjelma karsii ne askel kerrallaan. Kun ehdot toteutuvat jonkin sanan kohdalla, pääte poistetaan kyseisen säännön määrittelemällä tavalla, minkä jälkeen siirrytään seuraavaan vaiheeseen. Näin edetään aina viimeisen, viidennen vaiheen loppuun.
Sääntöjä on yhteensä noin 60, ja ne ovat muodoltaan varsin yksinkertaisia:
(condition) S1 -> S2
Toisin sanoen, jos sanan pääte on S1, ja päätettä S1 edeltävä sanan osa täyttää sille suluissa annetut ehdot, pääte S1 korvataan päätteellä S2.
Esimerkiksi sana generalizations typistyisi seuraavasti:
Vaihe Stemmattava Sovellettava sääntö Tulos Selitys 1 generalizations S -> generalization Jos sana päättyy s-kirjaimeen, pääte poistetaan. 2 generalization (m>0) IZATION -> IZE generalize Jos päätettä -ization edeltävä sanan osa sisältää vähintään yhden vokaalia seuraavan konsonantin, päätteeksi muutetaan -ize. 3 generalize (m>0) ALIZE -> AL general Jos päätettä -alize edeltävä sanan osa sisältää vähintään yhden vokaalia seuraavan konsonantin, päätteeksi muutetaan -al. 4 general (m>1) AL -> gener Jos päätettä -al edeltävä sanan osa sisältää vähintään kaksi vokaalia seuraavaa konsonanttia, pääte poistetaan. 5 gener gener Yhdenkään viimeisen vaiheen sääntöjen ehdot eivät enää täyty, joten lopullinen vartalo on gener.
Porterin algoritmi tuotti kuitenkin myös virheitä. Se saattoi palauttaa eri vartalon samaa tarkoittaville sanoille (false negative) tai saman vartalon eri asiaa tarkoittaville sanoille (false positive). Uudemmassa versiossa (Porter2) näiden virheiden määrää on saatu alennettua.
Lovins Stemmer (1968) Julie Beth Lovinsin 1960-luvun lopulla julkaisema englannin kielen stemmausalgoritmi oli järjestyksessä ensimmäinen karsintaohjelma, ja sillä on ollut huomattava merkitys automaattisen sananmuotojen käsittelyn kehityksessä. Ohjelma tukeutuu listaan, joka sisältää 294 päätettä (järjestettynä pituuden mukaan laskevasti), 29 kyseisiin päätteisiin liittyvää ehtoa sekä 35 muunnossääntöä. Se on kooltaan Porterin algoritmia suurempi – mutta myös erittäin nopea, sillä se tarvitsee vain 1-2 vaihetta päätteen poistamiseksi.
Ensimmäisessä vaiheessa pisin ehdot täyttävä loppuliite poistetaan. Esimerkiksi päätteeseen -ionate liittyy ehto D, jonka mukaan päätettä edeltävän vartalon täytyy koostua vähintään viidestä kirjaimesta, jotta poisto suoritetaan. Näin ollen pass-ionate ei läpäise ehtoa (pass sisältää vain neljä kirjainta), mutta sen sijaan passion-ate toteuttaa lyhyempään päätteeseen -ate liittyvän ehdon A, jossa edeltävän vartalon pituutta ei ole rajoitettu. Vartaloksi tulee siten passion.
Toisessa vaiheessa sovelletaan edellä mainittuja muunnossääntöjä, joilla voidaan poistaa muun muassa vartaloon jääneiden tuplakirjainten toinen esiintymä (esim. rubb(ing) » rub), epäsäännöllisiä monikkomuotoja ym. poikkeuksia.
Lovinsin karsintaohjelman ongelmana on, että jokaiseen päätteeseen liittyy stemmausvirheitä aiheuttavia, usein ainutkertaisia poikkeuksia, joiden kaikkien huomioon ottaminen uusien sääntöjen muodossa veisi paljon aikaa ja resursseja, eikä lopputulos olisi pitkällä aikavälillä silti juurikaan parempi. Tämän vuoksi kehityksessä onkin keskitytty lähinnä yleisimpiin poikkeuksiin.
Paice/Husk Stemmer (1990) Paice/Husk -karsintaohjelma on Chris Paicen ja Gareth Huskin vuonna 1990 julkaisema stemmeri englannin kielelle. Algoritmi koostuu neljästä päävaiheesta, joiden välillä ohjelma liikkuu iteratiivisesti. Mukaan kuuluu vain yksi taulukko sääntöjä, jotka on esitetty seuraavassa muodossa:
sanan pääte käänteisessä järjestyksessä, valinnainen koskemattomuusmerkintä (intact flag) * (sääntöä sovelletaan vain sanoihin, joita ei ole vielä karsittu), poistettavien merkkien määrän ilmoittava numero (voi olla myös nolla), valinnainen lisämerkkijono, jatkamissymboli > tai . (ilmoittaa, jatketaanko stemmausta vai lopetetaanko).
Stemmattavan termin viimeinen kirjain tunnistetaan, ja sen loppuliitettä verrataan kyseisellä kirjaimella alkaviin sääntöihin. Jos säännön ehdot täyttyvät, pääte muutetaan (tai poistetaan) ja palataan joko alkuun tai lopetetaan. Jos ehdot eivät täyty, siirrytään seuraavaan sääntöön niin kauan, kunnes alkukirjain vaihtuu; tällöin ohjelma lopettaa tarkistamisen. Esimerkiksi sana dependency typistyisi seuraavasti:
Stemmattava Sovellettava sääntö Tulos Selitys dependency ycn2t> dependent Jos sana loppuu -ncy, korvataan päätteen kaksi viimeistä kirjainta kirjaimella t ja käytetään sitten stemmeriä uudelleen. dependent tne3> depend Jos sana loppuu -ent, poistetaan päätteen kolme viimeistä kirjainta ja käytetään sitten stemmeriä uudelleen. depend dd1.dei3y>deec2ss.dee1.de2>dooh4> depend Yhdenkään d-kirjaimella alkavan säännön ehdot eivät toteudu sanan depend kohdalla, joten alkukirjaimen vaihtuessa e-kirjaimeen stemmaus lopetetaan, ja vartalo jää nykyiseen muotoonsa.
Paice/Husk -algoritmi on osoittautunut varsin tehokkaaksi, ja se on yksinkertainen ja helposti toteutettavissa. Korvaamalla liitteet pelkän poistamisen sijasta vältetään myös ylimääräinen vaihe poikkeusten määrittelyssä. Toisaalta ohjelma poistaa päätteitä hyvin aggressiivisesti ja voi siksi aiheuttaa ylistemmausvirheitä.
Sanakirjaan perustuvat karsintaohjelmat Muoto-opiltaan monimutkaisempien kielien kohdalla pelkällä päätteiden automaattisella karsinnalla ei yleensä saavuteta parasta tulosta (ks. Stemmaus suomen kielen käsittelyssä), minkä vuoksi apuna on käytetty laajoja, etukäteen määriteltyjä listoja termien välisten suhteiden määrittämiseksi. Ongelmaksi muodostuu tällöin sanakirjan koko: kielet kehittyvät ja niihin ilmestyy jatkuvasti uusia sanoja, mutta sanaston pituus ei voi olla rajaton. Niinpä sanakirjallistenkin menetelmien rinnalla käytetään usein algoritmeja.
Krovetz Stemmer (1993) Yksi tunnetuimmista sanakirjaan ja algoritmiin perustuvista hybridikarsintaohjelmista on Bob Krovetzin vuonna 1993 kehittämä stemmeri. Vaikka tämäkin menetelmä oli tarkoitettu alun perin englannin kielelle, sen idea on ehkä käytännöllisempi laajan morfologian kielissä (esim. arabia, unkari, heprea). Ohjelma on huomattavasti monimutkaisempi kuin puhtaasti algoritmiset ratkaisut, mutta yksinkertaistaen sen toiminta voidaan jakaa kolmeen vaiheeseen:
Sanan monikkomuodon muuttaminen yksikkömuotoon Sanan menneen muodon muuttaminen preesensiin Ing-muodon poistaminen
Ohjelma tarkistaa ennen jokaista vaihetta sanakirjasta, onko kyseinen sana olemassa. Jos on – eikä siihen liity poikkeuksia – sana jää stemmaamatta. Mikäli taas sanaa ei löydy, sen päätettä verrataan erilliseen, yleisten taivutus- ja johdospäätteiden listaan. Jos vastaava pääte löytyy, se poistetaan, minkä jälkeen tarkastetaan jälleen sanakirjasta sanan olemassaolo. Jos se löydetään, vartalo hyväksytään; muutoin sanan loppua muokataan poistetun päätteen perusteella. Esimerkiksi monikon sanasta dairies loppuliite -ies korvattaisiin ensin päätteellä -ie, mutta koska dairie ei ole englannin sanakirjassa, suffiksiksi vaihtuu -y.
Krovetzin karsintaohjelman etuna Porterin algoritmiin verrattuna on, että vartalot voidaan useimmiten indeksoida kokonaisina sanoina. Se myös palauttaa harvemmin saman vartalon eri asiaa tarkoittaville sanoille (false positive), mutta toisaalta myös useammin eri vartalon samaa tarkoittaville (false negative). Tuloksellisesti Krovetzin ja Porterin karsintaohjelmat ovat olleet melko lähellä toisiaan.
Krovetz itse ehdotti ohjelmansa käyttämistä eräänlaisena esikäsittelijänä jonkin toisen, varsinaisen stemmausalgoritmin rinnalla tarkkuuden lisäämiseksi.
Tilastolliset menetelmät