Probabilistic Model for Performance Analysis of a Heuristic with Multi-byte Suffix Matching

• Yoon-Ho Choi,

Vol. 7, No. 4, April 29, 2013
10.3837/tiis.2013.04.006, Download Paper (Free):

• Heuristic matching
• suffix matching
• probabilistic model
• average-case search
• Pattern matching

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.

Statistics

Cite this article