JPS583035A - Tree structure information searching control system - Google Patents

Abstract

PURPOSE:To prevent a page fault, by providing a non-selective register for storing a pointer which has not been selected during the search processing, and searching other output information being adjacent to one extracted output information. CONSTITUTION:A data 4 read out to a data register 3 by an address register from a tree structure storage information storing part 1 is made to branch and is decided by a branching and deciding circuit part 4. In accordance with its decision, a controlling circuit 5 controls multiplexers (MPX)6-9, selects a left or right pointer, and sets it to the register. A left non-selective register 10 and a right non-selective register 11 store a pointer which has not been selected, respectively. In one address in the information storing part 1, an information F containing a key information, a branch information, etc., a left pointer LPT and a right pointer RPT are stored.

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention provides a tree structure information search control method, 4! After extracting the output information of the end node expanded into a tree structure and stored in the storage area, the output information of the adjacent end node can be accessed at high speed. The present invention relates to a tree structure information search control method in which a pointer value related to a path is left and the value is used to search for other output information.

Conventionally, for example, in the case of an English dictionary, a correspondence relationship expanded into a tree structure is stored in an information storage unit, where output information is associated with a column of key information on multiple sides. , the information storage section is accessed based on the nine search code strings input during the search, and output information is extracted while comparing the key information with the bood on the search code string. ing.

In such a tree structure search processing device, for example, at the stage of extracting the output information corresponding to the end node N5 on the tree structure as shown in FIG.
There may be a case where it is desired to extract output information corresponding to the terminal node N4 or Nak in contact with @.

Conventionally, methods for effectively performing access in such cases include (1) a method using an inverse pointer, which will be described later with reference to FIG. 1, and (If) a method using a horizontal pointer, which will be described later with reference to FIG. (1) A method using a stack described later with reference to FIG. 3, ←) A method using the above first method.
A method is known in which the pointer is turned in the opposite direction during the process of searching for the end node shown in the figure, for example N5, and this is utilized.

However, each of these methods has its own drawbacks.

I will briefly discuss this point below.

(1) Method (1) above.

In general, Km that stores a tree structure is nodes AO, A1, . ......N12 is set to create pointers pO, νl... in the direction from the root of the tree to the end, and when searching for the end node, for example N5, the key corresponding to each node is Pointer 9 while looking up information
0. pL pL ts to reach node N5. In the method of Kyōdai (1).

After reaching the terminal node N5, it becomes adjacent. terminal node N
4 and N6 efficiently, the above pointer νO,j11. . . . A corresponding backward pointer pOnijil; . . . is added to the tree structure. When searching for the terminal node N6 from the terminal node N5, the pointer goes from the terminal node N5'' to the reverse pointer t3', and when one node (for example, A6 in the figure) is different.

A pointer pointing downward, not in the backward direction, and pointing to the leftmost point (p4 in the diagram) is checked for absence of elK, and if it exists, it is set to trace to the left, so to speak, from that node (A6 in the diagram). Ru.

In this method, since an inverse pointer is added to the tree structure, the rounding storage capacity for storing the tree structure appears to be large. Because of this, the tree structure is likely to be stored in a plurality of pages Kt, and a so-called page fault is likely to occur during the access process Km during s.

[Seal] Method (1) above.

In this method, as shown in Figure 2, the terminal node N
Place a horizontal pointer (point m> in the diagram) between O, Nl, and so on.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 in the illustration is only in one direction, and if there is a horizontal pointer in both directions, nodes N8 and N
A pointer connecting to O is not necessarily required.

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

[Rin] Method of the above building (-).

Figure 3 (from the root node AO to the terminal node N4 in A)
When searching toward , which pointer selected from the nine nodes passed during that time is stored in KJ[ in the stack STK shown in FIG. 3 ω). Mosquito stack S
The pointer ν1 and the direction of the ml pointer are stored in TK.

Note that, for example, the pointer p0 is the storage address itself where the node A1 pointed to by the insect revo pointer is stored, and the direction "10" indicates the left, the direction "11" indicates the middle, and the direction "01" indicates the right.

In the case shown in FIGS. 3(A) and 3(B), the left direction pointer νO at the node AO in the path to the terminal node N4.
is selected, so this fact is stored on the stack STK9.Next, the right pointer p3 is selected at the node AI, so this fact is stored,9Then, the right pointer t- is selected at the node A2. This information is stored. For example, K, which examines the terminal node N3, is
Using the contents of the stack, the direction in which the pointer exists at the node one level higher is checked and it is directed to node N3. In the case shown.

Node N4. Node A2. Make it face node N3. Note that the information indicated by arrow X in the illustrated stack STK is not necessarily required in the stack.

In the case of this method, the number of page faults mentioned above occurs less frequently (if this is a hardware stack in l#), which has four stacks separate from the tree structure, but As the number of stages in the structure increases, the number of stages required for the stack 87KK increases.

(W) Method number ← above.

In the case of this method, for example, the pointer 90 . 1, 9, K to change the direction of tS to the opposite direction (reverse direction pointer 90-ν1'...
is not used). Then, the pointer whose direction has been changed in the opposite direction is used in the same way as the backward pointer.

In the case of this method, since the above-mentioned reverse direction pointer is not added, the above-mentioned problem of increasing the storage capacity exists and it is dangerous. The present invention has been made in consideration of the above points, and is a tree-structured information search method that solves the above problems. The purpose is to provide a control method. And for that reason9
The tree structure information search control method of the present invention is as follows.

Output information is stored in a tree structure in which key information corresponding to a node and one or more pointers are set, and is based on multiple key codes; The tree structure search processing device extracts the output information while comparing it with the key information set in the tree structure, and includes a tree structure storage information storage section that stores 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 are not selected when ill searches the tree structure storage information storage section.

In order to extract other output information to be extracted, the main structure storage information storage section is accessed based on the contents of the left unselected register and the circled right unselected register. The present invention is characterized in that it performs processing to search for other output information. This will be explained below with reference to the drawings.

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

In the case of the present invention 9 For example, in FIG. 4, the following processing is performed during the search from node AO to terminal node N5. That is, (1) when the left pointer 10 is selected at the node AO, the register R (right unselected register) K is not selected and the right pointer p1B is set.

(2) When right pointer j6 is selected at node Alj, 1 register L (left non-selection register) K is set to the left pointer 141 that was not selected.

(3) At node A4, since the right pointer is selected, 1 register Lm and left pointer p are overwritten.

(4) At node A5, since the right pointer p10 is selected, the register LK shown in FIG. 9 overwrites the left pointer p.

(jl) At node A6, since the left pointer 911 is selected, 1 illustrated register RK right pointer tt
Overwrite S.

In this way, the terminal node N5 is reached at 9 o'clock.

The illustrated register LK is set to pointer status.

In addition, the pointer pls is set in the register RK. In case 11, for example, k which checks node N4 on the left side is based on the content lIC4 of register L (the content is the storage address of the node pointed to by pointer p9), and reaches node N4. It is checked whether there is a point further down to the right from N4, and finally the node N4 on the left is reached.

By doing this, there is no problem with increasing the storage capacity for storing the tree structure, and for example, if you want to check the left and right neighbors, you need about 2 registers. It's a shame. Of course, by preparing two registers as register L and two registers as register R, the left neighbor, its left neighbor,
Adjacent to the right.

It also becomes easy to examine each terminal node of its right neighbor.

In this case, Kd, for example, the register L shown in FIG. 4 is used as the register L1, and a register L2 is prepared to which the original contents of the #register L1 are transferred.

All you have to do is move it to Star L2.

FIG. 5 shows the configuration of an embodiment of the present invention. Reference numeral 1 in the figure indicates a tree structure storage information storage unit, a 2-digit address register, and 3
is a data register, 4 is a branch decision circuit, 5 is a control circuit that controls the multiplexer (MPX), and 6 to 9 are respectively! Multiplexer, 10 is a left non-selection register, which corresponds to "register L" shown in FIG. 4; 11 is a right non-selection register, which is "register L" shown in FIG.
The registers RJK and 12 and 13 respectively represent gates.

Information F including ship information, etc., a left pointer LPT, and a right pointer RPT are stored. The search process leading to the terminal node N5 will be described below.

(6) First, address register 2 is set to address AO of the wooden machine. As a result, the information storage section l
The contents of address AO within are read to data register 3.

(7) The branch determination circuit unit 4Fi compares the key information of the read information FO with the upper part of the search code string.

In this case, the control circuit unit 5 automatically outputs the information FO.
The left pointer 10 is selected at the multiplexer 6 and the right pointer ν13 is selected at the multiplexer 7 from the branch information inside.

(8) And in this case, since we are in search mode,
The left pointer yoFi is set in the register 2 via the multiplexer 8. On the other hand, since the left pointer has been selected, the gate 13 is turned on to set the register llk right pointer P13.

(.) 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 and the portion compared at the next higher node of the search code string (the portion to be compared first).

In this case as well, there is a coincidence, and based on the branch information in the information Fl the multiplexer 6 is directed to select the right pointer P6 and the multiplexer 7 is directed to select the left pointer t1. And the right pointer? - is set in register 2 via multiplexer 8, and left pointer 21 is set to 12
Register IOK is set via .

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

(b) Since there is a match at this time as well, the right pointer g7 is set to address register 2 based on the branch information in information F4, and the left pointer g7 is set to register IO.
K overwritten.

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

Q4 Since there is a match at this time as well, the right pointer p1G is set in address register 2 based on the branch information in information F5, and the left pointer P9 is set in register I.
OK Overwritten.

Next, the contents of address A6 of the information storage section 1 can be read out.

(b) Since there is a match at this time, the left pointer pim is set in address register 2 based on the branch information in information F6, and the right pointer tl! is overwritten on register 11.

Qf) Then enters the 9th exit information extraction mode and addresses N5.
The content DNS is read out as the output information. However, this mode is omitted from the top of FIG. At this time, pointer ν・ remains on register 10, and pointer t1! remains on register 11. remains.

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

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

[Brief explanation of drawings]

Figures 1 to 3 are explanatory diagrams explaining the prerequisite problems of the present invention, Figure 4 is an explanatory diagram explaining the concept of a control system of an embodiment of the present invention, and Figure 5 is a simplified embodiment configuration 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, and 5 is a tree-structured information storage section.
is the control circuit section, and 6 to 9 are! In the multiplexer, 10 represents a left non-selection register, and 11 represents a right non-selection register. Patent Applicant: Fujitsu Ltd. Representative Patent Attorney Mori 1) Hiro-JR2 Yamisu 3 Diagram (B)

Claims (1)

[Claims] Output information can be stored in a tree structure in which key information and one or more pointers are set corresponding to nodes, and each code of a code string based on multiple key codes is set corresponding to the above node. The tree structure search processing device extracts the output information while comparing the output information with the key information stored in the tree structure. The left non-select register and /l or right non-select register that stores the pointer that was not selected during the process of searching the stored information storage section are received, and the other output is ie* to the extracted one output information. When extracting information, the tree structure storage information storage section is accessed based on the contents of the left non-selection register and /l or the right non-selection register to search for other output information. A tree-structured information search control method characterized by K.