JP5220057B2 - 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.

First, 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 result of the search process.
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, the acquired array element number is stored in the search path stack, and the array element corresponding to the array element number is read as a node to be referred to. Then, the node type is extracted from the read node, and it is determined whether or not the node type is a branch node.
In this determination, when the read node is a branch node, information on the discrimination bit position is extracted from the node, and further, a bit value corresponding to the extracted discrimination bit position is extracted from the search key. Then, the representative node number is extracted from the node, the bit value extracted from the search key and the representative node number are added, and the process returns to the process of storing the array number acquired in the search path stack described above as a new array number. Perform loop processing.

Thereafter, the above loop processing is repeated until the node type is determined as a leaf node. If the node type is determined to be a leaf node, the index key is extracted from the leaf node as a search result key, and the process ends.

Next, 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, the node 211b stored in the array element having the array element number obtained by adding 1 to the array element number 220a storing the representative node number is linked. Since 2 is stored in the discrimination bit position 231b of the node 211b, the discrimination bit position of the search key “100010” is 0 when the bit value of 2 is viewed, and therefore the array number 221b in which the representative node number is stored is Link to the node 210f stored in the array element.
Since 5 is stored in the discrimination bit position 230f of the node 210f, the discrimination bit position of the search key “100010” is 0 when the bit value of 5 is seen, and therefore the array number 220f in which the representative node number is stored is 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 above description of the search process, the search process is completed by taking out the index key from the node as the search result key. However, the search result key and the search key are further matched, and if they match, the search is successful. If you don't do it, you can make the search fail.

  The leaf nodes of the coupled node tree shown in FIGS. 1A and 1B directly include a leaf node index key, and the search process described above extracts an index key from the leaf node. 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, which 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.

JP 2008-015862 A JP 2008-112240 A JP 2008-269503 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 node reference number, which is a virtual array number of the array element in which the root node is arranged, is 1, and the node reference number of the array element in which the representative node of the node pair to which the branch node is linked is It is obtained by doubling the node reference number of the arranged array element. Therefore, the branch node according to the present invention does not need to include the representative node number.

  Further, according to the present invention, a coupled node tree is configured by inserting a specific bit value “0” or “1” into a specific bit position of an index key to be searched, and similarly, 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.

A leaf node is determined only when the maximum number of stages of a coupled node tree is N. The tree is configured so that only a leaf node exists at the Nth stage and only a leaf node exists at the Nth stage. Is possible.

  Further, according to the present invention, at the beginning of the search process using the search key, the node position [0] and the node position [1] are linked at the link destination in each branch node based on the discrimination bit position of the branch node and the bit value of the search key. Find branch destination information that indicates which branch to branch to. The search process is performed by repeating a link operation that follows the branch destination information of each stage from the root node to the N-th node that is the final stage.

  According to the present invention, since the branch node does not include 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 present invention, in addition to reducing the size of the array in which the coupled node tree is arranged, the branch operation based on the determination of the node type in the search process is deleted, so that 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 structural example of the coupled node tree arrange | positioned at the arrangement | sequence in one Embodiment of this invention. It is a figure which shows notionally the tree structure of the coupled node tree in one Embodiment of this invention. It is a figure explaining the hardware structural example for implementing this invention. It is a figure explaining the concept of the search process in one Embodiment of this invention. It is a figure explaining the example of a processing flow of the search process in one Embodiment of this invention. It is a figure explaining the example of a processing flow which calculates | requires a branch destination arrangement | sequence from a branch node arrangement | sequence with a search key. It is a figure explaining the example of a processing flow which sets branch destination information to a branch destination arrangement | sequence by a discrimination bit position and a search key. It is a figure explaining the example of a processing flow which calculates | requires the node reference number of a leaf node arrangement | sequence based on a branch destination arrangement | sequence. It is a figure explaining the example of a processing flow which calculates | requires the arrangement | sequence number of the node of the next stage from branch destination information. It is a figure explaining the example of a processing flow which calculates | requires the node reference number of a leaf node arrangement | sequence by branch destination information. It is a figure explaining the functional block structural example of the bit string search device in one Embodiment of this invention. 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 one 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 one Embodiment of this invention. It is a figure explaining the example of a processing flow of the process which produces | generates the branch node in one Embodiment of this invention. It is a figure explaining the example of a processing flow of the process which produces | generates the leaf node in one Embodiment of this invention. It is a figure explaining the example of a process flow of the front | former stage of the process which calculates | requires the maximum number of stages of the tree before conversion. It is a figure explaining the example of a processing flow of the back | latter stage of the process which calculates | requires the maximum stage number of the tree before conversion.

Next, the basic concept of the present invention will be described with reference to FIGS.
FIG. 2A is a diagram illustrating a configuration example of a coupled node tree arranged in an array according to an embodiment of the present invention. Compared to the configuration example shown in FIG. 1A, the area for storing the node type is deleted from the leaf node and the branch node, and the area for storing the representative node number from the branch node is eliminated. In the configuration example shown in FIG. 2A, a virtual array number described later is not displayed because it matches the array number.

In this configuration example, leaf nodes are arranged only at the bottom level of the tree. In addition, as the array element in which each node is arranged, an array element having a sequence number from 1 to 15 is used. In the index key and search key, 0 is inserted in the most significant bit which is a specific bit position with respect to the original index key and search key. 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, the specific bit position is used as a discrimination bit position of a dummy branch node, which will be described later, and the dummy branch node is inserted into the tree so that the leaf node is arranged only at the bottom stage of the tree. It is possible.

Referring to FIG. 2A, the root node 401 is arranged in the array element of array number 1 in the array 400. The root node 401 is configured with a discrimination bit position 403. 2 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).

  0 is stored in the discrimination bit position of the node [0] 412, and the link destination is an array of the array number 4 that is twice the array number 2 of the node [0] 412, as indicated by a dotted arrow 440. A node 442 stored in the element. Further, 0 is stored in the discrimination bit position of the node 442, and the link destination is stored in the array element of the array number 4 that is twice the array number 4 of the node 442, as indicated by the dotted arrow 450. Node 452.

Since the node 452 is located at the bottom of the coupled node tree illustrated in FIG. 2A, the node 452 is a leaf node, and the index key 418 stores an index key “00001” in which 0 is inserted in the most significant bit. .
In the example shown in FIG. 2A, 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 403 of the root node 401. Therefore, 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, but in this embodiment, the node type for identifying the leaf node is not used. Dummy branch nodes 412 and 442 whose discrimination bit position is 0 of the most significant bit position are inserted so as to be positioned at the lowest level. Note that the node paired with the dummy branch node 442 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. 2A is empty.

  On the other hand, 4 is stored in the discrimination bit position of the node [1] 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). 5 is stored in the discrimination bit position of the node 422. Further, 6 is stored in the discrimination bit position of the node 423.

A node 432 that is a representative node of the link destination node pair 431 indicated by the dotted-line arrow 430 from the branch node 422 with the array element number 6 is arranged in the array element with the array element number 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. Further, the description of the link destination of the branch node 423 is also omitted.

FIG. 2B is a diagram conceptually showing a tree structure of a coupled node tree in one embodiment of the present invention. When the tree structure shown in FIG. 2B is compared with the tree structure shown in FIG. 1B, as described above, the node type disappears from the branch node and the leaf node, and the representative node number disappears from the branch node. 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 in the vicinity of each node is displayed as [1] with respect to the root node 210a. Also in the description of FIG. 2B, as in the example of FIG. 2A, a virtual array number described later is not displayed because it matches the array number.

Furthermore, when the tree structure shown in FIG. 2B is compared with the tree structure shown in FIG. 1B, in the tree structure shown in FIG. 2B, 0 is added to the most significant bit position of each index key stored in the leaf node. The length is changed from 6 bits to 7 bits. Accordingly, the discrimination bit position of the branch node denoted by the same reference numeral as that of the branch node shown in FIG. 1B is shifted by one, and the value is increased by one.

  Further, since the number of stages in the tree structure shown in FIG. 1B is five, in the tree structure shown in FIG. 2B, leaf nodes are located only at the fifth stage, which is the lowest stage. In the tree structure shown in FIG. 1B, the leaf node located in the hierarchy higher than the fifth level is a dummy branch node whose discrimination bit position is 0. The dummy branch nodes are inserted until the node immediately below the dummy branch node becomes the fifth-stage node.

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

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 search path stack 310 that stores an array 309 in which a coupled node tree is arranged, an array element number in which a node to be traced is stored, and a discrimination bit position and search of a branch node stored in the coupled node tree A data storage device 308 having a branch destination array 311 for storing branch destination information indicating a branch destination determined by the bit value of the discrimination bit position of the key can be realized by the main storage device 305 or the external storage device 306. Alternatively, it is also possible to use a remote device 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 includes the external storage device 306, the search path stack 310, and the branch destination array 311 in the main storage device 305. For example, the array 309 is appropriately hardware depending on the usable hardware environment and the size of the index key set. Obviously the configuration can be selected.
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.

FIG. 4 is a diagram illustrating the concept of search processing according to an embodiment of the present invention.
The array 309 for storing the coupled node tree shown in FIG. 3 is separated into a branch node array 309a for storing branch nodes and a leaf node array 309b for storing leaf nodes. Each array stores a branch node and a leaf node of the coupled node tree 200b shown in FIG. 2B.

  In addition to the array element numbers 730a and 730b, the node reference numbers 720a and 720b are assigned to the array elements of the branch node array 309a and the leaf node array 309b, respectively. Base numbers 700a and 700b are further assigned to the branch node array 309a and the leaf node array 309b, respectively. The node reference numbers are so-called virtual or logical array numbers, and are sequential numbers starting from 1.

The base number is for starting the node reference number of the array element of the array from the first. The sum of the base number and the node reference number is the array number. In the example of FIG. 4, since the top value of the array number 730a of the branch node array 309a is 11, the value of the node reference number 720a starts from 1 by setting the value of the base number 700a to 10. Since the leading value of the array element number 730b of the leaf node array 309b is 51, by setting the value of the base number 700b to 50, the value of the node reference number 720b starts from 1 like the node reference number 720a. It becomes.
By introducing the base number and the node reference number, the degree of freedom of arrangement within the branch node array 309a and the leaf node array 309b can be increased. In addition, the selectivity of the storage means for storing the branch node array 309a and the leaf node array 309b can be increased.
If the base number is 0, the node reference number and the array number are equal. A configuration example of a coupled node tree stored in an array in which the base number is 0 without separating the branch node array and the leaf node array is illustrated in FIG. 2A. Further, FIG. 2B is a diagram conceptually showing a tree structure of a coupled node tree stored in an array in which the base number is 0 without separating the branch node array and the leaf node array.

FIG. 4 further shows a search key 280 and a branch destination array 311. The search key 280 stores a bit string “0011010”.
The array element with the value 1 of the node reference number 720a of the branch node array 309a (hereinafter referred to as the array element of the node reference number 1) has the value 1 (hereinafter referred to as the discrimination bit position) of the root node 220a. 1) is stored, and the bit value at bit position 1 of the bit string stored in the search key 280 is 0, so 0 is stored in the array element of array number 1 in the branch target array.
The branch destination information 0 stored in the array element of the array element number 1 of the branch destination array is obtained by searching the coupled node tree shown in FIG. 2B with the search key 280 in the node pair 210b immediately below the root node 210a. This indicates that the search path branches to the node 210b whose position is 0.

Next, the discrimination bit position 2 of the node 210b is stored in the array element of the node reference number 2 of the branch node array 309a, and the bit value of the bit position 2 of the bit string stored in the search key 280 is 1. 1 is stored in the array element of array element number 2 in the branch target array.
Similarly, the discrimination bit position 3 of the node 211b is stored in the array element of the node reference number 3 of the branch node array 309a, and the bit value of the bit position 3 of the bit string stored in the search key 280 is 1. 1 is stored in the array element of array element number 3 in the branch target array.

In the array element of the node reference number 5 of the branch node array 309a, the discrimination bit position 3 of the node 211c is stored, and the bit value of the bit position 3 of the bit string stored in the search key 280 is 1, so that the branch destination array 1 is stored in the array element of array number 5 in FIG.
The discrimination bit position 6 is stored in the array element of the node reference number 6 of the branch node array 309a, and the bit value of the bit position 6 of the bit string stored in the search key 280 is 0. Therefore, the array number of the branch destination array 0 is stored in the array element 6.

The discrimination bit position 4 is stored in the array element of the node reference number 7 of the branch node array 309a, and the bit value of the bit position 4 of the bit string stored in the search key 280 is 0, so that the array number of the branch destination array 0 is stored in the array element 4.
The discrimination bit position 6 is stored in the array element of the node reference number 10 of the branch node array 309a, and the bit value of the bit position 6 of the bit string stored in the search key 280 is 0. Therefore, the array number of the branch destination array 0 is stored in 10 array elements.

  Since the discrimination bit position 0 of the node 211d is stored in the array element of the node reference number 11 of the branch node array 309a and the bit value of the bit position 0 of the bit string stored in the search key 280 is 0, the branch destination array 0 is stored in the array element of the array element number 11. Similarly, 0 is stored in the array element of the branch destination array 311 indicated by the array element number having the same value as the node reference number of the array element in which the discrimination bit position 0 is stored in the other branch node array 309a.

In one embodiment of the present invention, a branch node array 309a and a leaf node array 309b are generated from a set of bit strings to be subjected to bit string search, and when the search key 280 is designated, the search key 280 and the branch node array As a result, a branch destination array 311 is generated.
Then, the array element number of the leaf node array storing the index key as the search result is obtained from the branch destination array.

  First, the branch destination information stored in the array element indicated by the thick frame of the array number 1 of the branch destination array 311 (hereinafter referred to as the branch destination information of the array number 1) is read, and the array number is doubled. In addition to the value, branch destination information to be read next is stored, and the array element array number is obtained. In the illustration of FIG. 4, as shown by the dotted arrow 220a with the same reference as in FIG. 2B, array number 1 is doubled and 0 is added to determine array number 2. Reads the value 1 of the branch destination information stored in the array element indicated by the thick frame.

Next, as indicated by the dotted arrow 220b, the value 1 of the branch destination information stored in the array element indicated by the thick frame of the array number 2 is read and added to the value obtained by doubling the array number 2 to the array number 5 Ask for.
Further, as indicated by the dotted arrow 221c, the value 1 of the branch destination information stored in the array element indicated by the thick frame of the array number 5 is read, and the array number 11 is added to the value obtained by doubling the array number 5 Ask.

  The next branch destination is the lowest level of the coupled node tree. A value obtained by reading the value 0 of the branch destination information stored in the array element indicated by the thick frame of the array number 11 and adding it to the value obtained by doubling the array number 11 as indicated by the dotted arrow 221i Is subtracted from the maximum node reference number 15 of the branch node array 309a to obtain the node reference number 7 of the leaf node array 309b. The index key “0011010” is extracted from the leaf node 210i stored in the array element with the node reference number 7 of the leaf node array 309b indicated by the thick frame, and the search process is terminated.

  In the example of FIG. 4 described above, it is assumed that the branch node array 309a and the leaf node array 309b are separated. In order to obtain the node reference number 7 of the leaf node array 309b, the branch destination information 0 is assigned to the partition destination array. When the branch node and leaf node are stored in one array, the maximum node reference number 15 of the branch node array 309a is subtracted from the value obtained by adding twice the array number 11 of Since the reference numbers are a series of numbers, it is not necessary to subtract the node reference number of the last array element storing the branch node when obtaining the node reference number of the array element storing the leaf node.

Next, with reference to FIGS. 5 to 7, the search processing in one embodiment of the present invention will be described in detail.
FIG. 5 is a diagram showing an example of a processing flow of search processing in one embodiment of the present invention.

As shown in FIG. 5, first, in step S501, a search key is set. This search key setting corresponds to setting the bit string “0011010” in the search key 280 in the example shown in FIG.
In step S502, a branch destination array is obtained from the branch node array based on the search key. In the example shown in FIG. 4, this process corresponds to the process of generating the branch destination array 311 from the search key 280 and the branch node array 309a described above. The detailed processing flow of step S502 will be described later with reference to FIGS. 6A and 6B.

  In step S503, the node reference number of the leaf node array is obtained based on the branch destination array. In the example shown in FIG. 4, this processing sequentially reads the branch destination information stored in the array elements from the branch destination information stored in array element No. 1 of the branch destination array described above to the array elements of array number 11. This corresponds to the process of obtaining the node reference number of the leaf node array based on the branch destination information stored in the array element of the array element number 11 and the maximum value of the node reference number of the branch node array. A detailed processing flow of step S503 will be described later with reference to FIGS. 7A and 7B.

  Finally, in step S504, the content of the array element of the leaf node array pointed to by the node reference number obtained in step S503 is extracted as an index key, and the process ends. Here, the index key extracted in step S504 can be used as a search result key, or the index key is compared with the search key. If they match, the search can be successful, and if they do not match, the search can be failed.

  FIG. 6A is a diagram illustrating an example of a processing flow for obtaining a branch destination array from a branch node array using a search key, and is a diagram illustrating a detailed processing flow of step S502 illustrated in FIG. In the example shown in FIG. 6A, the number of branch nodes arranged in the branch node array is m.

First, in step S600, 1 is set to the array element number and the node reference number.
In step S601, a bit value indicating branch destination information is assigned to the array element of the branch destination array pointed to by array number 1 using the discrimination bit position and the search key stored in the array element of the branch node array pointed to by node reference number 1. Set.

  Subsequently, in step S602, a bit value indicating branch destination information is assigned to the array element of the branch destination array pointed to by array number 2 by the discrimination bit position stored in the array element of the branch node array pointed to by node reference number 2 and the search key. Set.

  Similarly, in step S603 to step S60m, the array element of the branch destination array indicated by array number 3 to m is determined by the discrimination bit position and the search key stored in the array element of the branch node array indicated by node reference number 3 to m. Is set to a bit value indicating branch destination information.

  In the example of the processing flow illustrated in FIG. 6A, a branch destination array is generated by a branch node array in which a specific number of m branch nodes are arranged, but an assembler macro using the number m as a parameter is used. It is possible to generate a processing flow for realizing a process of generating a branch destination array from a branch node array in which an arbitrary number of branch nodes are arranged.

  Further, as illustrated in FIG. 6A, in correspondence with each discrimination bit position arranged in the branch node array, the branch node array is replaced with a processing flow that sequentially executes processing using the discrimination bit positions. A determination process for determining whether all the processes corresponding to the discrimination bit positions arranged in is completed, and if the process is not completed, the same processing flow including a loop process that repeats the process using the next discrimination bit position is performed. It is clear that a processing result is obtained. Details of steps S601 to S60m will be described with reference to FIG. 6B.

  FIG. 6B is a diagram for explaining an example of a processing flow in which a bit value indicating branch destination information is set in an array element of a branch destination array based on a discrimination bit position and a search key stored in the array element of the branch node array.

  First, in step S610, the contents of the array element pointed to by the node reference number are read from the branch node array as a discrimination bit position. In the first process of step S610, 1 is set as the node reference number in the process of step S600 of FIG. 6A.

  Next, in step S611, the bit value indicated by the discrimination bit position read in step S610 is extracted from the search key, and in step S612, the extracted bit value is stored in the array element of the branch destination array indicated by the array number. Set as. In the first process in step S612, 1 is set as the array element number in the process in step S600 of FIG. 6A.

  In step S613, 1 is added to the array element number. In step S614, 1 is added to the node reference number, and the process is terminated. The processing in steps S610 to S614 described above is sequentially executed for each array element in the branch node array, so that branch destination information can be sequentially set in the array elements in the branch destination array.

  FIG. 7A is a diagram illustrating an example of a processing flow for obtaining a node reference number of a leaf node array based on a branch destination array, and is a diagram illustrating a detailed processing flow of step S503 illustrated in FIG. In the example shown in FIG. 7A, the number of stages of the coupled node tree is n.

First, in step S700, 1 is set as the array element number. Next, in step S701, it is stored in the array element number corresponding to the first node (root node) (hereinafter referred to as the array element number of the first node), that is, the branch destination array indicated by array element 1. The array element number of the second stage node is obtained from the branch destination information.

Subsequently, in step S702, the array element number of the third stage node is obtained from the branch destination information stored in the branch destination array indicated by the array element number of the second stage node.
Similarly, in steps S703 to S70n-2, the fourth to n-1 stages are respectively determined according to the branch destination information stored in the branch destination arrays indicated by the array element numbers of the third to n-2 stage nodes. Find the array number of the eye node. Details of the processing in steps S701 to S70n-2 will be described later with reference to FIG. 7B.

Finally, in step S70n-1, the node reference number of the leaf node array is obtained from the branch destination information stored in the branch destination array indicated by the array element number of the (n-1) th node, and the process is terminated. Details of the processing in step S70n-1 will be described later with reference to FIG. 7C.
Note that the processing flow example illustrated in FIG. 7A uses the coupled node tree of the present embodiment having a specific number of stages n. However, any assembler macro using the number of stages n as a parameter can be used for any of the embodiments. It is possible to generate a processing flow for realizing search processing using a coupled node tree having the number of stages.

  Further, as illustrated in FIG. 7A, processing using the branch destination information is sequentially executed in series corresponding to the branch destination information of the nodes of each stage of the coupled node tree arranged in the branch destination array. In place of the processing flow, a determination process is provided for determining whether the processing corresponding to the branch destination information of the node at the uppermost level of the lowest level has been completed. If not, the branch destination information of the node at the next level It is clear that the same processing result can be obtained by the processing flow including the loop processing that repeats the processing using.

  FIG. 7B is a diagram for explaining an example of a processing flow for obtaining the array number of the next-stage node from the branch destination information, and is a diagram for explaining a detailed processing flow of the processing in steps S702 to S70n-2 shown in FIG. 7A. is there.

  As shown in the figure, first, in step S711, the branch destination information indicated by the array element number is read from the branch destination array. In the first process of step S711, 1 is set as the array element number in the process of step S700 of FIG. 7A.

Next, in step S712, the array element number is doubled, and in step S713, the branch destination information obtained in step S711 is added to the array element number, and the process ends.
The process of FIG. 7B described above is a process indicated by dotted arrows 220a, 220b, and 221c in the example shown in FIG. For example, as indicated by the dotted arrow 220b, the value 1 of the branch destination information stored in the array element indicated by the thick frame of the array number 2 is read, and the array number 5 is obtained by adding to the value obtained by doubling the array number 2 It is processing.

FIG. 7C is a diagram illustrating an example of a processing flow for obtaining a node reference number of a leaf node array based on branch destination information, and is a diagram illustrating a detailed processing flow of step S70n-1 illustrated in FIG. 7A.

  As shown in the figure, first, in step S721, the branch destination information indicated by the array element number of the (n−1) -th node is read from the branch destination array. The array element number of the (n-1) -th node is set by the process in step S70n-2 of FIG. 7A.

  Next, in step S722, the array element number is doubled, and in step S723, a value obtained by adding the branch destination information obtained in step S711 to the array element number is set as the node reference number of the leaf node array.

  In step S724, the value obtained by subtracting the maximum value of the node reference number of the branch node array from the node reference number of the leaf node array set in step S723 is set as the node reference number of the leaf node array, and the process is terminated.

The process of FIG. 7C described above is a process indicated by a dotted arrow 221i in the example shown in FIG.
As described above, when the branch node and the leaf node are stored in one array, the node reference number is a series of numbers. Therefore, when obtaining the node reference number of the array element in which the leaf node is stored, There is no need to decrement the node reference number of the last array element that stores the branch node. Therefore, in that case, the process of step S724 shown in FIG. 7C is deleted from the process flow.

FIG. 8 is a diagram illustrating an example of a functional block configuration of the bit string search device according to the embodiment of the present invention.
The bit string search apparatus 800 according to this embodiment illustrated in FIG. 8 includes a search tree storage unit 810, a search start position setting unit 820, a search key setting unit 850, a branch destination information setting execution unit 802, a branch destination information storage unit 812, A first-stage node branch destination information storage position setting unit 880, a next-stage node branch destination information storage position calculation execution unit 804, and a leaf node output execution unit 806 are provided.

An array is secured in the storage area of the search tree storage unit 810, and a coupled node tree according to an embodiment of the present invention is arranged in the array. As illustrated in FIG. 4, the coupled node tree can be separately arranged in a branch node array that stores branch nodes and a leaf node array that stores leaf nodes.
The search start position setting means 820 sets 1 as the node reference number of the root node as the node reference number of the search start node, and sets 1 as the array element number of the branch destination array that stores the branch destination information. The function of the search start position setting unit 820 corresponds to the process of step S600 shown in FIG. 6A. In the search key setting means 850, a search key is set.

The branch destination information setting execution unit 802 includes branch node reading means 8301 to 830m and branch destination information extracting means 8601 to 860m. m is the number of branch nodes stored in the search tree storage unit 810. In the example shown in FIG. 4, m = 15.
The branch node reading means 8301 to 830m read the contents of the array element indicated by the node reference number from the branch node array arranged in the search tree storage means 810 as the discrimination bit position, and extract branch destination information together with the array number of the branch destination array Output to the means. Then, 1 is added to the array element number of the branch destination array and the node reference number of the branch node array, and the result is output to the next branch node reading means.

The branch destination information extracting means 8601-860m takes out the bit value indicated by the discrimination bit position output from the branch node reading means 8301-830m from the search key set in the search key setting means 850, and uses the bit value as the branch node. It is set as branch destination information in the array element of the branch destination array indicated by the array element number output by the reading means 8301 to 830m. The functions of the branch node reading unit 8301 and the branch destination information extracting unit 8601 correspond to the processing in step S601 shown in FIG. 6A. Similarly, the functions of the branch node reading means and the branch destination information extracting means up to the branch node reading means 830m and the branch destination information extracting means 860m correspond to the processes up to step S60m shown in FIG. 6A.
The branch destination array is secured in the storage area of the branch destination information storage unit 812.

  First stage node branch destination information storage position setting means 880 sets 1 to the array element number of the branch destination array. The function of the first-stage node branch destination information storage position setting means 880 corresponds to the processing in step S700 shown in FIG. 7A.

The next-stage node branch destination information storage position calculation execution unit 804 includes next-stage node branch destination information storage position calculation calculation means 8401 to 840n-2. n is the number of stages in the coupled node tree.

  Next-stage node branch destination information storage position calculation means 8401 to 840n-2 reads the branch destination information pointed to by the array element number from the branch object array, doubles the array element number, and adds the branch destination information to the array element number multiplied by 2. Is obtained as the array element number of the array element of the branch destination array in which the branch destination information corresponding to the next node is stored. The functions of the next-stage node branch destination information storage position calculation means 8401 to 840n-2 correspond to the processes of steps S701 to S70n-2 shown in FIG. 7A, respectively.

The array element number for the next stage node branch destination information storage position calculation means 8401 to read the branch destination information is set by the first stage node branch destination information storage position setting means 880. The array element numbers for the next-stage node branch destination information storage position calculation means 8402 to 840n-2 to read the branch destination information are array numbers obtained by the next-stage node branch destination information storage position calculation means of the previous stage.
The array element number obtained by the next-stage node branch destination information storage position calculation means 840n-2 is input to a leaf node output execution unit 806, which will be described next, and used for reading the leaf node.

The leaf node output execution unit 806 includes a leaf node storage position calculation unit 8061 and a search result output unit 8062.
The leaf node storage position calculation means 8061 reads the branch destination information pointed to by the array number obtained by the next-stage node branch destination information storage position calculation means 840n-2, doubles the array number, and branches to the array number that is doubled. A value obtained by adding information is obtained as a temporary node reference number of the array element of the leaf node array. Then, a value obtained by subtracting the maximum value of the node reference numbers in the branch node array from the temporary node reference number, that is, the number m of branch nodes stored in the search tree storage unit 810 is used as the node reference number of the array element in the leaf node array. Ask. The function of the leaf node storage position calculation means 8061 corresponds to step S70n-1 in FIG. 7A, that is, the processing shown in FIG. 7C.

The search result output unit 8062 reads the leaf node from the search tree storage unit 810 based on the node reference number of the array element of the leaf node array obtained by the leaf node storage position calculation unit 8061, and accesses the index key or the index key. Retrieve information. 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.

Next, generation of a coupled node tree according to an embodiment of the present invention will be described. In the following description, a coupled node tree according to an embodiment of the present invention may be referred to as a pointerless tree, and a 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. Then, the generation of the pointerless tree is realized by sequentially traversing the nodes of the tree from the root node and converting them into the nodes of one embodiment of the present invention.
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. 9A is a diagram illustrating an example of a processing flow in the previous stage of processing for generating a pointerless tree according to an embodiment of the present invention. As shown in FIG. 9A, first, in step S901, an array (branch node array and leaf node array) for generating a pointerless tree is acquired, and in step S902, array elements are initialized. The processing in step S902 is necessary to use a dummy branch node.

Next, in step S902a, the maximum number of stages of the tree before conversion is obtained, and in step S902b, the maximum number of stages is set as the upper limit value of the stage number counter.
Details of the processing in step S 9 02a, with reference to FIGS. 12A and 12B will be described later.

  In step S903, the base numbers of the branch node array and the leaf node array are set, and in step S905, 1 is set in the stage number counter. In step S906, 1 is set as the node reference number, and in step S907, the array element number of the root node of the tree is set as the array element number. Further, in step S908, the array element number and the count value of the stage number counter are stored in the search path stack, and the process proceeds to step S913 shown in FIG. 9B.

FIG. 9B is a diagram showing an example of a processing flow at the latter stage of the processing for generating the pointerless tree in one embodiment of the present invention. As illustrated in FIG. 9B, in step S913, 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 the first process of step S913, the array element number of the root node is set to the array element number in step S907. In the second and subsequent processing, have in step S920 to be described later is set at step S928. In the following description, the node read in step S913 may be referred to as a tour start node.

In step S915, the node type is extracted from the node read in step S913. In step S916, it is determined whether the extracted node type indicates a branch node. If it is determined in step S916 that the node type does not indicate a branch node but indicates a leaf node, the process proceeds to step S922. If the node type indicates a branch node, the process proceeds to step S916a.

  In step S916a, the node is written to the array element of the branch node array based on the node reference number. Details of the processing in step S916a will be described later with reference to FIG.

In step S917, a value of 1 is added to the stage number counter, and the flow advances to step S918 to double the node reference number. In step S919, the representative node number is extracted from the node read in step S913. In step S920, a value obtained by adding the value 0 to the extracted representative node number is set as the array number.
In step S921, the array element number and the count value of the stage number counter are stored in the search path stack, and the process returns to step S913. Here, since the array element number stored in the search path stack is the value obtained by adding the value 0 to the representative node number in step S920, it is the array element number of the node [0].

  The loop processing from step S913 to step S921 described above is repeated until the node type indicates a leaf node in step S916. 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. 9B, since the array node number is set by adding the value 0 to the representative node number in step S920, the node [0] side is preferentially visited. 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.

On the other hand, in step S916, the node type is determined not to indicate a branch node but to indicate a leaf node. When the process proceeds to step S922, the node is written to the array element of the leaf node array based on the node reference number. Details of the processing in step S922 will be described later with reference to FIG.

In step S923, 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.
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 S924.

  In step S924, the array element number and the count value of the stage number counter are extracted from the search path stack, and the stack pointer of the search path stack is decremented by one. Next, in step S928, the value 1 is added to the array element number extracted in step S924 to obtain the array element number of the node [1] as the array element number of the tour start node. In step S930, 1 is added to the node reference number, and the process returns to step S913.

  The loop processing of steps S913 to S930 described above is repeated until it is determined in step S923 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. 10 is a diagram illustrating an example of a processing flow of processing for generating a branch node according to an embodiment of the present invention, and is a diagram illustrating details of processing in step S916a illustrated in FIG. 9B.

  As shown in the figure, first, in step S1025, a value obtained by adding the base number of the branch node array to the node reference number is set to the array element number. In step S1026, the discrimination bit position is extracted from the node. In step S1027, a value of 1 is added to the discrimination bit position. In step S1028, the discrimination bit position is added to the array element of the branch node array pointed to by the array element number set in step S1025. Is generated, a branch node is generated, and the process is terminated.

  FIG. 11 is a diagram illustrating an example of a processing flow of processing for generating a leaf node according to an embodiment of the present invention, and illustrates details of the processing in step S922 illustrated in FIG. 9B.

As shown in the figure, first, in step S1129, the node reference number and the stage number counter are saved, and the process proceeds to step S1130.
In step S1130, it is determined whether the stage number counter is an upper limit value. If not, the node reference number is doubled in step S1131, value 1 is added to the stage number counter in step S1132, and the process returns to step S1130.

  The loop processing of steps S1130 to S1132 described above is for placing leaf nodes at the lowest level of the pointerless tree. In the example of FIGS. 1B and 2B, 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. 2B. Then, the position information of the node 210c in FIG. 2B is saved by the process of step S1129 in FIG.

The upper limit value of the stage number counter is set in step S902b shown in FIG. 9A. 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 according to the embodiment of the present invention is generated, the maximum value can be used as the upper limit value of the stage number counter.

If it is determined in step S1130 that the stage number counter is the upper limit value, the process proceeds to step S1134. In step S1134, a numerical value of a power of 2 is obtained by subtracting 1 from the upper limit value of the stage number counter, and the sum of the value obtained by subtracting the numerical value from the node reference number and the base number of the leaf node array is calculated . Set to array number. In the example of FIG. 2B, the upper limit value of the stage number counter is 5, and the power of 2 by the value obtained by subtracting 1 from the upper limit value is 16. A value 15 obtained by subtracting 1 from this value is the number of branch nodes arranged in the branch node array. Here, since the node reference number is the node reference number of the branch node array, the value obtained by subtracting 15 from this node reference number is the node reference number of the leaf node array as described in the example of FIG. Then, the array element number is obtained from the sum of the node reference number and the base number.

In step S1135, the index key is extracted from the node read in step S913 shown in FIG. 9B. In step S1136, a bit value “0” is inserted into the most significant bit position of the index key. The index key is written in the array element of the leaf node array pointed to by the array element number set in step S1134, a leaf node is generated, and the process proceeds to step S1138.
In step S1138, the node reference number and stage number counter saved in step S1129 are set in the node reference number and stage number counter, respectively, and the process ends.

Next, processing for obtaining the maximum number of levels of a tree before conversion will be described with reference to FIGS. 12A and 12B. The processing flow example shown in FIGS. 12A and 12B explains details of the processing in step S902a shown in FIG. 9A.
FIG. 12A is a diagram for explaining an example of the processing flow of the previous stage of the process for obtaining the maximum number of stages of the tree before conversion.

As shown in FIG. 12A, first, in step S1201, a value 1 is set in the stage number counter, and in step S1202, 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.
In step S1207, the array element number is set to the array node number of the root node of the tree, and the process advances to step S1213 shown in FIG. 12B.

12B is a drawing describing the processing flow example of a stage after the process for obtaining the maximum number of the previous tree transformation. As shown in FIG. 12B, in step S1213, 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 the first process of step S1213, the array element number is set to the array element number of the root node in step S1207. In the second and subsequent processing, it is set in step S1220 or step S1228 described later. Similar to the description in FIG. 9B, in the following description, the node read in step S1213 may be referred to as a tour start node.

In step S1215, the node type is extracted from the node read in step S1213. In step S1216, it is determined whether the extracted node type indicates a branch node. If the determination in step S1216 indicates that the node type does not indicate a branch node but a leaf node, the process proceeds to step S1221, and if the determination indicates a branch node, the process proceeds to step S1217.

In step S1217, a value of 1 is added to the stage number counter, the process proceeds to step S1219, the representative node number is extracted from the node read in step S1213, and in step S1220, the value obtained by adding the value 0 to the extracted representative node number is arranged. Set to a number.
In step S1220a, the array element number and the count value of the stage number counter are stored in the search path stack, and the process returns to step S1213. Here, since the array element number stored in the search path stack is the value obtained by adding the value 0 to the representative node number in step S1220, it is the array element number of the node [0].

  The loop processing from step S1213 to step S1220a described above is repeated until the node type indicates a leaf node in step S1216. That is, as a group of processes, the number of leaf nodes is obtained by circulating the nodes from the tour start node to the first leaf node. In the processing flow example shown in FIG. 12B, since the array node number is set by adding the value 0 to the representative node number in step S1220, the node [0] side is circulated in preference to the node. 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.

On the other hand, if it is determined in step S1216 that the node type indicates not a branch node but a leaf node, the process proceeds to step S1221, and it is determined whether or not the count value of the stage number counter is greater than the value set in the maximum stage number counter. . If the determination result in step S1216 is that the count value of the stage number counter is larger than the value set in the maximum stage number counter, in step S1222, the count value of the stage number counter is set in the maximum stage number counter, and the process proceeds to step S1223. If the determination result indicates that the count value of the stage number counter is not larger than the value set in the maximum stage number counter, the process proceeds to step S1223.

In step S1223, 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.
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 the number of stages for all the leaf nodes of the tree has been completed. Otherwise, the process proceeds to step S1224.

  In step S1224, the array element number and the count value of the stage counter are extracted from the search path stack, and the stack pointer of the search path stack is decremented by one. Next, in step S1228, the value 1 is added to the array element number extracted in step S1224 to obtain the array element number of the node [1] as the array element number of the cyclic start node, and the process returns to step S1213.

  The loop processing of steps S1213 to S1228 described above is repeated until it is determined in step S1223 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 levels of the tree is obtained.

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.
It is also clear that the bit string search device according to an embodiment of the present invention can be constructed on a computer by a program that causes the computer to execute the processes illustrated in FIGS.
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 array 101 node 102 node type 103, 403 discrimination bit position 104 representative node number 118, 418 index key 200, 200b coupled node tree 210a, 401 root node 280 search key 301 data processing unit 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 309a Branch node array 309b Leaf node array 310 Search path stack 311 Branch destination array 700a, 700b Base number 720a, 720b Node reference number 730a, 730b array Number 800 Bit string search device 802 Branch destination information setting execution unit 804 Next node branch destination information storage position calculation execution unit 806 Leaf Node output execution unit 810 Search tree storage means 812 Branch destination information storage means 820 Search start position setting means

Claims (6)

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 nth stage (n is a positive integer),
A root node which is a root node which is a starting point of the tree, and which is arranged in an array element having an array number having a value obtained by adding a base number which is a number for determining the position of the top array element of the array to node reference number And a node pair as a component of a tree having 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 arrangement of representative nodes of the nearest lower-level node pair that is a link destination Stores the area for storing the array element number of the array element and 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 a discrimination bit for the search key. An array of values obtained by adding the base number to a node reference number that is twice the node reference number of a branch node immediately above the representative node, the area not including an area for storing a position Search tree storage means for storing a coupled node tree, which is arranged in an array element of a number, and the leaf node is located only in the nth stage;
Branch destination information storage means for storing a branch destination array for storing the bit value of the bit position matching the discrimination bit position of each branch node of the search key as branch destination information corresponding to the branch node;
The branch nodes are read from the coupled node tree stored in the search tree storage means in the order of node reference numbers, the branch destination information is extracted by the discrimination bit position of the branch node and the search key, and the array number of the branch destination array A branch destination information setting execution unit for sequentially setting each array element from one array element;
The branch destination information stored in the array element of array number 1 set in the branch destination array is read as branch destination information of the first node of the coupled node tree, and the array number is read in the read branch destination information. A value obtained by adding a value obtained by doubling 1 is used as an array element number of the array element of the branch destination array in which the branch destination information of the second stage node of the coupled node tree is stored. The value obtained by adding twice the array element number of the array element in which the branch destination information of the second stage node is stored to the branch destination information of the second node is obtained as the third stage of the coupled node tree. As the array element number of the array element of the branch destination array in which the branch destination information of the node is stored, the branch destination information of the own node is stored in the branch destination information of the own node. Add the doubled sequence number The obtained value is used as the array element number of the array element of the branch destination array in which the branch destination information of the next node of the coupled node tree is stored. A next-stage node branch destination information storage position calculation execution unit that obtains the array element number of the branch destination array in which the branch destination information of the n−1-th stage node of the coupled node tree is stored,
The branch destination information of the (n−1) -th stage node of the coupled node tree is read from the branch destination array according to the array number obtained by the next-stage node branch destination information storage position calculation execution unit, and the read branch destination information A leaf node output execution unit that obtains a storage position of the leaf node based on the array number, and reads the leaf node stored in the storage position from the coupled node tree stored in the search tree storage unit;
A bit string search device comprising:
The bit string search device according to claim 1, wherein
The array for storing the coupled node tree includes a branch node array for storing branch nodes and a leaf node array for storing leaf nodes, and the branch node array is an array for storing the coupled node tree. It is the same as the part storing the elements of the tree up to the n-1 stage of the coupled node tree,
The leaf node output execution unit obtains branch destination information of the n−1-th stage node of the coupled node tree from the branch destination array based on the array number obtained by the next-stage node branch destination information storage position calculation execution unit. Read, obtain the node reference number of the leaf node array obtained by subtracting the maximum value of the node reference number of the branch node array from the sum of the read branch destination information and the value obtained by doubling the array number, and the node of the leaf node array A coupled node stored in the search tree storage means is obtained as an array number of a value obtained by adding a base number which is a number for determining the position of the first array element of the leaf node array to a reference number as a storage position of the leaf node Read the leaf node stored in the storage location from the tree, read the index key from the leaf node, or index Bit string search apparatus characterized by reading the index key based on the information for accessing the key. The bit string search method executed by the bit string search device according to claim 1,
The branch nodes are read from the coupled node tree stored in the search tree storage means in the order of node reference numbers, the branch destination information is extracted by the discrimination bit position of the branch node and the search key, and the array number of the branch destination array A branch destination information setting step for sequentially setting each array element from one array element;
The branch destination information stored in the array element of array number 1 set in the branch destination array is read as branch destination information of the first node of the coupled node tree, and the array number is read in the read branch destination information. A value obtained by adding a value obtained by doubling 1 is used as an array element number of the array element of the branch destination array in which the branch destination information of the second stage node of the coupled node tree is stored. The value obtained by adding twice the array element number of the array element in which the branch destination information of the second stage node is stored to the branch destination information of the second node is obtained as the third stage of the coupled node tree. As the array element number of the array element of the branch destination array in which the branch destination information of the node is stored, the branch destination information of the own node is stored in the branch destination information of the own node. Add the doubled sequence number The obtained value is used as the array element number of the array element of the branch destination array in which the branch destination information of the next node of the coupled node tree is stored. The next-stage node branch destination information storage position calculation step for obtaining the array element number of the array element of the branch destination array in which the branch destination information of the n-1 stage node of the coupled node tree is stored,
Based on the array element number obtained in the next-stage node branch destination information storage position calculation step, the branch destination information of the (n−1) -th stage node of the coupled node tree is read from the branch destination array, and the read branch destination information and A leaf node output step of obtaining a storage position of the leaf node based on the array number and reading the leaf node stored in the storage position from the coupled node tree stored in the search tree storage unit;
A bit string search method comprising: The bit string search method according to claim 3, wherein
The array for storing the coupled node tree includes a branch node array for storing branch nodes and a leaf node array for storing leaf nodes, and the branch node array is an array for storing the coupled node tree. It is the same as the part storing the elements of the tree up to the n-1 stage of the coupled node tree,
The leaf node output step reads the branch destination information of the n−1-th stage node of the coupled node tree from the branch destination array according to the array element number obtained in the next node branch destination information storage position calculation step, The node reference number of the leaf node array is obtained by subtracting the maximum value of the node reference number of the branch node array from the sum of the read branch destination information and the value obtained by doubling the array number. the determined sequence number of the value obtained by adding the head base number position is a number defining the array elements of leaf nodes arranged as a storage position of the leaf node, the coupled node stored before dangerous search tree storing means Read the leaf node stored at the storage location from the tree, read the index key from the leaf node, or Bit string search method characterized by reading the index key based on the information for accessing the Kusuki.
  A program for causing a computer to execute the bit string search method according to claim 3 or 4.   A computer-readable storage medium storing a program for causing a computer to execute the bit string search method according to claim 3 or 4.

Images