DocumentCode
969850
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.
Issue
1
fYear
1984
Firstpage
116
Lastpage
120
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;
fLanguage
English
Journal_Title
Software Engineering, IEEE Transactions on
Publisher
ieee
ISSN
0098-5589
Type
jour
DOI
10.1109/TSE.1984.5010205
Filename
5010205
Link To Document