+

WO2008004335A1 - dispositif de recherche de séquence de bits, procédé de recherche et programme - Google Patents

dispositif de recherche de séquence de bits, procédé de recherche et programme Download PDF

Info

Publication number
WO2008004335A1
WO2008004335A1 PCT/JP2007/000639 JP2007000639W WO2008004335A1 WO 2008004335 A1 WO2008004335 A1 WO 2008004335A1 JP 2007000639 W JP2007000639 W JP 2007000639W WO 2008004335 A1 WO2008004335 A1 WO 2008004335A1
Authority
WO
WIPO (PCT)
Prior art keywords
node
search
key
tree
branch
Prior art date
Application number
PCT/JP2007/000639
Other languages
English (en)
French (fr)
Inventor
Toshio Shinjo
Original Assignee
S.Grants Co., Ltd.
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by S.Grants Co., Ltd. filed Critical S.Grants Co., Ltd.
Priority to DE602007013905T priority Critical patent/DE602007013905D1/de
Priority to EP07766946A priority patent/EP2048584B1/en
Priority to CN2007800255634A priority patent/CN101484895B/zh
Priority to US12/308,560 priority patent/US8073874B2/en
Publication of WO2008004335A1 publication Critical patent/WO2008004335A1/ja
Priority to US12/385,956 priority patent/US8150856B2/en

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/903—Querying
    • G06F16/90335—Query processing
    • G06F16/90344—Query processing by using string matching techniques
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F16/31—Indexing; Data structures therefor; Storage structures
    • G06F16/316—Indexing structures
    • G06F16/322—Trees

Definitions

  • Bit string search device search method and program
  • the present invention relates to a search device for searching for a desired bit string from a set of bit strings, and particularly to a technical field in which a data structure for storing bit strings is devised to improve search speed and the like.
  • index keys are expressed as bit strings, it can be said that the database search results in a bit string search.
  • FIG. 17 shows an example of a Patricia tree used in the above-described conventional search processing.
  • the Patricia tree node includes an index key, a check bit position of the search key, and left and right link pointers.
  • the node contains information to access the record corresponding to the index key, although it is not specified.
  • the node 1750a holding the index key “100010” is the root node, and the check bit position is 0.
  • Node 1750a has left link 1740a connected to node 1750b and right link 174 ⁇ i — 17501 ⁇ .
  • the index key held by the node 1750b is "010011", and the check bit position 1730b is 1.
  • Node 1750c is connected to left link 1740b of node 1750b, and node 1750d is connected to right link 1741b.
  • the index key held by the node 1750G is “000111”, and the check bit position is 3.
  • the index key held by the node 1750d is “011010” and the check bit position is 2.
  • the right pointer 1741d of the node 1750d points to the node 1750d itself, and the node 1750e is connected to the left link 1740d.
  • the index key held by 1750e is "010010" and the check bit position is 5.
  • the left pointer 1740e of the node 1750e points to the node 1750b, and the right pointer 1741e points to the node 1750e.
  • the index key held by the node 1750f is "101011", and the check bit position 1730f is 2.
  • Node 1750g is connected to left link 1740f of node 1750f, and node 1750h is connected to right link 1741f.
  • the index key held by the node 1750g is "100011", and the check bit position 1730g is 5.
  • the left pointer 1740g of node 1750g points to node 1750a, and the right pointer 1741g points to node 1750g.
  • the index key held by the node 1750h is "101100", and the check bit position 1730h is 3.
  • the left pointer 1740h of node 1750h points to node 1750f, and the right pointer 1741h points to node 1750h.
  • the check bit position of each node is configured to increase as the tree descends from the root node 1750a.
  • Patent Document 1 there is a technique disclosed in Patent Document 1 below to attempt to eliminate the disadvantages of these Patricia trees.
  • the lower left and right nodes are stored in a continuous area to reduce the pointer storage capacity, and whether the next link power ⁇ / link By providing each node with a bit indicating whether or not, the back link determination process is reduced.
  • Patent Document 1 Japanese Patent Laid-Open No. 2 0 0 1 _ 3 5 7 0 70
  • the problem to be solved by the present invention is a data structure of a bit string to be searched for, which requires a small storage capacity, a high search speed, and an easy data maintenance data structure. It is to provide a bit string search device and a search method provided.
  • a tree having the following data structure named as a coupled node tree is provided.
  • an index key is searched using this coupled node tree. .
  • the coupled node tree of the present invention includes a branch node having linked data and a leaf node having an index key to be searched.
  • the tree structure is composed of a root node and a node pair of a branch node and leaf nodes or branch nodes or leaf nodes arranged in adjacent storage areas.
  • the branch node includes a discrimination bit position of a search key and a representative node number for linking to a representative node which is one of the linked node pairs, and the leaf node is composed of a bit string to be searched. Contains the index key.
  • the root node is a branch node except when there is only one node in the tree.
  • the discrimination bit position of the search key is the same as the check bit position of the Patricia tree in that the bit value at that position of the search key is used, but in the Patricia tree, the bit value of the check bit position is determined to determine the link destination.
  • the coupled node tree of the present invention is different in that the bit value at the discrimination bit position is used in the calculation for obtaining the link destination node.
  • Execution of a search using a search key is performed on one node of a link destination node pair according to the bit value of the search key at the discrimination bit position included in the branch node at each branch node including the root node. Linking is done by sequentially repeating until the leaf node.
  • the index key held by the leaf node is compared with the search key, and if they match, the search is successful. If they do n’t match, No index key matches the search key.
  • a search is first performed using the index key as a search key, and the index key of the found leaf node is acquired. Also, branch node numbers up to the leaf note are stored in the stack sequentially from the root node.
  • a size comparison and a bit string comparison are performed between the index key to be added and the index key acquired by the search, and the first (most significant) bit position and a bit value that are different in the bit string comparison are stored in the stack.
  • the insertion position of the node pair to be added is determined by the relative positional relationship with the discrimination bit position of the branch node, and the leaf node including the index key to be added by the size relationship is set as which node of the node pair to be added To decide.
  • the force Pludno-Dolly according to the present invention has a tree structure composed of node pairs, and the size of the index key set can be made compact.
  • a node that requires pointer information has a pointer information, but an area for an index key is required.
  • a node that requires an index key does not need an area for a pointer, so there is no waste in the storage area. Also, there is no need for backlink processing like Patricia Tree.
  • the pointer can be an array number, and the required storage capacity can be further reduced.
  • the storage capacity for storing the tree structure used for the search can be reduced, and the search processing load can be reduced accordingly.
  • the branch node is arranged so as to hold the discrimination bit position defined by the bit string configuration of the index included in the coupled node tree, so only the processing at the required bit position is performed. The burden is small. Also, the bit value at the discrimination bit position is not used for determination processing but for calculation processing, so the CPU processing burden is reduced in this respect as well.
  • Coupled node tree insertion processing and deletion processing are simple, and the maintenance burden is reduced.
  • bit string search device that can execute a bit string search at high speed and can easily perform data maintenance is provided.
  • FIG. 1 is a diagram for explaining a configuration example of a coupled node tree stored in an array.
  • FIG. 2 is a diagram for explaining a structure of a force Prudno-Dolly.
  • FIG. 3 is a diagram for explaining an example of a hardware configuration for carrying out the present invention.
  • FIG. 4 is a flowchart showing search processing in an embodiment of the present invention.
  • FIG. 5 is a diagram showing a processing flow of search processing, which is the first stage of insertion processing in one embodiment of the present invention.
  • FIG. 6 is a diagram illustrating a processing flow for preparing an array element for a node pair to be inserted in the insertion processing in one embodiment of the present invention.
  • FIG. 7 is a diagram showing a processing flow for finding a position to insert a node pair, writing the contents of each node of the node pair, and completing the insertion process.
  • FIG. 8 is a process flow diagram illustrating an entire node insertion process when adding an index key including a root node insertion process according to an embodiment of the present invention.
  • FIG. 10 illustrates a processing flow subsequent to deletion processing according to an embodiment of the present invention.
  • FIG. 1 1A A diagram illustrating a coupled node tree before deletion processing and a deletion key "01 1 01 0".
  • FIG. 11B is a diagram illustrating a coupled node tree after deletion processing.
  • FIG. 12A is a diagram for explaining a coupled node tree and an insertion key “001 1” before insertion processing.
  • FIG. 12B is a diagram illustrating a coupled node tree after insertion processing.
  • FIG. 13 is a diagram for explaining the flow of processing blocks in the search process that is the first stage of the insertion process shown in FIG. 5.
  • FIG. 14 is a diagram for explaining a flow of a processing block for preparing array elements for the node pair to be inserted shown in FIG.
  • FIG. 15 is a diagram for explaining the processing flow for obtaining the position on the coupled node of the node pair to be inserted in the first half of the processing shown in FIG.
  • FIG. 16 is a diagram for explaining the processing flow for completing the insertion processing by setting data in each node in the latter half of the processing shown in FIG.
  • FIG. 17 is a diagram showing an example of a Patricia tree used in a conventional search. BEST MODE FOR CARRYING OUT THE INVENTION
  • Data indicating the link destination position held by a branch node can also be used as address information of a storage device.
  • Array consisting of array elements that can store the larger storage capacity of the area occupied by a branch node or leaf node
  • the position of the node can be expressed by an array number, and the amount of position information can be reduced.
  • FIG. 1 is a diagram illustrating a configuration example of a coupled node tree stored in an array.
  • node 1 01 is placed in the array element of array number 1 0 of array 100.
  • Node 1 01 is node type 1 02, discrimination bit position 1 03 and representative node number No. 104.
  • Node type 102 is 0, indicating that node 101 is a branch node. 1 is stored in the discrimination bit position 103.
  • the representative node number 104 the array number 20 of the representative node of the link destination node pair is stored.
  • the array number stored in the representative node number is sometimes referred to as the representative node number.
  • 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 of array element number 20 stores node [0] 112, which is the representative node of node pair 111.
  • the next adjacent array element (array number 20 + 1) stores node [1] 113 paired with the representative node.
  • the node type further IJ1 14 of node [0] 112 stores 0, the discrimination bit position 115 stores 3, and the representative node number 116 stores 30.
  • 1 is stored in the node type 117 of the node [1] 113, which indicates that the node [1] 113 is a leaf node.
  • the index key 118 stores “0001”. As described above for the Patricia tree, it is natural that the leaf node contains information for accessing the record corresponding to the index key, but the notation is omitted.
  • a representative node may be represented by a node [0] and a pair of nodes may be represented by a node [1].
  • 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.
  • 0 or 1 assigned to the stored array elements of the node [0] 112, the node [1] 113, the node 122, and the node 123 is a node pair when a search is performed using a search key. Which node is linked to.
  • the search key bit value 0 or 1 in the discrimination bit position of the preceding branch node is linked to the node of the array number with the representative node number added.
  • the array element number of the array element in which the link destination node is stored can be obtained.
  • the representative node number is the smaller of the array element numbers in which the node pairs are arranged, but it is obvious that the larger one can be adopted.
  • Figure 2 is a diagram conceptually showing the tree structure of a coupled node tree.
  • the 6-bit index key shown in the figure is the same as the one of the patricia illustrated in FIG.
  • Reference numeral 210a indicates a root node.
  • the root node 210 a is a representative node of the node pair 201 a arranged at the array element number 220.
  • 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 201 are arranged below the node pair 201f.
  • g is arranged.
  • a node pair 201 d is arranged under the node pair 201 c, and a node pair 201 e is arranged therebelow.
  • the code 0 or 1 added in front of each node is the same as the code assigned in front of the array element described in FIG. According to the bit value of the discrimination bit position of the search key, the leaf node to be searched is found by following the tree.
  • 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 stored array element of the representative node 210b of the node pair 201b.
  • the node pair 201b is composed of nodes 210b and 21 1b, 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 in which the representative node 210c of the node pair 201c is stored is stored in the link destination representative node number.
  • this node is a leaf node, and therefore includes an index key.
  • the index key 250c contains "0001 1 ⁇ .
  • the node 21 1 c The type 261G is 0, the discrimination bit position 231G is 2, and the representative node number stores the array element number 221G of the array element in which the representative node 21 Od of the node pair 201d is stored.
  • the node type 261d of the node 211d that is 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, and the index keys 250e and 251e are index keys. “010010” and “010011” are stored.
  • [0044] 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 representative node number of the node pair 201f is 21 Of in the representative node number of the link destination.
  • the array element number 221b of the stored array element is stored.
  • the node types 260f and 261f of the nodes 21Of 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 array node number 220f of the array element in which the representative node 210g of the node pair 201g is stored is stored in the representative node number of the node 210f, and the node [0] that is the representative node of the node pair 201h is stored in the representative node number of the node 211f.
  • Array number 221 f of the stored array element of 210h is stored.
  • Node types 210g and 211g of node pair 201g are both 1, indicating that both are leaf nodes. "100010" and “100011" for index keys 250g and 251g, respectively. Is stored.
  • node [0] 210h which is the representative node of node pair 201h, and node pair [1] 211h, node types 260h and 261h are both 1, indicating that both are leaf nodes.
  • Each index key 250h, 251h contains "10101 1" and "101100".
  • the discrimination bit position is 0, 1, 2, ⁇ ⁇ 'from the left. First, processing is started from the root node 210a using the bit string “100010” as a search key.
  • the bit value of the discrimination bit position 0 of the search key “100010” is 1. Therefore, link is made to the node 21 1 b stored in the array element of the array element number obtained by adding 1 to the array element number 220a storing the representative node number. Since 2 is stored in the discrimination bit position 231 b of the node 21 1 b, the bit value of the discrimination bit position 2 of the search key “100010” is 0, so the array in which the representative node numbers are stored The node 2101 ⁇ stored in the array element with the number 221 b is linked.
  • node type 260g of node 210g is 1, indicating that it is a leaf node, when index key 250g is read and compared with the search key, both are "100010" and match. In this way, a search using a coupled node tree is performed.
  • the configuration of a coupled node tree is defined by a set of index keys.
  • the discrimination bit position of the root node 210a is 0 because the index key illustrated in FIG. 2 includes the 0th bit having 0 and the 1st bit.
  • the group of index keys whose 0th bit is 0 is classified under the node 210b, and the group of index keys whose 0th bit is 1 is classified under the node 21 1b.
  • the discrimination bit position of node 21 1 b is 2 because the 0th bit stored in nodes 21 1 h, 210h, 21 1 g, and 2 10g is 0 for all 1st bits of the index key. And reflects the nature of the set of index keys, with the first bit being different for the first time.
  • the case where the second bit is 1 is classified on the node 21 1 f side
  • the case where the second bit is 0 is classified on the node 210f side. Since the second bit key ⁇ 1 has an index key different from the third bit, 3 is stored in the discrimination bit position of the node 21 1 f, and the second bit key ⁇ 0 has an index key of the third bit. Since the 4th bit is the same and the 5th bit is different, 5 is stored in the discrimination bit position of the node 210f.
  • nodes 210h and 211h are leaf nodes, respectively. “101011” and “101100” are stored in 250h and 251h.
  • the structure of the coupled node tree is determined by the bit value of each bit position of each index key included in the set of index keys.
  • the index key follows the route placed on the force node tree. For example, if the search key is "10110 0", the node 211h can be reached. Also, as you can imagine from the above explanation, even when "101101" force and "101110" are used as search keys, it reaches node 211h and it can be seen that the search failed by comparing with index key 251h. .
  • the nodes 210a, 211b, 210f In the link path the 3rd and 4th bits of the search key are not used, and the 5th bit of "100100" is 0, so the node reaches 210 g as in the case of searching for "100010". become. In this way, branching is performed using the discrimination bit position corresponding to the bit configuration of the index key stored in the coupled node tree.
  • FIG. 3 is a diagram for explaining an example of a hardware configuration for carrying out the present invention.
  • Search processing and data maintenance by the search device of the present invention are performed by the data processing device 301 including at least the central processing unit 302 and the cache memory 303 using the data storage device 308.
  • 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 Alternatively, it is possible to use a remote device connected via the communication device 307.
  • the main storage device 305, the external storage device 306, and the communication device 307 are connected to the data processing device 301 by the single bus 304, but the connection method is not limited to this.
  • the main storage device 305 can be in the data processing device 301, and the search path stack 310 can be realized as a hard disk in the central processing unit 302.
  • the array 309 has the external storage device 306 and the search path stack 310 in the main storage device 305, and it is clear that the hardware configuration can be selected appropriately according to the available hardware environment, the size of the index key set, etc. It is.
  • FIG. 4 is a flowchart showing search processing according to an embodiment of the present invention. The search processing algorithm will be described with reference to Figure 2 as appropriate.
  • the array element number of the root node of the coupled node tree to be searched is acquired (step S401). Since a coupled node tree can be identified by its root node array number, the coupled node tree can be managed using the root node array number. Therefore, it is assumed that the root node array number of the coupled node tree is registered in the coupled node tree management means.
  • the above-described coupled node tree management means stores, for example, a program on a program that causes a computer to execute the search process. It can be an area.
  • search system When a search system using a plurality of coupled node trees is mounted on one computer system, the search system can be provided outside each search program.
  • this corresponds to obtaining SEQ ID NO: 220.
  • the acquisition of the array number of the root node is not limited to the above method, and the array number may be directly input from a keyboard or the like, or may be set in advance in the program as a fixed value.
  • step S402 the array element number acquired in step S401 is stored in the search path stack. Proceeding to step S403, the array element having the array element number stacked at the top of the search path stack is read out from the array as a link destination node. In step S404, the node type is extracted from the node read in step S403.
  • step S405 the node type is determined. If the determination in step S405 is a branch node, the process proceeds to step S406.
  • step S406 the discrimination bit position is extracted from the node.
  • step S407 the bit value of the discrimination bit position extracted in step S406 is acquired from the search key.
  • step S408 the array element number of the representative node of the link destination node pair is obtained from the node. Subsequently, the process proceeds to step S409, where the array element number acquired in step S408 is added to the array element number acquired in step S408 to acquire the array element number of the link destination node, and the process returns to step S402.
  • step S402 the array element number obtained in step S409 is stored in the search path stack.
  • step S402 to S409 is repeated until the determination at step S405 becomes a lift node.
  • step S405 If it is determined in step S405 that the node type is a leaf node, the process proceeds to step S410, and an index key is extracted from the node. Then, the process proceeds to step S411 to determine whether the search key and the index key are equal. If they are equal, the search is successful, and if they are not equal, the search is unsuccessful.
  • the stack is used to identify the array element number of the node being processed, but an ordinary work area can also be used as a temporary storage for searching only.
  • an ordinary work area can also be used as a temporary storage for searching only.
  • it is effective to use the stack so it is preferable to use the stack in the search process.
  • FIGS. 5 to 7 illustrate normal insertion processing
  • FIG. 8 illustrates root node insertion processing. Since the coupled node tree is generated by the root node insertion process and the normal insertion process, the description of the node insertion process is also the description of the coupled node tree generation process.
  • FIG. 5 is a diagram showing the processing flow of the search process that is the first stage of the insert process, and corresponds to the search key shown in FIG. 4 with the insert key as the search key.
  • the processing from step S501 to step S510 corresponds completely to step S401 to step S410 in FIG.
  • step S51 1 of FIG. 5 the insert key is compared with the index key. If they are equal, the insert key already exists in the coupled node tree. Input fails and processing ends. If they are not equal, the process proceeds to the next process, step S512 and subsequent steps in FIG.
  • FIG. 6 is a processing flowchart for explaining processing for preparing an array element for a node pair to be inserted.
  • step S512 an empty node pair is obtained from the array, and the array element number of the array element to be the representative node of the node pair is acquired.
  • step S513 the size of the insertion key and the index key obtained in step S510 are compared, and a value 1 is obtained when the insertion key is large, and a Boolean value 0 is obtained when the insertion key is small.
  • an array element number is obtained by adding the Boolean value obtained in step S513 to the array element number of the representative node obtained in step S512.
  • an array element number is obtained by adding the logical negation value of the Boolean value obtained in step S513 to the array element number of the representative node obtained in step S512.
  • the array number obtained in step S514 is the array element number of the array element in which the leaf node having the insertion key as an index key is stored.
  • the array number obtained in step S515 is stored in the branch node that forms a pair with the leaf node.
  • the leaf node holding the insertion key is stored in either node of the inserted node pair. Is decided.
  • the index key of the search result is “011010” stored in the node 211d.
  • a Boolean value is obtained by comparing the size of the insertion key “011011” and the index key “011010” stored in the node 211d.
  • the Boolean value 1 is obtained, and the node pair to be inserted
  • the leaf node that holds the insertion key is stored in the array element with 1 added to the representative node number.
  • the index key “011010” is stored in the array element of the array number obtained by adding the logical inversion of the Boolean value obtained by the size comparison to the representative node number.
  • the node 21 1d has the discrimination bit position set to 5 and the representative node number is inserted. It becomes a branch node with the array element number of the representative node of the node pair.
  • FIG. 7 is a diagram showing a processing flow for storing the node in the array prepared in FIG. 6, obtaining the insertion position, changing the contents of the existing node, and completing the insertion process.
  • step S523 The processing from step S51 6 to step S523 is processing for obtaining the position on the coupled node tree of the node pair to be inserted, and the processing after step S524 is processing for setting the data in each node and completing the insertion processing. is there.
  • step S516 the bit string comparison between the insertion key and the index key obtained in step S510 is performed by, for example, exclusive OR, to obtain a differential bit string.
  • the bit position of the first non-matching bit viewed from the upper 0 bit is obtained from the difference bit string obtained in step S516.
  • a difference bit string is input to the CPU and a bit position that does not match can be obtained. It is also possible to obtain the bit position of the first non-matching bit by performing processing equivalent to that of the priority encoder in software.
  • step S518 it is determined whether the stack pointer of the search path stack points to the array element number of the root node. If so, go to Step S524 If not, go to step S519.
  • step S519 the stack pointer of the search path stack is returned by 1, and the array element number stacked there is extracted.
  • step S520 the array element having the array element number extracted at step S519 is read out as a node from the array.
  • step S521 the discrimination bit position is extracted from the node read out at step S520.
  • the discrimination bit position taken out at step S521 is higher than the bit position obtained at step S517.
  • the upper positional relationship is a position on the left side of the bit string, that is, a position where the value of the bit position is small.
  • step S522 If the determination result in step S522 is negative, the process returns to step S518, and is repeated until the determination in step S518 is affirmative or the determination in step S522 is affirmative. If the determination in step S522 is affirmative, the stack pointer of the route search stack is advanced by 1 in step S523, and the process proceeds to step S524 and subsequent steps.
  • step S516 to step S523 described above performs bit string comparison between the index key to be inserted and the index key obtained by the search in order to determine the insertion position of the node pair to be inserted.
  • the relative positional relationship between the first (most significant) bit position, which is a different bit value in the comparison, and the discrimination bit position of the branch node stored in the search path stack is examined, and the discrimination bit position is The link destination of the branch node next to the branch node becomes the insertion position of the node pair to be inserted.
  • the index key of the search result is “101011” stored in the node 210h.
  • the most significant bit position 1 which is a different bit value is obtained.
  • Discrimination bit position indicates the positional relationship between the obtained bit position 1 and the discrimination bit position of the branch node stored in the array element with the array element number stacked in the path search stack. If the path search stack is followed in reverse until the position becomes higher, the route node 210a is reached. Therefore, the pointer of the search path stack is advanced by 1, and the array element number of node 211 b is obtained.
  • the insertion key “111000” is inserted into the link destination of the node 211b.
  • the discrimination bit position of the root node becomes a different bit value in the bit string comparison obtained earlier, and is not a higher bit position than the highest bit position.
  • the value of the upper bits of the index key of the coupled node tree and the values of the bits higher than the discrimination bit position of the root node are all equal.
  • an index key to be inserted has a bit value different from the value of the bit higher than the discrimination bit position of the root node. Therefore, the node pair to be inserted becomes the direct link destination of the root node, and the discrimination bit position of the root node is changed to the position of the most significant bit of the insertion key, which is different from the existing index key.
  • step S524 the array element number pointed to by the stack pointer is extracted from the search path stack.
  • step S525 1 (leaf node) is written in the node type of the array element indicated by the array element number obtained in step S514, and the insert key is written in the index key. Proceeding to step S526, the array element having the array element number obtained at step S524 is read from the array.
  • step S527 the contents read in step S526 are written in the array element having the array element number obtained in step S515.
  • step S528 0 (branch node) is obtained as the node type of the array element indicated by the array number obtained in step S524, the bit position obtained in step S517 is obtained as the discrimination bit position, and the representative node number is obtained in step S512. Write the sequence number and finish the process.
  • step S5 27 The contents of node 21 1 b are written to node [0] of the obtained empty node pair (step S5 27), and node [1] is made a leaf node holding the insertion key “1 1 1000” (step S525). ) Then, the most significant bit position 1 which becomes a different bit value by bit string comparison is stored in the discrimination bit position of the node 21 1 b, and the representative node number is an array element in which the representative node of the obtained node pair is stored Is stored (step S528).
  • FIG. 8 is a process flow diagram illustrating the entire node insertion process when adding an index key including a root node insertion process according to an embodiment of the present invention.
  • step S551 it is determined whether the array number of the root node of the coupled node requested to be acquired has been registered. If registered, the normal insertion process described with reference to FIGS. 5 to 7 is performed.
  • step S552 an empty node pair is obtained from the array, and the array element number of the array element to be the representative node of the node pair is acquired.
  • step S553 the sequence number obtained by adding 0 to the sequence number obtained in step S552 is obtained. (In fact, it is equal to the array element number obtained in step S552.)
  • step S554 the node type of the root node to be inserted is set to 1 (leaf node) in the array element of the array element number obtained in step S553.
  • the insert key is written in the index key, the array element number of the root node acquired in step S552 is registered in step S556, and the process is terminated.
  • FIG. 9 is a diagram showing a processing flow of search processing that is the first stage of deletion processing.
  • step S901 to step S910 corresponds completely to step S401 to step S410 in FIG.
  • step S911 in FIG. 9 the delete key and the index key are compared. If not, the index key to be deleted does not exist in the force key, so the deletion fails and the process finish. If they are equal, the process proceeds to the next process, and the process after step S912 in FIG.
  • FIG. 10 is a diagram for explaining the processing flow of the latter stage of the deletion processing.
  • step S912 it is determined whether two or more array numbers are stored in the search path stack.
  • the fact that two or more array numbers are not stored is, in other words, only one, and the array number is that of the array element in which the root node is stored. In that case, the process proceeds to step S918, and the node pair related to the root node array number obtained in step S901 is deleted. In step S919, the registered root node array element number is deleted and the process is terminated.
  • step S912 If it is determined in step S912 that two or more array element numbers are stored in the search path stack, the process proceeds to step S913, and the representative node number obtained in step S908 is set to the bit value obtained in step S907.
  • the sequence number is obtained by adding the inverted values of. In this process, the array element number in which the node that is paired with the leaf node storing the index key to be deleted is obtained.
  • step S914 the contents of the array element having the array element number obtained in step S913 are read, and in step S915, the stack pointer of the search path stack is returned by 1 to extract the array element number.
  • step S916 the contents of the array element read in step S914 are overwritten on the array element of the array element number obtained in step S915.
  • the branch node that is the link source to the leaf node storing the index key to be deleted is replaced with a node paired with the leaf node.
  • step S917 the node pair related to the representative node number obtained in step S908 is deleted, and the process ends.
  • FIGS. 11A and 11B are diagrams for explaining the process of deleting the index key “011010” from the coupled node tree illustrated in FIG.
  • nodes below node pair 201 f are not shown.
  • the index key “011010” to be deleted is stored in the deletion key 270 which is a temporary storage area.
  • the stack pointer of the search path stack 280 points to the array element number 221 G + 1, indicating that the search process has been completed.
  • the nodes surrounded by a thick frame in the figure are the nodes traced by the search process, and the array element numbers are stacked on the search path stack 280 from the root node 210a to the leaf node 211d.
  • the node 210b is read, the discrimination bit position 230b is 1, and the bit value of the bit position 1 of the deletion key is 1. Therefore, the representative node number 220b + 1 is stored in the search path stack 280.
  • node 211 G since node 211 G is read, discrimination bit position 231 G is 2, and the bit value of bit position 2 of the delete key is 1, the representative node number 221 G + 1 is the search path stack.
  • the node type 261 d of node 211 d stored in the array element with the array element number 221 G + 1 indicates that it is 1 and it is a leaf node, so when index key 251 d is taken out, its value is "011010 "And matches the index key to be deleted stored in the delete key 270.
  • the coupled node tree shown in Figure 1 1 B is the one after the deletion process. As shown in parentheses, the value stored in the node 210d is stored as it is in the node type 261c, the discrimination bit position 231c, and the representative node number 222c of the node 211c.
  • Figure 12 A shows a temporary storage area that holds a coupled node tree that has bit strings "0100”, “0001", and "0000” as index skis and an insertion key "0011" to be inserted. 1250.
  • the tree shown is composed of node pairs 1201a, 1201b, 1201c.
  • the representative node of the node pair 1201a is the root node 1210a, and 1 is held in the discrimination bit position.
  • the representative node 1210b of the node pair 1201b lower than the node pair 1201a is a branch node, 3 is held in the discrimination bit position, the node 1211b paired with the representative node 1210b is a leaf node, and the index key " 0100 "is held.
  • the nodes 1210G and 1211G constituting the node pair 1201G are both leaf nodes and hold index keys “0000” and “0001”, respectively.
  • FIG. 12B shows a coupled node tree in which the insertion key “0011” is inserted.
  • a new node pair 1201d is inserted between the node pair 1201b and the node pair 1201c.
  • FIGS. 12A and 12B will be described with reference to FIGS. 13 to 16 with appropriate reference to FIGS. Indicated in bold lines in Figs. 13 to 16
  • the flow of processing is in accordance with the example of FIGS. 12A and 12B.
  • the reference numeral S 501 etc. indicates that the processing of that part corresponds to the processing in step S 501 etc. described in FIGS.
  • FIG. 13 is a diagram for explaining the flow of the processing block in the search processing that is the first stage of the insertion processing shown in FIG.
  • the root node is set in the first processing block.
  • the position of the drill node is set by obtaining the root node array number.
  • the acquired array element number 1210a is stored in the search path stack.
  • the code representing the array element number is also used as the code representing the node.
  • step S505 it is determined that the node 1210a is a branch node, and branch processing is performed.
  • the node position of the link destination is calculated by adding “0” of the first bit of the insertion key “0011” and the array element number 1201b stored in the representative node number of the node 1210a.
  • the array element number stored in the representative node number is represented by the symbol of the link destination node pair.
  • the calculated node position 1210b is stored in the search path stack.
  • the node read determination process is performed again, and the node 121 Ob is read out and determined to be a branch node.
  • branch processing is performed again, and the node number of the link destination is calculated by adding “1” of the third bit of the insertion key “0011” and the array element number 1201c stored in the representative node number of the node 1210b.
  • the calculated node position 1211c is stored in the searched route stack.
  • the process branches to leaf processing, and the bit string comparison of the index key “0001” and the insertion key “0011” of the node 1211c is performed. If it does not match, proceed to the next process.
  • FIG. 14 is a diagram for explaining the flow of the processing block for preparing an array element for the node pair to be inserted shown in FIG.
  • the representative node number 1201 d related to the array number of two free array elements in a continuous area from the array is acquired.
  • the size of the insertion key "001 1" is compared with the index key "0001" obtained in step S510, and two array elements obtained in the empty node pair acquisition block Of which the leaf node holding the insert key is stored in which array element. Since the insertion key is large as a result of the comparison, the leaf node holding the insertion key is stored as node 1 21 1 d in the array element of the array element number obtained by adding 1 to the representative node number 1 201 d.
  • FIG. 15 is a diagram for explaining the processing flow for obtaining the position on the coupled node of the node pair to be inserted in the first half of the processing shown in FIG.
  • differential bit position detection block an exclusive OR “0010” for each bit of the insertion key “001 1” and the index key “0001” obtained in step S510 is calculated, and the differential bit position is the second bit. Is required.
  • the pointer is compared with the difference bit position of the node stored in the array element of the array number pointed to by the pointer in the search path stack until the discrimination bit position becomes higher. Are returned in order. If the boyer points to the root node array number in the middle, the insertion position will be directly below the root node.
  • the insertion node position search process is started by returning the pointer by one, and the node Take out the storage location of 1 210b and read node 1 210b put out.
  • the discrimination bit position of node 1 210b is 3, which is lower than the difference bit position 2. Since node 1 210b is not the root node, the search for the insertion node position is continued.
  • array element number 1 210b is read as the position to insert the insertion node.
  • FIG. 16 is a diagram for explaining a processing flow for completing the insertion processing by setting data in each node in the latter half of the processing shown in FIG.
  • Leaf node assembly In the write block, a leaf node storing 1 for the node type and the insertion key "001 1" for the index key is assembled, and the array calculated by the node storage location calculation block shown in Figure 14 Store in array element number 1 21 1 d
  • node 1 210b of the array element number read by the insertion node position read block shown in FIG. 15 is read, and the contents are shown in FIG. Stored in the array element of array element number 1 210d calculated by the node storage position calculation block.
  • 0 is stored as the node type, and the differential bit position 2 detected by the differential bit position detection block shown in Fig. 15 is stored in the discrimination bit position.
  • a branch node storing the representative node number 1201d acquired in the empty node pair acquisition block shown in FIG. 14 is assembled.
  • the assembled branch node is written in the array element of array element number 1210b read by the insertion node position read block shown in FIG.
  • bit string search device of the present invention can be constructed on a computer by storage means for storing a coupled node tree and a program for causing the computer to execute the processing shown in FIG.
  • the index insertion method of the present invention can be realized by a program that causes a computer to execute the index insertion processing shown in FIGS. 8 and 5 to 7 and its equivalent, and FIG. 9 and FIG. It is also clear that the index insertion method of the present invention can be realized by a program that causes a computer to execute the deletion processing shown in FIG.
  • the means for identifying the branch node and the leaf node, the means for linking to either of the linked node pairs according to the discrimination bit position of the branch node, etc. are realized on the computer.
  • 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.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Computational Linguistics (AREA)
  • Software Systems (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Description

明 細 書
ビッ卜列検索装置、 検索方法及びプログラム
技術分野
[0001 ] 本発明はビット列の集合から所望のビット列を検索する検索装置に関する ものであり、 特にビット列を記憶するデータ構造に工夫をして、 検索速度等 の向上を図る技術分野のものである。
背景技術
[0002] 近年、 社会の情報化が進展し、 大規模なデータベースが各所で利用される ようになってきている。 このような大規模なデータベースからレコードを検 索するには、 各レコードの記憶されたァドレスと対応づけられたレコード内 の項目をインデックスキーとして検索をし、 所望のレコードを探し出すこと が通例である。 また、 全文検索における文字列も、 文書のインデックスキー と見なすことができる。
[0003] そして、 それらのインデックスキーはビット列で表現されることから、 デ ータベースの検索はビット列の検索に帰着されるということができる。
上記ビット列の検索を高速に行うために、 ビット列を記憶するデータ構造 を種々に工夫することが従来から行われている。 このようなものの一つとし て、 パトリシアツリーという木構造が知られている。
[0004] 図 1 7は、 上述の従来の検索処理に用いられているパトリシアツリーの一 例を示すものである。 パトリシアツリーのノードは、 インデックスキー、 検 索キーの検査ビット位置、 左右のリンクポインタを含んで構成される。 明示 はされていないが、 ノードにはインデックスキーに対応するレコードにァク セスするための情報が含まれていることは勿論である。
[0005] 図 1 7の例では、 インデックスキー" 100010" を保持するノード 1750aがル ートノードとなっており、 その検査ビット位置は 0である。 ノード 1750aの左 リンク 1740aにはノード 1750bが接続され、 右リンク 174 ^i — 17501^ 接続されている。 [0006] ノード 1750bの保持するインデックスキーは" 010011" であり、 検査ビット 位置 1730bは 1である。 ノード 1750bの左リンク 1740bにはノード 1750cが、 右 リンク 1741bにはノード 1750dが接続されている。 ノード 1750Gが保持するィン デックスキーは" 000111" 、 検査ビット位置は 3である。 ノード 1750dが保持 するインデックスキーは" 011010" 、 検査ビット位置は 2である。
[0007] ノード 1750cから実線で接続された部分はノード 1750cの左右のリンクボイ ンタを示すものであり、 点線の接続されていない左ポインタ 1740cは、 その欄 が空欄であることを示している。 点線の接続された右ポインタ 1741cの点線の 接続先は、 ポインタの示すアドレスを表しており、 今の場合ノード 1750cを右 ポインタが指定していることを表している。
[0008] ノード 1750dの右ポインタ 1741dはノード 1750d自身を指しており、 左リンク 1740dにはノード 1750eが接続されている。 1750eの保持するインデックスキー は" 010010" 、 検査ビット位置は 5である。 ノード 1750eの左ポインタ 1740e はノード 1750bを、 右ポインタ 1741eはノード 1750eを指している。
[0009] また、 ノード 1750fの保持するインデックスキーは" 101011" であり、 検査 ビット位置 1730fは 2である。 ノード 1750fの左リンク 1740fにはノード 1750g が、 右リンク 1741fにはノード 1750hが接続されている。
[0010] ノード 1750gの保持するインデックスキーは" 100011" であり、 検査ビット 位置 1730gは 5である。 ノード 1750gの左ポインタ 1740gはノード 1750aを、 右 ポインタ 1741gはノード 1750gを指している。
[0011] ノード 1750hの保持するインデックスキーは" 101100" であり、 検査ビット 位置 1730hは 3である。 ノード 1750hの左ポインタ 1740hはノード 1750fを、 右 ポインタ 1741hはノード 1750hを指している。
[0012] 図 1 7の例では、 ルートノード 1750aからツリーを降りるにしたがって、 各 ノ一ドの検査ビット位置が大きくなるように構成されている。
ある検索キーで検索を行うとき、 ルートノードから順次各ノードに保持さ れる検索キーの検査ビット位置を検査していき、 検査ビット位置のビット値 が 1であるか 0であるか判定を行い、 1であれば右リンクをたどり、 0であ れば左リンクをたどる。 そして、 リンク先のノードの検査ビット位置がリン ク元のノードの検査ビット位置より大きくなければ、 すなわち、 リンク先が 下方でなく上方に戻れば （図 1 7において点線で示されたこの逆戻りのリン クをバックリンクという。 ）、 リンク先のノードのインデックスキーと検索キ 一の比較を行う。 比較の結果、 等しければ検索成功であり、 等しくなければ 検索失敗であることが保証されている。
[0013] 上記のように、 パトリシアツリーを用いた検索処理では、 必要なビットの 検査だけで検索できること、 キー全体の比較は 1回ですむことなどのメリッ 卜があるが、 各ノードからの 2つのリンクが必ずあることにより記憶容量が 増大することや、 バックリンクの存在による判定処理の複雑化、 バックリン クにより戻ることで初めてインデックスキーと比較することによる検索処理 の遅延及び追加削除等データメンテナンスの困難性などの欠点がある。
[0014] これらのパトリシアツリーの欠点を解消しょうとするものとして、 例えば 下記特許文献 1に開示された技術がある。 下記特許文献 1に記載されたパト リシアツリーにおいては、 下位の左右のノードは連続した領域に記憶するこ とによりポインタの記憶容量を削減するとともに、 次のリンク力《/くックリン クであるか否かを示すビットを各ノ一ドに設けることにより、 バックリンク の判定処理を軽減している。
[0015] しかしながら、 下記特許文献 1に開示されたものにおいても、 1つのノード は必ずィンデックスキーの領域とボインタの領域を占めること、 下位の左右 のノードを連続した領域に記憶するようにしてポインタを 1つとしたため、 例えば図 1 7に示したパトリシアツリーの最下段の部分である左ボインタ 1 74 0c、 右ボインタ 1 741 h等の部分にもノードと同じ容量の記憶領域を割り当てる 必要があるなど、 記憶容量の削減効果はあまり大きいものではない。 また、 バックリンクによる検索処理の遅延の問題や追加削除等の処理が困難である ことも改善されていない。
特許文献 1 ：特開 2 0 0 1 _ 3 5 7 0 7 0号公報
発明の開示 [001 6] そこで本発明の解決しょうとする課題は、 検索対象のビット列のデータ構 造であって、 必要とする記憶容量が小さく、 検索速度が高速であり、 データ メンテナンスの容易なデータ構造を備えたビット列検索装置及び検索方法を 提供することである。
[001 7] 本発明によれば、 カップルドノードツリーと名付ける以下のデータ構造を 持つツリーが提供され、 本発明のビット列検索装置においてはこのカップル ドノードツリーを用いてインデックスキーの検索が行われる。
[001 8] 本発明のカップルドノードツリーは、 リンク先のデータを有するブランチ ノードと検索対象であるインデックスキーを有するリーフノードを備える。 そしてそのツリー構造は、 ルートノードと、 隣接した記憶領域に配置される ブランチノードとリーフノードまたはブランチノード同士またはリーフノー ド同士のノード対から構成される。
[001 9] ブランチノードは、 検索キーの弁別ビット位置とリンク先のノード対のう ちの一方である代表ノードにリンクするための代表ノード番号を含み、 前記 リーフノードは検索対象であるビット列からなるインデックスキーを含む。 ルートノードは、 ツリーのノードがただ一つのときを除いてはブランチノー ドである。
[0020] 検索キーの弁別ビット位置は、 検索キーのその位置のビット値を用いる点 ではパトリシアツリーの検査ビット位置と同様であるが、 パトリシアツリー では検査ビット位置のビット値を判定してリンク先を求めるのに対して、 本 発明のカップルドノードツリーでは弁別ビット位置のビット値をリンク先の ノードを求める演算に用いる点で異なる。
[0021 ] 検索キーによる検索の実行は、 ルートノードを含む、 各ブランチノードに おいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に 応じてリンク先のノード対の一方のノードにリンクすることを順次リーフノ ードに至るまで繰り返すことにより行われる。
[0022] リーフノードに至ると、 リーフノードの保持するインデックスキーと検索 キーを比較し、 一致すれば検索は成功となる。 一致しなければ、 検索対象の インデックスキーには検索キーと一致するものはなかったことになる。
[0023] 本発明のカップルドノードツリーに新たなインデックスキーを追加する場 合は、 まずそのインデックスキーを検索キーとして検索を行い、 見つかった リーフノードのインデックスキーを取得する。 また、 リーフノートに至るま でたどったブランチノードの番号をルートノードから順次スタックに格納し てお
[0024] 追加するインデックスキーと検索により取得されたインデックスキーの間 で大小比較とビット列比較を行い、 ビット列比較で異なるビット値となる先 頭の （最上位の） ビット位置とスタックに格納されているブランチノードの 弁別ビット位置との相対的位置関係により追加されるノード対の挿入位置を 決定し、 大小関係により追加するインデックスキーを含むリーフノードを追 加されるノード対のどちらのノードとするかを決定する。
[0025] 本発明のカップルドノードツリーからあるインデックスキーを削除すると きは、 削除するキーにより検索を行い、 削除対象のインデックスキーを保持 するノードと同一ノード対を構成するノードの内容を当該ノード対のリンク 元のブランチノードに書き込み、 当該ノ一ド対を削除することにより行う。
[0026] 本発明による力ップルドノ一ドッリーは、 ッリ一構造をノード対で構成し ており、 インデックスキーの集合に対して、 その大きさをコンパクトにする ことができる。 また、 ノードを、 ポインタを含むブランチノードとインデッ クスキーを含むリーフノードに分離しているため、 ポインタ情報が必要なノ 一ドにはボインタ情報は持たせるが、 ィンデックスキーのための領域は必要 なく、 インデックスキーが必要なノードにはポインタのための領域は必要と しないから、 記憶領域に無駄が生じることがない。 また、 パトリシアツリー のようなバックリンクの処理も必要がない。
[0027] カップルドノードツリーを配列に格納した場合には、 ポインタを配列番号 とすることができ、 さらに必要な記憶容量を低減することができる。
本発明によれば、 上述のように検索に用いるツリー構造体を格納する記憶 容量を低減することができ、 それによつても検索処理負担を小さくできるが 、 さらにブランチノードは、 カップルドノードツリーに含まれるインデック スのビット列構成により規定される弁別ビット位置を保持するように配置さ れているから、 必要なビット位置での処理のみとなり、 分岐処理の負担も小 さい。 また、 弁別ビット位置のビット値は判定処理に用いられるのではなく 、 演算処理に用いられるので、 この点でも C P U処理負担は軽くなる。
[0028] また、 カップルドノードツリーの挿入処理や削除処理も単純であり、 メン テナンス負担も軽いものとなる。
以上のとおりであるので、 本発明によれば、 高速にビット列検索を実行す ることができ、 データメンテナンスの容易なビット列検索装置が提供される 図面の簡単な説明
[0029] [図 1 ]配列に格納されたカップルドノードツリーの構成例を説明する図である
[図 2]力ップルドノ一ドッリ一のッリ一構造を説明する図である。
[図 3]本発明を実施するためのハードウエア構成例を説明する図である。
[図 4]本発明の一実施形態における検索処理を示すフローチヤ一トである。
[図 5]本発明の一実施形態における挿入処理の前段である検索処理の処理フロ 一を示す図である。
[図 6]本発明の一実施形態における挿入処理における挿入するノード対のため の配列要素を準備する処理フローを説明する図である。
[図 7]ノ一ド対を挿入する位置を求め、 ノ一ド対の各ノ一ドの内容を書き込ん で挿入処理を完成させる処理フローを示す図である。
[図 8]本発明の一実施の形態におけるルートノードの挿入処理を含むインデッ クスキーを追加する場合のノード挿入処理全体を説明する処理フロー図であ る。
[図 9]本発明の一実施形態における削除処理の前段である検索処理の処理フロ 一を示す図である。
[図 10]本発明の一実施形態における削除処理の後段の処理フローを説明する 図である。
[図 1 1 A]削除処理前のカップルドノードツリーと削除キー" 01 1 01 0" を説明す る図である。
[図 1 1 B]削除処理後のカップルドノードツリーを説明する図である。
[図 1 2A]挿入処理前のカップルドノードツリーと挿入キー" 001 1 " を説明する 図である。
[図 1 2B]挿入処理後のカップルドノードツリーを説明する図である。
[図 1 3]図 5に示した挿入処理の前段である検索処理における処理ブロックの フローを説明する図である。
[図 1 4]図 6に示した挿入するノ一ド対のために配列要素を準備する処理プロ ックのフローを説明する図である。
[図 1 5]図 7に示した処理のうち、 前半の挿入するノード対のカップルドノ一 ドッリ一上の位置を求める処理フローを説明する図である。
[図 1 6]図 7に示した処理のうち、 後半の各ノ一ドにデータを設定して揷入処 理を完成させる処理フローを説明する図である。
[図 1 7]従来の検索で用いられるパトリシアツリーの一例を示す図である。 発明を実施するための最良の形態
[0030] 以下、 本発明を実施するための最良の形態として、 カップルドノードッリ 一を配列に格納する例について説明する。 ブランチノードが保持するリンク 先の位置を示すデータとして、 記憶装置のァドレス情報とすることもできる 力 ブランチノードあるいはリーフノードのうち占有する領域の記憶容量の 大きい方を格納可能な配列要素からなる配列を用いることにより、 ノードの 位置を配列番号で表すことができ、 位置情報の情報量を削減することができ る。
[0031 ] 図 1は、 配列に格納されたカップルドノードツリーの構成例を説明する図 である。
図 1を参照すると、 ノード 1 01が配列 1 00の配列番号 1 0の配列要素に配置さ れている。 ノード 1 01はノード種別 1 02、 弁別ビット位置 1 03及び代表ノード番 号 104で構成されている。 ノード種別 102は 0であり、 ノード 101がブランチノ ードであることを示している。 弁別ビット位置 103には 1が格納されている。 代表ノード番号 104にはリンク先のノード対の代表ノードの配列番号 20が格 納されている。 なお、 以下では表記の簡略化のため、 代表ノード番号に格納 された配列番号を代表ノード番号ということもある。 また、 代表ノード番号 に格納された配列番号をそのノードに付した符号あるいはノ一ド対に付した 符号で表すこともある。
[0032] 配列番号 20の配列要素には、 ノード対 111の代表ノードであるノード [0]1 12が格納されている。 そして隣接する次の配列要素 (配列番号 20+1) に代表ノ 一ドと対になるノード [1]113が格納されている。 ノード [0]112のノード種另 IJ1 14には 0が、 弁別ビット位置 115には 3が、 代表ノード番号 116には 30が格 納されている。 またノード [1]113のノード種別 117には 1が格納されており、 ノード [1]113がリーフノードであることを示している。 インデックスキー 118 には、 " 0001" が格納されている。 パトリシアツリーについて先に述べたと 同様に、 リーフノードにインデックスキーと対応するレコードにアクセスす る情報が含まれることは当然であるが、 表記は省略している。
[0033] なお、 代表ノードをノード [0]で表し、 それと対になるノードをノード [1] で表すことがある。
配列番号 30及び 31の配列要素に格納されたノード 122とノード 123からなる ノード対 121の内容は省略されている。
[0034] ノード [0] 112、 ノード [1] 113、 ノード 122、 及びノード 123の格納された配 列要素にそれぞれ付された 0あるいは 1は、 検索キーで検索を行う場合にノ 一ド対のどちらのノードにリンクするかを示すものである。 前段のブランチ ノードの弁別ビット位置にある検索キーのビット値である 0か 1を代表ノー ド番号に加えた配列番号のノードにリンクする。
[0035] したがって、 前段のブランチノードの代表ノード番号に、 検索キーの弁別 ビット位置のビット値を加えることにより、 リンク先のノードが格納された 配列要素の配列番号を求めることができる。 [0036] なお、 上記の例では代表ノード番号をノード対の配置された配列番号のう ち小さい方を採用しているが、 大きいほうを採用することも可能であること は明らかである。
図 2は、 カップルドノードツリーのツリー構造を概念的に示す図である。 図示の 6ビットのインデックスキーは、 図 1 7に例示されたパトリシアッリ 一のものと同じである。
[0037] 符号 210aで示すのがルートノードである。 図示の例では、 ルートノード 210 aは配列番号 220に配置されたノード対 201 aの代表ノードとしている。
ツリー構造としては、 ルートノード 210 aの下にノート対 201 bが、 その下層 にノード対 201 cとノード対 201 fが配置され、 ノード対 201 fの下層にはノード 対 201 hとノード対 201 gが配置されている。 ノード対 201 cの下にはノード対 201 dが、 さらにその下にはノード対 201 eが配置されている。
[0038] 各ノードの前に付された 0あるいは 1の符号は、 図 1において説明した配 列要素の前に付された符号と同じである。 検索キーの弁別ビット位置のビッ ト値に応じてツリーをたどり、 検索対象のリーフノードを見つけることにな る。
[0039] 図示された例では、 ルートノード 210aのノード種別 260aは 0でブランチノ ードであることを示し、 弁別ビット位置 230aは 0を示している。 代表ノード 番号は 220aであり、 それはノード対 201 bの代表ノード 210bの格納された配列 要素の配列番号である。
[0040] ノード対 201 bはノード 210bと 21 1 bで構成され、 それらのノード種別 260b、 2 61 bはともに 0であり、 ブランチノードであることを示している。 ノード 210b の弁別ビット位置 230bには 1が格納され、 リンク先の代表ノード番号にはノ 一ド対 201 cの代表ノード 210cの格納された配列要素の配列番号 220bが格納さ れている。
[0041 ] ノード 210cのノード種別 260cには 1が格納されているので、 このノードは リーフノードであり、 したがって、 インデックスキーを含んでいる。 インデ ックスキー 250 cには" 0001 1 Γ が格納されている。 一方ノード 21 1 cのノード 種別 261Gは 0、 弁別ビット位置 231Gは 2であり、 代表ノード番号にはノード 対 201 dの代表ノ一ド 21 Odの格納された配列要素の配列番号 221 Gが格納されて いる。
[0042] ノード 210dのノード種別 260dは 0、 弁別ビット位置 230dは 5であり、 代表 ノード番号にはノード対 201 eの代表ノード 210 eの格納された配列要素の配 列番号 220dが格納されている。 ノード 210dと対になるノード 211dのノード種 別 261dは 1であり、 インデックスキー 251dには" 011010" が格納されている
[0043] ノード対 201 eのノード 210e、 211eのノード種別 260e、 261 eはともに 1であ り双方ともリーフノードであることを示し、 それぞれのィンデックスキー 250 e、 251eにはインデックスキーとして" 010010" と" 010011" が格納されてい る。
[0044] ノード対 201bのもう一方のノードであるノード 211bの弁別ビット位置 231b には 2が格納され、 リンク先の代表ノ一ド番号にはノ一ド対 201 fの代表ノ一 ド 21 Ofの格納された配列要素の配列番号 221 bが格納されている。
[0045] ノード対 201 fのノード 21 Of、 211fのノード種別 260f、 261 fはともに 0であ り双方ともブランチノードである。 それぞれの弁別ビット位置 230f、 231fに は 5， 3が格納されている。 ノード 210fの代表ノード番号にはノード対 201g の代表ノード 210gの格納された配列要素の配列番号 220fが格納され、 ノード 2 11fの代表ノード番号にはノード対 201hの代表ノードであるノード [0]210hの 格納された配列要素の配列番号 221 fが格納されている。
[0046] ノード対 201gのノード 210g、 211gのノード種別 260g、 261gはともに 1であり 双方ともリーフノードであることを示し、 それぞれのィンデックスキー 250g 、 251 gには" 100010" と" 100011" が格納されている。
[0047] また同じくノード対 201hの代表ノードであるノード [0]210hとそれと対をな すノード [1]211hのノード種別 260h、 261hはともに 1であり双方ともリーフノ ードであることを示し、 それぞれのインデックスキー 250h、 251hには" 10101 1" と" 101100" が格納されている。 [0048] 以下、 上述のツリーからインデックスキー" 100010" を検索する処理の流れ を簡単に説明する。 弁別ビット位置は、 左から 0、 1、 2、 ■ ■ ' とする。 まず、 ビット列" 100010" を検索キーとしてルートノード 210aから処理を スタートする。 ルートノード 210aの弁別ビット位置 230aは 0であるので、 検 索キー" 100010" の弁別ビット位置 0のビット値をみると 1である。 そこで 代表ノード番号の格納された配列番号 220aに 1を加えた配列番号の配列要素 に格納されたノード 21 1 bにリンクする。 ノード 21 1 bの弁別ビット位置 231 bに は 2が格納されているので、 検索キー" 100010" の弁別ビット位置 2のビッ ト値をみると 0であるから、 代表ノード番号の格納された配列番号 221 bの配 列要素に格納されたノード 2101^ リンクする。
[0049] ノード 210fの弁別ビット位置 230fには 5が格納されているので、 検索キー" 100010" の弁別ビット位置 5のビット値をみると 0であるから、 代表ノード 番号の格納された配列番号 220fの配列要素に格納されたノード 210gにリンク する。
[0050] ノード 210gのノード種別 260gは 1でありリーフノードであることを示してい るので、 インデックスキー 250gを読み出して検索キーと比較すると両方とも " 100010" であって一致している。 このようにしてカップルドノードツリー を用いた検索が行われる。
[0051 ] 次に、 図 2を参照してカップルドノードツリーの構成の意味について説明 する。
カップルドノードツリーの構成はインデックスキーの集合により規定され る。 図 2の例で、 ルートノード 210aの弁別ビット位置が 0であるのは、 図 2 に例示されたィンデックスキーに 0ビット目が 0のものと 1のものがあるか らである。 0ビット目が 0のインデックスキーのグループはノード 210bの下 に分類され、 0ビット目が 1のインデックスキーのグループはノード 21 1 bの 下に分類されている。
[0052] ノード 21 1 bの弁別ビット位置が 2であるのは、 ノード 21 1 h、 210h、 21 1 g、 2 10gに格納された 0ビット目が 1のインデックスキーの 1 ビット目がすべて 0 で等しく、 2ビット目で初めて異なるものがあるという、 インデックスキー の集合の性質を反映している。
[0053] 以下 0ビット目の場合と同様に、 2ビット目が 1であるものはノード 21 1 f 側に分類され、 2ビット目が 0であるものはノード 210f側に分類される。 そして 2ビット目カ《1であるインデックスキーは 3ビット目の異なるもの があるのでノード 21 1 fの弁別ビット位置には 3が格納され、 2ビット目カ《0 であるインデックスキーでは 3ビット目も 4ビット目も等しく 5ビット目で 異なるのでノード 210fの弁別ビット位置には 5が格納される。
[0054] ノード 211 fのリンク先においては、 3ビット目が 1のものと 0のものがそ れぞれ 1つしかないことから、 ノード 210h、 211 hはリーフノードとなり、 それ ぞれインデックスキー 250hと 251 hに" 101011 " と" 101100" が格納されてい る。
[0055] 仮にインデックスキーの集合に" 101100" の代わりに" 101101 " か" 10111 0" が含まれていたとしても、 3ビット目までは" 101100" と等しいので、 ノ 一ド 211 hに格納されるインデックスキーが変わるだけで、 ツリー構造自体は 変わることはない。 しかし、 " 101100" に加えて" 101101 " が含まれている と、 ノード 211 hはブランチノードとなり、 その弁別ビット位置は 5になる。 追加されるインデックスキーが" 101110" であれば、 弁別ビット位置は 4と なる。
[0056] 以上説明したように、 カップルドノードツリーの構造は、 インデックスキ 一の集合に含まれる各インデックスキーの各ビット位置のビット値により決 定される。 検索キーで検索するときはィンデックスキーが力ップルドノ一ド ツリー上に配置されたルートをたどることになり、 例えば検索キーが" 10110 0" であればノード 211 hに到達することができる。 また、 上記説明からも想像 がっくように、 " 101101 " 力、" 101110" を検索キーとした場合でもノード 211 hにたどり着き、 インデックスキー 251 hと比較することにより検索が失敗した ことが分かる。
[0057] また、 例えば" 100100" で検索した場合でも、 ノード 210a、 211 b, 210fの リンク経路では検索キーの 3ビット目と 4ビット目は使われることがなく、 " 100100" の 5ビット目が 0なので、 " 100010" で検索した場合と同様にノ ード 210 gに到達することになる。 このように、 カップルドノードツリーに格 納されたインデックスキーのビット構成に応じた弁別ビット位置を用いて分 岐が行われる。
[0058] なお、 検索の詳細なアルゴリズム、 及びインデックスキーの集合に対して どのようにカツプルドノ一ドッリーを構成するかについては、 後に詳細に説 明をする。
図 3は、 本発明を実施するためのハードウエア構成例を説明する図である
[0059] 本発明の検索装置による検索処理及びデータメンテナンスは中央処理装置 3 02及びキヤッシュメモリ 303を少なくとも備えたデータ処理装置 301によりデ 一夕格納装置 308を用いて実施される。 カップルドノードツリーが配置される 配列 309と検索中にたどるノードが格納された配列要素の配列番号を記憶する 探索経路スタック 310を有するデータ格納装置 308は、 主記憶装置 305または外 部記憶装置 306で実現することができ、 あるいは通信装置 307を介して接続さ れた遠方に配置された装置を用いることも可能である。
[0060] 図 3の例示では、 主記憶装置 305、 外部記憶装置 306及び通信装置 307がー本 のバス 304によりデータ処理装置 301に接続されているが、 接続方法はこれに 限るものではない。 また、 主記憶装置 305をデータ処理装置 301内のものとす ることもできるし、 探索経路スタック 310を中央処理装置 302内のハードゥエ ァとして実現することも可能である。 あるいは、 配列 309は外部記憶装置 306 に、 探索経路スタック 310を主記憶装置 305に持つなど、 使用可能なハードウ エア環境、 インデックスキー集合の大きさ等に応じて適宜ハードウエア構成 を選択できることは明らかである。
[0061 ] また、 特に図示されてはいないが、 処理の途中で得られた各種の値を後の処 理で用いるためにそれぞれの処理に応じた一時記憶装置が用いられることは 当然である。 図 4は、 本発明の一実施形態における検索処理を示すフローチヤ一トであ る。 適宜図 2を参照しながら、 検索処理のアルゴリズムを説明する。
[0062] 検索処理を開始するに当たって、 検索対象であるカップルドノードツリー のルートノードの配列番号を取得する （ステップ S401 )。 カップルドノードッ リーはそのルートノードの配列番号により識別できることから、 カップルド ノードツリーの管理はルートノードの配列番号を用いて行うことができる。 そこで、 カップルドノードツリーの管理手段にカップルドノードツリーのル 一トノードの配列番号が登録されているものとする。
[0063] なお、 図示の検索処理がコンピュータ上のプログラムにより実現可能であ ることは明らかであるが、 上記カップルドノードツリーの管理手段は、 例え ば検索処理をコンピュータに実行させるプログラム上の記憶ェリアとするこ とができる。
[0064] また、 1つのコンピュータシステムに複数のカップルドノードツリーを用 いた検索システムが搭載されている場合は、 個々の検索プログラムの外部に 持つようにすることもできる。
[0065] 図 2の例では、 配列番号 220を取得することに相当する。 なお、 ルートノー ドの配列番号の取得は、 上記の方法に限らず、 キーボード等から直接配列番 号を入力するようにしてもよいし、 固定値として予めプログラム上に設定し ておいてもよい。
[0066] 次にステップ S402において、 ステップ S401で取得した配列番号を探索経路 スタックに格納する。 ステップ S403に進み、 探索経路スタックの最上部に積 まれた配列番号の配列要素をリンク先のノードとして配列から読み出す。 ス テツプ S404において、 ステップ S403で読み出したノードからノード種別を取 り出す。
[0067] 次にステップ S405においてノード種別の判定を行う。 ステップ S405での判 定がブランチノードであれば、 ステップ S406に移行する。 ステップ S406では ノードから弁別ビット位置を取り出す。 次にステップ S407において検索キー からステップ S406で取り出した弁別ビット位置のビット値を取得する。 次に ステップ S408に進み、 ノードから、 リンク先のノード対の代表ノードの配列 番号を取得する。 続いてステップ S409に進み、 ステップ S408で取得した配列 番号にステップ S407で取得したビット値を加算してリンク先ノードの配列番 号を取得し、 ステップ S402に戻る。
[0068] ステツプ S402ではステツプ S409で取得した配列番号を探索経路スタックに 格納する。
以上のステツプ S402から S409のループ処理をステツプ S405での判定がリ一 フノードとなるまで繰り返す。
[0069] ステップ S405でノード種別がリーフノードと判定されるとステップ S410に 移行し、 ノードからインデックスキーを取り出す。 そしてステップ S41 1に進 み、 検索キーとインデックスキーが等しいか判定する。 等しければ検索成功 であり、 等しくなければ検索失敗である。
[0070] 上記の説明では、 処理中のノードの配列番号を識別するためにスタックを 用いたが、 検索だけのためであれば普通のワークエリアを一時記憶として用 いることもできる。 しかし、 以下に説明する挿入処理においては、 スタック を用いることが有効であるから、 検索処理においてもスタックを用いること が好ましい。
[0071 ] 次に、 図 5〜図 8によりカップルドノードツリーにおけるノード挿入処理 を説明する。 図 5〜図 7が通常の挿入処理を説明するものであり、 図 8はル 一トノードの挿入処理を説明するものである。 ルートノードの挿入処理と通 常の挿入処理により、 カップルドノードツリーが生成されることから、 ノー ド揷入処理の説明はカップルドノードツリーの生成処理の説明でもある。
[0072] 図 5は挿入処理の前段である検索処理の処理フローを示す図であり、 図 4 に示した検索処理において挿入キーを検索キーとしたものに相当する。 ス亍 ップ S501〜ステツプ S510の処理は図 4のステツプ S401〜ステツプ S410に完全 に対応するので説明は省略する。
[0073] 図 5のステップ S51 1において挿入キーとインデックスキーを比較し、 等し ければ挿入キーは既にカップルドノードツリーに存在するのであるから、 揷 入は失敗となり、 処理を終了する。 等しくなければ次の処理、 図 6のステツ プ S512以下の処理に進む。
[0074] 図 6は、 挿入するノード対のための配列要素を準備する処理を説明する処 理フロー図である。
ステップ S512において、 配列から空きのノード対を求め、 そのノード対の うち代表ノードとなるべき配列要素の配列番号を取得する。
[0075] ステップ S513に進み、 挿入キーとステップ S510で得たインデックスキーの 大小を比較し、 挿入キーが大きいときは値 1を小さいときは値 0のブール値 を得る。
ステップ S514に進み、 ステップ S512で得た代表ノードの配列番号にステツ プ S513で得たブール値を加算した配列番号を得る。
[0076] ステップ S515に進み、 ステップ S512で得た代表ノードの配列番号にステツ プ S513で得たブール値の論理否定値を加算した配列番号を得る。
ステップ S514で得た配列番号は、 挿入キーをインデックスキーとして持つ リーフノードが格納される配列要素の配列番号であり、 ステップ S515で得た 配列番号は、 そのリーフノードと対を成すブランチノードが格納される配列 要素のものである。
[0077] つまり、 前段の検索処理で得られたリーフノードに格納されたインデック スキーと挿入キーの大小により、 挿入されるノード対のうちどちらのノード に挿入キーを保持するリーフノードが格納されるかが決定される。
[0078] 例えば図 2のカップルドノードツリーに" 011011 " を挿入する場合、 検索 結果のインデックスキーはノード 211 dに格納された" 011010" になる。 挿入 キー" 011011 " とノード 211 dに格納されたインデックスキー" 011010" の大 小比較によりブール値が求められ、 今の例では挿入キーが大きいのでブール 値 1が得られ、 挿入されるノード対の代表ノード番号に 1を加えた配列要素 に挿入キーを保持するリーフノードが格納される。 一方、 インデックスキー " 011010" は、 大小比較で得られたブール値を論理反転した値を代表ノード 番号に加算した配列番号の配列要素に格納される。 [0079] その際、 インデックスキー" 01 1010" と挿入キー" 01 101 1 " とは 5ビット 目で異なることから、 ノード 21 1 dは、 弁別ビット位置を 5とし、 代表ノード 番号を挿入されたノード対の代表ノードの配列番号とするブランチノードと なる。
[0080] また図 2のカップルドノードツリーに" 01 100Γ を揷入しょうとする場合 も、 検索結果のインデックスキーはノード 21 1 dに格納された" 01 1010" にな る。 この場合には挿入キーが小さいのでブール値 0が得られ、 挿入されるノ 一ド対の代表ノード番号に 0を加えた配列要素に挿入キーを保持するリーフ ノードが格納される。 そして、 インデックスキー" 01 1010" と挿入キー" 01 1 001 " とは 4ビット目で異なることから、 ノード 21 1 dは、 弁別ビット位置を 4 とし、 代表ノード番号を挿入されたノード対の代表ノードの配列番号とする ブランチノードとなる。 次に図 7のステップ S51 6以下の処理に進む。
[0081 ] 図 7は図 6で準備された配列にノードを格納するとともにその挿入位置を 求め、 既存のノードの内容を変更して挿入処理を完成させる処理フローを示 す図である。
ステップ S51 6〜ステップ S523までの処理は、 挿入するノード対のカップル ドノードツリー上の位置を求める処理であり、 ステップ S524以下の処理は各 ノードにデータを設定して挿入処理を完成させる処理である。
[0082] ステップ S51 6で、 挿入キーとステップ S510で得たインデックスキーのビッ ト列比較を例えば排他的論理和で行い、 差分ビット列を得る。
ステップ S51 7に進み、 ステップ S51 6で得た差分ビット列から、 上位 0ビッ ト目から見た最初の不一致ビットのビット位置を得る。 この処理は、 例えば プライオリティエンコーダを有する C P Uではそこに差分ビット列を入力し 、 不一致のビット位置を得ることができる。 また、 ソフト的にプライオリ亍 ィエンコーダと同等の処理を行い最初の不一致ビッ卜のビット位置を得るこ とも可能である。
[0083] 次にステップ S518に進み、 探索経路スタックのスタックポインタがルート ノードの配列番号を指しているか判定する。 指していればステップ S524に移 行し、 指していなければステツプ S519に進む。
[0084] ステップ S519において、 探索経路スタックのスタックポインタを 1つ戻し てそこにスタックされている配列番号を取り出す。
ステツプ S520に進み、 ステツプ S519で取り出した配列番号の配列要素を配 列からノードとして読み出す。
[0085] ステップ S521に進み、 ステップ S520で読み出したノードから、 弁別ビット 位置を取り出す。
次にステツプ S522に進み、 ステツプ S521で取り出した弁別ビット位置がス テツプ S517で得たビット位置より上位の位置関係か判定する。 ここで上位の 位置関係とは、 ビット列のより左側の位置、 すなわちビット位置の値が小さ い位置であることとする。
[0086] ステップ S522の判定結果が否定であれば、 ステップ S518に戻り、 ステップ S 518での判定が肯定になるかステップ S522での判定が肯定になるまで繰り返す 。 ステップ S522での判定が肯定になると、 ステップ S523で経路探索スタック のスタックポインタを 1つ進め、 ステップ S524以下の処理に移行する。
[0087] 上記ステップ S516〜ステップ S523で説明した処理は、 挿入するノード対の 挿入位置を決定するために、 挿入するインデックスキーと検索により取得さ れたインデックスキーの間でビット列比較を行い、 ビット列比較で異なるビ ット値となる先頭の （最上位の） ビット位置と探索経路スタックに格納され ているブランチノードの弁別ビット位置との相対的位置関係を調べ、 弁別ビ ット位置が上位となるブランチノードの次のブランチノードのリンク先を揷 入するノード対の挿入位置とするものである。
[0088] 例えば図 2のカップルドノードツリーに" 111000" を挿入するとき、 検索 結果のインデックスキーはノード 210hに格納された" 101011 " になる。 挿入 キー" 111000" とノード 210hに格納されたインデックスキー" 101011 " のビ ット列比較により異なるビット値となる最上位のビット位置 1が得られる。 得られたビット位置 1 と経路探索スタックに積まれた配列番号の配列要素に 格納されたブランチノードの弁別ビット位置との位置関係を弁別ビット位置 が上位になるまでを順次経路探索スタック逆にたどると、 ルートノード 210a に至る。 そこで探索経路スタックのポインタを 1つ進め、 ノード 211 bの配列 番号を得る。 挿入キー" 111000" はノード 211 bのリンク先に挿入される。
[0089] また、 経路探索スタックを逆にたどりルートノードに至っても、 ルートノ ードの弁別ビット位置が、 先に求めたビット列比較で異なるビット値となる 最上位のビット位置より上位のビット位置でないということは、 そのカップ ルドノードツリーのインデックスキーの上位ビッ卜で、 ルートノードの弁別 ビット位置より上位のビットの値は全て等しい場合である。 そして、 挿入す るインデックスキーにおいて、 初めてルートノードの弁別ビット位置より上 位のビッ卜の値に異なるビット値のものがあるということである。 したがつ て、 挿入するノード対はルートノードの直接のリンク先となり、 ルートノー ドの弁別ビット位置は、 既存のインデックスキーと異なる値である挿入キー の最上位ビッ卜の位置に変わる。
[0090] 次に、 ステップ S524以下の各ノードにデータを設定して挿入処理を完成さ せる処理について説明する。
ステツプ S524では探索経路スタックからスタックポインタの指す配列番号 を取り出す。
[0091 ] ステップ S525において、 ステップ S514で得た配列番号の指す配列要素のノ ード種別に 1 (リーフノード）を、 インデックスキーに挿入キーを書き込む。 ステツプ S526に進み、 配列からステツプ S524で得た配列番号の配列要素を 読み出す。
[0092] 次にステップ S527において、 ステップ S515で得た配列番号の配列要素にス テツプ S526で読み出した内容を書き込む。
最後にステップ S528において、 ステップ S524で得た配列番号の指す配列要 素のノード種別に 0 (ブランチノード） を、 弁別ビット位置にステップ S517で 得たビット位置を、 代表ノード番号にステップ S512で得た配列番号を書き込 み処理を終了する。
[0093] 上述の図 2のカップルドノードツリーに" 111000" を挿入する例では、 取 得された空ノード対のノード [0]にノード 21 1 bの内容を書き込み （ステップ S5 27) 、 ノード [1 ]を挿入キー" 1 1 1000" を保持するリーフノードとする （ステ ップ S525) 。 そして、 ノード 21 1 bの弁別ビット位置にビット列比較により異 なるビット値となる最上位のビット位置 1を格納し、 代表ノード番号には取 得されたノード対の代表ノードが格納される配列要素の配列番号が格納され る （ステップ S528) 。
[0094] 図 8は、 本発明の一実施の形態におけるルートノードの挿入処理を含むィ ンデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー 図である。
ステップ S551において、 取得することを求められたカップルドノードッリ 一のルートノードの配列番号が登録済みであるか判定される。 登録済みであ れば、 図 5〜図 7を用いて説明した通常の挿入処理が行われる。
[0095] ステツプ S551での判定が登録済みでなければ、 まったく新しい力ップルド ノードツリーの登録、 生成が始まることになる。
まず、 ステップ S552において、 配列から空きのノード対を求め、 そのノー ド対のうち代表ノードとなるべき配列要素の配列番号を取得する。 次にステ ップ S553において、 ステツプ S552で得た配列番号に 0を加えた配列番号を求 める。 （実際には、 ステップ S552で取得した配列番号に等しい。 ）さらにステ ップ S554において、 ステップ S553で得た配列番号の配列要素に、 挿入するル 一トノードのノード種別に 1 (リーフノード）とインデックスキーに挿入キー を書き込み、 ステップ S556でステップ S552で取得したルートノードの配列番 号を登録して処理を終了する。
[0096] 先にも述べたように、 インデックスキーの集合があるとき、 そこから順次 インデックスキーを取り出し、 図 8及び図 5〜図 7の処理を繰り返すことに より、 ィンデックスキーの集合に対応した本発明の力ップルドノ一ドッリ一 を構築することができることは明らかである。
[0097] 次に図 9、 図 1 0を参照して、 本発明の一実施の形態におけるカップルド ノードツリーに係るインデックスキーの集合から、 特定のインデックスキー を削除する処理フローを説明する。
[0098] 図 9は、 削除処理の前段である検索処理の処理フローを示す図であり、 図
4に示した検索処理において削除キーを検索キーとしたものに相当する。 ス 亍ップ S901〜ステツプ S910の処理は図 4のステツプ S401〜ステツプ S410に完 全に対応するので説明は省略する。
[0099] 図 9のステップ S911において削除キーとインデックスキーを比較し、 等し <なければければ削除するィンデックスキーは力ップルドノ一ドッリーに存 在しないのであるから、 削除は失敗となり、 処理を終了する。 等しければ次 の処理、 図 1 0のステップ S912以下の処理に進む。
[0100] 図 1 0は、 削除処理の後段の処理フローを説明する図である。
まず、 ステップ S912で探索経路スタックに 2つ以上の配列番号が格納され ているか判定する。 2つ以上の配列番号が格納されていないということは、 言い換えれば 1つだけで、 その配列番号はルートノードの格納された配列要 素のものである。 その場合はステップ S918に移行し、 ステップ S901で得たル 一トノードの配列番号に係るノード対を削除する。 次にステップ S919に進み 、 登録されていたルートノードの配列番号を削除して処理を終了する。
[0101 ] ステップ S912において探索経路スタックに 2つ以上の配列番号が格納され ていると判定されたときはステップ S913に進み、 ステップ S908で得た代表ノ 一ド番号にステップ S907で得たビット値を反転した値を加算した配列番号を 得る。 この処理は、 削除対象のインデックスキーが格納されたリーフノード と対をなすノードの配置された配列番号を求めるものである。
[0102] 次にステップ S914において、 ステップ S913で得た配列番号の配列要素の内 容を読み出し、 ステップ S915において探索経路スタックのスタックポインタ を 1つ戻して配列番号を取り出す。
[0103] 次にステップ S916に進み、 ステップ S914で読み出した配列要素の内容をス テツプ S915で得た配列番号の配列要素に上書きする。 この処理は、 削除対象 のインデックスキーが格納されたリーフノードへのリンク元であるブランチ ノードを上記リーフノードと対をなすノードに置き換えるものである。 [0104] 最後にステップ S917においてステップ S908で得た代表ノード番号に係るノ 一ド対を削除して処理を終了する。
図 1 1 A及び図 1 1 Bは、 図 2に例示したカップルドノードツリーからィ ンデックスキー" 011010" を削除する処理を説明する図である。
[0105] 図 1 1 Aに示したカップルドノードツリーは、 ノード対 201 f以下のノード は記載を省略している。 削除対象のインデックスキー" 011010" は一時記憶 エリアである削除キー 270に格納されている。 探索経路スタック 280のスタツ クポィンタは配列番号 221 G+1を指しており、 検索処理が完了したことを示し ている。 図中太枠で囲まれたノードが検索処理でたどられたノードであり、 その配列番号がルートノード 210aのものからリーフノード 211 dのものまで探 索経路スタック 280に積まれている。
[0106] 削除キーによる検索処理においては、 まず始めにルートノード 210aの配列 番号 220を取得し、 それを探索経路スタック 280に格納する。 ルートノード 210 aの弁別ビット位置 230aが 0であり、 削除キーのビット位置 0のビット値が 0 であるので、 代表ノード番号 220a+0=220aが探索経路スタック 280に格納され る。
[0107] するとノード 210bが読み出され、 弁別ビット位置 230bが 1であり、 削除キ 一のビット位置 1のビット値が 1であるので、 代表ノード番号 220b+1が探索 経路スタック 280に格納される。
[0108] 次にノード 211 Gが読み出され、 弁別ビット位置 231 Gが 2であり、 削除キー のビット位置 2のビット値が 1であるので、 代表ノード番号 221 G+1が探索経 路スタック 280に格納される。 配列番号が 221 G+1の配列要素に格納されたノー ド 211 dのノード種別 261 dは 1であり、 リーフノードであることを示している のでインデックスキー 251 dを取り出すとその値は" 011010" であり、 削除キ 一 270に格納された削除対象のインデックスキーと一致している。
[0109] 図 1 1 Aに示した状態において、 削除対象のインデックスキーを有するノ ード 211 dと対をなすノード 210dの内容が読み出され、 その内容が、 探索経路 スタック 280のスタックポインタを 1つ戻したところに格納されている配列番 号 220b+1の配列要素 （ノード 221G) に書き込まれる。 その後ノード対 201dを 削除する。 ノード対が削除された配列要素は空となり、 再利用可能となる。
[0110] 図 1 1 Bに示したカップルドノードツリーは、 削除処理の終了後のもので ある。 ノード 211cのノード種別 261c、 弁別ビット位置 231c、 代表ノード番号 2 21cには、 括弧書きで示すように、 ノード 210dに格納されていた値がそのまま 格納されている。
[0111] 次に、 図 1 2A、 図 1 2 B及び図 1 3〜図 1 6により、 具体例を挙げて揷 入処理を更に説明する。
図 1 2 Aに示すのは、 ビット列" 0100" 、 " 0001 " 、 " 0000" をインデッ クスキーとして持つカップルドノードツリーとこれから挿入しょうとする揷 入キー" 0011" を保持している一時記憶エリア 1250である。 図示のツリーは ノード対 1201a, 1201b, 1201cで構成されている。
[0112] ノード対 1201aの代表ノードはルートノード 1210aであり、 弁別ビット位置 には 1が保持されている。 ノード対 1201aの下位のノード対 1201bの代表ノー ド 1210bはブランチノードであり、 弁別ビット位置には 3が保持され、 代表ノ 一ド 1210bと対になるノード 1211bはリーフノードであり、 インデックスキー " 0100" が保持されている。 ブランチノードであるノード 1210bはノード対 12 Oleicリンクしている。
[0113] ノード対 1201Gを構成するノード 1210G， 1211Gはともにリーフノードであり 、 それぞれインデックスキー" 0000" 、 " 0001" を保持している。
図 1 2 Bは、 挿入キー" 0011" を挿入したカップルドノードツリーを示す 図である。 新たなノード対 1201dがノード対 1201bとノード対 1201cの間に挿入 されている。
[0114] 図 1 2 と図1 2 Bを比べると、 挿入されたノード 1210dの内容は、 挿入前 のノード 121 Obのものであり、 挿入後のノード 121 Obの弁別ビット位置が 3か ら 2に変化している。
以下、 図 5〜図 7を適宜参照しつつ図 1 3〜図 1 6により図 1 2 A及び図 1 2 Bに例示した挿入処理を説明する。 図 1 3〜図 1 6において太線で示す 処理のフローは、 図 1 2 A及び図 1 2 Bの例示に沿ったものである。 また、 S 501等の符号は、 その部分の処理が図 5〜図 7に記載されたステツプ S501等に おける処理に対応することを示している。
[0115] 図 1 3は、 図 5に示した挿入処理の前段である検索処理における処理プロ ックのフローを説明する図である。
図 1 3に示すように、 最初の処理ブロックでルートノード設定が行われる 。 ルートノードの配列番号を取得することによリル一トノードの位置を設定 する。 取得された配列番号 1210aを探索経路スタックに格納する。 なお、 ここ では、 配列番号を表す符合をノードを表す符号と兼用している。
[0116] 次にステップ S503、 ステップ S504及びステップ S505からなるノード読出 - 判定ブロックでノード 1210aがブランチノードであることが判定され、 ブラン チ処理が行われる。
ブランチ処理においては挿入キー" 0011" の 1 ビット目の" 0" とノード 12 10aの代表ノ一ド番号に格納された配列番号 1201 bを加算してリンク先のノー ド位置を算出する。 なおここでは、 代表ノード番号に格納された配列番号を リンク先のノード対の符号で表している。 算出されたノード位置 1210bは探索 経路スタックに格納される。
[0117] ブランチ処理で算出されたノード位置に基づいて再びノード読出■判定処 理が行われ、 ノード 121 Obが読み出され、 ブランチノードであることが判定さ れる。
そこで再度ブランチ処理が行われ、 挿入キー" 0011" の 3ビット目の" 1" とノード 1210bの代表ノード番号に格納された配列番号 1201cを加算してリン ク先のノード位置を算出する。 算出されたノード位置 1211cは探索経路スタッ クに格納される。
[0118] 次のノード読出■判定処理においてノード 1211cが読み出され、 リーフノー
ドであることが判定される。
そこで処理はリーフ処理に分岐し、 ノード 1211cのインデックスキー" 0001 " と挿入キー" 0011" のビット列比較が行われ、 一致していれば挿入失敗と なり、 不一致であれば次の処理に進む。
[01 19] なお、 点線の矢印の先に記載された符号 D513等の出口マークは点線の一方 につながつたデータ値が同じ符号のエントリボイントで使用されることを表 している。 D513のうち 513は、 ステップ S513で用いられることを表している。 以上は、 図 1 4〜図 1 6においても同様である。
[0120] 図 1 4は、 図 6に示した挿入するノード対のために配列要素を準備する処 理ブロックのフローを説明する図である。
空きノード対取得ブロックでは、 配列から連続した領域の 2つの空き配列 要素の配列番号に係る代表ノード番号 1 201 dを取得する。
[0121 ] 次にノード格納位置算出ブロックにおいて、 挿入キー" 001 1 " とステップ S 510で得られたインデックスキー" 0001 " との大小比較を行い、 空きノード対 取得ブロックで取得した 2つの配列要素のうち、 挿入キーを保持するリーフ ノードがどちらの配列要素に格納されるか決定する。 比較の結果挿入キーが 大きいので、 代表ノード番号 1 201 dに 1を加算した配列番号の配列要素にノー ド 1 21 1 dとして挿入キーを保持するリーフノードが格納されることになる。
[0122] 図 1 5は、 図 7に示した処理のうち、 前半の挿入するノード対のカップル ドノードッリ一上の位置を求める処理フローを説明する図である。
差分ビット位置検出ブロックにおいて、 挿入キー" 001 1 " とステップ S510 で得られたインデックスキー" 0001 " とのビットごとの排他的論理和" 0010 " が演算され、 差分ビット位置が 2ビット目であることが求められる。
[0123] 挿入ノード位置探索プロックでは、 探索経路スタックのボインタが指す配 列番号の配列要素に格納されたノードの弁別ビット位置と差分ビット位置を 比較しながら、 弁別ビット位置が上位になるまでポインタを順次戻していく 。 途中でボインタがルートノードの配列番号を指した場合は挿入位置はルー トノードのすぐ下になる。
[0124] 挿入ノード位置の探索を開始する前の段階では探索経路スタックのポイン タは配列番号 1 21 1 cを指しているから、 ポインタを 1つ戻して挿入ノード位置 探索処理を開始し、 ノード 1 210bの格納位置を取り出してノード 1 210bを読み 出す。 ノード 1 210bの弁別ビット位置は 3であり、 差分ビット位置 2より下位 であり、 ノード 1 210bはルートノードではないので、 さらに挿入ノード位置の 探索を続ける。
[0125] さらにポインタを 1つ戻すと、 ノード 1 210aの格納位置が取り出され、 ノー ド 1 210aが読み出される。 ノード 1 210aの弁別ビット位置は 1であり、 差分ビ ット位置 2より上位であるので、 ポインタの位置を 1つ進めて挿入ノード位 置読出ブロックの処理を行う。
[0126] 挿入位置読出しを行うときには探索経路スタックのポインタは配列番号 1 21 Obを指していることから、 挿入ノードを挿入する位置として、 配列番号 1 210b が読み出される。
図 1 6は、 図 7に示した処理のうち、 後半の各ノードにデータを設定して 挿入処理を完成させる処理フローを説明する図である。
[0127] リーフノード組立■書込ブロックでは、 ノード種別に 1、 インデックスキ 一に挿入キー" 001 1 " を格納したリーフノードを組み立て、 図 1 4に示した ノード格納位置算出ブロックで算出した配列番号 1 21 1 dの配列要素に格納する
[0128] 次に、 挿入位置のノード読出■書込ブロックにおいて、 図 1 5に示した揷 入ノード位置読出ブロックで読み出した配列番号のノード 1 210bを読み出し、 その内容を図 1 4に示したノード格納位置算出ブロックで算出した配列番号 1 210dの配列要素に格納する。
[0129] 次に、 ブランチノード組立■書込ブロックにおいて、 ノード種別に 0、 弁 別ビット位置に図 1 5に示した差分ビット位置検出ブロックで検出した差分 ビット位置 2を格納し、 代表ノード番号には図 1 4に示した空ノード対取得 ブロックで取得した代表ノ一ド番号 1 201 dを格納したブランチノードを組み立 てる。 そして組み立てたブランチノードを、 図 1 5に示した挿入ノード位置 読出ブロックで読み出した配列番号 1 210bの配列要素に書き込む。
[0130] 上記の処理により、 図 1 2 Aに示したカップルドノードツリーに挿入キー " 001 1 " が挿入され、 図 1 2 Aに示したカップルドノードツリーが完成する 以上本発明を実施するための最良の形態について詳細に説明したが、 本発 明の実施の形態はそれに限ることなく種々の変形が可能であることは当業者 に明らかである。
[0131 ] また、 本発明のビット列検索装置が、 カップルドノードツリーを格納する 記憶手段と図 4に示した処理をコンピュータに実行させるプログラムにより コンピュータ上に構築可能なことは明らかである。
[0132] さらに、 図 8、 図 5〜図 7に示したインデックス挿入処理とその均等物を コンピュータに実行させるプログラムにより、 本発明のインデックス挿入方 法が実現可能であり、 図 9及び図 1 0に示した削除処理とその均等物をコン ピュータに実行させるプログラムにより、 本発明のインデックス挿入方法が 実現可能であることも明らかである。 そして、 それらのプログラムにより、 ブランチノードとリーフノードの識別手段、 ブランチノードの弁別ビット位 置に応じてリンク先のノード対のどちらかにリンクする手段等がコンビユー タ上に実現される。
[0133] したがって、 上記プログラム、 及びプログラムを記憶したコンピュータ読 み取り可能な記憶媒体は、 本発明の実施の形態に含まれる。 さらに、 本発明 のカップルドノードツリーのデータ構造も、 本発明の実施の形態に含まれる
[0134] 以上詳細に説明した、 本発明が提供する全く新しいデータ構造であるカツ プルドノードツリーを用いることにより、 より高速なビット列データの検索 が可能となり、 しかもビット列データの追加削除も容易に実行することがで さる。

Claims

請求の範囲
[1 ] ルートノードと、 隣接した記憶領域に配置されるブランチノードとリーフ ノードまたはブランチノード同士またはリーフノード同士のノード対、 から なるビット列検索に用いるツリーであって、
前記ルートノードは、 前記ツリーの始点を表すノードであって、 該ツリー のノードが 1つのときは前記リーフノード、 該ツリーのノードが 2つ以上の ときは前記ブランチノードであり、
前記ブランチノードは、 ビット列検索を行う検索キーの弁別ビット位置と リンク先のノード対の一方のノードの位置を示す情報を含み、 前記リーフノ ードは検索対象のビット列からなるインデックスキーを含む、 カップルドノ ードツリーを備え、
前記ルートノードを含む前記ブランチノードにおいて、 該ブランチノード に含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード 対のどちらかのノードにリンクすることを順次前記リーフノードに至るまで 繰り返すことにより前記検索キーによる検索を実行することを特徴とするビ ット列検索装置。
[2] 前記カップルドノードツリーは、 配列に記憶され、 前記リンク先のノード 対の一方のノードの位置を示す情報は、 そのノードが格納された前記配列の 配列要素の配列番号であることを特徴とする請求項 1記載のビット列検索装 置。
[3] 前記配列番号と前記検索キーの弁別ビット位置のビット値との演算により リンク先のノードの格納された配列要素の配列番号を求めることを特徴とす る請求項 2記載のビット列検索装置。
[4] 前記ブランチノードとリーフノードは、 それぞれのノードの種別を示すデ 一夕を含むことを特徴とする請求項 1記載のビット列検索装置。
[5] 前記リーフノードに含まれるインデックスキーと前記検索キーを比較し、
—致すれば検索成功とし、 一致しなければ検索失敗とすることを特徴とする 請求項 1 ~ 4記載のビット列検索装置。 [6] 請求項 2記載のビット列検索装置の前記力ップルドノ一ドッリ一に所望の ビット列からなるインデックスキーを含むリーフノードを挿入するインデッ クスキー挿入方法において、
前記インデックスキーを前記検索キーとして前記カップルドノードツリー から該当するリーフノードを検索するとともに、 該リーフノードに至るまで たどったリンク経路のブランチノード及び該リーフノードが格納された配列 要素の配列番号をスタックに順次格納し、
前記検索キーと前記該当するリーフノードに含まれるインデックスキーの 間で大小比較とビット列比較を行い、
ビット列比較で異なるビット値となる先頭のビット位置と前記スタックに 格納されているブランチノードの弁別ビット位置との相対的位置関係により 挿入されるインデックスキーを含むリーフノードともう一方のノードからな るノード対の挿入位置を決定し、
前記大小関係により挿入するインデックスキーを含むリーフノードを前記 挿入されるノード対のどちらのノードとするかを決定する、
ことを特徴とするインデックスキー挿入方法。
[7] 請求項 2記載のビット列検索装置の前記力ップルドノ一ドッリ一から任意 のインデックスキーを含むリーフノードを削除するインデックスキー削除方 法において、
前記インデックスキーを前記検索キーとして前記カップルドノードツリー から該当するリーフノードを検索し、
削除対象のインデックスキーを保持する前記リーフノードと同一ノード対 を構成するノードの内容を当該ノード対のリンク元のブランチノードに書き 込み、
当該ノード対を削除する、
ことを特徴とするインデックスキー削除方法。
[8] ルートノードと、 隣接した記憶領域に配置されるブランチノードとリーフ ノードまたはブランチノード同士またはリーフノード同士のノード対、 から なるビット列検索に用いるツリーであって、
前記ルートノードは、 ツリーの始点を表すノードであって、 該ツリーのノ 一ドが 1つのときは前記リーフノード、 ツリーのノードが 2つ以上のときは 前記ブランチノードであり、
前記ブランチノードは、 ビット列検索を行う検索キーの弁別ビット位置と リンク先のノード対の一方のノードの位置を示す情報を含み、 前記リーフノ 一ドは検索対象のビット列からなるインデックスキーを含むカップルドノ一 ドツリーを用いたビット列検索方法において、
前記ルートノードを含む前記ブランチノードにおいて、 該ブランチノード に含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード 対のどちらかのノードにリンクすることを順次前記リーフノードに至るまで 繰り返すことにより、
前記検索キーによる検索を実行することを特徴とするビット列検索方法。 前記カップルドノードツリーは、 配列に記憶され、 前記リンク先のノード 対の一方のノードの位置を示す情報は、 そのノードが格納された前記配列の 配列要素の配列番号であることを特徴とする請求項 8記載のビット列検索方 法。
前記配列番号と前記検索キーの弁別ビット位置のビット値との演算により リンク先のノードの格納された配列要素の配列番号を求めることを特徴とす る請求項 9記載のビット列検索方法。
前記リーフノードに含まれるインデックスキーと検索キーを比較し、 一致 すれば検索成功とし、 一致しなければ検索失敗とすることを特徴とする請求 項 8〜 1 0記載のビット列検索方法。
請求項 8〜 1 1記載のビット列検索方法をコンピュータに実行させるため のプログラム。
請求項 6記載のインデックスキー挿入方法をコンピュータに実行させるた めのプログラム。
請求項 7記載のインデックスキー削除方法をコンピュータに実行させるた めのプログラム。
[15] ビット列検索に用いるツリー状のデータ構造であって、
ルートノードと、 隣接した記憶領域に配置されるブランチノードとリーフ ノードまたはブランチノード同士またはリーフノード同士のノード対、 から なり、
前記ルートノードは、 前記ツリーの始点を表すノードであって、 該ツリー のノードが 1つのときは前記リーフノード、 該ツリーのノードが 2つ以上の ときは前記ブランチノードであり、
前記ブランチノードは、 ビット列検索を行う検索キーの弁別ビット位置と リンク先のノード対の一方のノードの位置を示す情報を含み、
前記リーフノードは検索対象のビット列からなるインデックスキーを含み 前記ルートノードを含む前記ブランチノードにおいて、 該ブランチノード に含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード 対のどちらかのノードにリンクすることを順次前記リーフノードに至るまで 繰り返すことにより前記検索キーによる検索の実行を可能とすることを特徴 とするデータ構造。
[16] 前記データ構造は、 配列に記憶され、 前記リンク先のノード対の一方のノ 一ドの位置を示す情報は、 そのノードが格納された前記配列の配列要素の配 列番号であることを特徴とする請求項 1 5記載のデータ構造。
PCT/JP2007/000639 2006-07-07 2007-06-15 dispositif de recherche de séquence de bits, procédé de recherche et programme WO2008004335A1 (fr)

Priority Applications (5)

Application Number Priority Date Filing Date Title
DE602007013905T DE602007013905D1 (de) 2006-07-07 2007-06-15 Bitsequenz-sucheinrichtung, suchverfahren und programm
EP07766946A EP2048584B1 (en) 2006-07-07 2007-06-15 Bit sequence search device, search method, and program
CN2007800255634A CN101484895B (zh) 2006-07-07 2007-06-15 比特序列检索装置以及检索方法
US12/308,560 US8073874B2 (en) 2006-07-07 2007-06-15 Bit string searching apparatus, searching method, and program
US12/385,956 US8150856B2 (en) 2006-07-07 2009-04-24 Bit string searching apparatus, searching method, and program

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2006-187827 2006-07-07
JP2006187827A JP4271214B2 (ja) 2006-07-07 2006-07-07 ビット列検索装置、検索方法及びプログラム

Related Child Applications (2)

Application Number Title Priority Date Filing Date
US12/308,560 A-371-Of-International US8073874B2 (en) 2006-07-07 2007-06-15 Bit string searching apparatus, searching method, and program
PCT/JP2007/001120 Continuation-In-Part WO2008053583A1 (fr) 2006-07-07 2007-10-16 Procédé et programme de recherche de séquence de bits

Publications (1)

Publication Number Publication Date
WO2008004335A1 true WO2008004335A1 (fr) 2008-01-10

Family

ID=38894310

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2007/000639 WO2008004335A1 (fr) 2006-07-07 2007-06-15 dispositif de recherche de séquence de bits, procédé de recherche et programme

Country Status (7)

Country Link
US (1) US8073874B2 (ja)
EP (1) EP2048584B1 (ja)
JP (1) JP4271214B2 (ja)
CN (1) CN101484895B (ja)
DE (1) DE602007013905D1 (ja)
TW (1) TW200817945A (ja)
WO (1) WO2008004335A1 (ja)

Cited By (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2009004796A1 (ja) * 2007-07-03 2009-01-08 S.Grants Co., Ltd. ビット列検索方法及びプログラム
WO2009034689A1 (ja) * 2007-09-14 2009-03-19 S.Grants Co., Ltd. ビット列検索装置、検索方法及びプログラム
WO2009072233A1 (ja) * 2007-12-05 2009-06-11 S.Grants Co., Ltd. ビット列のマージソート装置、方法及びプログラム
WO2009084145A1 (ja) * 2007-12-28 2009-07-09 S.Grants Co., Ltd. データベースのインデックスキー更新方法及びプログラム
WO2009090697A1 (ja) * 2008-01-17 2009-07-23 S.Grants Co., Ltd. ビット列検索装置、検索方法及びプログラム
WO2009093290A1 (ja) * 2008-01-22 2009-07-30 S.Grants Co., Ltd. ビット列検索装置、検索方法及びプログラム
EP2149845A4 (en) * 2007-04-19 2010-12-08 S Grants Co Ltd COUPLING KNOB TREE SAVE / RESTORE PROCEDURE, POLLING PROCEDURE WITH THE LONGEST CONSISTENCY / SHORTEST CONSISTENCY, BIT POLLING PROCESS AND STORAGE MEDIUM
CN102449624A (zh) * 2009-03-29 2012-05-09 新叶股份有限公司 码串检索装置、检索方法以及程序
US8214405B2 (en) 2007-05-18 2012-07-03 S. Grants Co., Ltd. Longest-match/shortest-match search apparatus, search method, and program
US8224861B2 (en) 2006-11-28 2012-07-17 S. Grants Co., Ltd. Coupled node tree splitting/conjoining method and program
US8250076B2 (en) 2007-04-25 2012-08-21 S. Grants Co., Ltd. Bit string search apparatus, search method, and program
US8386526B2 (en) 2007-04-19 2013-02-26 KOUSOKUYA, Inc. Coupled node tree backup/restore apparatus, backup/restore method, and program

Families Citing this family (14)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8150856B2 (en) 2006-07-07 2012-04-03 S. Grants Co., Ltd. Bit string searching apparatus, searching method, and program
JP4402120B2 (ja) 2007-01-24 2010-01-20 株式会社エスグランツ ビット列検索装置、検索方法及びプログラム
JP2009251840A (ja) * 2008-04-04 2009-10-29 S Grants Co Ltd ビット列検索装置、検索方法及びプログラム
JP4514810B2 (ja) 2008-05-18 2010-07-28 株式会社エスグランツ ビット列検索装置、検索方法及びプログラム
JP2010257427A (ja) * 2009-04-28 2010-11-11 S Grants Co Ltd インデックス更新データ作成装置、作成方法及びプログラム
JP5165662B2 (ja) * 2009-10-27 2013-03-21 株式会社高速屋 ビット列キー分類・分配装置、分類・分配方法及びプログラム
WO2011064984A1 (ja) 2009-11-30 2011-06-03 株式会社エスグランツ ビット列検索装置、検索方法及びプログラム
JP5220057B2 (ja) * 2010-05-27 2013-06-26 株式会社高速屋 ビット列検索装置、検索方法及びプログラム
JP5220047B2 (ja) * 2009-11-30 2013-06-26 株式会社高速屋 ビット列検索装置、検索方法及びプログラム
CN102184165B (zh) * 2011-04-22 2013-01-02 烽火通信科技股份有限公司 一种节省内存的lcs算法
JP5912714B2 (ja) * 2012-03-21 2016-04-27 任天堂株式会社 データ構造、データ構造生成方法、情報処理装置、情報処理システム、及び情報処理プログラム
CN103902699B (zh) * 2014-03-31 2017-04-12 哈尔滨工程大学 一种用于大数据环境下可支持多格式特性的数据空间检索方法
JP5960863B1 (ja) * 2015-03-11 2016-08-02 エヌ・ティ・ティ・コミュニケーションズ株式会社 検索装置、検索方法、プログラム、及び記録媒体
JP6911877B2 (ja) * 2018-02-19 2021-07-28 日本電信電話株式会社 情報管理装置、情報管理方法及び情報管理プログラム

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2001357070A (ja) 2000-06-13 2001-12-26 Nec Corp 情報検索方法及び装置
JP2002224581A (ja) * 2001-01-31 2002-08-13 Kawamoto Kogyo Kk 竪型ミルのシール構造

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5202986A (en) * 1989-09-28 1993-04-13 Bull Hn Information Systems Inc. Prefix search tree partial key branching
JPH07210569A (ja) 1994-01-19 1995-08-11 Oki Electric Ind Co Ltd 情報検索方法および情報検索装置
US6012061A (en) * 1997-11-25 2000-01-04 International Business Machines Corp. Method and apparatus for deleting nodes in Patricia trees
US6029170A (en) * 1997-11-25 2000-02-22 International Business Machines Corporation Hybrid tree array data structure and method
US6675163B1 (en) * 2000-04-06 2004-01-06 International Business Machines Corporation Full match (FM) search algorithm implementation for a network processor
CN1432943A (zh) * 2002-01-17 2003-07-30 北京标杆网络技术有限公司 标杆智能搜索引擎系统
JP3691018B2 (ja) 2002-01-31 2005-08-31 日本電信電話株式会社 最長一致検索回路および方法およびプログラムおよび記録媒体

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2001357070A (ja) 2000-06-13 2001-12-26 Nec Corp 情報検索方法及び装置
JP2002224581A (ja) * 2001-01-31 2002-08-13 Kawamoto Kogyo Kk 竪型ミルのシール構造

Non-Patent Citations (4)

* Cited by examiner, † Cited by third party
Title
"Algorithm no Sekkei to Kaiseki I", vol. 1ST ED., 30 October 1977, pages: 132 - 136, XP003020565 *
"Hairetsu o Shitei suruto Memory Ryoiki o Kakuho suru", INTERFACE, vol. 32, no. 2, 1 February 2006 (2006-02-01), pages 49 - 50, XP003020564 *
"Patorishia Tsuri Patricia Tree)", JOURNAL OF JAPANESE SOCIETY FOR ARITIFICAL INTELLIGENCE, vol. 11, no. 2, 1 March 1996 (1996-03-01), pages 337 - 339, XP003020563 *
See also references of EP2048584A4

Cited By (19)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8224861B2 (en) 2006-11-28 2012-07-17 S. Grants Co., Ltd. Coupled node tree splitting/conjoining method and program
US8386526B2 (en) 2007-04-19 2013-02-26 KOUSOKUYA, Inc. Coupled node tree backup/restore apparatus, backup/restore method, and program
EP2149845A4 (en) * 2007-04-19 2010-12-08 S Grants Co Ltd COUPLING KNOB TREE SAVE / RESTORE PROCEDURE, POLLING PROCEDURE WITH THE LONGEST CONSISTENCY / SHORTEST CONSISTENCY, BIT POLLING PROCESS AND STORAGE MEDIUM
US8250076B2 (en) 2007-04-25 2012-08-21 S. Grants Co., Ltd. Bit string search apparatus, search method, and program
US8214405B2 (en) 2007-05-18 2012-07-03 S. Grants Co., Ltd. Longest-match/shortest-match search apparatus, search method, and program
WO2009004796A1 (ja) * 2007-07-03 2009-01-08 S.Grants Co., Ltd. ビット列検索方法及びプログラム
US8145665B2 (en) 2007-07-03 2012-03-27 S. Grants Co., Ltd. Bit string search apparatus, search method, and program
WO2009034689A1 (ja) * 2007-09-14 2009-03-19 S.Grants Co., Ltd. ビット列検索装置、検索方法及びプログラム
US8250089B2 (en) 2007-09-14 2012-08-21 S. Grants Co., Ltd. Bit string search apparatus, search method, and program
WO2009072233A1 (ja) * 2007-12-05 2009-06-11 S.Grants Co., Ltd. ビット列のマージソート装置、方法及びプログラム
US8332410B2 (en) 2007-12-05 2012-12-11 KOUSOKUYA, Inc. Bit string merge sort device, method, and program
US8103697B2 (en) 2007-12-28 2012-01-24 S. Grants Co., Ltd. Database index key update method and program
WO2009084145A1 (ja) * 2007-12-28 2009-07-09 S.Grants Co., Ltd. データベースのインデックスキー更新方法及びプログラム
US8195667B2 (en) 2008-01-17 2012-06-05 S. Grants Co., Ltd. Bit string search apparatus, search method, and program
JP2009169715A (ja) * 2008-01-17 2009-07-30 S Grants Co Ltd ビット列検索装置、検索方法及びプログラム
WO2009090697A1 (ja) * 2008-01-17 2009-07-23 S.Grants Co., Ltd. ビット列検索装置、検索方法及びプログラム
WO2009093290A1 (ja) * 2008-01-22 2009-07-30 S.Grants Co., Ltd. ビット列検索装置、検索方法及びプログラム
CN102449624A (zh) * 2009-03-29 2012-05-09 新叶股份有限公司 码串检索装置、检索方法以及程序
CN102449624B (zh) * 2009-03-29 2013-12-18 株式会社高速屋 码串检索装置、检索方法

Also Published As

Publication number Publication date
DE602007013905D1 (de) 2011-05-26
US8073874B2 (en) 2011-12-06
JP4271214B2 (ja) 2009-06-03
EP2048584B1 (en) 2011-04-13
EP2048584A4 (en) 2010-03-24
JP2008015872A (ja) 2008-01-24
CN101484895A (zh) 2009-07-15
CN101484895B (zh) 2011-12-28
EP2048584A1 (en) 2009-04-15
US20090240655A1 (en) 2009-09-24
TW200817945A (en) 2008-04-16

Similar Documents

Publication Publication Date Title
JP4271214B2 (ja) ビット列検索装置、検索方法及びプログラム
JP4514771B2 (ja) カップルドノードツリーの最長一致／最短一致検索装置、検索方法及びプログラム
JP4271227B2 (ja) ビット列検索装置、検索方法及びプログラム
US8224861B2 (en) Coupled node tree splitting/conjoining method and program
JP4527753B2 (ja) ビット列検索装置、検索方法及びプログラム
US8190591B2 (en) Bit string searching apparatus, searching method, and program
JP4439013B2 (ja) ビット列検索方法及び検索プログラム
WO2009084145A1 (ja) データベースのインデックスキー更新方法及びプログラム
US8250089B2 (en) Bit string search apparatus, search method, and program
US8166043B2 (en) Bit strings search apparatus, search method, and program
WO2009122651A1 (ja) ビット列検索装置、検索方法及びプログラム
JP2011018296A (ja) カップルドノードツリーのインデックスキー挿入／削除方法
JP4567754B2 (ja) ビット列検索装置、検索方法及びプログラム
JP4813575B2 (ja) ビット列検索装置
WO2010125742A1 (ja) インデックス更新データ作成装置、作成方法及びプログラム
JP2009199577A (ja) ビット列検索装置、検索方法及びプログラム

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 200780025563.4

Country of ref document: CN

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 07766946

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 12308560

Country of ref document: US

NENP Non-entry into the national phase

Ref country code: DE

WWE Wipo information: entry into national phase

Ref document number: 2007766946

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: RU

点击 这是indexloc提供的php浏览器服务，不要输入任何密码和下载