A faster quick search algorithm (Q1736618)

Summary: We present the FQS (faster quick search) algorithm, an improved variation of the quick search algorithm. The quick search (QS) exact pattern matching algorithm and its variants are among the fastest practical matching algorithms today. The FQS algorithm computes a statistically expected shift value, which allows maximal shifts and a smaller number of comparisons between the pattern and the text. Compared to the state-of-the-art QS variants of exact pattern matching algorithms, the proposed FQS algorithm is the fastest when \(| \Sigma| \leq 128\), where \(| \Sigma|\) is the alphabet size. FQS also has a competitive running time when \(|\Sigma| > 128\). Running on three practical text files, \textit{E. coli} (\(|\Sigma| =4\)), Bible (\(|\Sigma| =63\)) and World192 (\(|\Sigma| = 94\)), FQS resulted in the best performance in practice. Our FQS algorithm will have important applications in the domain of genomic database searching, involving DNA or RNA sequence databases with four symbols \(\Sigma = \{A,C,G,T(/U)\}\) or protein databases with \(|\Sigma| = 20\).