Towards Faster String Matching

Julkaisun otsikon käännös: Nopeampaa merkkijononhakua

Hannu Peltola

    Tutkimustuotos: Doctoral ThesisCollection of Articles

    Abstrakti

    Tarkka merkkijononhaku on pitkään tutkittu ja edelleen suosittu tutkimusongelma. Tehtävänä on löytää tekstistä kohdat, joissa esiintyy haettava merkkijono, jota kutsutaan hahmoksi. Tässä työssä esitetään tarkkaan merkkijonohakuun uusia algoritmeja, tutkitaan niiden suorituskykyä käytännössä ja vertaillaan niitä useisiin tunnettuihin kilpaileviin algoritmeihin. Sisällöltään toisteisista aineistoista haettaessa esiintyviä erikoistilanteita analysoidaan ja niihin esitetään algoritmeja. Työssä tarkastellaan myös pitkien – noin 50 merkkiä pidempien – hahmojen etsintää. Lisäksi käsitellään reilun ja tasapuolisen suoritusnopeustestauksen periaatteita sekä mittaustarkkuutta. Kehitetyistä algoritmeista osa on uusia ja toiset taas muunnelmia aiemmista. Useimmat esitetyt algoritmit hyödyntävät bittirinnakkaisuutta, joka on viime vuosina laajasti omaksuttu tehokas tekniikka. Monet ''klassiset'' algoritmit osoittautuivat usein selvästi hitaammiksi kuin uudet. Merkkijononhaku on sovelluksissa yleinen ongelma, ja toisinaan tutkittavat tekstit ovat niin suuria, että pienilläkin parannuksilla on käytännöllistä merkitystä. Osoittautui, että yleensä suoraviivaisin menetelmä on nopein; näin erityisesti lyhyillä hahmoilla. Ehdollisia hyppykäskyjä aiheuttavien testien vähentäminen nopeuttaa hakua. Hieman yllättäen tekstistä käsiteltävien merkkien määrän vähentäminen ei läheskään aina tuota nopeampaa algoritmia. Tyypillisesti tämän tyyppinen riippuvuus pätee vain hyvin samanlaisilla algoritmeilla. Mikään merkkijononhakualgoritmi ei ole nopein kaikilla aakkostoilla ja hahmon pituuksilla erilaisilla (tietokone)laitteistoilla.
    Julkaisun otsikon käännösNopeampaa merkkijononhakua
    AlkuperäiskieliEnglanti
    PätevyysTohtorintutkinto
    Myöntävä instituutio
    • Aalto-yliopisto
    Valvoja/neuvonantaja
    • Tarhio, Jorma, Vastuuprofessori
    • Tarhio, Jorma, Ohjaaja
    Kustantaja
    Painoksen ISBN978-952-60-5156-7
    Sähköinen ISBN978-952-60-5157-4
    TilaJulkaistu - 2013
    OKM-julkaisutyyppiG5 Tohtorinväitöskirja (artikkeli)

    Tutkimusalat

    • tarkka merkkijononhaku
    • q-gram
    • bittirinnakkaisuus
    • BNDM
    • Horspoolin algoritmi

    Sormenjälki

    Sukella tutkimusaiheisiin 'Nopeampaa merkkijononhakua'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

    Siteeraa tätä