On guards and symbol dependencies in substring search
Timo Raita · Software Practice and Experience · 1999
Several ingenious and theoretically elegant principles for shifting a pattern (relative to text) during a pattern matching process have been devised during the last decade. Somewhat surprisingly, however, the fastest practical implementations do not try to maximize the length of the shift – on the contrary, they strip the components assisting in moving the pattern to a bare minimum. To compensate, at least partly, for the loss thus incurred, the concept of a guard has been introduced, the purpose of which is to detect a possible mismatch at a small computational cost before entering the actual match loop. In this paper, a comprehensive study of the factors having an effect on the selectivity of various guard strategies is given. Our aim is to complement the report of Smith [1] (Softw. Pract. Exper., 24(4), 435–436 (1994)) and show that a fine-grained setting for this experiment is needed in order to detect detailed behaviour of the search process. Copyright © 1999 John Wiley & Sons, Ltd.