We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Probabilistic Model for Performance Analysis of a Heuristic with Multi-byte Suffix Matching.
- Authors
Yoon-Ho Choi
- Abstract
A heuristic with multi-byte suffix matching plays an important role in real pattern matching algorithms. By skipping many characters at a time in the process of comparing a given pattern with the text, the pattern matching algorithm based on a heuristic with multi-byte suffix matching shows a faster average search time than algorithms based on deterministic finite automata. Based on various experimental results and simulations, the previous works show that the pattern matching algorithms with multi-byte suffix matching performs well. However, there have been limited studies on the mathematical model for analyzing the performance in a standard manner. In this paper, we propose a new probabilistic model, which evaluates the performance of a heuristic with multi-byte suffix matching in an average-case search. When the theoretical analysis results and experimental results were compared, the proposed probabilistic model was found to be sufficient for evaluating the performance of a heuristic with suffix matching in the real pattern matching algorithms.
- Subjects
HEURISTIC; HASHING; PROBABILISTIC number theory; COMPUTER systems; MATHEMATICAL models
- Publication
KSII Transactions on Internet & Information Systems, 2013, Vol 7, Issue 4, p711
- ISSN
1976-7277
- Publication type
Article
- DOI
10.3837/tiis.2013.04.006