Analysis of Boyer-Moore-Horspool string-matching heuristic

✍ Scribed by Hosam M. Mahmoud; Robert T. Smythe; Mireille Régnier

• Publisher: John Wiley and Sons
• Year: 2000
• Tongue: English
• Weight: 216 KB
• Volume: 10
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199701/03)10:1/2<169::aid-rsa9>3.0.co;2-t

✦ Synopsis

We investigate the probabilistic behavior of a string-matching heuristic used for searching for the occurrences of a pattern in a random text. Our investigation covers the two cases when the pattern itself is fixed or random. Under suitable normalization we show that the total search time is asymptotically normally distributed in the case of fixed pattern, whereas in the case of random pattern the distribution of the search time becomes a mixture of degenerate distributions. An instrumental recurrence equation is obtained by shifting the pattern within the text. To handle the sum of dependent random variables appearing in the recurrence, analytic methods based on the behavior of the shift generating function near its dominant singularity in the complex plane are devised to yield moment calculation and the asymptotic distributions. Adaptation of the standard central limit theorem under mixing conditions complements our analytic toolkit.