Fast string matching for multiple searches

摘要

ew present a string matching or pattern matching method which is especially useful when a single block of text must be searched repeatedly for different patterns. The method combines linking the text according to diagrams, searching on the least-frequent diagram, and probing selected characters as a preliminary filter before full pattern comparison. Tests on real alphabetic data show that the number of character comparisons may be decreased by two orders of magnitude compared with Kunth-Morris- Pratt and similar searching, but with an initialization overhead comparable to five to ten conventional Searches.