Pattern matching method for tree structured data

• US 4,794,528 A
• Filed: 02/17/1987
• Issued: 12/27/1988
• Est. Priority Date: 02/21/1986
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Takeuchi, Youichi, Hirose, Tadashi, Nakao, Kazuo, Sakoda, Kousuke
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US07/015,111
• Time in Patent Office: 679 Days
• Field of Search: 364/200, 364/300, 364/900
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 8/3135 Unification or backtracking
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

In order to highly speed up the pattern matching of tree structured data in a logic programming language, the priority order is set when the data owned by the individual nodes of a tree structure are to be transversely sought, and the tree structured data are expressed in a vector type, in which they are arranged in that priority order, so that they are compared consecutively from the head for each element of the vector.

Claims

1. A pattern matching method of tree structured data, comprising the steps of:

converting n-ary tree structured data into a vector expression by arranging, in order of priority of transverse search in a tree structure, cells corresponding to memory elements of a constant length, which are constructed of a positional field for storing positional information on a whole tree structure occupied by each composing said tree structured data and a value field for storing a value of each of said nodes to be processed in a computer system; and

comparing said cells, which are converted into said vector expression, consecutively from a beginning position.

2. A pattern matching method according to claim 1, wherein said positional field information includes parent node flag information indicating whether or not a particular cell has an identical parent node.

3. A pattern matching method according to claim 2, wherein said parent node flag information contains a child node flag information indicating existence of a child node.

4. A pattern matching method according to claim 2, wherein flags under consideration of adjacent cells corresponding to nodes having an identical parent node flag information are set at an identical value and flags under consideration of adjacent cells corresponding to nodes having different parent node flag information are set at different values.

5. A pattern matching method according to claim 4, wherein said parent node flag information is expressed by a 1-bit flag.