Searching with Extended Guard and Pivot Loop

Waltteri Pakalen, Jorma Tarhio, Bruce Watson

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

We explore practical optimizations on comparison-based exact string matching algorithms. We present a guard test that compares q-grams between the pattern and the text before entering the match loop, and evaluate experimentally the benefit of optimization of this kind. As a result, the Brute Force algorithm gained most from the guard test, and it became faster than many other algorithms for short patterns. In addition, we present variations of a recent algorithm that uses a special skip loop where a pivot, a selected position of the pattern, is tested at each alignment of the pattern and in case of failure; the pattern is shifted based on the last character of the alignment. The variations include alternatives for the pivot and the shift function. We show the competitiveness of the new algorithm variations by practical experiments.
Original languageEnglish
Title of host publicationProceedings of the Prague Stringology Conference 2021
EditorsJan Holub, Jan Zdarek
PublisherCzech Technical University
Pages90-102
ISBN (Print)978-80-01-06869-4
Publication statusPublished - 2021
MoE publication typeA4 Article in a conference publication
EventPrague Stringology Conference - Prague, Czech Republic
Duration: 30 Aug 202131 Aug 2021
http://www.stringology.org/event/2021/

Conference

ConferencePrague Stringology Conference
Country/TerritoryCzech Republic
CityPrague
Period30/08/202131/08/2021
Internet address

Keywords

  • exact string matching
  • tune-up of algorithms
  • guard test
  • skip loop
  • experimental comparison

Fingerprint

Dive into the research topics of 'Searching with Extended Guard and Pivot Loop'. Together they form a unique fingerprint.

Cite this