Title :
A Method for Improving String Pattern Matching Machines
Author :
Aoe, Junichi ; Yamamoto, Yoneo ; Shimada, Ryosaku
Author_Institution :
Department of Information Science and Systems Engineering, Faculty of Engineering, Tokushima University, Minami-josanjima-cho, Tokushima-shi 770, Japan.
Abstract :
This correspondence describes an efficient string pattern matching machine to locate all occurrences of any of a finite number of keywords and phrases in an arbitrary text string. Some conditions are defined on the states of the machine in order to improve the speed and size of the machine by Aho and Corasick [1]. The pattern matching algorithm is partitioned into various cases by combining these conditions. Finally, the correspondence illustrates the proposed approach by applying it to the analysis of the machines for a simple search.
Keywords :
Algorithm design and analysis; Automata; Data structures; Keyboards; Partitioning algorithms; Pattern analysis; Pattern matching; Pattern recognition; Speech analysis; Speech recognition; Data structure; finite state machine; keywords; matching algorithm; storage requirements; string pattern matching machine;
Journal_Title :
Software Engineering, IEEE Transactions on
DOI :
10.1109/TSE.1984.5010205
