Computer Theory and Application Laboratory

Improved Pattern-Scan-Order Algorithms for String Matching

Improved Pattern-Scan-Order Algorithms for String
Matching

Cheol Ryu and Kunsoo Park


Introduction

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.

 


Download

Greedy Shift [download]

$ ./gs (pattern) (pattern length) (text) (text length)

$ ./gs GCAGAGAG 8 GCATCGCAGAGAGTATACAGTACG 24

High-order Maximal Shift [download]

$ ./hs (pattern) (pattern length) (text) (text length)

$ ./hs GCAGAGAG 8 GCATCGCAGAGAGTATACAGTACG 24

 

Contact us at: rcheol@theory.snu.ac.kr