Towards Faster String Matching

Abstract

Exact string matching is a much studied and popular problem. The task is to find the occurrences of a string pattern in a long text. We introduce several new algorithms for online exact string matching and study their experimental performance and compare them with some earlier algorithms. Moreover, we give examples of anomalies caused by repetitive texts, and present algorithms for that kind of data. Specialized algorithms for long patterns (longer than about 50 characters) are also studied. In addition, we discuss the principles of fair testing of string matching algorithms. Among the designed algorithms there are novel ones and variations of previous algorithms. Most algorithms are based on bit-parallelism, which is one of the most effective techniques adopted increasingly during the last few years. For example classical exact string matching algorithms were significantly slower than the best ones of the new algorithms. Exact string matching is so common task that even a small improvement is useful in practice. It turned out that the uncomplicated algorithms are often the fastest in practice, especially for short patterns. Reducing the number of tests in algorithms often accelerates search. Surprisingly, the number of examined text characters is not always correlated with practical search speed among various exact string matching algorithms. Typically, there is clear dependence on the number of examined text characters and performance only among closely related algorithms. However, no exact string matching algorithm is the best one for all alphabets and pattern lengths on all kinds of computer hardware.

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.