Towards Faster String Matching

Thumbnail Image

Files

isbn9789526051574.pdf (913.05 KB)
Errata_of_publications_P1_P2_P3_P4_P5_P6.pdf (152.18 KB)
publication1.pdf (80.29 KB)
publication5.pdf (357.44 KB)
publication6.pdf (142.53 KB)

URL

Journal Title

Journal ISSN

Volume Title

School of Science | Doctoral thesis (article-based) | Defence date: 2013-05-10
Checking the digitized thesis and permission for publishing
Instructions for the author
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2013

Department

Tietotekniikan laitos
Department of Computer Science and Engineering

Major/Subject

Mcode

Degree programme

Language

en

Pages

132 + app. 88

Series

Aalto University publication series DOCTORAL DISSERTATIONS, 78/2013

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.

Description

Supervising professor

Tarhio, Jorma, Prof., Aalto University, Department of Computer Science and Engineering, Finland

Thesis advisor

Tarhio, Jorma, Prof., Aalto University, Department of Computer Science and Engineering, Finland

Keywords

exact string matching, q-gram, bit-parallelism, BNDM, Horspool's algorithm, tarkka merkkijononhaku, q-gram, bittirinnakkaisuus, BNDM, Horspoolin algoritmi

Other note

Parts

  • [Publication 1]: Jorma Tarhio and Hannu Peltola: String matching in the DNA alphabet. Software: Practice and Experience, 27(7):851–861, 1997. doi:10.1002/(SICI)1097-024X(199707)27:7<851::AID-SPE108>3.3.CO;2-4
  • [Publication 2]: Hannu Peltola and Jorma Tarhio: Alternative algorithms for bitparallel string matching. In Proceedings of the 10th International Symposium on Information Processing and Information Retrieval, SPIRE’03, Lecture Notes in Computer Science 2857:80–93, 2003. doi: 10.1007/978-3-540-39984-1_7
  • [Publication 3]: Hannu Peltola and Jorma Tarhio: On string matching in chunked texts. In Proceedings of the Conference on Implementation and Application of Automata, CIAA’07, Lecture Notes in Computer Science 4783:157–167, 2007. doi:10.1007/978-3-540-76336-9_16
  • [Publication 4]: Petri Kalsi, Hannu Peltola, and Jorma Tarhio: Comparison of exact string matching algorithms for biological sequences. In Proceeding of the 2nd International Conference on Bioinformatics Research and Development, BIRD 2008, Communications in Computer and Information Science 13:417–426. Springer-Verlag, Berlin, 2008. doi: 10.1007/978-3-540-70600-7_31
  • [Publication 5]: Branislav Ďurian, Jan Holub, Hannu Peltola, Jorma Tarhio: Tuning BNDM with q-Grams. In Proceedings of ALENEX09, the Tenth Workshop on Algorithm Engineering and Experiments: 29–37, 2009. ISBN: 978-0-898719-30-7. doi:10.1137/1.9781611972894.3
  • [Publication 6]: Branislav Ďurian, Jan Holub, Hannu Peltola, Jorma Tarhio: Improving practical exact string matching. Information Processing Letters, 110(4):148–152, 2010. doi:10.1016/j.ipl.2009.11.010
  • [Publication 7]: Branislav Ďurian, Hannu Peltola, Leena Salmela, Jorma Tarhio: Bit-parallel search algorithms for long patterns. In Proceedings of the 9th International Symposium on Experimental Algorithms, SEA 2010, Lecture Notes in Computer Science 6049: 129–140, 2010. doi: 10.1007/978-3-642-13193-6_12

Citation

Permanent link to this item

https://urn.fi/URN:ISBN:978-952-60-5157-4

Collections

[diss] Perustieteiden korkeakoulu / SCI