Practical Methods for Approximate String Matching

Abstract

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.

Given a pattern string and a text, the task of approximate string matching is to find all locations in the text that are similar to the pattern. This type of search may be done for example in applications of spelling error correction or bioinformatics. Typically edit distance is used as the measure of similarity (or distance) between two strings. In this thesis we concentrate on unit-cost edit distance that defines the distance beween two strings as the minimum number of edit operations that are needed in transforming one of the strings into the other. More specifically, we discuss the Levenshtein and the Damerau edit distances.

Aproximate string matching algorithms can be divided into off-line and on-line algorithms depending on whether they may or may not, respectively, preprocess the text. In this thesis we propose practical algorithms for both types of approximate string matching as well as for computing edit distance.

Our main contributions are a new variant of the bit-parallel approximate string matching algorithm of Myers, a method that makes it easy to modify many existing Levenshtein edit distance algorithms into using the Damerau edit distance, a bit-parallel algorithm for computing edit distance, a more error tolerant version of the ABNDM algorithm, a two-phase filtering scheme, a tuned indexed approximate string matching method for genome searching, and an improved and extended version of the hybrid index of Navarro and Baeza-Yates.

To evaluate their practicality, we compare most of the proposed methods with previously existing algorithms. The test results support the claim of the title of this thesis that our proposed algorithms work well in practice.