Efficient multi-attribute pattern matching using the extended Aho-Corasick method
K. Ando, M. Okada, Masami Shishibori, Jun‐ichi Aoe · 2002
The paper describes an efficient multi attribute pattern matching machine using the extended Aho-Corasick method (A.V. Aho and M.J. Corasick, 1975) to locate all occurrences of any of a finite number of the sequence of rule structures (called matching rules) in a sequence of input structures. The proposed algorithm enables us to match set representations containing multiple attributes. Therefore, in the proposed algorithm, confirming transition is decided by the relationship, whether the input structure includes the rule structure or not. It consists of constructing a finite state pattern matching machine from matching rules and then using the pattern matching machine to process the sequence of input structures in a single pass. Finally, the pattern matching algorithm is evaluated by theoretical evaluations and the experimental evaluations that are supported by the simulation results with rules for the extraction of keywords.