JP5220047B2 - Bit string search device, search method and program - Google Patents

Description

The present invention relates to a bit string search technique, and more particularly to a bit string search using a coupled node tree.

In recent years, with the progress of informatization of society, large-scale databases are being used in various places. In order to search for a record from such a large database, it is usual to search for an item in the record associated with the stored address of each record using an index key to find a desired record. A character string in full-text search can also be regarded as a document index key.

Since these index keys are represented by bit strings, it can be said that a database search is reduced to a bit string data search.
As a technique related to bit string search for searching bit string data, there is a search technique using a coupled node tree disclosed in Patent Document 1, Patent Document 2, and Patent Document 3 below.

FIG. 1A is a diagram illustrating a configuration example of a conventional coupled node tree arranged in an array.
Referring to FIG. 1A, a node 101 is arranged in an array element of array number 10 in array 100. The node 101 includes a node type 102, a discrimination bit position 103, and a representative node number 104. The node type 102 is 0, indicating that the node 101 is a branch node. 1 is stored in the discrimination bit position 103. The representative node number 104 stores the array element number 20 of the representative node of the link destination node pair. Hereinafter, for simplification of the notation, the array element number stored in the representative node number may be referred to as a representative node number. Further, the array element number stored in the representative node number may be represented by a code attached to the node or a code attached to the node pair.

  The array element with the array element number 20 stores the node [0] 112 that is the representative node of the node pair 111. Then, node [1] 113 paired with the representative node is stored in the next adjacent array element (array number 20 + 1). 0 is stored in the node type 114 of the node [0] 112, 3 is stored in the discrimination bit position 115, and 30 is stored in the representative node number 116. Further, 1 is stored in the node type 117 of the node [1] 113, indicating that the node [1] 113 is a leaf node. The index key 118 stores “0001”.

A representative node may be represented by a node [0] and a node paired therewith may be represented by a node [1]. In addition, a node stored in an array element having a certain array number may be referred to as a node having the array number, and an array number of the array element in which the node is stored may be referred to as a node array number.
The contents of the node pair 121 composed of the node 122 and the node 123 stored in the array elements of the array element numbers 30 and 31 are omitted.

The 0 or 1 added to the array elements stored in the node [0] 112, the node [1] 113, the node 122, and the node 123 are linked to either node of the node pair when searching with the search key. It shows what to do. The search key bit value 0 or 1 at the discrimination bit position of the preceding branch node is linked to the node of the array element number obtained by adding the representative node number.
Therefore, by adding the bit value of the discrimination bit position of the search key to the representative node number of the preceding branch node, the array element number of the array element storing the link destination node can be obtained.
In the above example, the representative node number is the smaller of the array element numbers where the node pairs are arranged. However, it is obvious that the larger one can be adopted.

FIG. 1B is a diagram conceptually showing a tree structure of a conventional coupled node tree.
Reference numeral 210a indicates the root node of the coupled node tree 200 illustrated in FIG. 1B. In the illustrated example, the root node 210a is a representative node of the node pair 201a arranged at the array element number 220.

  As a tree structure, a note pair 201b is arranged below the root node 210a, a node pair 201c and a node pair 201f are arranged below it, and a node pair 201h and a node pair 201g are arranged below the node pair 201f. A node pair 201d is disposed below the node pair 201c, and a node pair 201e is disposed below the node pair 201d.

  The code of 0 or 1 added before each node is the same as the code assigned before the array element described in FIG. The tree is traversed according to the bit value of the discrimination bit position of the search key, and the leaf node to be searched is found.

In the illustrated example, the node type 260a of the root node 210a is 0, indicating that it is a branch node, and the discrimination bit position 230a indicates 0. The representative node number is 220a, which is the array element number of the array element stored in the representative node 210b of the node pair 201b.
The node pair 201b is composed of nodes 210b and 211b, and the node types 260b and 261b are both 0, indicating that they are branch nodes. 1 is stored in the discrimination bit position 230b of the node 210b, and the array element number 220b of the array element stored in the representative node 210c of the node pair 201c is stored in the link representative node number.

Since 1 is stored in the node type 260c of the node 210c, this node is a leaf node and therefore includes an index key. “000111” is stored in the index key 250c. On the other hand, the node type 261c of the node 211c is 0, the discrimination bit position 231c is 2, and the array element number 221c of the array element stored in the representative node 210d of the node pair 201d is stored in the representative node number.
The node type 260d of the node 210d is 0, the discrimination bit position 230d is 5, and the array number 220d of the array element in which the representative node 210e of the node pair 201e is stored is stored in the representative node number. The node type 261d of the node 211d paired with the node 210d is 1, and “011010” is stored in the index key 251d.
The node types 260e and 261e of the nodes 210e and 211e of the node pair 201e are both 1, indicating that both are leaf nodes. “010010” and “010011” are stored as index keys in the index keys 250e and 251e, respectively. Has been.

2 is stored in the discrimination bit position 231b of the node 211b which is the other node of the node pair 201b, and the array element number 221b of the array element in which the representative node 210f of the node pair 201f is stored is stored in the representative node number of the link destination. Stored.
The node types 260f and 261f of the nodes 210f and 211f of the node pair 201f are both 0, and both are branch nodes. 5 and 3 are stored in the discrimination bit positions 230f and 231f, respectively. The representative node number of the node 210f stores the array element number 220f of the array element in which the representative node 210g of the node pair 201g is stored, and the representative node number of the node 211f contains the node [0] 210h that is the representative node of the node pair 201h. The array element number 221f of the stored array element is stored.
The node types 260g and 261g of the nodes 210g and 211g of the node pair 201g are both 1, indicating that both are leaf nodes, and “100010” and “1000011” are stored in the respective index keys 250g and 251g. .
Similarly, the node type 260h and 261h of the node [0] 210h, which is the representative node of the node pair 201h, and the node [1] 211h that is paired with the node [0] 210h are both 1, indicating that both are leaf nodes. In “250h” and “251h”, “101011” and “101100” are stored.

Next, basic search processing using the above-described coupled node tree will be described. In the following description, although not particularly illustrated, a temporary storage area corresponding to each process is used in order to use various values obtained during the process in a later process. In some cases, data stored in a certain data storage area is described with the data storage area code added, and the name of the data itself may be used as the name of a temporary storage area for storing the data.

FIG. 2 is a diagram illustrating an example of a processing flow of bit string search using a conventional coupled node tree.
First, in step S201, the array element number of the search start node is acquired. The array corresponding to the acquired array element number stores arbitrary nodes constituting a coupled node tree. The search start node may be specified by an input from an operator or by an application program that uses the processing illustrated in FIG.
The obtained array number of the search start node is set in a search start node setting area (not shown). This search start node setting area is used to set various values obtained in the middle of processing as described later. This is one of the “temporary storage areas corresponding to each process for use in the process”. In the following description, instead of the expression “set in a search start node setting area (not shown)”, “get the search start node array number”, “set as search start node” or simply “start search” It may also be described as “set to node”.

Next, in step S202, the array element number acquired in the search path stack is stored, and in step S203, the array element corresponding to the array element number is read as a node to be referred to. In step S204, the node type is extracted from the read node. In step S205, it is determined whether the node type is a branch node.
If it is determined in step S205 that the read node is a branch node, the process proceeds to step S206, and information on the discrimination bit position is extracted from the node. Retrieve from search key. In step S208, the representative node number is extracted from the node. In step S209, the bit value extracted from the search key and the representative node number are added, and the process returns to step S202 as a new array number.

Thereafter, the processing from step S202 to step S209 is repeated until it is determined in step S205 that the node is a leaf node and the process proceeds to step S210. In step S210, the index key is extracted from the leaf node as a search result key, and the process ends.

A process for searching the index key “100010” from the coupled node tree 200 illustrated in FIG. 1B with the root node as a search start node will be briefly described. The discrimination bit positions are 0, 1, 2,... From the most significant bit position.

Since the search start node is the root node, processing is started from the root node 210a using the bit string “100010” as a search key. Since the discrimination bit position 230a of the root node 210a is 0, it is 1 when the bit value of the discrimination bit position of the search key “100010” is 0 is seen. Therefore link 1 to node 211b stored in the array element having the array element number obtained by adding to the SEQ ID NO: 220a stored as node indicator. Because 2 is stored in the discrimination bit position 231b of the node 211b, the search of the discrimination bit position of the key "100010" is 0 Looking at the second bit value, the stored sequence number 221b as node indicator Link to the node 210f stored in the array element.
Since 5 in the discrimination bit position 230f of node 210f is stored, searched because the discrimination bit position of the key "100010" is 0 Looking at bit value of 5, the stored sequence number 220f as node indicator Link to the node 210g stored in the array element.
Since the node type 260g of the node 210g is 1, indicating that it is a leaf node, the index key 250g is read out as a search result key. In this way, a search using a coupled node tree is performed. When the search result key is compared with the search key, both are “100010” and match.

In the example of the flowchart shown in FIG. 2 described above, the search process is completed by extracting the index key from the node as the search result key. However, the search result key and the search key are further determined to match, and if they match, the search is successful. If they do not match, the search can be failed.

  The leaf nodes of the coupled node tree shown in FIGS. 1A and 1B directly include leaf node index keys, and the search process shown in FIG. 2 extracts index keys from the leaf nodes. The configuration of the leaf node and the retrieval of the index key in the search process are the same as those disclosed in Patent Document 1 and Patent Document 2.

On the other hand, a leaf node of the coupled node tree disclosed in Patent Document 3 stores a reference pointer that is a pointer indicating the position of the storage area in which the index key is stored, instead of the index key. The retrieval of the index key in the search process is performed by retrieving the reference pointer from the leaf node and accessing the storage area pointed to by the reference pointer.
Patent Document 4 describes that the nodes of the coupled node tree are sequentially evacuated and saved.

JP 2008-015862 A JP 2008-112240 A JP 2008-269503 A JP 2008-269197 A

The coupled node tree has a feature that the storage capacity for storing the tree is smaller than that of the tree previously used for the search process. However, when the search target data size becomes very large, it is desirable that the tree structure be arranged in a storage unit having a smaller capacity.
Therefore, the problem to be solved by the present invention is to provide a tree structure of a coupled node tree that can be arranged in a storage means having a smaller capacity.

  According to the present invention, each node of the coupled node tree is arranged in an array element of an array corresponding to the position on the tree. The array element number of the array element in which the root node is arranged is 1, and the array element number of the array element in which the representative node of the node pair linked to the branch node is arranged is the array element number of the array element in which the branch node is arranged. It is obtained by doubling. Therefore, the branch node according to the present invention does not need to include the representative node number.

  According to the first aspect of the present invention, the branch node includes the node type and the discrimination bit position, but does not include the representative node number. Further, the leaf node includes a node type and an index key or information for accessing the index key. The information for accessing the index key may be a reference pointer indicating the position of the storage area in which the index key is stored described in Patent Document 3 described above, and is not limited to this, and the index key is stored. It may be an index for obtaining the position of the storage area.

  According to the second aspect of the present invention, a coupled node tree is constructed by inserting a specific bit value “0” or “1” into a specific bit position of an index key to be searched. The search is performed by inserting the same specific bit value “0” or “1” into the same specific bit position as the index key to be searched. The branch node and the leaf node do not include the node type, the branch node includes the discrimination bit position but does not include the representative node number, and the leaf node includes the index key or information for accessing the index key.

  Then, when the maximum number of stages of the coupled node tree is N, the leaf node exists only in the Nth stage, and the tree is configured so that only the leaf node exists in the Nth stage. Can be determined. Therefore, the search process is performed by repeating the link operation from the root node to the N-th node as the final stage.

  According to the present invention, since the branch node does not include at least the representative node number for identifying the link destination, the size of the node can be reduced. For example, if the number of index keys is 16, the number of bits for expressing an index key that defines the size of a leaf node is four. On the other hand, the number of bits necessary for the discrimination bit position that defines the size of the conventional branch node is 2, and the number of bits necessary for the representative node number is 1 + 1 + 2 + 4 + 8 = 16, which is the number of node pairs as link destinations including the root node. Since it is 4, the total number of required bits is 6.

  Therefore, the conventional branch node requires a larger storage capacity than the leaf node. This difference in storage capacity further increases as the number of index keys increases. However, according to the present invention, since the storage area for storing the representative node number is not necessary, the size of the array for arranging the coupled node tree can be reduced.

  Furthermore, according to the second embodiment of the present invention, in addition to reducing the size of the array in which the coupled node tree is arranged, the branch operation by the determination of the node type in the search process is deleted, so the processing speed Can be improved.

It is a figure explaining the structural example of the conventional coupled node tree arrange | positioned at the arrangement | sequence. It is a figure which shows notionally the tree structure of the conventional coupled node tree. It is a figure explaining the example of a processing flow of the bit string search using the conventional coupled node tree. It is a figure explaining the hardware structural example for implementing this invention. It is a figure explaining the structural example of the coupled node tree arrange | positioned at the arrangement | sequence in the 1st Embodiment of this invention. It is a figure which shows notionally the tree structure of the coupled node tree which concerns on the 1st Embodiment of this invention. It is a figure explaining the functional block structural example of the bit string search device in the 1st Embodiment of this invention. It is a figure explaining the example of a processing flow of the bit string search in the 1st Embodiment of this invention. It is a figure which shows the example of a search using the coupled node tree in the 1st Embodiment of this invention. It is a figure explaining the structural example of the coupled node tree arrange | positioned at the arrangement | sequence in the 2nd Embodiment of this invention. It is a figure which shows notionally the tree structure of the coupled node tree which concerns on the 2nd Embodiment of this invention. It is a figure explaining the example of a functional block structure of the bit string search device in the 2nd Embodiment of this invention. It is a figure explaining the example of a processing flow of the bit string search in the 2nd Embodiment of this invention. It is a figure explaining the example of a processing flow which calculates | requires the array element number of the link destination in the 2nd Embodiment of this invention. It is a figure which shows the example of a search using the coupled node tree in the 2nd Embodiment of this invention. It is a figure explaining the structural example of the coupled node tree arrange | positioned at the arrangement | sequence in the modification of the 1st Embodiment of this invention. It is a figure explaining the example of a processing flow of the bit string search in the modification of the 1st Embodiment of this invention. It is a figure explaining the structural example of the coupled node tree arrange | positioned at the arrangement | sequence in the modification of the 2nd Embodiment of this invention. It is a figure explaining the example of a processing flow of the bit string search in the modification of the 2nd Embodiment of this invention. It is a figure explaining the example of a processing flow which calculates | requires the array number of a link destination. It is a figure explaining the example of a processing flow of the front | former stage of the process which produces | generates the pointerless tree in the 1st and 2nd embodiment of this invention. It is a figure explaining the example of a processing flow of the back | latter stage of the process which produces | generates the pointerless tree in the 1st and 2nd embodiment of this invention. It is a figure explaining the example of a processing flow which circulates a tree from a circulation start node, and stores a node in a pointerless tree. It is a figure explaining the example of a processing flow of the process which produces | generates the node in the 1st Embodiment of this invention. It is a figure explaining the example of a processing flow of the process which produces | generates the node in the 2nd Embodiment of this invention. It is a figure explaining the example of a processing flow which calculates | requires the maximum stage number of the tree before conversion. It is a figure which shows the example of a processing flow which circulates a tree from the circulation start node, counts the number of node stages, and obtains the maximum number of visited nodes.

FIG. 3 is a diagram for explaining a hardware configuration example for carrying out the present invention. The search processing by the search device of the present invention can be performed using the data storage device 308 by the data processing device 301 including at least the central processing unit 302 and the cache memory 303. A data storage device 308 having a search path stack 310 for storing an array 309 in which a coupled node tree is arranged and an array element number in which a node to be traced is stored is a main storage device 305 or an external storage device 306. It is also possible to use a device that can be implemented or that is located remotely connected via the communication device 307.
When storing information for accessing the index key instead of the index key in the leaf node, the data storage device is provided with a storage area for storing the index key.

In the example of FIG. 3, the main storage device 305, the external storage device 306, and the communication device 307 are connected to the data processing device 301 by a single bus 304, but the connection method is not limited to this. Further, the main storage device 305 can be in the data processing device 301, and the search path stack 310 can be realized as hardware in the central processing unit 302. Alternatively, the array 309 has an external storage device 306, a search path stack 310 in the main storage device 305, etc. It is clear that the hardware configuration can be appropriately selected according to the usable hardware environment, the size of the index key set, etc. It is.
Further, although not particularly illustrated, it is natural that a temporary storage device corresponding to each process is used in order to use various values obtained during the process in a later process.

Next, a first embodiment of the present invention will be described with reference to FIGS. 4A to 7.
FIG. 4A is a diagram illustrating a configuration example of a coupled node tree arranged in an array according to the first embodiment of this invention. Compared to the configuration example shown in FIG. 1A, there is no area for storing the representative node number from the branch node. Moreover, the sequence number from 1 to 15 is described.

  Referring to FIG. 4A, the root node 401 is arranged in the array element of array number 1 in the array 400. The root node 401 includes a node type 402 and a discrimination bit position 403. The node type 402 is 0, indicating that the root node 401 is a branch node. 1 is stored in the discrimination bit position 403.

  The node [0] 412 that is the representative node of the link destination node pair 411 indicated by the dotted-line arrow 410 from the root node 401 whose array element number is 1 is the root node 401 that is the parent node positioned immediately above the tree. It is arranged in the array element of array number 2 having a value twice that of array number 1. A node [1] 413 that is paired with the representative node is arranged in the next adjacent array element (array number 3). The node type of the node [0] 412 stores 1, indicating that the node [0] 412 is a leaf node. The index key 418 stores “0001”. On the other hand, 0 is stored in the node type of the node [1] 413, which indicates that the node [1] 413 is a branch node. 3 is stored in the discrimination bit position of the branch node 413.

  The node 422, which is the representative node of the link destination node pair 421 indicated by the dotted arrow 420 from the branch node 413 having the array element number 3, has an array number having a value twice that of the array element 3 of the node 413 that is the parent node. 6 array elements. A node 423 that is paired with the representative node is arranged at the next adjacent array element (array number 7). The node type of the node 422 stores 0, indicating that the node 422 is a branch node. 4 is stored in the discrimination bit position of the branch node 422. Also, 0 is stored in the node type of the node 423, indicating that the node 423 is a branch node. 5 is stored in the discrimination bit position of the branch node 422.

In addition, no node is arranged in the array elements of array element number 4 and array element number 5.
As is clear from the above example, the array element number of the representative node of the link destination node pair is twice the array element number of the parent node.

Therefore, the node 432 that is the representative node of the link destination node pair 431 indicated by the dotted arrow 430 from the branch node 422 whose array number is 6 is arranged in the array element whose array number is 12. A node 433 that is paired with the representative node is arranged in the next adjacent array element (array number 13). Description of the contents of the node 432 and the node 433 is omitted.

Similarly, the node 442 that is the representative node of the link destination node pair 441 indicated by the dotted arrow 440 from the branch node 423 with the array element number 7 is arranged in the array element with the array element number 14. A node 443 that is paired with the representative node is arranged at the next adjacent array element (array number 15). Description of the contents of the nodes 442 and 443 is omitted.
Further, no nodes are arranged in the array elements of array number 8 to array number 11.

FIG. 4B is a diagram conceptually showing a tree structure of a coupled node tree in the first exemplary embodiment of the present invention. Compared to the tree structure of the coupled node tree 200 shown in FIG. 1B, the leaf node of the coupled node tree 200a shown in FIG. 4B is the same, and the value of the discrimination bit position of the branch node is also the same as that shown in FIG. 1B. Therefore, the branch pattern of the tree itself is the same. However, the branch node does not include the representative node number that is the array element number of the representative node of the link destination node pair. Since the representative node number is obtained by doubling the array number of the branch node, the connection to the link destination by the representative node number is represented by a dotted arrow with a symbol of the representative node number. Further, the array element number of the array element in which each node is arranged is displayed in the vicinity of the code indicating each node as [1] with respect to the root node 210a. Except for the representation of the representative node number and the array number, the description is the same as that described in FIG.

FIG. 5 is a diagram illustrating a functional block configuration example of the bit string search device according to the first embodiment of the present invention.
The bit string search device 500 according to this embodiment illustrated in FIG. 5 includes a search tree storage unit 510, a search start position setting unit 520, a node reading unit 530, a node type determination unit 540, a search key setting unit 550, and a node link unit 560. And a search result output means 570.

  An array is secured in the storage area of the search tree storage means 510, and a coupled node tree is arranged in the array. In the search start position setting means 520, the array element number of the search start node is set. When the root node is the search start node, 1 is set as the array element number. The search start position can be set by a user who uses the result of the search process.

The node reading unit 530 reads the search start node having the array element number set in the search start position setting unit 520 or the link destination node having the array element number set by the node link unit 560. The node type identification unit 540 determines the type of the node read by the node reading unit 530, and if it is a leaf node, passes the leaf node to the search result output unit 570. Pass to means 560.

  A search key is set in the search key setting means 550. The search key can be set by a user who uses the result of the search process. The node link means 560 has the bit value of the search key set in the search key setting means 550 at the branch bit discrimination bit position passed from the node type determination means 540 and the array element where the branch node is arranged. A value obtained by adding the value obtained by doubling the array number is set as the array number of the array element in which the node to be read next is arranged.

The search result output unit 570 takes out the index key or information for accessing the index key from the leaf node passed from the node type determination unit 540. When what is extracted from the leaf node is an index key, the index key is output as a search result key. When the information extracted from the leaf node is information for accessing the index key, the index key is read out and output as a search result key based on the information for accessing the extracted index key.
It is also possible to compare the search result key with the search key, and output a search result indicating that the search is successful if they match, and that the search fails if they do not match.
The functional block configuration described with reference to FIG. 5 is merely an example, and it is obvious that various modifications are possible.

Hereinafter, the search processing according to the first embodiment of the present invention will be described with reference to FIG. FIG. 6 is a diagram illustrating an example of a processing flow of bit string search in the first embodiment of the present invention.

  First, in step S601, 1 is set to the link destination array number. The link destination array number here is an example of the temporary storage area (not shown) described above. In the link destination array number, an array number of the search start node and an array number of the representative node of the link destination node pair are set. In the example shown in FIG. 6, the search start node is the root node. Even when the search start node is other than the root node, the following processing flow is the same.

  In step S603, the array element having the array element number set as the link destination array element number is read from the array as a node to be referred to. In step S604, the node type is extracted from the read node. In step S605, it is determined whether the node type is a branch node.

If it is determined in step S605 that the read node is a branch node, the process proceeds to step S606, where information about the discrimination bit position is extracted from the node, and in step S607, a bit value corresponding to the extracted discrimination bit position is searched. Take out from the key. In step S608, the array element number set in the link destination array number is doubled and set in the link destination array number. In step S609, the bit value extracted from the search key in step S607 is added to the array number set in the link destination array number in step S608, set as the link destination array number as a new array number, and the process returns to step S603. .

Thereafter, the processing from step S603 to step S609 is repeated until it is determined as a leaf node in the determination in step S605 and the process proceeds to step S610. In step S610, the index key is extracted from the leaf node, and the process ends.
In the above example, it is assumed that the index key is directly included in the leaf node. However, if the leaf node includes information for accessing the index key, the index from the leaf node is determined in step S610. Information for accessing the key is extracted, and in an additional step, the index key is extracted using the information for accessing the extracted index key.
In addition, after the index key is extracted, the index key can be used as a search result key in another application, or a match with the search key can be determined to determine success or failure of the search.

Next, a search example using the coupled node tree according to the first embodiment of the present invention will be described with reference to FIG. FIG. 7 shows only a part necessary for the description in the coupled node tree illustrated in FIG. 4B, and a part lower than the node 211b is omitted.
In the example shown in FIG. 7, a bit string “011010” (hereinafter referred to as the search key 270) is set as a search key in the search key setting area 270, and the search start node is the root node 210a. It also describes that the array number of the link destination is obtained as the sum of the representative node number obtained by doubling the array number of the link source branch node and the bit value of the discrimination bit position of the search key.

Hereinafter, the flow of the search process will be described with reference to FIG.
Since the search start node is the root node, 1 is set in the link destination array number at the start of the search, so the node 210a is read. Since the node type 220a of the node 210a is 0, indicating that it is a branch node, the value 0 is extracted from the discrimination bit position 230a. Since the value of the bit position 0 of the search key 270 is 0, the link destination array number is 2, which is obtained by adding 0 to the representative node number 220a that is twice the array number 1, and is arranged in the array element of the array number 2. Node 210b is then read.

Since the node type 220b of the node 210b is 0, indicating that it is a branch node, its value 1 is extracted from the discrimination bit position 230b. Since the value of the bit position 1 of the search key 270 is 1, the link destination array number is 5 which is obtained by adding 1 to the representative node number 220b obtained by doubling the array number 2, and is arranged in the array element of the array number 5. Node 211c is then read out.

Since the node type 221c of the node 211c is 0, indicating that it is a branch node, its value 2 is extracted from the discrimination bit position 231c. Since the value of the bit position 2 of the search key 270 is 1, the link destination array number is 11, which is obtained by adding 1 to the representative node number 221c obtained by doubling the array number 5, and is arranged in the array element of the array number 11 Node 211d is then read out.

Since the node type 221d of the node 211d is 1, indicating that it is a leaf node, the index key “011010” is extracted from the index key 251d, and the search process ends.

Next, a second embodiment of the present invention will be described with reference to FIGS.
FIG. 8A is a diagram illustrating a configuration example of a coupled node tree arranged in an array according to the second embodiment of the present invention. In the present embodiment, the node type is deleted from the leaf node and the branch node, and the leaf node is arranged only at the bottom level of the tree. Further, the index key and the search key are assumed to have 0 inserted in the most significant bit that is a specific bit position with respect to the original index key and search key. The method of obtaining the linked sequence number is the same as in the first embodiment. The bit value added as the most significant bit can be 1 instead of 0. In short, the same bit value may be added as the most significant bit. Also, a specific bit position into which a specific bit value is inserted is not limited to the most significant bit position, and can be an arbitrary bit position. The bit position into which the same bit value is inserted does not appear in the discrimination bit position of the original branch node of the coupled node tree. Therefore, a leaf node can be arranged only at the bottom of the tree by inserting a dummy branch node by using it as a discrimination bit position of a dummy branch node described later.

Referring to FIG. 8A, a root node 801 is arranged in the array element of array element 1 in array 800. The root node 801 is configured with a discrimination bit position 803. 2 is stored in the discrimination bit position 803.

  The node [0] 812, which is the representative node of the link destination node pair 811 indicated by the dotted-line arrow 810 from the root node 801 having the array element number 1, is the root node 801 that is the parent node positioned immediately above in the tree. It is arranged in the array element of array number 2 having a value twice that of array number 1. A node [1] 813 that is paired with the representative node is arranged in the next adjacent array element (array number 3).

  0 is stored in the discrimination bit position of the node [0] 812, and the link destination is an array of the array number 4 that is twice the array number 2 of the node [0] 812, as indicated by a dotted arrow 840. A node 842 stored in the element. Further, 0 is stored in the discrimination bit position of the node 842, and the link destination is stored in the array element of array number 8 that is twice the array number 4 of node 842, as indicated by the dotted arrow 850. Node 852.

Since the node 852 is located at the bottom of the coupled node tree illustrated in FIG. 8A, the node 852 is a leaf node, and the index key “00001” in which 0 is inserted in the most significant bit is stored in the index key 818. .
In the example shown in FIG. 8A, the index key “00001” is distinguished from the index key already stored in another array element by the bit value 0 in the bit position 2 of the discrimination bit position 803 of the root node 801. Therefore, as in the first embodiment shown in FIG. 4A, the node stored in the array element of the array element number 2 immediately below the root node is the position of the original leaf node. Therefore, dummy branch nodes 812 and 842 whose discrimination bit position is 0 of the most significant bit position are inserted and positioned at the lowest level. Note that the node paired with the dummy branch node 842 in the second stage is an empty node that does not substantially exist so that the array element with the array element number 5 shown in FIG. 8A is empty.

  On the other hand, 4 is stored in the discrimination bit position of the node [1] 813. The node 822 that is the representative node of the link destination node pair 821 indicated by the dotted-line arrow 820 from the branch node 813 whose array number is 3 has an array number that has a value twice that of the array number 3 of the node 813 that is the parent node. 6 array elements. A node 823 that is paired with the representative node is arranged at the next adjacent array element (array number 7). In the discrimination bit position of the node 822, 5 is stored. Further, 6 is stored in the discrimination bit position of the node 823.

A node 832 that is a representative node of the link destination node pair 831 indicated by the dotted arrow 830 from the branch node 822 having the array element number 6 is arranged in the array element having the array element number 12. A node 833 that is paired with the representative node is arranged at the next adjacent array element (array number 13). Description of the contents of the node 832 and the node 833 is omitted. Further, the description of the link destination of the branch node 823 is also omitted.

FIG. 8B is a diagram conceptually showing a tree structure of a coupled node tree in the second exemplary embodiment of the present invention. In the tree structure shown in FIG. 8B, 0 is added to the most significant bit position of each index key stored in the tree structure shown in FIG. 4B, and the bit length is changed from 6 bits to 7 bits. Accordingly, the discrimination bit position of the branch node denoted by the same symbol as that of the branch node shown in FIG. 4B is shifted by one, and the value is increased by one.

Further, since the number of stages in the tree structure shown in FIG. 4B is five, the leaf node is located only in the fifth stage in the tree structure shown in FIG. 8B. Then, the leaf node positioned at a higher level than the fifth stage in the tree structure shown in FIG. 4 B is a discrimination bit position is 0 dummy branch nodes. The dummy branch nodes are inserted until the node immediately below the dummy branch node becomes the fifth-stage node.
The method for calculating the representative node number, which is the array element number of the array element in which the representative node of the nearest lower node pair is arranged, is the same as that of the first embodiment.

  In the example shown in FIG. 4B, since 0 is added as the most significant bit, for example, the original index key “000111” is stored in the leaf node 210j, but when 1 is added as the most significant bit, the leaf It is clear that the data is stored in the node 211j.

FIG. 9 is a diagram illustrating a functional block configuration example of the bit string search device according to the second embodiment of the present invention.
The bit string search device 900 according to this embodiment illustrated in FIG. 9 includes a search tree storage unit 910, a search start position setting unit 920, node reading units 9301 to 930n, a search key setting unit 950, and node link units 9601 to 960n-1. And search result output means 970. Here, n is the number of stages in the coupled node tree.

  Similar to the first embodiment described above, an array is secured in the storage area of the search tree storage unit 910, and the coupled node tree according to the second embodiment of the present invention is arranged in the array. In the search start position setting unit 920, 1 that is the array element number of the root node is set as the array element number of the search start node.

Node reading means 9301 reads the root node of array number 1 set in the search start position setting means.
A search key is set in the search key setting means 950. The search key can be set by a user who uses the result of the search process. The node link means 9601 is a value obtained by doubling the value of the search key bit set in the search key setting means 950 at the branch bit discrimination bit position read by the node reading means 9601 and the root node array number 1. Is set as the array element number of the array element in which the node to be read next is arranged.

Similarly, the node link means 9602 to 960n-1 includes the bit value of the search key set in the search key setting means 950 at the discrimination bit position of the branch node read by the node reading means 9302 to 930n-1. Then, a value obtained by adding a value obtained by doubling the array element number set by the node link means 9601 to 960n-2 in the previous stage is set as the array element number of the array element where the node to be read next is arranged.

The node reading means 9302 to 930n-1 read the branch node having the array number set by the preceding node link means 9601 to 960n-2, and the node reading means 930n has the leaf of the array number set by the node link means 960n-1. The node is read and passed to the search result output means 970.

The search result output unit 970 extracts the index key or information for accessing the index key from the leaf node passed from the node reading unit 930n, as in the first embodiment. When what is extracted from the leaf node is an index key, the index key is output as a search result key. When the information extracted from the leaf node is information for accessing the index key, the index key is read out and output as a search result key based on the information for accessing the extracted index key.
Further, the search result key and the search key are compared, and if they match, it is possible to output a search result indicating that the search is successful, and if they do not match, it is possible to output a search result indicating that the search is unsuccessful. is there.

Next, search processing according to the second embodiment of the present invention will be described with reference to FIGS.
FIG. 10 is a diagram illustrating an example of a processing flow of bit string search in the second embodiment of the present invention. In the example shown in FIG. 10, the number of stages of the coupled node tree is n.

First, in step S1001, 1 is set to the link destination array number.
In step S1002, the array number of the second node is obtained from the discrimination bit position and the search key stored in the array pointed to by the link destination array number (root node array number).

In step S1003, the array number of the third-stage node is obtained from the discrimination bit position and the search key stored in the array indicated by the array number of the second-stage node.
Similarly, in steps S1004 to S100n, the fourth to nth nodes are respectively determined by the discrimination bit position and the search key stored in the array indicated by the array number of the third to n−1th node. Determine the sequence number of. Details of the processing in steps S1002 to S100n will be described later with reference to FIG.

Finally, the bit string stored in the array pointed to by the array element number of the n-th node is taken out as an index key, and the process ends.
Note that the processing flow example illustrated in FIG. 10 uses the coupled node tree of the present embodiment having a specific number of stages n. However, an arbitrary assembler macro using the number of stages n as a parameter can be used. It is possible to generate a processing flow for realizing search processing using a coupled node tree having the number of stages.

  FIG. 11 is a diagram for explaining an example of a processing flow for obtaining a link destination array element number according to the second embodiment of the present invention, and shows details of the processing in steps S1002 to S100n shown in FIG.

First, in step S1101, the contents stored in the array element indicated by the link destination array number are read from the array as a discrimination bit position, and in step S1102, the bit value indicated by the read discrimination bit position is extracted from the search key.

In step S1103, the array element number set as the link destination array number is doubled and set as the link destination array number. Further, in step S1104, the bit number extracted in step S1102 is added to the array number set in step S1103 as the link destination array number to set the link destination array number, and the process ends.

Next, a search example using a coupled node tree according to the second embodiment of the present invention will be described with reference to FIG. FIG. 12 shows only the part necessary for the description in the coupled node tree illustrated in FIG. 8B, and the part below the node 211b is omitted.
In the example shown in FIG. 12, a bit string “0011010” (hereinafter referred to as search key 280) is set as a search key in the search key setting area 280. The search key 280 is obtained by adding 0 as the most significant bit to the search key 270 in the search example using the coupled node tree according to the first embodiment of the present invention shown in FIG. 4B. The search start node is the root node 210a. Similarly to the search example shown in FIG. 4B, it is also described that the link destination array element number is obtained as the sum of the representative node number obtained by doubling the array element number of the link source branch node and the bit value of the discrimination bit position of the search key. Has been.

Hereinafter, the flow of the search process will be described with reference to FIG.
Since the search start node is the root node, 1 is set in the link destination array number at the start of the search, so the node 210a is read. The value 1 is extracted from the discrimination bit position 230a of the node 210a. Since the value of the bit position 1 of the search key 280 is 0, the link destination array number is 2, which is obtained by adding 0 to the representative node number 220a that is twice the array number 1, and is arranged in the array element of the array number 2. Node 210b is then read.

Then, the value 2 is extracted from the discrimination bit position 230b of the node 210b. Since the value of bit position 2 of the search key 280 is 1, the link destination array number is 5 which is obtained by adding 1 to the representative node number 220b obtained by doubling array number 2, and is arranged in the array element of array number 5. Node 211c is then read out.

  Then, the value 3 is extracted from the discrimination bit position 231c of the node 211c. Since the value of the bit position 3 of the search key 280 is 1, the link destination array number is 11, which is obtained by adding 1 to the representative node number 221c obtained by doubling the array number 5, and is arranged in the array element of the array number 11 Node 211d is then read out.

  Then, the value 0 is extracted from the discrimination bit position 231d of the node 211d. Since the value of the bit position 0 of the search key 280 is 0, the link destination array number is 22 obtained by adding 0 to the representative node number 221i that is twice the array number 11, and is arranged in the array element of the array number 22 Node 210l is then read.

  Since the node 210l is positioned at the lowest level of the coupled node tree, the index key “0011010” as a search result is extracted from the index key 250l, and the search process is completed.

  Next, modified examples of the above-described first embodiment and second embodiment will be described. These modifications are for making it possible to flexibly arrange an array for storing a tree in an area of a storage device, or to arrange a tree in an array existing in an arbitrary area of the storage device.

FIG. 13 is a diagram illustrating a configuration example of the coupled node tree stored in the array according to the modification of the first embodiment of the present invention. Compared with the configuration example shown in FIG. 4A, a base number 600 and an offset number 610 are added. Also, values 1 to 15 of the node reference number 620 are described instead of the array numbers 1 to 15 in FIG. 4A. In FIG. 13, as for the array element number 630, 100, 111, 122, 123, 134 to 137, and 148 to 155 are described as the value of the number.
FIG. 13 illustrates 100 as the value of the base number 600 and 10, 20, 30, and 40 as the values of the offset number 610.
For other codes, the corresponding codes shown in FIG. 4A with “a” added are used.

The base number is a number that determines the position of the root node of the tree in combination with the first-stage offset number described later. By using the base number, it is possible to eliminate the need to restrict the array element number of the root node to 1 as illustrated in FIGS. 4A and 4B.
The offset number is a number that determines the starting position where the node of each stage of the tree is stored. By using the offset number, a tree node can be arranged for each number of stages on the tree where the node is located. The offset number is set in the offset number table for each stage number.
The node reference number is a number that determines the order of the nodes, and corresponds to the array element number illustrated in FIGS. 4A and 4B .
The array element number can be obtained from the sum of the base number, the offset number, and the node reference number.
In this modification, when the base number is 0 and the offset number of each stage is 0, the node reference number matches the array number illustrated in FIGS. 4A and 4B, and the coupled node tree of this modification is shown in FIG. 4A. And the coupled node tree of the first embodiment illustrated in FIG. 4B.

  Referring to FIG. 13, base number 600 is 100 (hereinafter referred to as base number 100), offset number 610 (first stage) is 10 (hereinafter referred to as offset number 10), and node reference is made. Since the number 620 is 1 (hereinafter referred to as node reference number 1), the root node 401a is an array element whose array number 630 of the array 400a is 111 (hereinafter referred to as array number 111). Is arranged. The root node 401a includes a node type 402a and a discrimination bit position 403a. The node type 402a is 0, indicating that the root node 401a is a branch node. 1 is stored in the discrimination bit position 403a.

  The node [0] 412a, which is the representative node of the link destination node pair 411a indicated by the dotted arrow 410a from the root node 401a with the node reference number 1, is the node of the root node 401a that is the parent node positioned immediately above the tree. It is arranged in an array element of array number 122, which is obtained by adding the sum of base number 100 and offset number 20 to node reference number 2 having a value twice that of reference number 1. A node [1] 413a that is paired with the representative node is arranged in the next adjacent array element (node reference number 3, array number 123). 1 is stored in the node type of the node [0] 412a, which indicates that the node [0] 412a is a leaf node. “0001” is stored in the index key 418a. On the other hand, 0 is stored in the node type of the node [1] 413a, which indicates that the node [1] 413a is a branch node. 3 is stored in the discrimination bit position of the branch node 413a.

  The node 422a, which is the representative node of the link destination node pair 421a indicated by the dotted arrow 420a from the branch node 413a whose node reference number is 3, has a value twice as large as the node reference number 3 of the node 413a which is the parent node. It is arranged in the array element of array element number 136 obtained by adding the sum of base number 100 and offset number 30 to node reference number 6. A node 423a that is paired with the representative node is arranged in the next adjacent array element (node reference number 7, array number 137). 0 is stored in the node type of the node 422a, indicating that the node 422a is a branch node. 4 is stored in the discrimination bit position of the branch node 422a. Also, 0 is stored in the node type of the node 423a, indicating that the node 423a is a branch node. 5 is stored in the discrimination bit position of the branch node 422a.

No nodes are arranged in the array elements of array element number 134 and array element number 135.
As is clear from the above example, the node reference number of the representative node of the link destination node pair is twice the node reference number of the parent node.

Therefore, the node 432a, which is the representative node of the link destination node pair 431a indicated by the dotted arrow 430a from the branch node 422a having the node reference number 6, adds the sum of the base number 100 and the offset number 40 to the node reference number 12. It is arranged in the array element of the added array element number 152. Then, a node 433a that is paired with the representative node is arranged in the next adjacent array element (node reference number 13, array number 153). Description of the contents of the node 432a and the node 433a is omitted.

Similarly, the node 442a, which is the representative node of the link destination node pair 441a indicated by the dotted arrow 440a from the branch node 423a whose node reference number is 7, is the sum of the base number 100 and the offset number 40 in the node reference number 14. Are arranged in the array element of SEQ ID NO: 154. A node 443a that is paired with the representative node is arranged at the next adjacent array element (node reference number 15, array number 155). Description of the contents of the node 442a and the node 443a is omitted.
Further, no nodes are arranged in the array elements of array element numbers 148 to 151.

Also in this modification, the tree structure itself of the coupled node tree is the same as that shown in FIG. 4B. 4A and 4B are different from each other in that the position of the node on the tree is defined by the array number associated with the array. In this modification, the node reference independent of the array is used. It is a point specified by a number.
The node can be accessed by combining the node reference number, the base number, and the offset number.

  Therefore, by appropriately selecting the offset number, for example, it is possible to arrange the upper n stages of the tree in the main storage device and arrange the nodes lower than the n stage in the external storage device.

Next, search processing in a modification of the first embodiment of the present invention will be described with reference to FIG. FIG. 14 is a diagram for explaining an example of a processing flow of bit string search in the modification of the first embodiment of the present invention. Compared to the processing flow example shown in FIG. 6, the handling of the node reference number, the base number, and the offset number is added, and the array number is obtained based on these numbers.

  First, a base number is set in step S1401a, and an offset number table is set in step S1401b. Further, in step S1401c, a value 1 is set in the stage number counter, and in step S1401d, a value 1 is set in the node reference number. In the example shown in FIG. 14, the search start node is the root node. However, even when a number other than 1 is specified for the stage counter and the node reference number and the search start node is other than the root node, The processing flow is the same.

In step S1402a, the offset number pointed to by the stage number counter is extracted from the offset number table. In step S1402b, a value obtained by adding the base number and the offset number to the node reference number is set in the link destination array number.
In step S1403, the array element having the array element number set as the link destination array element number is read from the array as a node to be referred to. In step S1404, the node type is extracted from the read node. In step S1405, it is determined whether the node type is a branch node.

If it is determined in step S1405 that the read node is a branch node, the process proceeds to step S1406, where information on the discrimination bit position is extracted from the node, and in step S1407, a bit value corresponding to the extracted discrimination bit position is searched. Take out from the key. In step S1408, the value obtained in step S1407 is set to the node reference number to a value obtained by doubling the node reference number. Further in step S1409, 1 is added to the number of stages counter returns to step S140 2a.

Thereafter, the processing from step S1402a to step S1409 is repeated until it is determined as a leaf node in the determination in step S1405 and the process proceeds to step S1410. In step S1410, the index key is extracted from the leaf node, and the process ends.
In the above example, it is assumed that the index key is directly included in the leaf node. However, if the leaf node includes information for accessing the index key, the index from the leaf node in step S1410. Information for accessing the key is extracted, and in an additional step, the index key is extracted using the information for accessing the extracted index key.
In addition, after the index key is extracted, the index key can be used as a search result key in another application, or a match with the search key can be determined to determine success or failure of the search.

Next, a modification of the second embodiment of the present invention will be described. The technical significance of the base number, the offset number, and the node reference number, and the relationship with the array element number are the same as in the modification of the first embodiment.
FIG. 15 is a diagram illustrating a configuration example of a coupled node tree stored in the array according to the modification of the second embodiment of the present invention. Compared with the configuration example shown in FIG. 8A, a base number 700 and an offset number 710 are added. Also, values 1 to 15 of the node reference number 720 are described instead of the array numbers 1 to 15 in FIG. 8A. In FIG. 15, for the array element number 730, 100, 111, 122, 123, 134 to 137, and 148 to 155 are described as the value of the number.
FIG. 15 illustrates 100 as the value of the base number 700 and 10, 20, 30, and 40 as the values of the offset number 710.
For other codes, the corresponding codes shown in FIG. 8A with “a” added are used.
In this modification, as in the modification of the first embodiment, if the base number is 0 and the offset number of each stage is 0, the node reference number matches the array number illustrated in FIGS. 8A and 8B. The coupled node tree of the present modification matches the coupled node tree of the second embodiment illustrated in FIGS. 8A and 8B.

Referring to FIG. 15, since the base number is 100, the offset number is 10, and the node reference number is 1, the root node 801a is arranged in the array element of array element 111 in the array 800a. The root node 801a includes a discrimination bit position 803a. 2 is stored in the discrimination bit position 803a.

  A node [0] 812a, which is a representative node of the link destination node pair 811a indicated by the dotted arrow 810a from the root node 801a having the node reference number 1, is a root node 801a that is a parent node positioned immediately above the tree. The node reference number 2 having a value twice that of the node reference number 1 is added to the array element of the array number 122 obtained by adding the sum of the base number 100 and the offset number 20. A node [1] 813a that is paired with the representative node is arranged in the next adjacent array element (node reference number 3, array number 123).

  0 is stored in the discrimination bit position of the node [0] 812a, and the link destination is a node having a value twice the node reference number 2 of the node [0] 812a, as indicated by the dotted arrow 840a. The node 842a is stored in the array element of the array element number 134 obtained by adding the sum of the base number 100 and the offset number 30 to the reference number 4. Further, 0 is stored in the discrimination bit position of the node 842, and the link destination is the node reference number 8 having a value twice the node reference number 4 of the node 842a, as indicated by the dotted arrow 850a. , Node 852a stored in the array element of array number 148 obtained by adding the sum of base number 100 and offset number 40.

Since the node 852a is positioned at the bottom of the coupled node tree illustrated in FIG. 15, it is a leaf node, and the index key “00001” with 0 inserted in the most significant bit is stored in the index key 818a. .

  On the other hand, 4 is stored in the discrimination bit position of the node [1] 813a. The node 822a that is the representative node of the link destination node pair 821a indicated by the dotted arrow 820a from the branch node 813a that has the node reference number 3 has a value that is twice the node reference number 3 of the node 813a that is the parent node. It is arranged in the array element of array element number 136 obtained by adding the sum of base number 100 and offset number 30 to node reference number 6. A node 823a that is paired with the representative node is arranged in the next adjacent array element (node reference number 7, array number 137). 5 is stored in the discrimination bit position of the node 822a. Further, 6 is stored in the discrimination bit position of the node 823a.

The node 832a, which is the representative node of the link destination node pair 831a indicated by the dotted arrow 830a from the branch node 822a whose node reference number is 6, is based on the node reference number 12 having a value twice that of the node reference number 6. Arranged in the array element of array number 152, which is the sum of number 100 and offset number 40. A node 833a that is paired with the representative node is arranged in the next adjacent array element (node reference number 13, array number 153). Description of the contents of the node 832 and the node 833 is omitted. Further, the description of the link destination of the branch node 823a is also omitted.

Also in this modification, the tree structure itself of the coupled node tree is the same as that shown in FIG. 8B. The difference is that in the case shown in FIGS. 8A and 8B, the position of the node on the tree is defined by the array number associated with the array, whereas this is the same as the modification of the first embodiment. Also in the modified example, it is a point defined by a node reference number independent of the array.
The node can be accessed by combining the node reference number, the base number, and the offset number.

  Therefore, by appropriately selecting the offset number, for example, it is possible to arrange the upper n stages of the tree in the main storage device and arrange the nodes lower than the n stage in the external storage device.

Next, search processing in a modification of the second embodiment of the present invention will be described with reference to FIG. FIG. 16 is a diagram for explaining an example of a processing flow of bit string search in the modification of the second embodiment of the present invention. Compared to the processing flow example shown in FIG. 10, the handling of node reference numbers, base numbers, and offset numbers is added, and the array number is obtained based on these numbers.

  First, a base number is set in step S1601a, and an offset number table is set in step S1601b. In step S1601c, a value 1 is set as the node reference number. In step S1601d, a value obtained by adding the base number and the offset number to the node reference number is set to the link destination array number. By the process of step S1601d, the array element number of the root node is set as the link destination array element number.

In step S1602, the array number of the second node is obtained from the discrimination bit position and the search key stored in the array pointed to by the array number (link destination array number) of the root node.
In step S1603, the array number of the third-stage node is obtained from the discrimination bit position and the search key stored in the array indicated by the array number of the second-stage node.
Similarly, in steps S1604 to S160n, the fourth to n-th nodes are respectively determined by the discrimination bit positions and search keys stored in the arrays indicated by the array numbers of the third to n-1-th nodes. Determine the sequence number of. Details of the processing in steps S1602 to S160n will be described later with reference to FIG.

Finally, the bit string stored in the array pointed to by the array element number of the n-th node is taken out as an index key, and the process ends.
Similar to the process flow example illustrated in FIG. 10, the process flow example illustrated in FIG. 16 uses the coupled node tree of the present embodiment having a specific number of stages n. By using the assembler macro described above, it is possible to generate a processing flow for realizing search processing using an arbitrary number of coupled node trees of this embodiment.

FIG. 17 is a diagram for explaining an example of a processing flow for obtaining the array number of the link destination in the modification of the second embodiment of the present invention, and shows details of the processing in steps S1602 to S160n shown in FIG. is there.

First, in step S1701, the content stored in the array element pointed to by the link destination array number is read from the array as a discrimination bit position. In step S1702, the bit value pointed to by the read discrimination bit position is extracted from the search key.

Next, in step S1703a, the next-stage offset number is extracted from the offset number table, and in step S1703b, a value obtained by adding the value obtained in step S1702 to the value obtained by doubling the node reference number is set. . In step S1704, a value obtained by adding the base number and the offset number to the node reference number is set in the link destination array number, and the process is terminated.

Next, generation of a coupled node tree according to the first and second embodiments of the present invention will be described. In the following description, the trees according to the first and second embodiments of the present invention may be referred to as pointerless trees, and the conventional coupled node tree may be simply referred to as a tree or a tree before conversion.
The generation of the pointerless tree according to the present invention can be realized as follows, for example. That is, when the pointerless tree is generated, it is assumed that the tree in the form illustrated in FIGS. 1A and 1B is generated by the index key stored in the pointerless tree. The generation of the pointerless tree is realized by sequentially circulating the nodes of the tree from the root node and converting them into the nodes of the first embodiment or the second embodiment of the present invention. This node patrol will be described in detail below, but the node saving process disclosed in FIGS. 10A to 12 of JP-A-2008-269197 cited as Patent Document 4 and the description related thereto is disclosed. Are similar to those used in
The generation of the tree is disclosed and described in detail in FIGS. 5 to 8 of Japanese Patent Application Laid-Open No. 2008-15872 cited as Patent Document 1 and the description related thereto. Omitted.

FIG. 18A is a diagram showing an example of a processing flow before the processing for generating a pointerless tree in the first and second embodiments of the present invention. As shown in FIG. 18A, first, in step S1801, an array for generating a pointerless tree is acquired, and in step S1802, array elements are initialized. The processing in step S1802 is necessary in the processing example in the second embodiment using a dummy branch node, and can be omitted in the first embodiment.
Next, in step S1802a, the maximum number of stages of the tree before conversion is obtained, and in step S1802b, the maximum number of stages is set as the upper limit value of the stage number counter. The upper limit value of the stage number counter is used for arranging the leaf node in the lowest stage of the pointerless tree in the second embodiment. Therefore, similar to the processing in step S1802, it can be omitted in the first embodiment.
Details of the processing in step S1802a will be described later with reference to FIGS.

In step S1803, a base number is set. In step S1804, an offset number table is set.
Furthermore, in step S1805, 1 is set in the stage number counter, in step S1806, 1 is set in the node reference number, and in step S1807, the array number of the root node of the tree is set in the array number of the cyclic start node. Proceed to step S1812 shown in FIG. 18B.

Note that the flow illustrated in FIG. 18A and the following drawings corresponds to the modification shown in FIG. 13 or FIG. However, in the modification, assuming that the base number is 0, the offset number in each stage is 0, and the node reference number is the array number, the tree generation processing in the form shown in FIG. 4A or 8A is shown. Therefore, the flow illustrated in FIG. 18A and the following drawings explains the pointerless tree generation processing of the first embodiment and the second embodiment including a modification.

  FIG. 18B is a diagram illustrating a processing flow example at the latter stage of the processing for generating the pointerless tree in the first and second embodiments of the present invention. As shown in FIG. 18B, in step S1812, the tree is circulated from the circulation start node, and the circulation destination node is converted and stored in the pointerless tree. Details of the processing in step S1812 will be described later with reference to FIG.

In step S1813, it is determined whether the stack pointer of the search path stack points to the array element number of the root node of the tree. The storage of the array element number in the search path stack is performed in the process of step S1812.
If the stack pointer of the search path stack points to the array element number of the root node of the tree, the processing is completed because the processing of all the nodes of the tree has been completed. Otherwise, the process proceeds to step S1814.

  In step S1814, the array element number is extracted from the search path stack, and the stack pointer of the search path stack is decremented by one. In step S1815, a node position is obtained from the array element number extracted in step S1814, and it is determined in step S1816 whether the node position is node [0]. If the node position is not the node [0], the value 1 is subtracted from the stage number counter in step S1817, and the process returns to step S1813. If the node position is node [0], the process advances to step S1818.

In step S1818, the value 1 is added to the array element number extracted in step S1814 to obtain the array element number of the node [1]. In step S1819, the array element number of the node [1] obtained in step S1818 is set as the array element number of the tour start node. In step S1820, 1 is added to the node reference number, and the process returns to step S1812.
The loop processing from step S1812 to step S1820 described above is repeated until it is determined in step S1813 that the stack pointer of the search path stack points to the array element number of the root node of the tree. Each node is converted into a node of a pointerless tree, and a pointerless tree is generated.

FIG. 19 is a diagram for explaining an example of a processing flow for traversing a tree from a tour start node and storing the node in a pointerless tree, and is a diagram for explaining details of the processing in step S1812 in FIG. 18B.
As shown in the figure, first, in step S1901, the array element number of the tour start node is set to the array element number. The array element number of the patrol start node is set in step S1807 in FIG. 18A in the initial processing of the loop processing in steps S1812 to S1820 shown in FIG. 18B, and in the subsequent processing, the step shown in FIG. 18B. It is set in S1819.

  In step S1902, the array element number is stored in the search path stack. This array number is set in step S1901 or step S1910 described later.

  Next, in step S1903, the array element indicated by the array element number is read out as a node from the array in which the tree before conversion is stored. In step S1904, the array element acquired in step S1801 in FIG. 18A based on the node reference number is read. A node of a pointerless tree is generated by writing a node to an array element. Details of the processing in step S1904 will be described later with reference to FIGS. 20A and 20B. FIG. 20A is for the first embodiment, and FIG. 20B is for the second embodiment.

  In step S1905, the node type is extracted from the node read in step S1903. In step S1906, it is determined whether the extracted node type indicates a branch node. If it is determined in step S1906 that the node type does not indicate a branch node but indicates a leaf node, the process ends. If the node type indicates a branch node, the process proceeds to step S1907.

In step S1907, a value of 1 is added to the stage number counter, and the flow advances to step S1908 to double the node reference number. In step S1909, the representative node number is extracted from the node read in step S1903. In step S1910, a value obtained by adding the value 0 to the extracted representative node number is set as the array number, and the process returns to step S1902.

  The loop processing from step S1902 to step S1910 described above is repeated until the node type indicates a leaf node in step S1906. That is, as a group of processes, the node is visited from the tour start node to the first leaf node, the node is read, the node is converted, and the node of the pointerless tree is written. In the example of the processing flow shown in FIG. 19, since the array node number is set by adding the value 0 to the representative node number in step S1910, the node [0] side is preferentially circulated. It will be apparent to those skilled in the art from the above description that the node can be visited with priority on the [1] side.

  FIG. 20A is a diagram for explaining a processing flow example of processing for generating a node in the first embodiment of the present invention, and is a diagram for explaining details of processing in the first embodiment in step S1904 shown in FIG. is there.

  As shown in the figure, first, in step S2001, the offset number indicated by the stage number counter is extracted from the offset number table, and in step S2002, a value obtained by adding the base number and the offset number to the node reference number is set as the array number. The array number here is a temporary storage area for setting the array element number of the array element for storing the pointerless tree. The array number for storing the tree before conversion set in step S1901 or step S1910 in FIG. 19A. This is different from the temporary storage area for setting the array element array number.

  Next, in step S2003, the node type is extracted from the node read in step S1903 of FIG. 19, and in step S2004, it is determined whether the extracted node type is a branch node. If the determination result is positive, the process proceeds to step S2005. If the determination result is negative, the process proceeds to step S2007.

In step S2005, the discrimination bit position is extracted from the node. In step S2006, the node type and discrimination bit position are written in the array element indicated by the array element number set in step S2002, a branch node is generated, and the process ends.
In step S2007, the index key is extracted from the node. In step S2008, the node type and index key are written in the array element indicated by the array number set in step S2002, a branch node is generated, and the process is terminated.

  FIG. 20B is a diagram for explaining a processing flow example of processing for generating a node in the second embodiment of the present invention, and is a diagram for explaining details of processing in the second embodiment in step S1904 shown in FIG. is there.

  As shown in the figure, first, in step S2021, the offset number indicated by the stage number counter is extracted from the offset number table. In step S2023, the node type is extracted from the node read in step S1903 in FIG. 19, and the process proceeds to step S2024. .

In step S2024, it is determined whether the node type extracted in step S2023 is a branch node. If the determination result is affirmative, the process proceeds to step S2025. If the determination result is negative, the process proceeds to step S2029.

In step S2025, the array number is set to a value obtained by adding the base number and the offset number to the node reference number. In step S2026, the discrimination bit position is extracted from the node. In step S2027, the value 1 is added to the discrimination bit position. In step S2028, the discrimination bit position is written in the array element indicated by the array element number set in step S2025. Generate a node and finish the process.

  On the other hand, if the determination in step S2024 is negative and the node type extracted in step S2023 is a leaf node, the process proceeds to step S2029, where the node reference number and the stage number counter are saved, and the process proceeds to step S2030. move on.

  In step S2030, it is determined whether the stage number counter is the upper limit value. If not, the node reference number is doubled in step S2031, the value 1 is added to the stage number counter in step S2032, and the offset number table is used in step S2033. The offset number pointed to by the stage number counter is taken out and the process returns to step S2030.

  The loop processing of steps S2030 to S2033 described above is for placing leaf nodes in the second embodiment at the lowest level of the pointerless tree. In the example of FIGS. 1B and 8B, for example, the leaf node 210c at the third level in the tree before conversion in FIG. 1B is converted to the node 210j at the fifth level in FIG. 8B. Then, the position information of the node 210c in FIG. 8B is saved by the process of step S2029 in FIG. 20B.

Note that the upper limit value of the stage number counter is set in step S1802b shown in FIG. 18A. Instead, when generating a tree before conversion, the number of stages of the leaf node is set each time a leaf node is inserted. The maximum value is counted and stored as an attribute of the tree, and when the pointerless tree of the second embodiment is generated, the maximum value can be used as the upper limit value of the stage number counter.

If it is determined in step S2030 that the stage number counter is the upper limit value, the process advances to step S2034 to set a value obtained by adding the base number and the offset number to the node reference number. In step S2035, the index key is extracted from the node. In step S2036, the bit value “0” is inserted into the most significant bit position of the index key. In step S2037, the array element pointed to by the array number set in step S2034. The index key is written in, a leaf node is generated, and the process proceeds to step S2038.
In step S2038, the node reference number and stage number counter saved in step S2029 are set in the node reference number and stage number counter, respectively, and the process ends.

Next, a process for obtaining the maximum number of trees before conversion will be described.
FIG. 21 is a diagram for explaining an example of a processing flow for obtaining the maximum number of levels of a tree before conversion, and details the processing in step S1802a in FIG. 18A.

  As shown in FIG. 21, first, in step S2101, the value 1 is set in the stage number counter, and in step S2102, the value set in the stage number counter is set in the maximum stage number counter. That is, a value 1 is set as an initial value in the stage number counter and the maximum stage number counter.

Next, in step S2112, the tree is circulated from the circulation start node, and the number of stages of the circulation destination node is counted to obtain the maximum number of circulated nodes. Details of the processing in step S2112 will be described later with reference to FIG.

In step S2113, it is determined whether the stack pointer of the search path stack points to the array element number of the root node of the tree. The storage of the array element number in the search path stack is performed in the process of step S2112.
If the stack pointer of the search path stack points to the array element number of the root node of the tree, the circulation is completed for all the nodes of the tree, and the process ends. Otherwise, the process proceeds to step S2114.

  In step S2114, the array element number is extracted from the search path stack, and the stack pointer of the search path stack is decremented by one. In step S2115, the node position is obtained from the array element number extracted in step S2114, and it is determined in step S2116 whether the node position is node [0]. If the node position is not the node [0], the value 1 is subtracted from the stage number counter in step S2117, and the process returns to step S2113. If the node position is node [0], the process proceeds to step S2118.

In step S2118, value 1 is added to the array element number extracted in step S2114 to obtain the array element number of node [1]. In step S2119, the array element number of node [1] obtained in step S2118 is set in the array element number of the tour start node, and the process returns to step S2112.
The loop processing of steps S2112 to S2119 described above is repeated until it is determined in step S2113 that the stack pointer of the search path stack points to the array element number of the root node of the tree. And the maximum number of stages of the visited nodes, that is, the maximum number of stages of the tree before conversion is obtained.

FIG. 22 is a diagram illustrating an example of a processing flow in which a tree is traversed from a tour start node, and the number of stages of nodes is counted to obtain the maximum number of visited nodes, and the details of the process in step S2112 of FIG. 21 are illustrated. It is.
As shown in the figure, first, in step S2201, the array element number of the patrol start node is set to the array element number. The array element number of the tour start node is set in step S2107 of FIG. 21 in the first processing of the loop processing in steps S212 to S2119 shown in FIG. 21, and in the subsequent processing, the steps shown in FIG. It is set in S2119.

  In step S2202, the array element number is stored in the search path stack. This array number is set in step S2201 or step S2210 described later.

  In step S2203, the array element indicated by the array element number is read as a node from the array in which the tree before conversion is stored, and in step S2205, the node type is extracted from the read node.

In step S2206, it is determined whether the extracted node type indicates a branch node. If it is determined in step S2206 that the node type indicates a branch node, the process proceeds to step S2207, and if it is determined that the node type indicates a leaf node instead of a branch node, step S2207 is performed. The process proceeds to S2210.

  In step S2207, 1 is added to the stage number counter. In step S2209, the representative number is extracted from the node read in step S2203. In step S2210, the value obtained by adding 0 to the extracted representative node number is used as the array number. Set, and return to step S2202.

  The loop processing from step S2202 to step S2210 described above is repeated until the node type indicates a leaf node in step S2206. In the example of the processing flow shown in FIG. 22, since the array node number is set by adding the value 0 to the representative node number in step S2210, the node [0] is preferentially circulated. It is obvious to those skilled in the art that, similarly to the processing of FIG. 19 described above, it is also possible to circulate the node with priority given to the node [1] side.

In the above step S2206, the node type is determined as indicating a leaf node, processing proceeds to step S221 1, the value of the number counter is greater or decision by the maximum number the value set in the counter, it is not greater processing Exit, larger, in step S221 2, the process ends by setting the value of the number counter to the maximum number counter.

Although the embodiment for carrying out the present invention has been described in detail above, it is obvious to those skilled in the art that the embodiment of the present invention is not limited thereto and can be variously modified.
Also, the bit string search device according to the first and second embodiments of the present invention causes the computer to execute the processing illustrated in FIG. 6, FIG. 10 and FIG. 11, or FIG. It is clear that the program can be built on a computer.
Therefore, the program and a computer-readable storage medium storing the program are included in the embodiment of the present invention. Furthermore, the data structure of the coupled node tree of the present invention is also included in the embodiment of the present invention.

100, 400, 800 Array 101 Node 102, 402 Node type 103, 403, 803 Discrimination bit position 104 Representative node number 118, 418, 818 Index key 200, 200a, 200b Coupled node tree 210a, 401, 801 Root node 270, 280 Search key 301 Data processing device 302 Central processing unit 303 Cache memory 304 Bus 305 Main storage device 306 External storage device 307 Communication device 308 Data storage device 309 Array 310 Search path stack 500, 900 Bit string search device 510, 910 Search tree storage means 520, 920 Search start position setting means 530 Node reading means 540 Node type determination means 550, 950 Search key setting means 560 Node link means 570, 70 search result output unit 9301, ···, 930n node reading unit 9601, ···, 960n-1 node link means 600 and 700 base number 610 and 710 offset number 620, 720 node reference numbers 630, 730 SEQ ID NO:

Claims (24)

In a bit string search device for searching for an index key based on a data structure of a tree in which an index key consisting of a bit string to be searched or information for accessing the index key is stored using a search key consisting of a bit string,
The tree is stored in an array, and is a start node of the tree, a root node disposed in an array element of array number 1 of the array, and a representative node disposed in an adjacent array element of the array And a node pair as a constituent element of a tree having two nodes which are non-representative nodes, and the node has an area for storing a node type indicating whether the node is a branch node or a leaf node. The branch node includes an area for storing the discrimination bit position of the search key in addition to the node type, and the array element number of the array element in which the representative node of the nearest lower-level node pair that is the link destination is arranged That does not include an area for storing information and an index key composed of the bit string to be searched or information for accessing the index key The leaf node includes, in addition to the node type, an index key composed of the bit string to be searched or an area for storing information for accessing the index key, the discrimination bit position of the search key being A couple that does not include a storage area, and the representative node is arranged in an array element having an array number that is twice the array element number of the array element in which the branch node immediately above the representative node is disposed. Node tree,
A search start position setting means for acquiring an array element number of an array element in which a node for starting a search is arranged, and setting the acquired array element number as an array element number of a link destination node;
Node readout means for reading out the node arranged in the array element from the array element of the array number set as the array number of the link destination node by the search start position setting means or the link means described later;
A node type that reads out the node type from an area that stores the node type of the node read by the node reading unit, and determines whether the node type indicates the leaf node or the branch node A determination means;
Index key reading means for reading out the index key directly from the index key of the leaf node or an area storing information for accessing the index key, or reading out the index key based on information for accessing the index key; ,
When the node type determined by the node type determination means indicates a branch node, the discrimination bit position is read from the area storing the discrimination bit position of the branch node, and the search key of the read discrimination bit position is read A link means for setting a sum of the bit value of the branch node and a value twice the array number of the array element in which the branch node is arranged as the array number of the link destination node;
With
The node type of the node read by the node reading unit is determined by the node type determining unit, and if the node type indicates a leaf node, the index key is read by the index key reading unit, and the node type is branch If it indicates a node, the link means sets the array number of the link destination node, reads the node placed in the array element of the set link destination node array number by the node reading means, The determination of the node type of the read node by the node type determination unit is repeated until the node type indicates a leaf node. When the node type indicates a leaf node, the index key is read by the index key reading unit. A bit string search device characterized by reading. The bit string search method executed by the bit string search device according to claim 1,
A search start position setting step of acquiring the array element number of the array element where the node to start the search is arranged, and setting the acquired array element number as the array element number of the link destination node;
A node reading step of reading out a node arranged in the array element from the array element of the array element number set as the array element number of the link destination node in the search start position setting step or the link step described later;
Node type for reading out the node type from the area for storing the node type of the node read out in the node reading step, and determining whether the node type indicates the leaf node or the branch node A determination step;
An index key reading step of reading the index key directly from the index key of the leaf node or an area storing information for accessing the index key, or reading the index key based on the information for accessing the index key; ,
When the node type determined in the node type determination step indicates a branch node, the discrimination bit position is read from the area storing the discrimination bit position of the branch node, and the search key of the read discrimination bit position A link step of setting a sum of a bit value of the branch node and a value twice the array number of the array element in which the branch node is arranged as the array number of the link destination node;
With
The node type of the node read in the node reading step is determined in the node type determining step. If the node type indicates a leaf node, the index key is read in the index key reading step, and the node type is a branch. If it indicates a node, the array number of the link destination node is set in the link step, and the node arranged in the array element of the array number of the set link destination node is read in the node read step, Determining the node type of the read node in the node type determination step is repeated until the node type indicates a leaf node. When the node type indicates a leaf node, the index key is read in the index key reading step. Characterized by reading Tsu door column search method.   A program for causing a computer to execute the bit string search method according to claim 2.   A computer-readable storage medium storing a program for causing a computer to execute the bit string search method according to claim 2. In a data structure of a tree in which an index key consisting of a bit string to be searched or information for accessing the index key used for a bit string search by a search key consisting of a bit string is stored,
The tree is stored in an array, and is a start node of the tree, a root node disposed in an array element of array number 1 of the array, and a representative node disposed in an adjacent array element of the array And a node pair as a constituent element of a tree having two nodes which are non-representative nodes, and the node has an area for storing a node type indicating whether the node is a branch node or a leaf node. The branch node includes an area for storing the discrimination bit position of the search key in addition to the node type, and the array element number of the array element in which the representative node of the nearest lower-level node pair that is the link destination is arranged That does not include an area for storing information and an index key composed of the bit string to be searched or information for accessing the index key The leaf node includes, in addition to the node type, an index key composed of the bit string to be searched or an area for storing information for accessing the index key, the discrimination bit position of the search key being The representative node is arranged in an array element having an array number that is twice the array element number of the array element in which the branch node immediately above the representative node is disposed. Yes,
By the bit string search device provided with the storage means of the tree,
A search start position setting step of acquiring the array element number of the array element where the node to start the search is arranged, and setting the acquired array element number as the array element number of the link destination node;
A node reading step of reading out a node arranged in the array element from the array element of the array element number set as the array element number of the link destination node in the search start position setting step or the link step described later;
Node type for reading out the node type from the area for storing the node type of the node read out in the node reading step, and determining whether the node type indicates the leaf node or the branch node A determination step;
An index key reading step of reading the index key directly from the index key of the leaf node or an area storing information for accessing the index key, or reading the index key based on the information for accessing the index key; ,
When the node type determined in the node type determination step indicates a branch node, the discrimination bit position is read from the area storing the discrimination bit position of the branch node, and the search key of the read discrimination bit position A link step of setting a sum of a bit value of the branch node and a value twice the array number of the array element in which the branch node is arranged as the array number of the link destination node;
With
The node type of the node read in the node reading step is determined in the node type determining step. If the node type indicates a leaf node, the index key is read in the index key reading step, and the node type is a branch. If it indicates a node, the array number of the link destination node is set in the link step, and the node arranged in the array element of the array number of the set link destination node is read in the node read step, Determining the node type of the read node in the node type determination step is repeated until the node type indicates a leaf node. When the node type indicates a leaf node, the index key is read in the index key reading step. Execute search method to read Data structure, characterized in that the capacity.   A computer-readable storage medium storing the data structure according to claim 5. In a bit string search device for searching for an index key based on a data structure of a tree in which an index key consisting of a bit string to be searched or information for accessing the index key is stored using a search key consisting of a bit string,
The tree is stored in an array, and is a root node that is a starting point of the tree, and a node reference number 1 includes a base number that is an array number that determines the position of the root node and each level of the tree. A root node arranged in an array element having an array number having a value obtained by adding an offset number, which is a number defining a start position of the node, and two representative nodes and non-representative nodes arranged in adjacent array elements of the array A node pair as a component of a tree having a node, the node having an area for storing a node type indicating whether the node is a branch node or a leaf node, and the branch node includes the node In addition to the node type, an area for storing the discrimination bit position of the search key is included, but the representative node of the nearest lower-level node pair that is the link destination is arranged. It does not include an area for storing the array element array number and an index key composed of the bit string to be searched or an area for storing information for accessing the index key, and the leaf node is added to the node type. Including an index key consisting of the bit string to be searched or an area for storing information for accessing the index key, but not including an area for storing the discrimination bit position of the search key, The node is an array number of a value obtained by adding the base reference number and the offset number of the next stage of the nearest upper branch node to the node reference number twice the node reference number of the nearest upper branch node of the representative node A coupled node tree placed in the array element of
Based on the node reference number of the node that starts the search, the offset number for the node, and the base number, the array element number of the array element in which the node is arranged is acquired, and the array element of the link destination node is obtained. A search start position setting means to set as a number;
Node readout means for reading out the node arranged in the array element from the array element of the array number set as the array number of the link destination node by the search start position setting means or the link means described later;
A node type that reads out the node type from an area that stores the node type of the node read by the node reading unit, and determines whether the node type indicates the leaf node or the branch node A determination means;
Index key reading means for reading out the index key directly from the index key of the leaf node or an area storing information for accessing the index key, or reading out the index key based on information for accessing the index key; ,
When the node type determined by the node type determination means indicates a branch node, the discrimination bit position is read from the area storing the discrimination bit position of the branch node, and the search key of the read discrimination bit position is read Is the node reference number of the link destination node, and the node reference number, the base number, and the offset number of the next stage of the branch node. A link means for setting the sum as the array number of the link destination node;
With
The node type of the node read by the node reading unit is determined by the node type determining unit, and if the node type indicates a leaf node, the index key is read by the index key reading unit, and the node type is branch If it indicates a node, the link means sets the array number of the link destination node, reads the node placed in the array element of the set link destination node array number by the node reading means, The determination of the node type of the read node by the node type determination unit is repeated until the node type indicates a leaf node. When the node type indicates a leaf node, the index key is read by the index key reading unit. A bit string search device characterized by reading. The bit string search method executed by the bit string search device according to claim 7 ,
Based on the node reference number of the node that starts the search, the offset number for the node, and the base number, the array element number of the array element in which the node is arranged is acquired, and the array element of the link destination node is obtained. A search start position setting step to be set as a number;
A node reading step of reading out a node arranged in the array element from the array element of the array element number set as the array element number of the link destination node in the search start position setting step or the link step described later;
Node type for reading out the node type from the area for storing the node type of the node read out in the node reading step, and determining whether the node type indicates the leaf node or the branch node A determination step;
An index key reading step of reading the index key directly from the index key of the leaf node or an area storing information for accessing the index key, or reading the index key based on the information for accessing the index key; ,
When the node type determined in the node type determination step indicates a branch node, the discrimination bit position is read from the area storing the discrimination bit position of the branch node, and the search key of the read discrimination bit position Is the node reference number of the link destination node, and the node reference number, the base number, and the offset number of the next stage of the branch node. A link step for setting the sum as the array number of the link destination node;
With
The node type of the node read in the node reading step is determined in the node type determining step. If the node type indicates a leaf node, the index key is read in the index key reading step, and the node type is a branch. If it indicates a node, the array number of the link destination node is set in the link step, and the node arranged in the array element of the array number of the set link destination node is read in the node read step, Determining the node type of the read node in the node type determination step is repeated until the node type indicates a leaf node. When the node type indicates a leaf node, the index key is read in the index key reading step. Characterized by reading Tsu door column search method.   A program for causing a computer to execute the bit string search method according to claim 8.   A computer-readable storage medium storing a program that causes a computer to execute the bit string search method according to claim 8. In a data structure of a tree in which an index key consisting of a bit string to be searched or information for accessing the index key used for a bit string search by a search key consisting of a bit string is stored,
The tree is stored in an array, and is a root node that is a starting point of the tree, and a node reference number 1 includes a base number that is an array number that determines the position of the root node and each level of the tree. A root node arranged in an array element having an array number having a value obtained by adding an offset number, which is a number defining a start position of the node, and two representative nodes and non-representative nodes arranged in adjacent array elements of the array A node pair as a component of a tree having a node, the node having an area for storing a node type indicating whether the node is a branch node or a leaf node, and the branch node includes the node In addition to the node type, an area for storing the discrimination bit position of the search key is included, but the representative node of the nearest lower-level node pair that is the link destination is arranged. It does not include an area for storing the array element array number and an index key composed of the bit string to be searched or an area for storing information for accessing the index key, and the leaf node is added to the node type. Including an index key consisting of the bit string to be searched or an area for storing information for accessing the index key, but not including an area for storing the discrimination bit position of the search key, The node is an array number of a value obtained by adding the base number and the offset number of the next stage of the nearest upper branch node to the node reference number that is twice the node reference number of the nearest upper branch node of the representative node Is placed in the array element of
By the bit string search device provided with the storage means of the tree,
Based on the node reference number of the node that starts the search, the offset number for the node, and the base number, the array element number of the array element in which the node is arranged is acquired, and the array element of the link destination node is obtained. A search start position setting step to be set as a number;
A node reading step of reading out a node arranged in the array element from the array element of the array element number set as the array element number of the link destination node in the search start position setting step or the link step described later;
Node type for reading out the node type from the area for storing the node type of the node read out in the node reading step, and determining whether the node type indicates the leaf node or the branch node A determination step;
An index key reading step of reading the index key directly from the index key of the leaf node or an area storing information for accessing the index key, or reading the index key based on the information for accessing the index key; ,
When the node type determined in the node type determination step indicates a branch node, the discrimination bit position is read from the area storing the discrimination bit position of the branch node, and the search key of the read discrimination bit position Is the node reference number of the link destination node, and the node reference number, the base number, and the offset number of the next stage of the branch node. A link step for setting the sum as the array number of the link destination node;
With
The node type of the node read in the node reading step is determined in the node type determining step. If the node type indicates a leaf node, the index key is read in the index key reading step, and the node type is a branch. If it indicates a node, the array number of the link destination node is set in the link step, and the node arranged in the array element of the array number of the set link destination node is read in the node read step, Determining the node type of the read node in the node type determination step is repeated until the node type indicates a leaf node. When the node type indicates a leaf node, the index key is read in the index key reading step. Execute search method to read Data structure, characterized in that the capacity.   A computer-readable storage medium storing the data structure according to claim 11. In a bit string search device for searching for an index key based on a data structure of a tree in which an index key consisting of a bit string to be searched or information for accessing the index key is stored using a search key consisting of a bit string,
The index key is obtained by inserting a specific bit value at a specific bit position of the original index key,
The search key is the original search key with the specific bit value inserted in the same specific bit position as the original index key,
The tree is stored in an array and has tree elements up to the nth stage (n is a positive integer), and is arranged at the array element of array number 1 of the array, which is the starting point of the tree A node pair as a constituent element of a tree having a root node and two nodes that are a representative node and a non-representative node arranged in adjacent array elements of the array, and the node is a branch node or a leaf node The branch node includes an area for storing a discrimination bit position of the search key, an area for storing a node type for identifying a branch node and a leaf node, and a representative node of the nearest lower-level node pair that is a link destination An area for storing the array element number of the array element arranged, and an area for storing the index key or information for accessing the index key The leaf node includes an area for storing the index key or information for accessing the index key, the area for storing the node type, and the discrimination bit position of the search key. The representative node is arranged in an array element having an array number that is twice the array element number of the array element in which the branch node immediately above the representative node is disposed; The node is located only in the nth stage, a coupled node tree,
Search start position setting means for setting the array element number 1 of the array element where the root node for starting the search is arranged as the array element number of the link destination node;
First to (n- 1 ) th node reading means;
First to (n-1) -th link means;
Index key reading means;
With
The first node reading means reads the root node arranged in the array element from the array element of array number 1 set as the array number of the link destination node by the search start position setting means,
Said first link means twice the sequence number of the arranged array element of said first node the search key bit value and the root node of the valve by the bit position of the root node read out by the reading means Set the sum of the values of and as the array number of the link destination node,
The second to (n-1) -th node reading means reads the array element indicated by the array element number of the link destination node set by each of the first to (n-2) -th link means as a branch node,
Said second to n-1 of the link means, respectively the second to the search key bit value and the branch node of the valve by the bit position of the branch node read out by the n-1 node read-out means The sum of the array element number of the arranged array element and the value twice the array element number is set as the array number of the link destination node;
The index key reading means reads the array elements SEQ ID NO points of the first n-1 link unit sets the destination node as a leaf node, to access the index key or the index key of the reading out the re Funodo Reading the index key directly from the area for storing information for reading, or reading the index key based on information for accessing the index key,
A bit string search device characterized by that.
The bit string search method executed by the bit string search device according to claim 13,
A search start position setting step for setting the array element number 1 of the array element where the root node for starting the search is arranged as the array element number of the link destination node;
First to (n- 1 ) th node reading steps;
First to (n-1) th link steps;
An index key reading step;
With
In the first node reading step, the root node arranged in the array element is read from the array element of array number 1 set as the array number of the link destination node in the search start position setting step;
In the first link step, twice the SEQ ID NO of the deployed array element of said first node the search key bit value and the root node of the valve by the bit position of the read root node in reading step Set the sum of the values of and as the array number of the link destination node,
In the second to (n-1) th node reading steps, the array element indicated by the array element number of the link destination node set in each of the first to (n-2) th link steps is read as a branch node,
Said second to n-1 of the link step, the bit value of the search key of the valve by the bit position of the read branch node respectively the second to n-1 node reading step and the branch node The sum of the array element number of the arranged array element and the value twice the array element number is set as the array number of the link destination node;
In the index key reading step reads out the array elements SEQ ID NO points of the link destination node set by the n-1 link step as a leaf node, to access the index key or the index key of the reading out the re Funodo Reading the index key directly from the area for storing information for reading, or reading the index key based on information for accessing the index key,
A bit string search method characterized by the above.
  A program for causing a computer to execute the bit string search method according to claim 14.   A computer-readable storage medium storing a program for causing a computer to execute the bit string search method according to claim 14. In a data structure of a tree in which an index key consisting of a bit string to be searched or information for accessing the index key used for a bit string search by a search key consisting of a bit string is stored,
The index key is obtained by inserting a specific bit value at a specific bit position of the original index key,
The search key is the original search key with the specific bit value inserted in the same specific bit position as the original index key,
The tree is stored in an array and has tree elements up to the nth stage (n is a positive integer), and is arranged at the array element of array number 1 of the array, which is the starting point of the tree A node pair as a constituent element of a tree having a root node and two nodes that are a representative node and a non-representative node arranged in adjacent array elements of the array, and the node is a branch node or a leaf node The branch node includes an area for storing a discrimination bit position of the search key, an area for storing a node type for identifying a branch node and a leaf node, and a representative node of the nearest lower-level node pair that is a link destination An area for storing the array element number of the array element arranged, and an area for storing the index key or information for accessing the index key The leaf node includes an area for storing the index key or information for accessing the index key, the area for storing the node type, and the discrimination bit position of the search key. The representative node is arranged in an array element having an array number that is twice the array element number of the array element in which the branch node immediately above the representative node is disposed; The node is located only at the nth stage,
By the bit string search device provided with the storage means of the tree,
A search start position setting step for setting the array element number 1 of the array element where the root node for starting the search is arranged as the array element number of the link destination node;
First to (n- 1 ) th node reading steps;
First to (n-1) th link steps;
An index key reading step;
With
In the first node reading step, the root node arranged in the array element is read from the array element of array number 1 set as the array number of the link destination node in the search start position setting step;
In the first link step, twice the SEQ ID NO of the deployed array element of said first node the search key bit value and the root node of the valve by the bit position of the read root node in reading step Set the sum of the values of and as the array number of the link destination node,
In the second to (n-1) th node reading steps, the array element indicated by the array element number of the link destination node set in each of the first to (n-2) th link steps is read as a branch node,
Said second to n-1 of the link step, the bit value of the search key of the valve by the bit position of the read branch node respectively the second to n-1 node reading step and the branch node The sum of the array element number of the arranged array element and the value twice the array element number is set as the array number of the link destination node;
In the index key reading step reads out the array elements SEQ ID NO points of the link destination node set by the n-1 link step as a leaf node, to access the index key or the index key of the reading out the re Funodo A data structure characterized by enabling execution of a search method for reading out an index key directly from an area for storing information for reading or reading out the index key based on information for accessing the index key.
  A computer-readable storage medium storing the data structure according to claim 17. In a bit string search device for searching for an index key based on a data structure of a tree in which an index key consisting of a bit string to be searched or information for accessing the index key is stored using a search key consisting of a bit string,
The index key is obtained by inserting a specific bit value at a specific bit position of the original index key,
The search key is the original search key with the specific bit value inserted in the same specific bit position as the original index key,
The tree is stored in an array and has tree components up to the n-th stage (n is a positive integer), and is a root node that is a starting point of the tree, and the node reference number 1 includes the root node. A root node arranged in an array element of an array number having a value obtained by adding a base number that is an array number that determines the position of the node and an offset number that is a number that determines the start position of a node in each stage of the tree; A node pair as a component of a tree having two nodes that are a representative node and a non-representative node arranged in the array element, and the node is a branch node or a leaf node, and the branch node is It includes an area for storing the discrimination bit position of the search key, but an area for storing a node type for identifying a branch node and a leaf node. The leaf node does not include an area for storing the array element number of the array element in which the representative node of the representative node pair is arranged, and an area for storing the index key or information for accessing the index key. , Including an area for storing the index key or information for accessing the index key, but not including an area for storing the node type and an area for storing a discrimination bit position of the search key, The representative node is a value obtained by adding the base number and the offset number of the next stage of the nearest higher branch node to the node reference number that is twice the node reference number of the nearest higher branch node of the representative node. A coupled node tree that is arranged in an array element with an array number and the leaf node is located only in the nth stage ,
Based on the node reference number 1 of the root node for starting the search, the offset number and the base number for the node, the array element number of the array element in which the root node is arranged is acquired, and the acquired array number is linked to A search start position setting means to set as an array number of a node;
First to (n- 1 ) th node reading means;
First to (n-1) -th link means;
Index key reading means;
With
The first node reading means reads the root node arranged in the array element from the array element of the array number set as the array number of the link destination node by the search start position setting means,
Said first link means, and the twice the value of the node reference numeral 1 in the first node the search key bit value and the root node of the valve by the bit position of the root node read out by the reading means The sum is set as the node reference number of the link destination node, and the sum of the node reference number, the base number, and the offset number of the next stage of the root node is set as the array number of the link destination node,
The second to (n-1) -th node reading means reads the array element indicated by the array element number of the link destination node set by each of the first to (n-2) -th link means as a branch node,
Said second to n-1 of the link means, respectively the second to the search key bit value and the branch node of the valve by the bit position of the branch node read out by the n-1 node read-out means The sum of two times the node reference number is the node reference number of the link destination node, and the sum of the node reference number, the base number, and the offset number of the next stage of the branch node is the array number of the link destination node Is set as
The index key reading means reads the array elements SEQ ID NO points of the first n-1 link unit sets the destination node as a leaf node, to access the index key or the index key of the reading out the re Funodo Reading the index key directly from the area for storing information for reading, or reading the index key based on information for accessing the index key,
A bit string search device characterized by that.
The bit string search method executed by the bit string search device according to claim 19,
Based on the node reference number 1 of the root node that starts the search, the offset number and the base number for the root node, the array element number of the array element in which the root node is arranged is acquired, and the acquired array number is linked A search start position setting step to set as the array number of the destination node;
First to (n- 1 ) th node reading steps;
First to (n-1) th link steps;
An index key reading step;
With
In the first node reading step, the root node arranged in the array element is read from the array element of the array number set as the array number of the link destination node in the search start position setting step;
In the first link step, and the twice the value of the node reference numeral 1 in the bit value of the search key and the root node of the valve by the bit position of the root node read out at the first node reading step The sum is set as the node reference number of the link destination node, and the sum of the node reference number, the base number, and the offset number of the next stage of the root node is set as the array number of the link destination node,
In the second to (n-1) th node reading steps, the array element indicated by the array element number of the link destination node set in each of the first to (n-2) th link steps is read as a branch node,
Said second to n-1 of the link step, the bit value of the search key of the valve by the bit position of the read branch node respectively the second to n-1 node reading step and the branch node The sum of two times the node reference number is the node reference number of the link destination node, and the sum of the node reference number, the base number, and the offset number of the next stage of the branch node is the array number of the link destination node Is set as
In the index key reading step reads out the array elements SEQ ID NO points of the link destination node set by the n-1 link step as a leaf node, to access the index key or the index key of the reading out by said leaf node Reading the index key directly from the area for storing information for reading, or reading the index key based on information for accessing the index key,
A bit string search method characterized by the above.
  A program causing a computer to execute the bit string search method according to claim 20.   A computer-readable storage medium storing a program for causing a computer to execute the bit string search method according to claim 20. In a data structure of a tree in which an index key consisting of a bit string to be searched or information for accessing the index key used for a bit string search by a search key consisting of a bit string is stored,
The index key is obtained by inserting a specific bit value at a specific bit position of the original index key,
The search key is the original search key with the specific bit value inserted in the same specific bit position as the original index key,
The tree is stored in an array and has tree components up to the n-th stage (n is a positive integer), and is a root node that is a starting point of the tree, and the node reference number 1 includes the root node. A root node arranged in an array element of an array number having a value obtained by adding a base number that is an array number that determines the position of the node and an offset number that is a number that determines the start position of a node in each stage of the tree; A node pair as a component of a tree having two nodes that are a representative node and a non-representative node arranged in the array element, and the node is a branch node or a leaf node, and the branch node is It includes an area for storing the discrimination bit position of the search key, but an area for storing a node type for identifying a branch node and a leaf node. The leaf node does not include an area for storing the array element number of the array element in which the representative node of the representative node pair is arranged, and an area for storing the index key or information for accessing the index key. , Including an area for storing the index key or information for accessing the index key, but not including an area for storing the node type and an area for storing a discrimination bit position of the search key, The representative node is a value obtained by adding the base number and the offset number of the next stage of the nearest higher branch node to the node reference number that is twice the node reference number of the nearest higher branch node of the representative node. Arranged in the array element of the array element number, the leaf node is located only in the nth stage,
By the bit string search device provided with the storage means of the tree,
Based on the node reference number 1 of the root node that starts the search, the offset number and the base number for the root node, the array element number of the array element in which the root node is arranged is acquired, and the acquired array number is linked A search start position setting step to set as the array number of the destination node;
First to (n- 1 ) th node reading steps;
First to (n-1) th link steps;
An index key reading step;
With
In the first node reading step, the root node arranged in the array element is read from the array element of the array number set as the array number of the link destination node in the search start position setting step;
In the first link step, and the twice the value of the node reference numeral 1 in the bit value of the search key and the root node of the valve by the bit position of the root node read out at the first node reading step The sum is set as the node reference number of the link destination node, and the sum of the node reference number, the base number, and the offset number of the next stage of the root node is set as the array number of the link destination node,
In the second to (n-1) th node reading steps, the array element indicated by the array element number of the link destination node set in each of the first to (n-2) th link steps is read as a branch node,
Said second to n-1 of the link step, the bit value of the search key of the valve by the bit position of the read branch node respectively the second to n-1 node reading step and the branch node The sum of two times the node reference number is the node reference number of the link destination node, and the sum of the node reference number, the base number, and the offset number of the next stage of the branch node is the array number of the link destination node Is set as
In the index key reading step reads out the array elements SEQ ID NO points of the link destination node set by the n-1 link step as a leaf node, to access the index key or the index key of the reading out by said leaf node A data structure characterized by enabling execution of a search method for reading out an index key directly from an area for storing information for reading or reading out the index key based on information for accessing the index key.
  24. A computer-readable storage medium storing the data structure according to claim 23.

Images