Efficient multi-attribute pattern matching

Abstract

This paper describes an efficient multi-attribute pattern matching machine to locate all occurrences of any of a finite number of a sequence of rule structures in a series of input structures. The matching operation of the proposed machine is similar to the method of Aho-Corasick or the method of retrieval using a trie, however, the proposed machine has the following distinctive features: (1) The proposed machine enables us to match set representations containing multiple attributes; (2) It enables us to match separate components; (3) It enables us to match a rule consisting of an exclusive set. In this paper, their features are described in detail. Moreover, the pattern matching algorithm is evaluated by the theoretical observations and the experimental observations that are supported by the simulation results for a variety of rules for document processing as text proofreading, text reduction, and examining a relation between sentences.

Keywords:

• Information retrieval
• string pattern matching
• multi-attribute pattern matching
• met representation
• separate components
• exclusive set

C. R. Categories General Terms::

• Algorithms
• H.3.3
• Information Search and Retrieval
• 1.2.7.
• Natural Language Processing
• 1.2.8
• Problem Solving
• Control Methods and Search
• F.2.2.
• Nonnumerical Algorithms and Problems