Prague Stringology Conference 2021
Waltteri Pakalén, Jorma Tarhio and Bruce W. Watson
Searching with Extended Guard and Pivot Loop
| 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. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |