Towards Faster String Matching

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Tarhio, Jorma, Prof., Aalto University, Department of Computer Science and Engineering, Finland
dc.contributor.author Peltola, Hannu
dc.date.accessioned 2013-04-30T09:00:05Z
dc.date.available 2013-04-30T09:00:05Z
dc.date.issued 2013
dc.identifier.isbn 978-952-60-5157-4 (electronic)
dc.identifier.isbn 978-952-60-5156-7 (printed)
dc.identifier.issn 1799-4942 (electronic)
dc.identifier.issn 1799-4934 (printed)
dc.identifier.issn 1799-4934 (ISSN-L)
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/9853
dc.description.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. en
dc.description.abstract 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. fi
dc.format.extent 132 + app. 88
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Aalto University en
dc.publisher Aalto-yliopisto fi
dc.relation.ispartofseries Aalto University publication series DOCTORAL DISSERTATIONS en
dc.relation.ispartofseries 78/2013
dc.relation.haspart [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
dc.relation.haspart [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
dc.relation.haspart [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
dc.relation.haspart [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
dc.relation.haspart [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
dc.relation.haspart [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
dc.relation.haspart [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
dc.subject.other Computer science en
dc.title Towards Faster String Matching en
dc.title Nopeampaa merkkijononhakua fi
dc.type G5 Artikkeliväitöskirja fi
dc.contributor.school Perustieteiden korkeakoulu fi
dc.contributor.school School of Science en
dc.contributor.department Tietotekniikan laitos fi
dc.contributor.department Department of Computer Science and Engineering en
dc.subject.keyword exact string matching en
dc.subject.keyword q-gram en
dc.subject.keyword bit-parallelism en
dc.subject.keyword BNDM en
dc.subject.keyword Horspool's algorithm en
dc.subject.keyword tarkka merkkijononhaku fi
dc.subject.keyword q-gram fi
dc.subject.keyword bittirinnakkaisuus fi
dc.subject.keyword BNDM fi
dc.subject.keyword Horspoolin algoritmi fi
dc.identifier.urn URN:ISBN:978-952-60-5157-4
dc.type.dcmitype text en
dc.type.ontasot Doctoral dissertation (article-based) en
dc.type.ontasot Väitöskirja (artikkeli) fi
dc.contributor.supervisor Tarhio, Jorma, Prof., Aalto University, Department of Computer Science and Engineering, Finland
dc.opn Kärkkäinen, Juha, Dr., University of Helsinki, Finland
dc.rev Faro, Simone, Assistant Prof., Università di Catania, Italy
dc.rev Fredriksson, Kimmo, Ph.D., University of Eastern Finland, Finland
dc.date.defence 2013-05-10


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account