Designing optimal- and fast-on-average pattern matching algorithms

DOI10.1016/J.JDA.2016.11.001MaRDI QIDQ511153zbMATHOpenAlexFDO

Authors L. Tichit, Gilles Didier

Publication date 14 February 2017

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.08860

zbMATH Keywords

Markov chainspattern matchingaverage complexity

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Abstract: Given a pattern $w$ and a text $t$, the speed of a pattern matching algorithm over $t$ with regard to $w$, is the ratio of the length of $t$ to the number of text accesses performed to search $w$ into $t$. We first propose a general method for computing the limit of the expected speed of pattern matching algorithms, with regard to $w$, over iid texts. Next, we show how to determine the greatest speed which can be achieved among a large class of algorithms, altogether with an algorithm running this speed. Since the complexity of this determination make it impossible to deal with patterns of length greater than 4, we propose a polynomial heuristic. Finally, our approaches are compared with 9 pre-existing pattern matching algorithms from both a theoretical and a practical point of view, i.e. both in terms of limit expected speed on iid texts, and in terms of observed average speed on real data. In all cases, the pre-existing algorithms are outperformed.

Recommendations

• Optimal pattern matching algorithms
• A simple fast hybrid pattern-matching algorithm
• Simple Optimal String Matching Algorithm
• Combinatorial Pattern Matching
• scientific article; zbMATH DE number 1615293

Cites work

• scientific article; zbMATH DE number 5725179 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 1794216 (Why is no real title available?)
• A fast string searching algorithm
• An algorithm to compute the character access count distribution for pattern matching algorithms
• An analytical comparison of two string searching algorithms
• Analysis of Boyer-Moore-Horspool string-matching heuristic
• Average case analysis of the Boyer‐Moore algorithm
• Average running time of the Boyer-Moore-Horspool algorithm
• Combinatorial Pattern Matching
• Efficient randomized pattern-matching algorithms
• Efficient variants of the backward-oracle-matching algorithm
• Exact analysis of Horspool's and Sunday's pattern matching algorithms with probabilistic arithmetic automata
• Fast Pattern Matching in Strings
• Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics
• String overlaps, pattern matching, and nontransitive games
• The Boyer-Moore-Horspool heuristic with Markovian input
• The Complexity of Pattern Matching for a Random String
• The exact online string matching problem: a review of the most recent results

Cited in

(8)

• Byte-aligned pattern matching in encoded genomic sequences
• Fast Average-Case Pattern Matching on Weighted Sequences
• Optimal pattern matching algorithms
• Fast pattern matching method for a bitstream
• Faster pattern matching with character classes using prime number encoding
• Fast string matching for DNA sequences
• An algorithm to compute the character access count distribution for pattern matching algorithms
• Improved pattern-scan-order algorithms for string matching

This page was built for publication: Designing optimal- and fast-on-average pattern matching algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q511153)