Practical Methods for Approximate String Matching
Hyyrö, Heikki (2003)
Hyyrö, Heikki
Tampere University Press Tampereen yliopisto
2003
Tietojenkäsittelyoppi - Computer Science
Informaatiotieteiden tiedekunta - Faculty of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Väitöspäivä
2003-12-05
Julkaisun pysyvä osoite on
https://urn.fi/urn:isbn:951-44-5840-0
https://urn.fi/urn:isbn:951-44-5840-0
Tiivistelmä
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.
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.
Kokoelmat
- Väitöskirjat [4980]