Exact Analysis of Pattern Matching Algorithms with Probabilistic Arithmetic Automata

Details Exact Analysis of Pattern Matching Algorithms with Probabilistic Arithmetic Automata Exact Analysis of Pattern Matching Algorithms with Probabilistic Arithmetic Automata

2010-09-30

arxiv.org/abs/1009.6114v1

Computer Science

Data Structures and Algorithms

Scientific paper

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 show how to efficiently obtain the distribution of such an algorithm's running time cost for any given pattern in a random text model, which can be quite general, from simple uniform models to higher-order Markov models or hidden Markov models (HMMs). Furthermore, we provide a technique to compute the exact distribution of \emph{differences} in running time cost of two algorithms. In contrast to previous work, our approach is neither limited to simple text models, nor to asymptotic statements, nor to moment computations such as expectation and variance. Methodically, we use extensions of finite automata which we call deterministic arithmetic automata (DAAs) and probabilistic arithmetic automata (PAAs) [13]. To our knowledge, this is the first time that substring- or suffix-based pattern matching algorithms are analyzed exactly. 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.

Affiliated with

Also associated with

No associations

Rating

Exact Analysis of Pattern Matching Algorithms with Probabilistic Arithmetic Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Exact Analysis of Pattern Matching Algorithms with Probabilistic Arithmetic Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact Analysis of Pattern Matching Algorithms with Probabilistic Arithmetic Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-243166