Improved pattern-scan-order algorithms for string matching

The pattern scan order is a major factor affecting the performance of string matching algorithms. Depending on the pattern scan order, one can reduce the number of comparisons in a window or increase the shift length. Classical algorithms for string matching determine the pattern scan order only usi...

Full description

Saved in:
Bibliographic Details
Published in:Journal of discrete algorithms (Amsterdam, Netherlands) Netherlands), 2018-03, Vol.49, p.27-36
Main Authors: Ryu, Cheol, Park, Kunsoo
Format: Article
Language:English
Subjects:
Asymptotic speed
Pattern scan order
String matching
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The pattern scan order is a major factor affecting the performance of string matching algorithms. Depending on the pattern scan order, one can reduce the number of comparisons in a window or increase the shift length. Classical algorithms for string matching determine the pattern scan order only using the characteristics of a text and a pattern. However, if we additionally use the scan results at the time we determine each scan position of the pattern, we can improve the performance of string matching. In this paper we propose new pattern-scan-order algorithms that maximize shift lengths using scan results. We present the theoretical analysis and experimental results that these algorithms run faster than previous algorithms on average.
ISSN:1570-8667
1570-8675
DOI:10.1016/j.jda.2018.05.002