Merkkijonohaun tekniikat ja algoritmit luonnollisen tekstin nopeaan hakuun

Abstract

Merkkijonohaut ovat tietojenkäsittelytieteen yksi klassisista aiheista. Merkkijonohakua on tutkittu tietojenkäsittelytieteen alusta lähtien, ja ne ovat perustana hakukoneille, jotka ovat nykyiselle yhteiskunnalle tärkeitä. Merkkijonohaussa teksti on merkkijono, josta hakusanoja etsitään. Tarkastelen luonnollisen kielen merkkijonohakuja, jotka löytävät kaikki hakuosumat tarkalla merkkijonohaulla, eli hakuosumaa ei tule yhdenkään merkin erosta hakusanassa. Työssäni tutkin merkkijonohaun tekniikoita ja esitän nopeimpia hakualgoritmeja, kun tekstin esikäsittely sallitaan ja kun sitä ei sallita. Tutkimukseni jakautuu siis kolmeen osaan: merkkijonohaun tekniikat, nopeimmat hakualgoritmit ilman tekstin esikäsittelyä ja nopeimmat hakualgoritmit tekstin esikäsittelyllä.

Selvitän työssäni merkkijonohaun tekniikoita tarkastelemalla naiivia algoritmia, Boyer-Moore-algoritmia, bittirinnakkaisuutta käyttäviä algoritmeja, suodattavia algoritmeja ja suffiksitaulukon hakualgoritmeja. Otan näistä tarkempaan tarkasteluun naiivin algoritmin ja Boyer-Mooren. Osoitan, miten vertailujärjestyksen muutoksella naiivi algoritmi saadaan varsin tehokkaaksi, ja selitän, miten Boyer-Mooren käänteisestä vertailujärjestyksestä saadaan huonon merkin ja hyvän suffiksin sääntö havaintojen perusteella. Työssäni saan tekniikoiksi vertailujärjestyksen muuttaminen, huonon merkin sääntö, hyvän suffiksin sääntö, hakusanan esikäsittely, parhaan hakualgoritmin valitseminen, suodatus, bittirinnakkaisuus ja suffiksitietorakenne.

Selvitän nopeimmat merkkijonohakualgoritmit kirjallisuudesta. Saan työssäni selville, että EPSMA (Exact Packed String Matching AVX2) ja SSEFA (Streaming SIMD Extensions Filter AVX2) ovat nopeimpia merkkijonohakualgoritmeja, jotka eivät esikäsittele tekstiä mutta voivat esikäsitellä hakusanaa. Yhteistä näissä molemmissa algoritmeissa on se, että ne käyttävät suodatusta ja bittirinnakkaisuutta.

Kun sallitaan tekstin esikäsittely, voidaan käyttää suffiksitietorakennetta, jolla pystyy poistamaan merkkijonohaun aikavaatimuksen riippuvuuden tekstin pituudesta. Valitsen suffiksitietorakenteista suffiksitaulukon, ja esitän kirjallisuudesta useita tapoja hakea merkkijonoja suffiksitaulukolla. Nopeimman merkkijonohaun voi toteuttaa Burrows-Wheeler-muunnoksella, jonka avulla merkkijonohaut onnistuvat hakusanan pituuden suhteen lineaarisessa ajassa.