The Prague Stringology Club Workshop '96
Kazuaki Ando, Masami Shishibori and Jun-ichi Aoe
An Efficient Multi-Attribute Pattern Matching Machine
| Abstract: |
| We describe an efficient multi-attribute pattern matching machine 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 proposed algorithm, confirming transition is decided by the relationship, whether the input structure includes the rule structure or not. It consists in 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 analysis and the evaluation is supported by the simulation results with rules for the extraction of keywords. |
| Download paper: |  |
 |
| PostScript |