Premium
On guards and symbol dependencies in substring search
Author(s) -
Raita Timo
Publication year - 1999
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/(sici)1097-024x(199909)29:11<931::aid-spe264>3.0.co;2-x
Subject(s) - guard (computer science) , substring , computer science , complement (music) , symbol (formal) , implementation , process (computing) , pattern matching , algorithm , theoretical computer science , artificial intelligence , programming language , data structure , biochemistry , chemistry , complementation , gene , phenotype
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.