JPS6326411B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention provides a tree structure information search control method, in particular, after extracting output information of a terminal node expanded and stored in a tree structure, output information of adjacent terminal nodes is extracted at high speed. This relates to a tree-structured information search control method in which a pointer value related to a path that was not selected at least at the closest point in time is left in order to be accessible, and the pointer value is used to search for other output information. be.

Conventionally, for example, in the case of an English dictionary, a correspondence relationship developed in a tree structure is stored in an information storage unit, in which output information is associated with a plurality of columns of key information. The information storage section is accessed based on a search code string input during a search, and output information is extracted while comparing the key information with the code on the search code string.

In such a tree structure search processing device, for example, at the stage of extracting output information corresponding to the end node N5 on the tree structure shown in FIG. There may be cases where you want to extract the output information that is displayed.

Conventionally, methods for effectively performing access in such cases include (i) a method using a reverse pointer, which will be described later with reference to FIG. 1, and (ii) a method using a horizontal pointer, which will be described later with reference to FIG. (iii)
There are two methods: a method using a stack, which will be described later with reference to FIG. Are known.

However, each of these methods has its own drawbacks. I will briefly discuss this point below.

[] Method (i) above Generally, when storing a tree structure, pointers p ₀ , p ₁ . . . are moved from the nodes A0, A1, . When searching for the end node, for example N5, select the pointers p ₀ , p ₁ , p ₂ , p ₃ while checking the key information corresponding to each node and search for the node N5.
reach. In the method (i), in order to efficiently check the adjacent terminal nodes N4 and N6 after reaching the terminal node N5, the inverse operation is performed corresponding to the pointers p ₀ , p ₁ , . . . direction pointer
Add p ₀ ′, p ₁ ′, ... to the tree structure. Then, from the terminal node N5 to the terminal node N6
When searching, use the reverse pointer from the end node N5.
p ₃ '..., and when one node (for example, A6 in the figure) is reached, the pointer that is pointing downward, not in the direction of going back, and pointing to the leftmost side (p ₄ in the figure) The presence or absence of the node is checked, and if the node exists, the path is traced to the left from that node (A6 in the figure).

In this method, since a reverse pointer is added to the tree structure, the storage capacity for storing the tree structure is large. Moreover, for this reason, the tree structure is likely to be stored across a plurality of pages, and a so-called page fault is likely to occur during actual access processing.

[] Method (ii) above In this method, as shown in FIG. 2, a horizontal pointer (indicated by a dotted line in the figure) is placed between the end nodes N0, N1, . . . . and,
Now, when one terminal node N5 has been reached and it is desired to examine the adjacent node N4, the node N4 can be accessed immediately based on the contents of the horizontal pointer. Of course, the horizontal pointer shown in the figure may be in only one direction, and if there is a pointer in both directions, a pointer connecting nodes N8 and N0 is not necessarily required.

In this method as well, a horizontal pointer is added to the tree structure, leading to an increase in storage capacity and an increase in the frequency of page fault occurrence.

[] Method (iii) above.

When searching from the root node A0 to the end node N4 in FIG. 3A, which pointers from the nodes passed during the search are selected are stored in order in the stack STK shown in FIG. 3B. I will do it. A pointer pi and the direction of the pointer are stored in the stack STK. For example, the pointer _p0 is the storage address itself where the node A1 pointed to by the pointer is stored, and the direction "10" indicates left, the direction "11" indicates middle, and the direction "01" indicates right. ing.

In the case shown in FIGS. 3A and 3B, in the process of reaching the end node N4, the left direction pointer p ₀ was selected at the node A0, so this fact is not displayed in the stack.
STK, then at node A1 we store this because right pointer p ₃ was selected, then at node A2 we store right pointer p ₆
This information is stored because it was selected. For example, to check the end node N3, the contents of the stack are used to check the direction of the pointer at the node one level above and direct it to the node N3. In the case shown, node N4, node A
2. Make it face node N3. Note that the information indicated by the arrow x in the illustrated stack STK is not necessarily required in the stack.

In this method, since the stack is created separately from the tree structure (especially if this is a hardware stack), the frequency of page faults mentioned above occurs less frequently, but the number of stages in the tree structure is large. As the number of stages increases, the number of stages required for stack STK increases.

[] Method (iv) above.

In the case of this method, for example, the directions of the pointers p ₀ , p ₁ , p ₂ , and p ₃ that have passed during the process of searching for the end node N5 in FIG. 1 are changed to opposite directions. (backward pointer p ₀ ′,
p ₁ ′... is not used). Then, the pointer whose direction has been changed to the opposite direction is used in the same way as the backward pointer.

In the case of this method, since the above-mentioned backward pointer is not added, there is no problem such as the above-mentioned increase in storage capacity. However, as described above, it is necessary to restore the pointer that has been redirected in the opposite direction, and during this process, an undesired page fault may occur.

The present invention has been made in consideration of the above points, and an object of the present invention is to provide a tree structure information search control method that solves the above problems. Therefore, the tree structure information search control method of the present invention is
Output information is stored in a tree structure in which key information corresponding to nodes and one or more pointers are set, and each code of a code string based on multiple key codes is associated with the above node. A tree structure search processing device for extracting the output information while comparing it with the set key information, further comprising a tree structure storage information storage unit storing the key information and the pointer based on the tree structure, and A left non-selection register and/or a right non-selection register are provided to store pointers that were not selected during the process of searching the tree-structured storage information storage section, and other output information adjacent to one extracted output information is provided. When extracting, the tree structure storage information storage section is accessed based on the contents of the left unselected register and/or the right unselected register to search for other output information. It is said that This will be explained below with reference to the drawings.

FIG. 4 is an explanatory diagram illustrating the concept of a control method according to an embodiment of the present invention, and FIG. 5 shows the configuration of an embodiment of the present invention.

In the case of the present invention, for example in FIG. 4, the following processing is performed during the search from node A0 to terminal node N5. That is, (1) When the left pointer p ₀ is selected at node A0, the illustrated register R (right unselected register)
Set the right pointer _p13 that was not selected.

(2) When the right pointer _p6 is selected in node A1, the illustrated register L (left unselected register)
The left pointer _P1 that was not selected is reset.

(3) Since the right pointer _p8 is selected at node A4, the left pointer _p7 is stored in the illustrated register L.
overwrite.

(4) Since the right pointer _p10 is selected at node A5, the left pointer is stored in the illustrated register L.
Overwrite p ₉ .

(5) Since the left pointer _p11 is selected at node A6, the right pointer is stored in the illustrated register R.
Overwrite p ₁₂ .

In this way, when the end node N5 is reached, the pointer _p9 is set in the register L shown, and the pointer _p12 is set in the register R. In this state, for example, to check the left neighbor node N4, register L
Based on the content of (the content is the storage address of the node pointed to by pointer _p9 ), it is checked whether there is a point that reaches node N4 and further descends to the right from node N4, and finally It reaches the node N4 on the left.

By doing this, there is no problem with increasing the storage capacity for storing the tree structure, and if you need, for example, to check the left and right adjacent items, you only need to prepare about two registers. Enough. Of course, by preparing two registers as register L and two registers as register R, it is also easy to check the left neighbor, its left neighbor, right neighbor, and each end node of its right neighbor. becomes. In this case, for example, the register L shown in FIG. 4 itself is set as register L1, a register L2 is prepared to which the original contents of register L1 are transferred, and the contents of register L1 are as explained in relation to FIG. 4. When the register L1 is updated, the contents stored in the register L1 may be moved to the register L2.

FIG. 5 shows the configuration of an embodiment of the present invention. In the figure, numeral 1 is a tree-structured information storage section, 2 is an address register, 3 is a data register, 4 is a branch judgment circuit section, 5 is a control circuit section that controls the multiplexer (MPX), 6 9 to 9 are multiplexers, 10 is a left non-selection register, which corresponds to "register L" shown in FIG. 4, and 11 is a right non-selection register, which corresponds to "register R" shown in FIG. 4. thing,
12 and 13 represent gates, respectively.

At one address in the information storage section 1, information F including key information branch information, etc., a left pointer LPT, and a right pointer RPT are stored. below,
The search process leading to the terminal node N5 will be explained.

(6) First, address register 2 is set to address A0 of the root of the tree. As a result, the contents of address A0 in information storage section 1 are read to data register 3.

(7) The branch determination circuit 4 compares the key information of the read information F0 with the upper part of the search code string. In this case, they match, and the control circuit unit 5 determines the left pointer from the branch information in the information F0.
p ₀ is selected in multiplexer 6 and the right pointer p ₁₃ is selected in multiplexer 7.

(8) Since the present case is the search mode, the left pointer _p0 is set in register 2 via multiplexer 8. On the other hand, since the left pointer has been selected, the gate 13 is turned on and the right pointer _p13 is set in the register 11.

(9) Next, the contents of address A1 of the information storage section 1 are read out.

(10) At this time, the branch determination circuit 4 compares the read key information with the portion to be compared next to the portion compared at the next higher node in the search code string. In this case as well, there is a coincidence, and on the basis of the branch information in the information F1 the multiplexer 6 is caused to select the right pointer p ₆ and the multiplexer 7 is caused to select the left pointer p ₁ . The right pointer p ₆ is then set in register 2 via multiplexer 8, and the left pointer p ₁ is set in register 10 via gate 12.

(11) Next, the contents of address A4 of the information storage section 1 are read out.

(12) Since there is a match at this time as well, the right pointer p8 is set in address register ₂ based on the branch information in information F4, and the left pointer p8 is set in address register 2.
_p7 is overwritten into register 10.

(13) Next, the contents of address A5 of the information storage section 1 are read out.

(14) Since there is a match in this case as well, information F5
The right pointer p ₁₀ is set in address register 2 based on the branch information therein, and the left pointer p ₉ is overwritten in register 10.

(15) Next, the contents of address A6 of the information storage section 1 are read out.

(16) Since there is a match in this case as well, information F
Based on the branch information in 6, the left pointer _p11 is set in address register 2, and the right pointer _p12 is overwritten onto register 11.

(17) Then, enter the output information extraction mode,
The content DN5 at address N5 is read out as output information. However, this mode is omitted from the top of FIG. At this time, register 10
Pointer _p9 remains on top, and pointer _p12 remains on register 11.

(18) Next, when checking the terminal node N4 on the left, for example, the contents _p9 of the register 10 are set in the address register 2, and the contents of the address N4 of the information storage section 1 are read out.

As explained above, according to the present invention, information regarding adjacent terminal nodes can be held without increasing the storage capacity and by providing a simple register.

[Brief explanation of drawings]

Figures 1 to 3 are explanatory diagrams for explaining the prerequisite problems of the present invention, Figure 4 is an explanatory diagram for explaining the concept of a control method of an embodiment of the present invention, and Figure 5 is an explanatory diagram for explaining the configuration of an embodiment of the present invention. shows. In the figure, 1 is a tree-structured information storage section, 2 is an address register, 3 is a data register, 4 is a branch judgment circuit section, 5 is a control circuit section, 6 to 9 are multiplexers, 10 is a left non-selection register, 11 represents a right non-selection register.

Claims (1)

[Claims] 1 Output information is stored in a tree structure in which key information corresponding to a node and one or more pointers are set, and each code of a code string based on multiple key codes is associated with the above node. A tree structure search processing device for extracting the output information while comparing it with key information set in the tree structure, further comprising a tree structure storage information storage section storing the key information and the pointer based on the tree structure, A left non-selection register and/or a right non-selection register are provided to store pointers that were not selected during the process of searching the tree-structured information storage section, and other output information adjacent to the extracted one output information is provided. In extracting the information, the tree structure storage information storage section is accessed based on the contents of the left non-selection register and/or the right non-selection register to search for the other output information. Features a tree-structured information search control method.