An algorithm to compute the character access count distribution for pattern matching algorithms
type: Item
instance of: scholarly article
title: An algorithm to compute the character access count distribution for pattern matching algorithms
zbMATH Open document ID: 1461.68270
author: Tobias Marschall
author: Sven Rahmann
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: We propose a framework for the exact probabilistic analysis of window-based pattern matching algorithms, such as Boyer-Moore, Horspool, Backward DAWG Matching, Backward Oracle Matching, and more. In particular, we develop an algorithm that efficiently computes the distribution of a pattern matching algorithm's running time cost (such as the number of text character accesses) for any given pattern in a random text model. Text models range from simple uniform models to higher-order Markov models or hidden Markov models (HMMs). Furthermore, we provide an algorithm to compute the exact distribution of \textit{differences} in running time cost of two pattern matching algorithms. Methodologically, we use extensions of finite automata which we call \textit{deterministic arithmetic automata} (DAAs) and \textit{probabilistic arithmetic automata} (PAAs) [the authors, Lect. Notes Comput. Sci. 5029, 95--106 (2008; Zbl 1143.68440)]. Given an algorithm, a pattern, and a text model, a PAA is constructed from which the sought distributions can be derived using dynamic programming. To our knowledge, this is the first time that substring- or suffix-based pattern matching algorithms are analyzed exactly by computing the whole distribution of running time cost. Experimentally, we compare Horspool's algorithm, Backward DAWG Matching, and Backward Oracle Matching on prototypical patterns of short length and provide statistics on the size of minimal DAAs for these computations.
Mathematics Subject Classification ID: 68W32
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 7042109
zbMATH Keywords: pattern matching
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: finite automaton
zbMATH Keywords: minimization
zbMATH Keywords: deterministic arithmetic automaton
zbMATH Keywords: probabilistic arithmetic automaton
describes a project that uses: Regexpcount
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a4040285
OpenAlex ID: W2105205612
Wikidata QID: Q61704584
cites work: Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics
cites work: Fast Pattern Matching in Strings
cites work: A fast string searching algorithm
cites work: Speeding up two string-matching algorithms
cites work: Q4552402
cites work: Q4534878
cites work: Q3138910
cites work: Average running time of the Boyer-Moore-Horspool algorithm
cites work: Analysis of Boyer-Moore-Horspool string-matching heuristic
cites work: The Boyer-Moore-Horspool heuristic with Markovian input
cites work: Average case analysis of the Boyer‐Moore algorithm
cites work: Motif statistics.
cites work: Q4432973
cites work: Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata
cites work: Multiple pattern matching: a Markov chain approach
cites work: Exact Analysis of Horspool’s and Sunday’s Pattern Matching Algorithms with Probabilistic Arithmetic Automata
cites work: Q4045961
cites work: Re-describing an algorithm by Hopcroft
DBLP publication ID: journals/algorithms/MarschallR11
DOI: 10.3390/A4040285
description: scientific article; zbMATH DE number 7042109