Defining a data structure for pattern matching
View Patent ↗An information processing method for defining a data structure for pattern matching, the method executed by an information processing apparatus, comprises generating, by the apparatus, an ordered tree structure by defining transition edges between nodes using, as transition conditions, respective constraints from one or more constraint patterns each including plural constraints; searching, by the apparatus, for a second substructure similar to a first substructure from a root node by determining a set relation between transition conditions of respective transition edges; and defining, by the apparatus, an additional transition link from a tail node of the second substructure to a child node at a tail end of the first substructure, the additional transition link adding a constraint to be met by an indeterminant identified from the set relation.
1. An information processing method for defining a data structure for pattern matching, the method executed by an information processing apparatus, the method comprising:
generating, by the information processing apparatus, an ordered tree structure by defining transition edges between nodes using, as transition conditions, respective constraints from one or more constraint patterns each including plural constraints;
searching, by the information processing apparatus, for a second substructure of the ordered tree structure similar to a first substructure of the ordered tree structure from a root node by determining a set relation between transition conditions of respective transition edges; and
defining, by the information processing apparatus, an additional transition link from a tail node of the second substructure to a child node at a tail end of the first substructure, the additional transition link adding a constraint to be met by an indeterminant identified from the set relation.
2. The method according to claim 1 , further comprising:
defining, by the information processing apparatus, a reference link from the tail node of the second substructure to a tail node of the first substructure the tail end of which is an end state, the reference link being subject to the constraint to be met by the indeterminant identified from the set relation.
3. The method according to claim 1 , wherein searching for a second substructure similar to a first substructure comprises searching for a node string connected by a transition edge whose transition condition is in an EQUALS, INCLUDED, INCLUDES, or INTERSECTS relation.
4. The method according to claim 1 , wherein when a transition condition from a tail node of the first substructure is in neither INCLUDED nor EQUALS relation with a transition condition from the tail node of the second substructure, the additional transition link is defined.
5. The method according to claim 1 , further comprising:
when a transition condition from a node of the first substructure is in an INCLUDED or INTERSECTS relation with a corresponding transition edge at the second substructure, recording the corresponding transition edge as the indeterminant and a constraint of the transition condition as the constraint to be met by the indeterminant identified from the set relation.
6. The method according to claim 1 , further comprising:
providing, by the information processing apparatus, an automaton configured to match input information with the one or more constraint patterns represented by the defined data structure.
7. The method according to claim 1 , wherein each of the constraints comprising a constraint pattern includes one or more constraint elements for a character string expression, regular expression, or part-of-speech information of a word.
8. The method according to claim 1 , further comprising:
storing the ordered tree structure and additional transition link as the defined data structure for pattern matching in a storage device.