Yliopistologo

FM Heikki Hyyrön tietojenkäsittelytieteiden alaan kuuluva väitöskirja

Practical Methods for Approximate String Matching (Käytännöllisiä menetelmiä likimääräiseen merkkijonohakuun)

tarkastetaan 5.12.2003 klo 12 Tampereen yliopiston Pinnin B auditoriossa B1096, Kanslerinrinne 1, Tampere.

Vastaväittäjänä on akatemiaprofessori Esko Ukkonen (Helsingin yliopisto). Kustoksena toimii professori Martti Juhola.

***

Heikki Hyyrö on syntynyt Tampereella ja hän on suorittanut filosofian maisterin tutkinnon Tampereen yliopistossa. Hän on työskennellyt vuodesta 1999 lähtien tutkijana Tampereen yliopiston tietojenkäsittelytieteiden laitoksella.

Hyyrön väitöskirja ilmestyy Tietojenkäsittelytieteiden laitoksen sarjassa, A-2003-4, Tampereen yliopisto, Tampere 2003. ISBN 951-44-5818-4, ISSN 1459-6903. Ilmestyy myös sähköisenä sarjassa Acta Electronica Universitatis Tamperensis; 308, Tampereen yliopisto 2003.
ISBN 951-44-5840-0, ISSN 1456-954X, http://acta.uta.fi.

Väitöskirjan tilausosoite: Verkkokirjakauppa Granum, http://granum.uta.fi, tai Tampereen yliopiston julkaisujen myynti, PL 617, 33101 Tampere, puh. (03) 215 6055, e-mail: taju@uta.fi.

Lisätietoja: Heikki Hyyrö, (03) 215 6071 (työ), heikki.hyyro@cs.uta.fi

LEHDISTÖTIEDOTE

Merkkijonohaku tarkoittaa hakusanan esiintymien etsimistä tekstistä. Tällainen toiminto on yleinen esimerkiksi tekstinkäsittelyohjelmissa tai tietokantahauissa. Varsinkin tietokantahauissa käytetään usein indeksoitua merkkijonohakua, jossa haku saadaan tehtyä hyvin nopeasti käyttäen etukäteen tietokannan aineistosta koostettua indeksirakennetta.

Usein käytetään ns. eksaktia merkkijonohakua, jossa etsitään ainoastaan hakusanan kanssa identtisiä tekstinosia. Eksakti merkkijonohaku ei kuitenkaan välttämättä löydä kaikkia haluttuja tekstin kohtia, jos teksti tai hakusana voi sisältää kirjoitusvirheitä tai niiden kirjoitusasu muuten poikkeaa. Esimerkiksi hakusana "Tschaikovski" ei täsmää "Tschaikovskyn" tai "Tshaikovskin" kanssa, vaikka näiden jälkimmäisten kirjoitusmuotojen esiintymät voisivat olla hakijan kannalta kiinnostavia. Toinen esimerkki eksaktin merkkijonohaun rajoituksista on merkkijonohaku perimä- eli DNA-sekvenssistä. DNA-sekvensseissä tyypillisesti esiintyvä pieni vaihtelu esim. mutaatioiden seurauksena tekee eksaktin merkkijonohaun riittämättömäksi.

Likimääräinen merkkijonohaku pyrkii ottamaan variaation (esim. kirjoitusvirheet) huomioon etsimällä sellaiset tekstinosat, jotka ovat riittävän samankaltaisia hakusanan kanssa. Merkkijonojen välistä samankaltaisuutta mitataan usein editointietäisyydellä, ts. etsitään sellaisia merkkijonoja joiden editointietäisyys hakusanasta katsotaan riittävän pieneksi. Kahden merkkijonon välinen editointietäisyys määritellään usein pienimmäksi tarvittavaksi editointioperaatioiden lukumääräksi, joka tarvitaan kun merkkijonot editoidaan keskenään identtisiksi. Yksittäinen editointioperaatio voi tyypillisesti olla yhden merkin lisäys, poisto tai korvaus toisella merkillä. Lisäksi varsinkin kirjoitusvirheiden yhteydessä on tyypillistä sallia myös ns. transpositio, joka vaihtaa kahden vierekkäisen merkin paikkaa keskenään. Esimerkiksi hakusana "Tschaikovski" täsmää sekä "Tschaikovskyn" että "Tshaikovskin" kanssa, jos käytetään likimääräistä merkkijonohakua sallien yhden editointioperaation virhe.

Väitöskirjatutkimuksessa on tutkittu ja edelleen kehitetty käytännössä tehokkaita menetelmiä likimääräiseen merkkijonohakuun. Työ sisältää menetelmiä editointietäisyyden laskemiseen, likimääräiseen merkkijonohakuun sekä indeksoituun likimääräiseen merkkijonohakuun. Työssä myös esitetään empiirisiä vertailuja uusien ja aiempien menetelmien välillä, ja vertailujen pohjalta voidaan sanoa että uudet menetelmät toimivat monessa tapauksessa aiempia huomattavasti nopeammin.


[laskuri] käyntiä 24.11.2003 alkaen

Väitökset    Tampereen yliopiston kirjasto   Tampereen yliopisto