JP5387092B2 - Storage medium and trie tree generation method - Google Patents

Description

  The present invention relates to a trie tree generation device that performs various processes using a trie tree.

  In a document search system, a trie tree is used to search a desired document, value, and the like from a key at high speed (see, for example, Patent Documents 1 and 2). FIG. 90 is a diagram illustrating an example of a conventional trie tree. In this trie tree, a tree structure is constructed by assigning one node per character to nodes other than the root node. 90 is a trie tree in which the values “1, 3, 4, 5, 3, 2, 1” are assigned to the keys “black, green, blue, grey, black, grey, greenyellow”, respectively. Is shown.

  When a conventional search device executes a trie tree search process, the input key is extracted character by character, and the node of the same key on the trie tree is traced. For example, when the input key “blue” is specified, the search device detects “4” assigned to “blue” by tracing the nodes of the trie tree in the order of nodes b, l, u, and e. To do.

  Incidentally, the trie tree shown in FIG. 90 has a problem that the number of nodes increases and the amount of used memory increases when the key for constructing the trie tree is long. Further, when the key is long, the number of nodes to be compared at the time of the search process increases, and there is a problem that the time until the search process is completed becomes long.

  Therefore, a trie tree called a Patricia tree has been devised to solve the problem of the trie tree (see, for example, Non-Patent Document 1). FIG. 91 is a diagram illustrating an example of a Patricia tree. In this Patricia tree, the amount of memory used is reduced by expressing an edge portion that transitions from one node to another by a character string instead of a character. The Patricia tree shown in FIG. 91 is a Patricia tree in which the values “1, 3, 4, 5, 3, 2, 1” are assigned to the keys “black, green, blue, grey, black, grey, greenyellow”, respectively. Is shown.

  When a conventional search apparatus executes a trie tree search process, the input key and the character string at the edge portion are sequentially compared, and the Patricia tree is traced. For example, when the input key “blue” is designated, the search device detects “4” assigned to “blue” by tracing the edge of the Patricia tree in the order of bl and ue.

JP 59-47669 A Japanese Patent Laid-Open No. 11-7451

“Radix Tree”, [online], [Search February 25, 2009], Internet <http://en.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%9C % A8>

  However, although the Patricia tree described above can solve the memory usage problem and the like as compared with a normal trie tree, it requires a node to be created for each predetermined character string, so the number of characters in the key is large. In this case, there is a problem that the amount of memory used increases.

  Accordingly, the present invention has been made to solve the above-described problems of the prior art, and an object thereof is to provide a storage medium and a trie tree generation method capable of reducing the memory usage.

  In order to solve the above-described problems and achieve the object, this storage medium stores a trie tree in which a node corresponding to a predetermined character is connected in a tree structure in a computer and stores the trie tree in a new state. When registering a character string, the characters of the new character string are read in order from the top and the nodes included in the trie tree are traced according to the characters corresponding to the node, When registering a new character string in one of the traced nodes, the character string registered in the child node of the registration target node is compared with the new character string. It is necessary to store a program that realizes the character string registration function that determines the matching character and registers the remaining character string obtained by removing the matching character from the new character string and the number of matching characters in the registration target node. And

  By executing the program stored in the storage medium, the computer associates one tag key with one node and eliminates the node having no tag key, so that the memory use efficiency can be improved.

FIG. 1 is a diagram for explaining the terms of nodes included in a tree structure. FIG. 2 is a diagram (1) for explaining an overview of the search device according to the present embodiment. FIG. 3 is a diagram (2) for explaining the outline of the search device according to the present embodiment. FIG. 4 is a diagram for explaining the comparison target node. FIG. 5 is a diagram for explaining processing for registering a new key in the trie tree. FIG. 6 is a diagram illustrating an example of a trie tree that holds tag keys in a form in which the key of the trie portion is deleted. FIG. 7 is a diagram (1) showing the used memory amount by the data structure of the conventional Patricia tree and the used memory amount of the trie tree according to the present invention. FIG. 8 is a diagram illustrating a trie tree when a pointer array is deleted from a leaf node. FIG. 9 shows the amount of memory used by the data structure of the conventional Patricia tree and the amount of memory used by the trie tree according to this embodiment when the amount of memory is reduced using the method shown in FIGS. FIG. FIG. 10 is a diagram illustrating the configuration of the search device according to the first embodiment. FIG. 11 is a diagram illustrating an example of the data structure of the registration data management table according to the first embodiment. FIG. 12 is a diagram illustrating an example of the data structure of the trie tree according to the second embodiment. FIG. 13A is a diagram illustrating an example of a data structure when the trie tree illustrated in FIG. 12 is represented by real data. FIG. 13B is a diagram of an example of another data structure of the trie tree. FIG. 14 is a diagram for explaining an overview of a process in which the trie tree generation unit generates a trie tree. FIG. 15 is a diagram (1) for explaining the process of generating the trie tree. FIG. 16 is a diagram (2) for explaining the process of generating the trie tree. FIG. 17 is a diagram (3) for explaining the process of generating the trie tree. FIG. 18 is a diagram (4) for explaining the process of generating the trie tree. FIG. 19 is a diagram (5) for explaining the process of generating the trie tree. FIG. 20 is a diagram (6) for explaining the process of generating the trie tree. FIG. 21 is a diagram (7) for explaining the process of generating the trie tree. FIG. 22 is a diagram (8) for explaining the process of generating the trie tree. FIG. 23 is a diagram (9) for explaining the process of generating the trie tree. FIG. 24 is a diagram (10) for explaining the process of generating the trie tree. FIG. 25 is a diagram (1) for explaining the process of extracting the total value. FIG. 26 is a diagram (2) for explaining the process of extracting the total value. FIG. 27 is a diagram (3) for explaining the process of extracting the total value. FIG. 28 is a diagram (1) for explaining the search processing when the binary search method is used. FIG. 29 is a diagram (2) for explaining the search processing when the binary search method is used. FIG. 30 is a diagram (3) for explaining the search processing when the binary search method is used. FIG. 31 is a diagram (4) for explaining the search processing when the binary search method is used. FIG. 32 is a diagram (5) for explaining the search processing when the binary search method is used. FIG. 33 is a diagram (6) for explaining the search processing when the binary search method is used. FIG. 34 is a diagram (7) for explaining the search processing when the binary search method is used. FIG. 35 is a diagram (8) for explaining the search processing when the binary search method is used. FIG. 36 is a diagram (1) for explaining search processing when the binary search method is not used. FIG. 37 is a diagram (2) for explaining the search processing when the binary search method is not used. FIG. 38 is a diagram (3) for explaining the search processing when the binary search method is not used. FIG. 39 is a diagram (4) for explaining the search processing when the binary search method is not used. FIG. 40 is a diagram (5) for explaining the search processing when the binary search method is not used. FIG. 41 is a diagram for explaining the deletion process. FIG. 42 is a flowchart of the process procedure of the trie tree generation process according to the first embodiment. FIG. 43 is a flowchart (1) illustrating the processing procedure of the data addition processing that does not use the binary search method. FIG. 44 is a flowchart (2) illustrating the processing procedure of the data addition processing that does not use the binary search method. FIG. 45 is a flowchart (1) illustrating a processing procedure of data addition processing using the binary search method. FIG. 46 is a flowchart (2) illustrating the processing procedure of the data addition processing using the binary search method. FIG. 47 is a flowchart (3) illustrating the processing procedure of the data addition processing using the binary search method. FIG. 48 is a flowchart showing a processing procedure of search processing that does not use the binary search method. FIG. 49 is a flowchart (1) showing a processing procedure of search processing using the binary search method. FIG. 50 is a flowchart (2) showing the processing procedure of the search processing using the binary search method. FIG. 51 is a flowchart illustrating the processing procedure of the total value extraction processing. FIG. 52 is a flowchart (1) showing the processing procedure of the deletion processing. FIG. 53 is a flowchart (2) showing the processing procedure of the deletion processing. FIG. 54 is a diagram for explaining the problem of the search device according to the first embodiment. FIG. 55 is a diagram for explaining the outline of the search device according to the second embodiment. FIG. 56 is a diagram illustrating the configuration of the search device according to the second embodiment. FIG. 57 is a diagram illustrating an example of the data structure of the registration data management table according to the second embodiment. FIG. 58 is a diagram illustrating an example of the data structure of the trie tree according to the second embodiment. FIG. 59 is a diagram showing an example of a data structure when the trie tree shown in FIG. 58 is represented by real data. FIG. 60 is a diagram (1) for explaining the process of generating the trie tree according to the second embodiment. FIG. 61 is a diagram (2) for explaining the process of generating the trie tree according to the second embodiment. FIG. 62 is a diagram (3) illustrating the process of generating the trie tree according to the second embodiment. FIG. 63 is a diagram (4) illustrating the process of generating the trie tree according to the second embodiment. FIG. 64 is a diagram (5) for explaining the process of generating the trie tree according to the second embodiment. FIG. 65 is a diagram (6) illustrating the process for generating the trie tree according to the second embodiment. FIG. 66 is a diagram (7) illustrating the process of generating the trie tree according to the second embodiment. FIG. 67 is a diagram (8) illustrating the process for generating the trie tree according to the second embodiment. FIG. 68 is a diagram (9) illustrating the process of generating the trie tree according to the second embodiment. FIG. 69 is a diagram (10) for explaining the process of generating the trie according to the second embodiment. FIG. 70 is a diagram (1) for explaining the process of extracting the total value in the second embodiment. FIG. 71 is a diagram (2) for explaining the process of extracting the total value in the second embodiment. FIG. 72 is a diagram (3) for explaining the process of extracting the total value in the second embodiment. FIG. 73 is a diagram (1) illustrating the search process according to the second embodiment. FIG. 74 is a diagram (2) for explaining the search process according to the second embodiment. FIG. 75 is a diagram (3) for explaining the search processing according to the second embodiment. FIG. 76 is a diagram (4) for explaining the search processing according to the second embodiment. FIG. 77 is a diagram (5) for explaining the search processing according to the second embodiment. FIG. 78 is a flowchart of the process procedure of the trie tree generation process according to the second embodiment. FIG. 79 is a flowchart (1) illustrating the processing procedure of the data addition processing according to the second embodiment. FIG. 80 is a flowchart (2) illustrating the processing procedure of the data addition processing according to the second embodiment. FIG. 81 is a flowchart (3) illustrating the processing procedure of the data addition processing according to the second embodiment. FIG. 82 is a flowchart (1) illustrating the processing procedure of the search processing according to the second embodiment. FIG. 83 is a flowchart (2) illustrating the processing procedure of the search processing according to the second embodiment. FIG. 84 is a flowchart of a process procedure of a total value extraction process according to the second embodiment. FIG. 85 is a flowchart (1) illustrating the processing procedure of the deletion processing according to the second embodiment. FIG. 86 is a flowchart (2) illustrating the processing procedure of the deletion processing according to the second embodiment. FIG. 87 is a flowchart (3) illustrating the processing procedure of the deletion processing according to the second embodiment. FIG. 88 is a flowchart (4) illustrating the processing procedure of the deletion processing according to the second embodiment. FIG. 89 is a diagram illustrating a hardware configuration of a computer corresponding to the search device illustrated in the second embodiment. FIG. 90 is a diagram illustrating an example of a conventional trie tree. FIG. 91 is a diagram illustrating an example of a Patricia tree.

  Hereinafter, embodiments of a storage medium and a trie tree generation method disclosed in the present application will be described in detail with reference to the drawings. Note that the present invention is not limited to the embodiments.

  First, before describing the search apparatus according to the present embodiment, terms of nodes included in the tree structure will be described. FIG. 1 is a diagram for explaining the terms of nodes included in a tree structure. As shown in FIG. 1, among the nodes constituting the trie tree, the node located at the uppermost layer is defined as the root node. In addition, a node that exists in the layer one level above the reference node and is connected to the reference node is defined as a parent node for the reference node (hereinafter simply referred to as a parent node). Further, a node that exists in a layer below the reference node and is connected to the reference node is defined as a child node (hereinafter simply referred to as a child node) with respect to the reference node.

  Further, a node that exists in the same layer as the reference node, is connected to the same parent node as the reference node, and exists above the reference node is defined as an older brother node (hereinafter simply referred to as an older brother node) with respect to the reference node. Further, a node that exists in the same layer as the reference node, is connected to the same parent node as the reference node, and exists below the reference node is defined as a brother node (hereinafter simply referred to as a brother node) with respect to the reference node. Each node from the root node to the parent node is collectively defined as an ancestor node. Also, each node connected under the reference node is collectively defined as a descendant node.

  Next, an outline of the search device according to the present embodiment will be described. 2 and 3 are diagrams for explaining the outline of the search device according to the present embodiment. First, as illustrated in FIG. 2, the search device according to the present embodiment assigns one key to one node when generating a trie tree based on a designated key. In the following description, a key assigned to a node is referred to as a tag key. In FIG. 2, one tag key “black, blue, green, grey, greenyellow” is assigned to each of the nodes b, l, g, r, and e. Further, the values “1, 3”, “4”, “3”, “5, 2”, and “1” are assigned to the nodes b, l, g, r, and e, respectively.

  The trie tree shown in FIG. 2 has a value “1” for each of the tag keys “black, green, blue, grey, black, grey, greenyellow” in the same manner as the trie tree shown in FIG. 90 or the Patricia tree shown in FIG. 3, 4, 5, 3, 2, 1 ". However, unlike the trie and patricia trees shown in FIGS. 90 and 91, the trie tree according to the present embodiment associates one tag key with one node, so there is no node that does not have data, Memory utilization efficiency can be increased. In addition, the trie tree according to the present embodiment does not require an increase in the number of nodes in the trie tree even when the number of characters included in the node is large, so that the memory usage can be suppressed.

  However, the trie tree according to the present embodiment determines whether or not the input key hits the tag key unless the tag key actually registered in the node is referred to as a price for assigning one tag key to one node. Can not. For example, in the trie tree shown in FIG. 2, when a node is transitioned by the first character “b” of the input key “blue”, the root node is first transitioned to the node b. When moving to node b, it cannot be determined whether or not the input key is hit. Actually, it can be determined that there is no hit until the tag key “black” of node b is compared.

  Then, transition to node l by the second character “l”, and comparing the tag key “blue” of node l with the input key “blue”, it can be determined that the input key and tag key match, so it is added to node l The value “4” is detected as a detection result. Therefore, if a tag key is assigned to each node in the dark cloud, the comparison is performed sequentially with the tag key of each node transitioned by each input key, and the processing efficiency cannot be improved.

  In order to solve this problem, as shown in FIG. 3, the search device according to the present embodiment constructs a trie tree so that tag keys are arranged in the depth-first search order. In this way, when tag keys are arranged in the depth-first search order, nodes having tag keys to be compared with the input keys can be narrowed down when searching for data, and processing efficiency can be improved. When constructing a trie tree so that keys are arranged in the depth-first search order, the search device determines the priority of each key, and assigns a key with a lower priority to a node closer to the root node.

  When determining the priority, the search device extracts the characters of each key in order from the top until a different character is detected. In the extracted characters, in the alphabetical order, the closer to a, the lower the priority, and the closer to z, the higher the priority. That is, the priority is “a <b <c <d <e <f <g <h <i <j <k <l <m <n <o <p <q <r <s <t <u <v <W <x <y <z ”. Note that character strings having the same priority can be said to be equal character strings.

  For example, when the tag keys “black” and “blue” are compared, different characters are extracted at the third character. Specifically, “a” is extracted from “black”, and “u” is extracted from “blue”. When “a” is compared with “u”, “u” has a higher priority than “a”. Therefore, “black” having a lower priority is assigned to a node closer to the root node than “blue”.

  Further, when “green” and “greenyellow” are compared, different characters are extracted at the sixth character. Specifically, since there is no sixth character in “green”, “sky” is extracted, and “y” is extracted from “greenyellow”. In such a case, the search device determines that the key “greenyellow” from which no blank has been extracted has a higher priority than “green”. Therefore, “green” having a lower priority is assigned to a node closer to the root node than “greenyellow”.

  In this embodiment, when there are a plurality of child (child) nodes directly connected to the same parent node, a key having a low priority is arranged on the brother node side, and a key having a high priority is assigned to the brother node. Place on the side. For example, when “black” and “green” are compared, different characters are extracted at the first character. Specifically, “b” is extracted from “black”, and “g” is extracted from “green”. When “b” and “g” are compared, “g” has a higher priority than “b”. Therefore, “black” having a lower priority is placed on the brother node than “green”. As shown in FIG. 2, when each tag key is assigned, the priority relationship between the tag key of the parent node having a plurality of child nodes and the tag key of the sibling node is expressed as follows: the key of the parent node <the key of the eldest son node <the second son node The key is <the third son node <... Further, the priority is higher as the node is connected to the subordinate. For example, in FIG. 3, the priority of the key of the node e is higher than the priority of the nodes r and g.

  As shown in FIG. 3, when a tag key is arranged at each node, the position of the input key to be searched can be narrowed down from the relationship between the priority of the input key and the priority of the tag key. Since it is only necessary to search for a tag key having the same priority as the input key, it is compared with the tag key of the node (descendant node) after the node having a higher priority than the input key among the nodes that are transitioned by the character of the input key. This is not necessary, and it is not necessary to compare with the tag key of the node (ancestor node) before the node having a lower priority than the input key.

  Here, the characters of the input key are read one by one from the top, each node of the trie tree is transitioned, and the node that reaches the end is defined as the reaching node. Further, a node having a key with the highest priority among nodes having an older brother node included in each node from the root node to the reaching node is defined as a specific node. If there is no node having an older brother node, a child node of the root node is defined as a specific node.

  When searching for a tag key that matches the input key, the search device according to the present embodiment may search for any one of the nodes from the reaching node to the specific node. If there is no tag key that matches the input key in the search target node, it can be determined that there is no tag key that matches the input key without referring to other tag keys.

  Because the priority of the key of the parent node of the specific node is lower than the priority of the key of the brother node, the priority of the key of the brother node is the input of the registration target belonging to the key character string of the brother node (specific node) This is because the priority of the input key is larger than the priority of the tag key on the brother node when the input key follows the younger brother node. .

  In the following description, each node from the reaching node to the specific node is referred to as a comparison target node. When searching for a key that matches the input key, the search device may perform a comparison process for the tag key of the comparison target node.

  FIG. 4 is a diagram for explaining the comparison target node. When the input key is read character by character from the beginning and finally reaches the node 6, the tag keys of the nodes 5 and 6 included in the comparison target node A may be compared with the input key.

  Next, a case where the search device according to the present embodiment registers a new key in the trie tree will be described. FIG. 5 is a diagram for explaining processing for registering a new key in the trie tree. Even when a new key is constructed in the trie tree, a comparison process is performed with the tag key of the comparison target node, and the new key may be registered in the trie tree according to the priority.

  This will be specifically described with reference to FIG. In the trie tree shown on the left side of FIG. 5, one key “beige, bisque, black, blueviolet” is assigned to each of the nodes b, i, l, u. Also, the values “2”, “4”, “1, 3”, and “3” are assigned to the nodes b, i, l, and u, respectively.

  When the search device adds the key “blue” and the value “4” to the trie tree shown on the left side of FIG. 5, the reaching node is “node u” and the specific node is “node l”. Accordingly, the comparison target nodes are node l, node u (nodes connected under node u).

  When comparing the keys "blueviolet" and "black" connected to the registration target node with "blue", the priority of the key "blue" is lower than "blueviolet" and higher than "black". "Blue" may be registered between a node having "" and a node having "black". In this case, as shown on the right side of FIG. 5, the key “blue” and the value “4” are assigned to the node u, the node e is created under the node u, and “blueviolet” and the value are assigned to the node u. Assign “3”.

  By the way, in order to further reduce the memory usage of the trie tree, the search device according to the present embodiment holds the tag key added as a tag to the node in a form in which the key of the trie part is deleted. FIG. 6 is a diagram illustrating an example of a trie tree that holds tag keys in a form in which the key of the trie portion is deleted.

  For example, the tag key “ack” is registered in the node l, which has the same meaning as that in which the tag key “black” is registered in the node l. Since the key of the trie part from the root node to the node l is “b, l”, the black part is “black” when the trie part and the tag key are combined.

  By adopting the data structure as shown in FIG. 6, the number of tag keys is reduced, and the number of tag keys to be compared with the input keys can be reduced. Further, as shown in FIG. 6, each node may hold only a pointer to the tag key without having tag key data on the trie tree. Alternatively, all the tag key data may be held and the character position at which the comparison is started may be changed.

  FIG. 7 is a diagram showing the used memory amount according to the data structure of the conventional Patricia tree and the used memory amount of the trie tree according to the present invention. In both the Patricia tree and the trie tree, “1, 2, 3, 4, 5” are assigned to the keys “aaaaa, aacab, ababc, aabac, abcab”, respectively.

  Here, assuming that the node memory is 1 KB, the tag key memory is 1 byte, and the value memory is 4 bytes, the Patricia tree has 10 nodes, 17 tag keys, and 5 values, so the total is about 10 KB. . On the other hand, the trie tree according to the present invention has 6 nodes, 16 characters of tag keys, and 4 values, so the total is about 6 KB. Therefore, the trie tree according to the present invention can reduce the amount of memory used compared to the conventional Patricia tree.

  In addition, the search device according to the present embodiment may delete the pointer array from the leaf node corresponding to the end node of the trie tree. Here, the pointer array is an array of pointers indicating connection destination nodes. FIG. 8 is a diagram illustrating a trie tree when a pointer array is deleted from a leaf node. In this way, by deleting the pointer array from the leaf node, the amount of memory used by the leaf node can be reduced.

  FIG. 9 shows the amount of memory used by the data structure of the conventional Patricia tree and the amount of memory used by the trie tree according to this embodiment when the amount of memory is reduced using the method shown in FIGS. FIG.

  Here, if the internal node memory is 1 KB, the leaf node memory is 12 bytes, the memory per key character is 1 byte, and the value memory is 4 bytes, the Patricia tree has 5 internal nodes, 5 leaf nodes, and 17 keys. Since it has 5 characters and values, the total is about 5 KB. On the other hand, the trie tree of this embodiment has three internal memories, three leaf nodes, 19 keys, and five values, so the total is about 3 KB. Thus, even when the used memory usage is reduced by using the methods of FIGS. 8 and 9, the memory usage of the trie tree according to the present embodiment is larger than that of the Patricia tree. It can be reduced.

  Next, the configuration of the search device according to the present embodiment will be described. FIG. 10 is a diagram illustrating the configuration of the search device according to the first embodiment. As illustrated in FIG. 10, the search device 100 includes an input unit 110, an output unit 120, an input / output control unit 130, a storage unit 140, and a control unit 150.

  Among these, the input unit 110 is an input unit for inputting information such as input keys, and corresponds to a keyboard, a mouse, or the like. The output unit 120 is an output unit that outputs information such as search results using a trie tree, and corresponds to a monitor, a display, a touch panel, or the like. The input / output control unit 130 is a processing unit that controls input / output of data by the input unit 110, the output unit 120, the storage unit 140, and the control unit 150.

  The storage unit 140 is a storage unit that stores data and programs necessary for various processes performed by the control unit 150. The storage unit 140 includes a registered data management table 140a and a trie tree 140b.

  Here, the registration data management table 140a is a table that stores keys and values registered in the trie tree in association with each other. FIG. 11 is a diagram illustrating an example of the data structure of the registered data management table 140a according to the first embodiment. As shown in FIG. 11, the registered data management table 140a stores keys and values in association with each other.

  The trie tree 140b is a trie tree generated based on the registered data management table 140a. FIG. 12 is a diagram illustrating an example of the data structure of the trie tree according to the first embodiment. FIG. 12 shows a trie tree corresponding to the registered data management table 140a shown in FIG. 11 as an example. As shown in FIG. 12, node b and node g are connected to the root node, and node l is connected to node b.

  The node b is connected to the tag key “eige” and the value “2”. The node l is connected with the tag key “ack” and the values “1, 3”. The node g is connected with the tag key “reen” and the value “4”.

  When the trie tree shown in FIG. 12 is represented by real data, the data structure shown in FIG. FIG. 13A is a diagram illustrating an example of a data structure when the trie tree illustrated in FIG. 12 is represented by real data. As illustrated in FIG. 13A, the trie tree 140 b includes pointer arrays 10 to 13 and a text table 14.

  Here, the pointer array 10 connected to the root node pointer corresponds to the root node in FIG. 12, the pointer array 11 corresponds to the node b in FIG. 12, and the pointer array 12 corresponds to the node l in FIG. To do. The pointer array 13 corresponds to the node g in FIG.

  The pointer arrays 10 to 13 have a “TAG” area and a “Data” area, and “TAG” represents a tag key connected to a node by associating with a character in the text table 14. For example, since the pointer array 11 is connected to “e” in the text table 14, the character string “eige” from “e” to the next space is designated as a tag key. “Data” expresses a value connected to a node by associating it with a value. For example, the pointer array 11 is connected to the value “2”.

  Each of the pointer arrays 10 to 13 has a key number (pointer) “0 × 00 to 0 × FF” for determining a pointer array connected thereunder. For example, the key number “0 × 62” of the pointer array 10 is connected to the pointer array 11, and the key number “0 × 67” of the pointer array 10 is connected to the pointer array 13.

  Note that the data structure of the real data of the trie tree 140b shown in FIG. 13A and the like shows a case of 8 bits corresponding to one character of ASCII code per node, but is not limited to this. For example, one character of ASCII code may be divided into two in 4-bit units, and 4 bits per node may be used. In this case, the key number of the pointer array is 256 “0x00-0xFF” in the case of 8 bits, whereas it can be reduced to 16 “0x0-0xF” in the case of 4 bits, Memory usage can be reduced. FIG. 13-2 is a diagram illustrating an example of another data structure of the trie tree 140b.

  For example, in the case of “beige”, in the case of 8 bits per node, the head key number “0x62” is connected to the pointer array 11, but in the case of 4 bits per node, “0x62” is set as the top key number. "0x6" in the first half of "" is connected to the pointer array XX in FIG. 13-2. When “black” is continuously added in addition to “beige”, in the case of 8 bits per node, the second key number “0x6c” is connected to the pointer array 12, but 4 bits per node. In this case, the second key number “0x2” in the latter half of “0x62” is connected to the pointer array YY in FIG. The pointer array YY is a node representing “0x62”, that is, “b”, which is a combination of the key number “0x6” for connection to the pointer array XX and the key number “0x2” for connection to the pointer array YY. In addition, when “blue” is continuously added, in the case of 8 bits per node, the key number “0x75” of the third character “u” is connected to the next pointer array, but 4 bits per node. In this case, “0x6” in the first half of the key number “0x6c” of the second character “l” is connected to the next pointer array as the third key number.

  Also, with regard to multibyte characters such as Japanese codes, multiple bytes are treated as one character, instead of 16 bits per node, each character is divided into multiples to 8 bits per node, It may be 4 bits.

  Although it is not possible to directly extract a bit string by designating a bit position in the current computer, a byte position including a desired bit string is specified from the bit position, and after extracting one byte, a desired bit processing operation is used. Can be processed by extracting the bit string. The same can be done when extracting a character string representing a tag key.

  In addition, since all the key number areas of the pointer array corresponding to the leaf node are NULL, the pointer array may be simplified by omitting a part (key number area) of the pointer array. In this case, a flag indicating whether or not its own pointer array is a leaf node is set in each pointer array.

  Returning to the description of FIG. 10, the control unit 150 is a control unit that has an internal memory for storing programs and control data that define various processing procedures, and executes various processes. As illustrated in FIG. 10, the control unit 150 includes a trie tree generation unit 150a and a trie tree search unit 150b.

  The trie tree generation unit 150a is a process of generating the trie tree 140b based on the key registered in the registration data management table 140a. Note that the trie tree generation unit 150a constructs the trie tree 140 by assigning one key to one node, as described with reference to FIGS. In addition, when registering tag keys in a node, the trie tree generation unit 150a generates a trie tree so that the tag keys are arranged in the depth-first search order.

  FIG. 14 is a diagram for explaining an outline of processing in which the trie tree generation unit 150a generates the trie tree 140b. Here, for convenience of explanation, a case where the input key “blue” and the value “4” are registered in the trie tree shown on the left side of FIG. 14 will be described. Further, the trie tree shown on the left side of FIG. 14 assigns a tag key to each node in a state in which the key of the trie part is deleted in the same manner as the trie tree described in FIG.

  First, the trie tree generation unit 150a extracts characters one by one from the input key and traces the nodes on the trie tree. In the middle of tracing, the trie tree generation unit 150a does not compare the input key with the tag key. When the input key is “blue”, characters are extracted one by one from the head of “blue”, and when a node on the trie tree is traced, transition is made in the order of the root node, nodes b, l, and u.

  Next, the trie tree generation unit 150a uses the input key to return to the node having the brother node or the child node of the root node after tracing all input keys when there is no node to be traced. Search for even smaller keys. That is, a tag key having a lower priority than the input key is searched for in the comparison target node. In addition, when comparing the priority of the input key and the tag key, the remaining keys excluding the trie key from the input key are compared with the tag key.

  When the input key is “blue”, since the comparison target nodes are the node u and the node l, the comparison is performed in the order of the node u and the node l. The input key “blue” has a lower priority than the tag key “violet” of the node l and a higher priority than the “ack”. When comparing the priority between the input key “blue” and the tag key “violet”, the key “blue” of the trie section from the root node to the node u is removed from the input key “blue” and then compared. When comparing the priority of the input key “blue” with the tag key “ack”, the key “bl” of the trie section from the root node to the node l is removed from the input key “blue” and then compared.

  The trie tree generation unit 150a registers the input key and the value corresponding to the input key in the node having the tag key with the lowest priority among the tag keys having a higher priority than the input key. Shift the tag key.

  When the input key is “blue”, the trie tree generating unit 150a registers the input key “blue” and the value “4” in the node u. Since the key of the trie portion from the root node to the node u is “blu”, the tag key “e” is actually registered in the node u. Also, the trie tree generation unit 150a creates a new node e under the node u and registers the tag key “blueviolet” in order to shift the tag key “blueviolet” registered in the node u. Since the key of the trie part leading to the node e is “blue”, the tag key “violet” is actually registered in the node e. By executing the registration process as described above, the trie tree shown on the right side of FIG. 14 is generated. The trie tree generation unit 150a may register identification information in order to identify a node having an older brother node. For example, on the right side of FIG. 14, since node l has brother node i, identification information is registered in node l.

  Hereinafter, a process in which the trie tree generation unit 150a generates a trie tree will be described in detail. 15 to 24 are diagrams for explaining processing for generating a trie tree. Here, for convenience of explanation, the key “http://aaa.aaa/e/”, the value “1”, the key “http://aaa.aaa/e/c/”, the value “2”, and the key “ Explains how to create a trie tree in the order of "http://aaa.aaa/e/c/", value "3", key "http://aaa.aaa/e/", value "4" To do.

  As shown in FIG. 15, first, a case where a key “http://aaa.aaa/e/” and a value “1” are added in a state where no node exists will be described. The trie tree generation unit 150a generates a root node (step S10a). On the actual data, the trie tree generation unit 150 a generates a pointer array 20 corresponding to the root node, and connects the root node pointer and the pointer array 20. Further, since the pointer array 20 corresponds to the root node, “TAG” is connected to the empty (step S10b).

  The trie tree generation unit 150a prepares an input key “http://aaa.aaa/e/” (step S11a). On the actual data, the trie tree generation unit 150a stores the input key “http://aaa.aaa/e/” in the text table 14, and sets the pointer of the input key to “h” in the first column of the text table 14. (Step S11b).

  The trie tree generation unit 150a refers to the root node because there is no child node whose key is the first character “h” of the input key “http://aaa.aaa/e/”. Here, since the tag key does not exist in the root node, the priority of the input key “http://aaa.aaa/e/” becomes higher than the priority of the tag key of the root node.

  The trie tree generation unit 150a creates a node with “h” as a key under the root node, and uses the remaining keys obtained by removing the character “h” from the input key “http://aaa.aaa/e/”. Connect to node h as tag key. The value “1” of the input key “http://aaa.aaa/e/” is also connected to the node h (step S12a).

  On the actual data, the trie tree generation unit 150 a generates the pointer array 21 corresponding to the node h, and connects the pointer array 20 and the pointer array 21 with the key number “0 × 68” of the pointer array 20. The trie tree generation unit 150a connects “TAG” of the pointer array 21 to “t” in the second column of the text table 14, and connects “Data” of the pointer array 21 and the value “1” (step S12b). ).

  Subsequently, the case where the key “http://aaa.aaa/e/c/” and the value “2” are added to the trie tree created in steps S12a and 12b will be described with reference to FIG. The trie tree generation unit 150a transitions from the root node to the node h at the first character h of the input key “http://aaa.aaa/e/c/”. Then, the trie tree generation unit 150a advances the pointer of the input key “http://aaa.aaa/e/c/” by one and sets it to “t” of the second character (step S13a).

  On the actual data, the trie tree generation unit 150a leaves one key “http://aaa.aaa/e/” registered last in the text table 14 and then generates the key “http: // aaa .aaa / e / c ”. Then, the trie tree generating unit 150a connects the pointer of the input key to the character “t” in the second row and second column of the text table 14 (step S13b).

  Since there is no child node having “t” as a key in the node h, the trie tree generating unit 150a determines the priority of the tag key “ttp: //aaa.aaa/e/” of the node h and “ The priority of the input key “ttp: //aaa.aaa/e/c/” from which “h” is removed is compared. Then, since the 17th character of the input key is c and the 17th character of the tag key is empty, the priority of the input key is higher than the priority of the tag key (step S14). Therefore, the input key “ttp: //aaa.aaa/e/c/” is registered in the node after the node h.

  Subsequently, the process proceeds to FIG. 17, the trie tree generation unit 150 a generates a new node t using the second character “t” of the input key “http://aaa.aaa/e/c/” as a key, The pointer of the input key is advanced to “t” of the third character (step S15a).

  On the actual data, the trie tree generation unit 150 a generates the pointer array 22 corresponding to the node t, and connects the pointer array 21 and the pointer array 22 with the key number “0 × 74” of the pointer array 21. Further, the input key pointer is advanced by one, and the input key pointer is connected to “t” in the second row and third column of the text table 14 (step S15b).

  The trie tree generation unit 150a adds the remaining key “tp: // aaa” obtained by removing the “ht” of the trie part from the input key “http://aaa.aaa/e/c/” to the node t created in step S15a. .aaa / e / c / "is registered as a tag key (step S16a).

  On the actual data, the trie tree generating unit 150a connects “TAG” in the pointer array 22 to “t” in the second row and third column of the text table 14, and “Data” and the value “2” in the pointer array 22 are connected. Are connected (step S16b).

  Subsequently, the case where the input key “http://aaa.aaa/d/” and the value “3” are added to the trie tree created in steps S16a and 16b will be described with reference to FIG. The trie tree generation unit 150a extracts characters one by one from the first character of the input key “http://aaa.aaa/d/”, and transitions on the trie tree in the order of nodes h and t. Then, the trie tree generation unit 150a advances the pointer of the input key “http://aaa.aaa/d/” by two according to the number of transitioned nodes, and sets the third character “t”.

  The trie tree generation unit 150a does not have a child node having “t” as a key in the node t, and therefore the priority of the tag key “tp: //aaa.aaa/e/c/” of the node t, Compare the priority of the input key “tp: //aaa.aaa/d/” without the “ht” in the trial part. Then, since the 14th character of the tag key is “e” and the 14th character of the input key is “d”, the priority of the tag key is higher than the priority of the input key (step S17a).

  On the actual data, the trie tree generation unit 150a leaves one key “http://aaa.aaa/e/c/” registered last in the text table 14 and the key “http: / /aaa.aaa/d/ ”. Then, the trie tree generating unit 150a connects the pointer of the input key to the character “t” in the third line and the fifth character of the text table 14. When the character string starting with the character connected to “TAG” in the pointer array 22 and the character string starting with the character connected to the pointer of the input key are sequentially compared, the 14th character of the tag key is “ e ”and the 14th character of the input key is“ d ”, the priority of the tag key is greater than the priority of the input key (step S17b).

  The trie tree generation unit 150a returns one pointer of the input key “http://aaa.aaa/d/”, sets it to “t” of the second character, and sets it to the node h that is the parent node of the node t. Transition. Then, the trie tree generation unit 150a uses the priority of the tag key “ttp: //aaa.aaa/e/c” of the node h and the input key “ttp: //aaa.aaa” from which the “h” of the trie part is removed. / d / "is compared. Then, since the 15th character of the tag key is “e” and the 14th character of the input key is “d”, the priority of the tag key is higher than the priority of the input key (step S18a).

  On the actual data, the trie tree generation unit 150 a connects the pointer of the current node to the pointer array 21 and connects the pointer of the input key to the character “t” in the third row and the fourth character of the text table 14. When the character string starting with the character connected to “TAG” in the pointer array 22 and the character string starting with the character connected to the pointer of the input key are sequentially compared, the 15th character of the tag key is “ e ”and the 15th character of the input key is“ d ”, the priority of the tag key is greater than the priority of the input key (step S18b).

  Subsequently, the process proceeds to FIG. Since the parent node of the node h is the root node, the trie tree generation unit 150a exchanges the data (tag key, value) of the node h and the input data (input key, value). That is, the trie tree generation unit 150a uses the remaining key “ttp: //aaa.aaa/d/” obtained by removing the trie part “h” from the input key “http://aaa.aaa/d/” as the node h. Register with the tag key. Also, the value “3” corresponding to the input key “http://aaa.aaa/d/” is also registered in the node h. In addition, the trie tree generation unit 150a adds a trie part “h” to the head of the tag key “ttp: //aaa.aaa/e/” registered in the node h, and takes it out as an input key. Further, the value “1” associated with the tag key “ttp: //aaa.aaa/e/” is also extracted (step S19a).

  On the actual data, the trie tree generation unit 150a exchanges the data (tag key, value) of the node h and the input data (input key, value). That is, the trie tree generation unit 150 a connects “TAG” of the pointer array 21 corresponding to the node h to the character “t” in the third row and fourth column of the text table 14. Further, “Data” of the pointer array 21 and the value “3” are connected. Then, the trie tree generation unit 150 a connects the input key pointer to “t” in the first row and second column of the text table 14. Further, the value “1” connected to “Data” of the pointer array 21 is held as the input value (step S19b).

  The trie tree generation unit 150a transitions from the node h to the node t with the second character t of the input key “http://aaa.aaa/e/”, and the data (tag key, value) and input data of the node t Exchange (input key, value). That is, the trie tree generating unit 150a uses the remaining key “tp: //aaa.aaa/e/” obtained by removing the trie part “ht” from the input key “http://aaa.aaa/e/” as a node t. Register with the tag key. Further, the value “1” corresponding to the input key “http://aaa.aaa/e/” is also registered in the node t. In addition, the trie tree generation unit 150a adds a trie part “h” to the head of the tag key “tp: //aaa.aaa/e/c/” registered in the node t, and takes it out as an input key. Further, the value “2” associated with the tag key “ttp: //aaa.aaa/e/c/” is also extracted (step S20a).

  On the actual data, the trie tree generation unit 150a exchanges the data (tag key, value) of the node t and the input data (input key, value). That is, the trie tree generation unit 150 a connects “TAG” of the pointer array 22 corresponding to the node t to the character “t” in the first column and the third column of the text table 14. Further, “Data” of the pointer array 22 and the value “1” are connected. Then, the trie tree generation unit 150 a connects the pointer of the input key to “t” in the second row and third column of the text table 14. Further, the value “2” connected to “Data” of the pointer array 21 is held as the input value (step S20b).

  Subsequently, the process proceeds to FIG. Since the node t corresponding to the third character of the input key “http://aaa.aaa/e/c/” does not exist under the node t, the trie tree generation unit 150a adds a new node under the node t. Create node t. Here, in order to distinguish each node t, in the following description, the node t on the parent side is expressed as node t (parent), and the node t on the child side is expressed as node t (child). Further, the trie tree generation unit 150a sets the pointer of the input key to “p” of the third character (step S21a).

  On the actual data, the trie tree generation unit 150 a generates the pointer array 23 corresponding to the node t (child), and connects the pointer array 22 and the pointer array 23 with the key number “0 × 74” of the pointer array 22. . Further, the trie tree generation unit 150a connects the pointer of the input key to “p” in the second row and the fourth column of the text table 14 (step S21b).

  Then, it transfers to FIG. The trie tree generation unit 150a uses the remaining key “p: //aaa.aaa/e/c/” obtained by removing the trie part “htt” from the input key “http://aaa.aaa/e/c/”. Connect to node t (child). Further, the trie tree generating unit 150a connects the value “2” corresponding to the input key “http://aaa.aaa/e/c/” to the node t (child) (step S22a).

  On the actual data, the trie tree generation unit 150a connects “TAG” in the pointer array 23 to “p” in the second row and fourth column of the text table 14 and releases the pointer of the input key. In addition, the trie tree generation unit 150a connects the value “2” to “Data” of the pointer array 23 (step S22b).

  Subsequently, the case where the key “http://aaa.aaa/e/” and the value “4” are added to the trie tree created in steps S22a and 22b will be described with reference to FIG. The trie tree generation unit 150a sequentially reads characters from the head of the input key “http://aaa.aaa/e/”, and transitions to nodes h, t (parent), and t (child). Then, the trie tree generation unit 150a sets the pointer of the input key “http://aaa.aaa/e/” to “p” of the fourth character (step S23a).

  On the actual data, the trie tree generation unit 150a leaves one key “http://aaa.aaa/e/d/” registered last in the text table 14 and then presses the key “http: / /aaa.aaa/e/ ”. Then, the trie tree generating unit 150a connects the pointer of the input key to the character “p” in the fourth row and the sixth column of the text table 14 (step S23b).

  Subsequently, the process proceeds to FIG. The trie tree generation unit 150a does not have a child node having “p” as a key in the node t (child), and therefore the tag key “p: //aaa.aaa/e/c/” of the node t (child). The priority is compared with the priority of the input key “p: //aaa.aaa/e/” from which “htt” in the trial part is removed. Then, since the 15th character of the input key is “empty” and the 15th character of the tag key is “c”, the priority of the tag key is higher than that of the input key.

  Therefore, the trie tree generation unit 150a returns from the node t (child) to the node t (parent) without exchanging the data of the node t (child) with the input data, and enters the input key “http: // aaa The pointer of “.aaa / e /” is set to “t” as the third character (step S24a).

  On the actual data, the trie tree generation unit 150a connects the pointer of the input key to the character “p” in the fourth row and sixth column of the text table 14. Further, the trie tree generation unit 150a sequentially compares the character string starting with the character connected to “TAG” of the pointer array 23 and the character string starting with the character connected to the pointer of the input key. Since the 15th character of the input key is “empty” and the 15th character of the tag key is “c”, it is determined that the priority of the tag key is higher than that of the input key. Then, the trie tree generating unit 150a sets the pointer of the input key to “t” in the fourth row and the fifth column (step S24b).

  Subsequently, the process proceeds to FIG. The trie tree generation unit 150a uses the priority of the tag key “tp: //aaa.aaa/e/” of the node t (parent) and the input key “tp: //aaa.aaa” from which “ht” of the trie part is removed. / e / ”priority. Then, the input key and the tag key have the same priority (the input key and the tag key are the same). In this case, the trie tree generation unit 150a adds the value “4” corresponding to the input key “http://aaa.aaa/e/” to the node t (step S25a).

  On the actual data, the trie tree generation unit 150a connects the pointer of the input key to the character “t” in the fourth row and the fifth column of the text table 14. Further, the trie tree generation unit 150a sequentially compares the character string starting with the character connected to “TAG” in the pointer array 22 and the character string starting with the character connected to the pointer of the input key. Since each character string leading up to the sky is equal, the priority of the tag key and the priority of the input key are determined to be equal (the tag key and the input key are the same). Then, the trie tree generation unit 150a adds the value “4” to “Data” to the pointer array 22 (step S25b).

  As shown in FIGS. 15 to 24, when the trie tree generation unit 150a generates a trie tree 140b, one key is assigned to one node, so that the memory usage of the trie tree 140b can be reduced. I can do it. In addition, when assigning a new input key to the trie tree 140b, the trie tree generation unit 150a does not compare all the tag keys with the input key, but compares only the tag key of the comparison target node with a new tag key. Therefore, the trie tree 140b can be generated so that the tag keys are arranged in the depth-first search order while reducing the processing load.

  It is assumed that various data (pointer array, text table, etc.) corresponding to the actual data shown in FIGS. 15 to 24 are stored in the storage unit 140.

  Returning to the description of FIG. 10, the trie tree searching unit 150b executes a process of extracting a total value of values registered in the trie tree 140b and a process of searching the trie tree 140b for a value corresponding to a predetermined key. Part.

  First, a process in which the trie tree searching unit 150b extracts a total value of values registered in the trie tree 140b will be described. The trie tree search unit 150b reads out the characters of the specified input key one by one from the beginning, traces each node, and sequentially outputs the tag key and value registered in the node in association with each other, thereby extracting the aggregate value To do. When a plurality of values are registered in the node, the trie tree search unit 150b may sum the values or may output them separately. As an example, the trie tree search unit 150b according to the present embodiment sums and outputs each value.

  FIGS. 25 to 27 are diagrams for explaining the process of extracting the total value. As shown in FIG. 25, in the trie tree 140b, a node h, a node t (parent), and a node t (child) are sequentially connected under the root node. Node h registers tag key “ttp: //aaa.aaa/d/” and value “3”, and node t (parent) has tag key “tp: //aaa.aaa/e/” and value “1”. 4 ”is registered, and the node t (child) has registered the tag key“ p: //aaa.aaa/e/c/ ”and the value“ 2 ”.

  In addition, in the description in FIGS. 25 to 27, the total value extraction process when the input key “http://aaa.aaa/e/” is designated will be described. In FIG. 25, the trie tree search unit 150b sets the first character of the input key “http://aaa.aaa/e/” as a pointer, and proceeds to the node h according to the character of the pointer.

  Since the node h is registered with the tag key “ttp: //aaa.aaa/d/” and the value “3”, the trie tree search unit 150b uses the trie part “h” as the tag key “ttp: // aaa. The key “http://aaa.aaa/d/” added to the head of “aaa / d /” and the value (total value) “3” are output (step S30a).

  On the actual data, the trie tree search unit 150b registers the input key “http://aaa.aaa/d/” in the fourth row and third column of the text table 14, and sets the input key pointer in the fourth row and third column. Connect to the row. The trie tree search unit 150 b connects the pointer of the current node to the pointer array 21. Further, the trie tree search unit 150b includes a character string “http://aaa.aaa/d/” up to the empty space before and after the character connected to “TAG” of the pointer array 21 corresponding to the node h, and “Data”. The value “3” connected to is output (step S30b).

  The description shifts to the description of FIG. The trie tree searching unit 150b sets the second character of the input key “http://aaa.aaa/e/” as a pointer, and moves from the node h to the node t (parent) according to the character of the pointer. Since the node t (parent) is registered with the tag key “tp: //aaa.aaa/e/” and the values “1, 4”, the trie tree searching unit 150b uses the trie part “ht” as the tag key “tp”. A value “5” obtained by adding the key added to the head of “: //aaa.aaa/e/” and the values “1, 4” is output (step S31a).

  On the actual data, the trie tree search unit 150b shifts the pointer connection destination of the input key by one character and connects to the character “t” in the fourth row and fourth column of the text table 14. The trie tree searching unit 150 b connects the pointer of the current node to the pointer array 22. Further, the trie tree search unit 150b includes a character string “http://aaa.aaa/e/” up to an empty space before and after the character connected to “TAG” of the pointer array 22 corresponding to the node t (parent), The total value “5” of the values “1, 4” connected to “Data” is output (step S31b).

  The description shifts to the description of FIG. The trie tree searching unit 150b sets the third character of the input key “http://aaa.aaa/e/” as a pointer, and moves from the node t (parent) to the node t (child) according to the pointer character. To do. Since the node t (child) is registered with the tag key “p: //aaa.aaa/e/c/” and the value “2”, the trie tree search unit 150b uses the trie part “htt” as the tag key “p”. The key added to the head of “: //aaa.aaa/e/c/” and the value (total value) “2” are output (step S32a).

  On the actual data, the trie tree search unit 150b shifts the pointer connection destination of the input key by one character and connects it to the character “t” in the fourth row and fifth column of the text table 14. Further, the trie tree search unit 150 b connects the pointer of the current node to the pointer array 23. Further, the trie tree search unit 150b uses the character string “http://aaa.aaa/e/c/” up to the character before and after the character connected to “TAG” of the pointer array 23 corresponding to the node t (child). Then, the value (total value) “2” connected to “Data” is output (step S32b).

  As shown in FIGS. 25 to 27, by sequentially reading the input keys and tracing the trie tree 140b, the total value corresponding to the input keys can be output.

  Next, a process in which the trie tree search unit 150b searches the trie tree 140b for a value corresponding to the designated input key will be described. Since the trie tree 140b is generated so that the tag keys are arranged in the depth-first search order, the trie tree search unit 150b may compare the tag key registered in the comparison target node with the input key. In addition, when comparing each node included in the comparison target node with the input key, the processing load can be further reduced by using the binary search method.

  In the following, a search process when the binary search method is used will be described. 28 to 31 are diagrams for explaining search processing when the binary search method is used. As shown in FIG. 28, in the trie tree 140b, a node h, a node t (parent), and a node t (child) are sequentially connected under the root node. Node h registers tag key “ttp: //aaa.aaa/d/” and value “3”, and node t (parent) has tag key “tp: //aaa.aaa/e”, value “1, 4 ”is registered, and the node t (child) has registered the tag key“ p: //aaa.aaa/e/c ”and the value“ 2 ”.

  In the description of FIGS. 28 to 31, search processing when the input key “http://aaa.aaa/d” is designated will be described. In FIG. 28, the trie tree search unit 150b reads characters sequentially from the first character of the input key “http://aaa.aaa/d”, and starts from the root node to node h, node t (parent), and node t (child). Transition in the order. Then, the trie tree searching unit 150b sets the pointer of the input key “http://aaa.aaa/d” to “p” which is shifted by three characters from the initial position “h”. Further, a stack is added to each transitioned node (step S40a).

  On the actual data, the trie tree search unit 150b adds stacks to the pointer arrays 21, 22, and 23 corresponding to the node h, the node t (parent), and the node t (child), respectively. In addition, the trie tree search unit 150b connects the pointer of the current node to the pointer array 23 (step S40b). Here, for convenience of explanation, the description of the input key “http://aaa.aaa/d” is omitted, but the information of the input key “http://aaa.aaa/d” is stored in the text table 14. It is assumed that

  Subsequently, the description proceeds to FIG. The trie tree search unit 150b transitions to the node t (parent) in the middle of the stack, and returns the pointer of the input key by the amount returned. Here, since the node t (child) has returned to the node t (parent), the pointer of the input key “http://aaa.aaa/d” is returned from “p” by “t (third character) T) ”.

  Then, the trie tree search unit 150b receives the priority of the tag key “tp: //aaa.aaa/e” of the node t and the input key “tp: //aaa.aaa/d” obtained by removing the trie part “ht”. Compare with the priority of. Then, since the 14th character of the input key is “d” and the 14th character of the tag key is “e”, the trie tree searching unit 150b determines that the priority of the tag key is higher than the priority of the input key. (Step S41a). When the priority of the node t (parent) tag key is higher than the priority of the input key, the node after the node t (parent) has no tag key to be searched.

  On the actual data, the trie tree search unit 150b moves the pointer of the current node to the pointer array 22 connected in the middle of the stack. Then, the trie tree search unit 150b leaves the character string “tp: //aaa.aaa/e” after the character connected to “TAG” in the pointer array 22 and the remaining input keys excluding the trie part “ht”. Compare with "tp: //aaa.aaa/d". Then, since the 14th character of the input key is “d” and the 14th character of the tag key is “e”, the trie tree searching unit 150b determines that the priority of the tag key is higher than the priority of the input key. (Step S41b).

  Subsequently, the description proceeds to FIG. 30. As described with reference to FIG. 29, when the priority of the node t (parent) tag key is higher than the priority of the input key, the node after the node t (parent) has no tag key to be searched. Therefore, the trie tree searching unit 150b deletes the stack added to the node t (parent) and the node t (child), which is the second half of the stack.

  The trie tree search unit 150b transitions to the node h in the middle of the stack, and returns the input key pointer by the amount returned. Here, since the node t (parent) has returned to the node h, the pointer of the input key “http://aaa.aaa/d/” is returned by one from “t (third character)” “t ( 2nd character) ”(step S42a).

  On the actual data, the trie tree generation unit 150a moves the pointer of the current node to the pointer array 21 connected in the middle of the stack (step S41b).

  The description shifts to the description of FIG. The trie tree searching unit 150b determines the priority of the tag key “ttp: //aaa.aaa/d/” of the node h and the input key “ttp: //aaa.aaa/d/” from which the trie part “h” is removed. Compare the priorities of. Then, since the priority of the tag key and the input key is equal (the tag key and the input key are the same), the trie tree search unit 150b is placed at the head of the tag key “ttp: //aaa.aaa/d/” connected to the node h. The key “http://aaa.aaa/d/” to which the trial part “h” is added and the value “3” are output as search results (step S43a).

  On the actual data, the trie tree search unit 150b determines the priority of the character string “ttp: //aaa.aaa/d/” after the character connected to “TAG” in the pointer array 21 and the trie part “h”. Compare the priorities of the remaining input keys “tp: //aaa.aaa/d/” with the key removed. Then, since the priority of the tag key and the input key is the same (the tag key and the input key are the same), the trie tree search unit 150b causes the character string “http: up to the space before and after the character connected to“ TAG ”of the pointer array 21 //aaa.aaa/d/ ”and the value“ 3 ”connected to“ Data ”are output (step S43b).

  Next, in FIG. 32 to FIG. 35, the search processing when the binary search method is used will be described using other examples. As illustrated in FIG. 32, the trie tree 140b connects the node a, the node b, and the node c under the root node. Node a registers tag key “aa” and value “3”, node b registers tag key “c” and value “1”, node c registers tag key “b” and value “2” It shall be. The relationship between node b and node c is that node b is an older brother node and node c is a younger brother node.

  In the description of FIGS. 32 to 35, search processing when the input key “ac” is designated will be described. In FIG. 32, the trie tree search unit 150b reads “a” from the input key “ac” and shifts the pointer of the input key from “a” to “c”. Further, the trie tree searching unit 150b adds a stack to the node a (step S50a).

  On the actual data, the trie tree search unit 150b adds a stack to the pointer array 21 corresponding to the node a. The trie tree search unit 150 b connects the pointer of the current node to the pointer array 21. The trie tree searching unit 150b sets the pointer of the input key to the character “c” in the first row and the 14th column of the text table 14 (step S50b).

  Subsequently, the description proceeds to FIG. The trie tree search unit 150b reads “c” specified by the pointer from the input key “ac”, and transitions to the node c. At the time of transition to the node c, the priority of the tag key registered in the ancestor node of the node a is all lower than the priority of the input key “ac”, so it is necessary to exclude it from the search target. Therefore, the trie tree searching unit 150b empties the stack once and adds a new node c to the stack. Also, the pointer of the input key is shifted by one character from “c”, and the pointer is set to “empty” (step S51a).

  On the actual data, the trie tree search unit 150 b designates the current node in the pointer array 23. The trie tree search unit 150 b deletes the stack connected to the pointer array 21 and adds the stack to the pointer array 23. In addition, the trie tree search unit 150b sets the pointer of the input key to “empty” on the 15th character in the first line of the text table 14 (step S51b).

  Subsequently, the description proceeds to FIG. Since the character designated by the pointer is “empty”, the trie tree search unit 150b sets the node c in the middle of the stack as the current node, and sets the priority of the tag key “b” of the node c and the trie part “ac”. Compare the priority of "empty" except. As a result of the comparison, the trie tree searching unit 150b determines that the priority of the tag key is higher than the priority of the input key (step S52a).

  On the actual data, the trie tree searching unit 150b sets the current node in the pointer array 23 corresponding to the middle of the stack, the character string starting with the character connected to “TAG” in the pointer array 23, and the input Compare "empty" connected to key pointer. As a result of the comparison, the trie tree searching unit 150b determines that the priority of the tag key is higher than the priority of the input key (step S52b).

  Subsequently, the description proceeds to FIG. Since the priority of the tag key is higher than the priority of the input key, the trie tree searching unit 150b deletes the stack of the node c that registers the tag key. Since all stacks are lost and there is no tag key that matches the input key “ac”, the trie tree search unit 150b outputs that no matching data exists (step S53a).

  On the actual data, the trie tree search unit 150b deletes the stack connected to the pointer array 28 corresponding to the node c because the priority of the tag key is higher than the priority of the input key. Since all the stacks are lost and there is no tag key that matches the input key “ac”, the trie tree search unit 150b outputs that no matching data exists (step S53b).

  In FIG. 28 to FIG. 35 described above, the trie tree search unit 150b executes the search process using the binary search method. However, the trie tree search unit 150b does not necessarily need to use the binary search method. . 36 to 40 are diagrams for describing search processing when the binary search method is not used. As shown in FIG. 36, in the trie tree 140b, node b, node a, node b, and node c are connected under the root node. Here, in order to distinguish each node b, the node b corresponding to the child node of the root node is expressed as node b (1), and the other node b is expressed as node b (2).

  Node b (1) registers tag key “a” and value “1”, node a registers tag key “aa” and value “3”, and node b (2) registers tag key “c” and value It is assumed that “1” is registered and the node c has registered the tag key “b” and the value “2”.

  36 to 40, search processing when the input key “baca” is designated will be described. In FIG. 36, the trie tree search unit 150b sets the pointer of the input key to the first character “b”, and transitions from the root node to the node b (1) by “b” designated by the pointer. Then, the trie tree search unit 150b sets the input key pointer to “a”, which is shifted by one character from “b” (step S60a).

  On the actual data, the trie tree search unit 150 b registers the input key “baca” in the text table 14 and connects the pointer of the input key to “b” in the second row and first column of the text table 14. The trie tree search unit 150b causes the pointer of the current node to transition from the pointer array 20 to the pointer array 21 by “b” connected to the pointer of the input key, and changes the pointer of the input key to “a” shifted by one character. Set (step S60b).

  Subsequently, the description proceeds to FIG. The trie tree search unit 150b transitions from the node b (1) to the node a by “a” designated by the pointer, and sets the pointer of the input key to “c” shifted by one character from “a” (step S61a). ).

  On the actual data, the trie tree search unit 150b shifts the pointer of the current node from the pointer array 21 to the pointer array 22 by “a” connected to the input key pointer, and shifts the input key pointer by one character. “C” is set (step S61b).

  Subsequently, the description proceeds to FIG. The trie tree search unit 150b transitions from the node a to the node c by “c” designated by the pointer, and sets the pointer of the input key to “a” shifted by one character from “c” (step S62a).

  On the actual data, the trie tree search unit 150b shifts the pointer of the current node from the pointer array 22 to the pointer array 24 by “c” connected to the input key pointer, and shifts the input key pointer by one character. “A” is set (step S62b).

  The description shifts to the description of FIG. The trie tree search unit 150b removes the priority of the tag key “b” registered in the node c and the trie part “bac” because the child node corresponding to “a” designated by the pointer does not exist in the node c. The priority of the input key “a” is compared. As a result of the comparison, the trie tree search unit 150b determines that the priority of the tag key is higher than the priority of the input key (step S63a).

  On the actual data, the trie tree search unit 150b compares the priority of the character “b” connected to “TAG” in the pointer array 24 with the priority of the character “a” connected to the pointer of the input key. . As a result of the comparison, the trie tree searching unit 150b determines that the priority of the tag key is higher than the priority of the input key (step S63b).

  The description shifts to the description of FIG. Since the node c has an older brother node (node b (2)), the trie tree search unit 150b has a node having a tag key that matches the input key at a node before the node c (node a, node b (1)). Is determined not to exist. The trie tree search unit 150b outputs that there is no corresponding data (step S64).

  By the way, when the key to be deleted is designated for the trie tree 140b, the trie tree search unit 150b deletes the designated input key from the trie tree 140b. FIG. 41 is a diagram for explaining the deletion process. Here, a case where the tag key “black” and the value “1” are deleted from the trie tree shown on the left side of FIG. 41 will be described.

  First, the trie tree searching unit 150b searches for the node l having the same tag key as the input key “black” in the same manner as the search process described above, and uses the tag key “ack” and the value “1” registered in the node l. delete.

  Then, the trie tree searching unit 150b registers the tag key “e (blue)” and the value “4” of the node u that becomes the eldest node of the node l in the node l. In addition, the trie tree search unit 150b registers the tag key “blueviolet” and the value “3” of the node e that is the eldest node of the node u in the node u, and deletes the node e from the trie tree. The trie tree searching unit 150b deletes the key “black” and the value “1” from the trie tree shown on the left side of FIG. 41, thereby generating the trie tree shown on the right side of FIG.

  Next, various processing procedures of the search device 100 according to the first embodiment will be described. First, the process in which the search device 100 according to the first embodiment generates the trie tree 140b will be described. FIG. 42 is a flowchart of the process procedure of the trie tree generation process according to the second embodiment.

  As shown in FIG. 42, the trie tree generation unit 150a generates a root node (step S101), and determines whether or not the next input data (key, value) exists in the registered data management table 140a (step S101). S102).

  If the trie tree generation unit 150a determines that the next input data does not exist in the registered data management table 140a (No in step S103), the trie tree generation unit 150a ends the process. On the other hand, if the next input data is registered in the registered data management table 140a (Yes in step S103), the trie tree generation unit 150a reads out unread input data (step S104) and executes data addition processing. (Step S105), the process proceeds to Step S102.

  Next, the procedure of the data addition process shown in step S105 of FIG. 42 will be described. Here, a case where the data addition process is executed without using the binary search method and a case where the data addition process is executed using the binary search method will be described separately.

  FIG. 43 and FIG. 44 are flowcharts showing a processing procedure of data addition processing that does not use the binary search method. As shown in FIG. 43, the trie tree generation unit 150a sets the current node as the root node (step S150), and determines whether or not the input key is empty (step S151).

  When the input key is not empty (No in step S152), the trie tree generation unit 150a refers to the child node with the key of the first character of the input key, and determines whether or not the child node exists (step S152). S153). If there is a child node (step S154, Yes), the trie tree generation unit 150a reads the first character of the input key, advances the pointer of the input key by one character, and sets the read character as a key to the child node. A transition is made (step S155), and the process proceeds to step S151.

  On the other hand, if there is no child node (No at Step S154), the trie tree generation unit 150a proceeds to Step S156.

  In step S152, if the input key is empty (step S152, Yes), the node information is referred to (step S156), and the priority of the tag key is equal to the priority of the input key (the tag key is the input key). It is determined whether or not (step S157). When the priority of the tag key and the priority of the input key are equal (step S158, Yes), the trie tree generation unit 150a adds an input value (value corresponding to the input key) to the current node (step S159). The data addition process is terminated.

  On the other hand, when the priority of the tag key is different from the priority of the input key (No in step S158), the trie tree generating unit 150a determines whether the priority of the tag key is higher than the priority of the input key. (Step S160). When the priority of the tag key is lower than the priority of the input key (step S161, No), the process proceeds to step S164.

  If the priority of the tag key is higher than the priority of the input key (step S161, Yes), it is determined whether there is an older brother node or whether the parent node is a root node (step S162). When there is no brother node and the parent node is not the root node (when the condition is not satisfied) (step S163, No), the input key pointer is returned by one character, and the transition is made to the parent node ( Step S164) and the process proceeds to Step S160.

  On the other hand, if the older brother node exists or the parent node is the root node (when the condition is satisfied) (step S163, Yes), the tag key, the value and the input key, and the input value of the current node are respectively exchanged ( Step S168) and the process proceeds to Step S165.

  By the way, if the priority of the tag key is lower than the priority of the input key in step S161 (step S161, No), the trie tree generation unit 150a refers to the child node with the key of the first character of the input key, It is determined whether or not a child node exists (step S165).

  When there is a child node (step S166, Yes), the trie tree generation unit 150a reads the first character of the input key, advances the pointer of the input key by one character, and transitions to the child node using the read character as a key. (Step S167), the process proceeds to Step S168.

  On the other hand, if no child node exists (step S166, No), the trie tree generation unit 150a generates a new node (step S169), reads the first character of the input key, and sets the input key pointer to one character. Then, using the read character as a key, the current node is connected to the new node (step S170).

  The trie tree generation unit 150a adds the input key as a tag key to the new node (step S171), adds the input value to the new node (step S172), and ends the data addition process.

  45 to 47 are flowcharts showing a processing procedure of data addition processing using the binary search method. The trie tree generation unit 150a sets the current node as the root node (step S180), and determines whether or not the input key is empty (step S181).

  If the input key is empty (step S182, Yes), the trie tree generation unit 150a proceeds to step S190. On the other hand, when the input key is not empty (step S182, No), the trie tree generation unit 150a refers to the child node with the key of the first character of the input key, and determines whether or not the child node exists. (Step S183).

  When a child node exists (step S184, Yes), the trie tree generation unit 150a determines whether the child node is the eldest son (step S185), and when the child node is the eldest son (step S186). , Yes), the process proceeds to step S188.

  On the other hand, when the child node is not the eldest son (step S186, No), the trie tree generation unit 150a sets the stack to empty (step S187), reads the first character of the input key, and sets the input key pointer. One character is advanced, and the read character is used as a key to make a transition to the child node (step S188). The trie tree generation unit 150a adds the transitioned node to the stack (step S189), and proceeds to step S181.

  By the way, when there is no child node in Step S184 (No in Step S184), the trie tree generation unit 150a determines whether or not the stack is empty (Step S191), and the stack is not empty. (Step S191, No), the data in the middle of the stack is set as the current node, and the input key pointer is shifted by the amount moved (step S192).

  Shifting to FIG. The trie tree generation unit 150a determines whether the priority of the tag key and the priority of the input key are equal (step S193), and if the priority of the tag key and the priority of the input key are equal (step S194, Yes). ), An input value is added to the current node (step S195).

  On the other hand, when the priority of the tag key and the priority of the input key are different (No in step S194), the trie tree generating unit 150a determines whether the priority of the tag key is higher than the priority of the input key. (Step S196).

  If the priority of the tag key is higher than the priority of the input key (step S197, Yes), the trie tree generation unit 150a deletes the second half of the stack including the middle stack (step S199), and FIG. The process proceeds to step S190.

  On the other hand, when the priority of the tag key is lower than the priority of the input key (No at Step S197), the trie tree generation unit 150a deletes the first half of the stack including the middle stack (Step S198). The process proceeds to step S190 of 45.

  By the way, when the stack is empty in step S191 of FIG. 45 (step S191, Yes), the process proceeds to FIG. 47, and the trie tree generation unit 150a refers to the child node with the key of the first character of the input key, It is determined whether or not a child node exists (step S200).

  If there is a child node (Yes in step S201), the trie tree generation unit 150a reads the first character of the input key, advances the pointer of the remaining input key by one character, and uses the read character as a key to set the child node. (Step S202). Then, the trie tree generation unit 150a exchanges the tag key, value, input key, and input value of the current node (step S203), and proceeds to step S200.

  On the other hand, if there is no child node (No in step S201), the trie tree generation unit 150a generates a new node (step S204), reads the first character of the input key, and sets the pointer of the remaining input key to 1. The character is advanced and the current character is connected to the new node using the read character as a key (step S205). The trie tree generation unit 150a adds the input key as a tag key to the new node (step S206), and adds the input value to the new node (step S207).

  Next, a process in which the search device 100 according to the present embodiment performs a search using the trie tree 140b will be described. Here, a case where search processing is executed without using the binary search method and a case where search processing is executed using the binary search method will be described.

  First, a processing procedure of search processing that does not use the binary search method will be described. FIG. 48 is a flowchart showing a processing procedure of search processing that does not use the binary search method. As shown in FIG. 48, the trie tree searching unit 150b sets the current node as the root node (step S300), and determines whether or not the input key is empty (step S301).

  If the input key is not empty (No in step S302), the trie tree searching unit 150b refers to the child node with the key of the first character of the input key, and determines whether or not the child node exists (step). S303). If there is no child node (No at Step S304), the trie tree searching unit 150b proceeds to Step S306.

  On the other hand, if there is a child node (Yes in step S304), the trie tree search unit 150b reads the first character of the input key, advances the pointer of the input key by one character, and uses the read character as a key to the child node. (Step S305), the process proceeds to Step S301.

  By the way, when the input key is empty in step S302 (step S302, Yes), the trie tree search unit 150b refers to the node information and determines whether the priority of the tag key is equal to the priority of the input key. Is determined (step S306). When the priority of the tag key and the priority of the input key are equal (Yes in step S307), the trie tree search unit 150b outputs data (value) of the current node (step S308).

  On the other hand, if the priority of the tag key is different from the priority of the input key (No in step S307), the trie tree search unit 150b determines whether the priority of the tag key is higher than the priority of the input key. (Step S310). When the priority of the tag key is smaller than the priority of the input key (No at Step S310), the trie tree searching unit 150b proceeds to Step S314.

  On the other hand, if the priority of the tag key is higher than the priority of the input key (step S310, Yes), the trie tree search unit 150b determines whether there is an older brother node or whether the parent node is the root node. Is determined (step S311).

  When there is no brother node and the parent node is not the root node (when the condition is not satisfied) (No in step S312), the trie tree search unit 150b returns the input key pointer by one character, (Step S313).

  On the other hand, the trie tree searching unit 150b outputs that no matching data exists when there is an older brother node or when the parent node is a root node (when the condition is satisfied) (Yes in step S312) (step S312). Step S314).

  Subsequently, a processing procedure of search processing using the binary search method will be described. FIG. 49 and FIG. 50 are flowcharts showing the processing procedure of search processing using the binary search method. As shown in FIG. 49, the trie tree searching unit 150b sets the current node as the root node (step S350), and determines whether or not the input key is empty (step S351).

  If the input key is empty (Yes in step S352), the trie tree searching unit 150b proceeds to step S360 in FIG. On the other hand, when the input key is not empty (step S352, No), the trie tree searching unit 150b determines whether a child node exists with the key of the first character of the input key (step S353).

  If there is no child node (No in step S354), the trie tree searching unit 150b proceeds to step S360 in FIG. On the other hand, when there is a child node (Yes in step S354), the trie tree searching unit 150b determines whether the child node is the eldest son (step S355).

  When the child node is the eldest son (step S356, Yes), the trie tree searching unit 150b proceeds to step S358. On the other hand, when the child node is not the eldest son (step S356, No), the trie tree search unit 150b sets the stack to be empty (step S357).

  The trie tree search unit 150b reads the first character of the input key, advances the pointer of the input key by one character, and transitions to a child node using the read character as a key (step S358). Then, the trie tree searching unit 150b adds the transitioned node to the stack (step S359), and proceeds to step S351.

  By the way, if the input key is empty in step S352 (step S352, Yes), or if no child node exists in step S354 (step S354, No), the trie tree searching unit 150b in FIG. The process proceeds to step S360.

  In FIG. 50, the trie tree search unit 150b determines whether or not the stack is empty (step S360), and if the stack is empty (step S361, Yes), outputs information indicating that there is no matching data. (Step S362).

  On the other hand, when the stack is not empty (step S361, No), the trie tree search unit 150b sets the middle node of the stack as the current node and shifts the input key pointer by the amount moved (step S363).

  The trie tree searching unit 150b determines whether the priority of the tag key and the priority of the input key are equal (step S364), and if the priority of the tag key and the priority of the input key are equal (step S365, Yes). ), Data (value) of the current node is output (step S366).

  On the other hand, if the priority of the tag key and the priority of the input key are different (No in step S365), the trie tree searching unit 150b determines whether the priority of the tag key is higher than the priority of the input key. (Step S367).

  When the priority of the tag key is lower than the priority of the input key (No at Step S368), the trie tree searching unit 150b deletes the first half of the stack including the middle stack (Step S369), and proceeds to Step S360. To do.

  On the other hand, when the priority of the tag key is higher than the priority of the input key (Yes in step S368), the trie tree searching unit 150b deletes the second half of the stack including the middle stack (step S370), and step S360. Migrate to

  Next, a process in which the search device 100 extracts a total value will be described. FIG. 51 is a flowchart illustrating the processing procedure of the total value extraction processing. As shown in FIG. 51, the trie tree search unit 150b sets the current node as the root node (step S400), and determines whether there is a child node (step S401).

  When there is a child node (Yes in step S402), the trie tree search unit 150b transitions to the eldest node among the child nodes (step S403), and processes and outputs various data of the current node ( Step S404) and the process proceeds to Step S401. In step S404, for example, when a plurality of values are registered in the eldest son node, the trie tree search unit 150b performs a process of adding each value and outputs the added value.

  On the other hand, when there is no child node (step S402, No), the trie tree search unit 150b determines whether there is a younger brother node (step S405), and when there is a younger brother node (step S405). (S406, Yes), transition to the next younger brother node (step S407), and transition to step S404.

  On the other hand, if there is no younger brother node (step S406, No), the trie tree search unit 150b transitions to the parent node (step S408) and determines whether the current node is the root node (step S408). S409).

  When the current node is not the root node (No at Step S410), the trie tree searching unit 150b proceeds to Step S405. On the other hand, when the current node is the root node (step S410, Yes), the trie tree search unit 150b ends the process.

  Next, a deletion process in which the search device 100 deletes the data of the trie tree 140b will be described. 52 and 53 are flowcharts showing the procedure of the deletion process. As shown in FIG. 52, the trie tree searching unit 150b sets the current node as the root node (step S450), and determines whether or not the input key is empty (step S451).

  When the input key is not empty (step S452, No), the trie tree searching unit 150b refers to the child node with the key of the first character of the input key, and determines whether or not the child node exists (step S453). ). If there is no child node (No in step S454), the trie tree searching unit 150b proceeds to step S456.

  On the other hand, if there is a child node (Yes in step S454), the trie tree search unit 150b reads the first character of the input key, advances the pointer of the input key by one character, and sets the read character as a key to the child node. A transition is made (step S455), and the process proceeds to step S451.

  By the way, in step S452, when the input key is empty (Yes in step S452), the trie tree searching unit 150b refers to the node information and determines whether the priority of the tag key is equal to the priority of the input key. Determination is made (step S456).

  When the priority of the tag key is not equal to the priority of the input key (No in step S457), the trie tree searching unit 150b determines whether the priority of the tag key is higher than the priority of the input key (step S457). S458). When the priority of the tag key is smaller than the priority of the input key (No in step S459), the trie tree searching unit 150b proceeds to step S463.

  When the priority of the tag key is higher than the priority of the input key (step S459, Yes), the trie tree searching unit 150b determines whether there is an older brother node or whether the parent node is the root node. (Step S460).

  When there is no brother node and the parent node is not the root node (when the condition is not satisfied) (step S461, No), the trie tree search unit 150b returns the input key pointer by one character, (Step S462), the process proceeds to Step S456.

  On the other hand, the trie tree search unit 150b outputs that no deletion data exists (step S463) when the brother node exists or the parent node is the root node (step S461, Yes).

  Incidentally, in step S457, when the priority of the tag key is equal to the priority of the input key (step S457, Yes), the trie tree searching unit 150b proceeds to step S464 in FIG.

  The trie tree search unit 150b determines whether there is data (value) to be deleted (step S464). If there is no data to be deleted (step S465, No), no deleted data exists. A message is output (step S466).

  On the other hand, when there is data to be deleted (Yes in step S465), the trie tree searching unit 150b determines whether there is other data (value) (step S467). The trie tree search unit 150b ends the process when other data exists (step S468, Yes).

  On the other hand, when there is no other data (No at Step S468), the trie tree searching unit 150b determines whether there is a child node (Step S469). When there is no child node (No in step S470), the trie tree searching unit 150b deletes (disconnects) the edge of the parent node to the current node, and deletes the current node (step S471).

  On the other hand, when there is a child node (step S470, Yes), the trie tree searching unit 150b sets the current node data as the eldest son node data (step S472), and transitions to the eldest son node (step S473). The process proceeds to S469.

  As described above, when the trie tree generation unit 150a creates the trie tree 140b, the search device 100 according to the present embodiment associates one tag key with one node and eliminates a node having no tag key. Memory usage efficiency can be improved.

  In addition, when the trie tree generating unit 150a registers a tag key in each node of the trie tree 140b, the search device 100 according to the present embodiment registers a tag key having a low priority in the tag key on the root node side. When the search unit 150b executes a search process or the like, it is possible to narrow down the area of the node to be compared and improve the processing efficiency of the search process.

  First, the problem of the search device 100 according to the first embodiment will be described. FIG. 54 is a diagram for explaining the problem of the search device 100 according to the first embodiment. In the trie tree shown in FIG. 54, a node h, a node t (parent), and a node t (child) are connected in order to the root node, and the node h has a tag key “ttp: //aaa.aaa/e/”. Node t (parent) has a tag key “tp: //aaa.aaa/e/c/” and node t (child) has a tag key “p: //aaa.aaa/g/” Yes. Here, for convenience of explanation, description of values is omitted, but each node has a value.

  For example, when the search device 100 newly registers a key, characters are read in order from the first character of the input key to be registered, and each node of the trie tree is transitioned using the read character as a key. Then, the search apparatus 100 registers the input key by sequentially comparing each character of the tag key registered in the node with each character of the input key in order from the transition destination node, and determining the priority level. Was.

  Specifically, the input key to be registered is described as “http://aaa.aaa/b/”. The search device 100 reads the characters of the input key in order from the first character, and transitions between the nodes of the trie tree using the read characters as keys. Here, since the characters “h, t, t” are read in order, the transition from the root node to node h, node t (parent), node t (child) is made, and the current node is set to node t (child) To do.

  Then, the search device 100 uses the key “p: //aaa.aaa/d/” obtained by removing the trie part “htt” from the input key and the tag key “p: //aaa.aaa/g” of the node t (child). When “/” is compared character by character from the beginning, the priority of the tag key is higher than the priority of the input key, so the search device 100 transitions the current node to the node t (parent).

  The search apparatus 100 uses “tp: //aaa.aaa/b/” obtained by removing the trial part “ht” from the input key and the tag key “tp: //aaa.aaa/e/c/” of the node t (parent). ”Is compared character by character from the beginning, the priority of the tag key is higher than the priority of the input key, so the search device 100 moves the current node to the node h.

  The search device 100 adds “ttp: //aaa.aaa/b/” obtained by removing the trie part “h” from the input key and the tag key “ttp: //aaa.aaa/e/” of the node h from the top. When comparing character by character, the priority of the tag key is higher than the priority of the input key. Here, since the parent node of the node h is the root node, the search device 100 determines to register “ttp: //aaa.aaa/b/” in which the try part “h” is removed from the input key in the node h.

  As described above, the search device 100 according to the first embodiment determines a node to register an input key by sequentially comparing each character of the tag key of each node and each character of the input key. However, referring to each tag key of the trie tree shown in FIG. 54, the tag key “http://aaa.aaa/” including the trie portion is common. As described above, even when a part of each tag key is common, the search device 100 according to the first embodiment performs the comparison in order from the first character, and thus the processing efficiency is poor.

  For example, after comparing the input key with the tag key “p: //aaa.aaa/g/” of the node t (child), the tag key “tp: //aaa.aaa/e/c” of the node t (parent) / "And the input key, the tag key" tp: //aaa.aaa/ "has already been compared, so the input key and tag key" tp: //aaa.aaa/e/c/ It is useless to compare each character from the beginning.

  The search device according to the second embodiment increases the processing speed by eliminating the waste of the search device according to the first embodiment. FIG. 55 is a diagram for explaining the outline of the search device according to the second embodiment. As shown in the figure, when the search device according to the second embodiment generates a trie tree, the tag key of the child node is compared with the tag key of the parent node. Then, when registering the tag key in the parent node, the search device does not register all the tag keys but registers only the character string of the portion that does not match the child node in the parent node. In addition, the search device also registers the number of characters that match the tag key of the child node and the tag key of the parent node in the parent node.

  For example, as shown in FIG. 55, when the tag key of the parent node is “tp: //aaa.aaa/e/c/” and the tag key of the child node is “p: //aaa.aaa/g/” Since the matching character is “(t) p: //aaa.aaa/”, the number of characters “13” that matches the parent node and the remaining character string “e / c /” are registered. In the following description, the number of matching characters is expressed as the number of matches.

  If the tag key of the parent node is “ttp: //aaa.aaa/e/” and the tag key of the child node is “tp: //aaa.aaa/e/c/”, the matching character is “( t) tp: //aaa.aaa/e/ ”, so that the number of matches“ 16 ”is registered in the parent node. In this case, since the matching character string is directly used as the tag key of the parent node, the character string is not registered in the parent node.

  As shown in FIG. 55, by generating a trie tree, it is possible to eliminate the waste of redundantly comparing character strings that have been compared once, as in the search device 100 of the first embodiment. Specifically, the input key to be registered is described as “http://aaa.aaa/b/”.

  The search device according to the second embodiment reads the characters of the input key in order from the top, and transitions each node of the trie tree using the read characters as keys. Here, since the characters “h, t, t” are read in order, the transition from the root node to node h, node t (parent), node t (child) is made, and the current node is set to node t (child) To do.

  The search apparatus according to the second embodiment has a key “p: //aaa.aaa/b/” obtained by removing the try part “htt” from the input key and a tag key “p: // aaa. When comparing “aaa / g /” one character at a time from the beginning, the priority of the tag key is higher than the priority of the input key, so the search device transitions the current node to the node t (parent).

  The search device according to the second embodiment compares “tp: //aaa.aaa/b/” obtained by removing the try part “ht” from the input key and the tag key of the node t (parent). Here, since the number of matches “13” is registered in the parent node t (parent), the search device compares the 13th character from the beginning of the key “tp: //aaa.aaa/b/”. Processing is skipped, and comparison is made with the tag key “e / c /” of node t (parent) from the 14th character. Then, since the priority of the tag key is higher than the priority of the input key, the search device shifts the current node to the node h.

  The search device according to the second embodiment compares the tag key of the node h with “ttp: //aaa.aaa/b/” obtained by removing the try portion “h” from the input key. Here, since the number of matches “16” is registered in the node h, the search device skips the comparison process from the head to the 16th character in the key “ttp: //aaa.aaa/b/”. . Then, the key to be compared becomes empty. In this case, it is determined that the tag key is larger than the input key. Here, since the parent node of the node h is the root node, the search device determines to register “ttp: //aaa.aaa/b/”, which is obtained by removing the try part “h” from the input key, in the node h.

  As described above, when comparing the tag key of each node with the input key, the search device according to the second embodiment does not compare the characters of each key in order from the first character, but compares the characters to be compared by the number of matches. Skipping can speed up the process of registering the input key in the trie tree.

  By the way, in the example shown in FIG. 55, the process in the case of newly registering an input key has been described. However, when searching for a tag key that matches the input key from the trie tree, the search process is similarly performed using the number of matches. The processing efficiency can be improved.

  Next, the configuration of the search device 200 according to the second embodiment will be described. FIG. 56 is a diagram illustrating the configuration of the search device 200 according to the second embodiment. As shown in FIG. 56, the search device 200 includes an input unit 210, an output unit 220, an input / output control unit 230, a storage unit 240, and a control unit 250.

  Among these, the input unit 210 is an input unit for inputting information such as input keys, and corresponds to a keyboard, a mouse, or the like. The output unit 220 is an output unit that outputs information such as search results using a trie tree, and corresponds to a monitor, a display, a touch panel, or the like. The input / output control unit 230 is a processing unit that controls input / output of data by the input unit 210, the output unit 220, the storage unit 240, and the control unit 250.

  The storage unit 240 is a storage unit that stores data and programs necessary for various processes performed by the control unit 250. As shown in FIG. 56, the storage unit 240 includes a registration data management table 240a and a trie tree 240b.

  Here, the registration data management table 240a is a table that stores the keys and values registered in the trie tree in association with each other. FIG. 57 is a diagram illustrating an example of the data structure of the registration data management table 240a according to the second embodiment. As shown in FIG. 57, the registered data management table 240a stores keys and values in association with each other.

  The trie tree 240b is a trie tree generated based on the registered data management table 240a. FIG. 58 is a diagram illustrating an example of the data structure of the trie tree according to the second embodiment. FIG. 58 shows a trie tree corresponding to the registered data management table 240a shown in FIG. 57 as an example. As shown in FIG. 58, node b and node g are connected to the root node, and node l is connected to node b.

  The node b has a match number “1”, a tag key “ack”, and a value “2”, and the node l has a match number “0”, a tag key “ue”, and a value “1, 3”, and the node g Has a match number “0”, a tag key “reen”, and a value “4”.

  If the trie tree 240b shown in FIG. 58 is represented by real data, the data structure shown in FIG. 59 is obtained. FIG. 59 is a diagram showing an example of a data structure when the trie tree shown in FIG. 58 is represented by real data. As shown in FIG. 59, the trie tree 240b has pointer arrays 30 to 33 and a text table 34.

  Here, the pointer array 30 connected to the root node pointer corresponds to the root node in FIG. 58, and the pointer array 31 corresponds to the node b in FIG. The pointer array 32 corresponds to the node l in FIG. 58, and the pointer array 33 corresponds to the node g in FIG.

  The pointer arrays 30 to 33 have a “match” area, a “TAG” area, and a “Data” area. “Match” expresses the number of node matches by associating with a numerical value. “TAG” represents a tag key connected to a node by associating with a character in the text table 34. For example, since the pointer array 31 is connected to “a” in the text table 34, the character string “ack” from “a” to the next space is designated as a tag key. “Data” expresses a value connected to a node by associating it with a value. For example, the pointer array 31 is connected to the value “2”.

  Further, each of the pointer arrays 30 to 33 has a key number (pointer) “0 × 00 to 0 × FF” for determining a pointer array connected to the subordinate array. For example, the key number “0 × 62” of the pointer array 30 is connected to the pointer array 31, and the key number “0 × 67” is connected to the pointer array 33.

  Returning to the description of FIG. 56, the control unit 250 is a control unit that includes an internal memory for storing programs and control data that define various processing procedures, and executes various processes. As shown in FIG. 56, the control unit 250 includes a trie tree generation unit 250a and a trie tree search unit 250b.

  The trie tree generation unit 250a is a process of generating the trie tree 240b based on the key registered in the registration data management table 240a. Note that the trie tree generation unit 250a generates trie trees so that the tag keys are arranged in the depth-first search order, as in the first embodiment. Further, as described with reference to FIG. 55, the trie tree generation unit 250a compares the tag key of the parent node with the tag key of the child node, and registers the number of matching characters in the node as the number of matches. In addition, the trie tree generation unit 250a deletes the character string in which the tag key of the parent node and the tag key of the child node match, and registers only the remaining character string as a tag key in the node.

  Hereinafter, a process in which the trie tree generation unit 250a generates a trie tree will be described in detail. FIGS. 60 to 69 are diagrams for explaining processing for generating a trie tree according to the second embodiment. Here, for convenience of explanation, the key “http://aaa.aaa/e/”, the value “1”, the key “http://aaa.aaa/e/c/”, the value “2”, and the key “ A case where a trie tree is generated in the order of “http://aaa.aaa/d/”, value “3”, key “http://aaa.aaa/e/”, and value “4” will be described.

  As shown in FIG. 60, first, a case where a key “http://aaa.aaa/e/” and a value “1” are added in a state where no node exists will be described. The trie tree generation unit 250a generates a root node (step S70a). On the actual data, the trie tree generation unit 250 a generates a pointer array 30 corresponding to the root node, and connects the root node pointer and the pointer array 30. Further, since the pointer array 30 corresponds to the root node, “TAG” is connected to the empty (step S70b).

  The trie tree generation unit 250a prepares an input key “http://aaa.aaa/e/” (step S71a). On the actual data, the trie tree generation unit 250a stores the input key “http://aaa.aaa/e/” in the text table 34, and sets the input key pointer in the first row and first column of the text table 34. To "h" (step S71b).

  The trie tree generation unit 250a refers to the root node because there is no child node whose key is the first character “h” of the input key “http://aaa.aaa/e/”. Here, since the tag key does not exist in the root node, the priority of the input key “http://aaa.aaa/e/” becomes higher than the priority of the tag key of the root node.

  Therefore, the trie tree generation unit 250a creates a node using “h” as a key under the root node, and removes the trie part “h” from the input key “http://aaa.aaa/e/”. The key “ttp: //aaa.aaa/e/” is used as a tag key to connect to the node h. In addition, the trie tree generation unit 250a connects the number of matches “0” and the value “1” to the node h (step S72a).

  On the actual data, the trie tree generation unit 250 a generates the pointer array 31 corresponding to the node h, and connects the pointer array 30 and the pointer array 31 with the key number “0 × 68” of the pointer array 30. The trie tree generation unit 250 a connects “TAG” in the pointer array 31 to “t” in the first row and second column of the text table 34, and connects 1 to “Data” in the pointer array 31. In addition, the trie tree generation unit 250a sets the match (number of matches) of the pointer array 31 to “0” (step S72b).

  Next, the case where the key “http://aaa.aaa/e/c/” and the value “2” are added to the trie tree created in steps S72a and 72b will be described with reference to FIG. The trie tree generation unit 250a transitions from the root node to the node h at the first character h of the input key “http://aaa.aaa/e/c/”. Then, the trie tree generation unit 250a advances the pointer of the input key “http://aaa.aaa/e/c/” by one and sets it to “t” of the second character (step S73a).

  On the actual data, the trie tree generating unit 250a leaves one key “http://aaa.aaa/e/” registered last in the text table 34 and the key “http: // aaa”. .aaa / e / c ”. Then, the trie tree generation unit 250a connects the pointer of the input key to the character “t” in the second row and second column of the text table 34 (step S73b).

  Since there is no child node having “t” as a key in the node h, the trie tree generation unit 250a determines the priority of the tag key “ttp: //aaa.aaa/e/” of the node h and “ The priority of the input key “ttp: //aaa.aaa/e/c/” from which “h” is removed is compared. Since the number of matches of node h is “0”, the trie tree generation unit 250a performs comparison in order from the top of the input key.

  Then, since the 17th character of the input key is c and the 17th character of the tag key is empty, the trie tree generation unit 250a determines that the priority of the input key is higher than the priority of the tag key. In addition, the trie tree generation unit 250a compares the input key and the tag key, and determines that the 16 characters “ttp: //aaa.aaa/e/” match (step S74).

  Subsequently, the flow proceeds to FIG. The trie tree generation unit 250a registers the number of matches “16” in the node h, and advances the pointer of the tag key “ttp: //aaa.aaa/e/” of the node h by 16 characters. As a result, the tag key connected to the node h becomes empty.

  The trie tree generation unit 250a generates a new node t using the second character “t” of the input key “ttp: //aaa.aaa/e/c/” as a key, and sets the input key pointer to three characters. The process proceeds to “t” of the eye (step S75a).

  On the actual data, the trie tree generation unit 250 a generates the pointer array 32 corresponding to the node t, and connects the pointer array 31 and the pointer array 32 with the key number “0 × 74” of the pointer array 31. The trie tree generation unit 250a registers the number of matches “16” in the “match” of the node h, advances the character connected to “TAG” by 16 characters, and sets it to empty in the first row and the 18th column of the text table 34. To do. The trie tree generation unit 250a advances the input key pointer by one and connects the input key pointer to “t” in the second row and third column of the text table 34 (step S75b).

  The trie tree generation unit 250a removes the “ht” of the trie part from the input key “http://aaa.aaa/e/c/” and the remaining key “tp: //aaa.aaa/e/c/” Is registered as a tag key of the node t. The trie tree generation unit 250a registers the value “2” corresponding to the input key “http://aaa.aaa/e/c/” in the node t. Also, the trie tree generation unit 250a registers the number of matches “0” in the node t (step S76a).

  On the actual data, the trie tree generation unit 250a connects “TAG” in the pointer array 32 to “t” in the second row and third column of the text table 34, and “Data” and the value “2” in the pointer array 32 are displayed. Connect. Further, the trie tree generation unit 250a registers the number of matches “0” in the “match” of the pointer array 32 (step S76b).

  Next, the case where the input key “http://aaa.aaa/d/” and the value “3” are added to the trie tree created in steps S76a and 76b will be described with reference to FIG. The trie tree generation unit 250a extracts characters one by one from the first character of the input key “http://aaa.aaa/d/”, and transitions on the trie tree in the order of nodes h and t. Then, the trie tree generation unit 250a advances the pointer of the input key “http://aaa.aaa/d/” by two in accordance with the number of transitioned nodes, and sets the third character “t”.

  Since there is no child node having “t” as a key in the node t, the trie tree generating unit 250a determines the priority of the tag key “tp: //aaa.aaa/e/c” of the node t and the trie portion. The priority of the input key “tp: //aaa.aaa/d/” with “ht” removed is compared. Then, since the 14th character of the tag key is “e” and the 14th character of the input key is “d”, the priority of the tag key is higher than the priority of the input key (step S77a).

  On the actual data, the trie tree generation unit 250a leaves one key “http://aaa.aaa/e/c” registered last in the text table 34 and the key “http: // "aaa.aaa/d/" is registered. Then, the trie tree generation unit 250 a connects the pointer of the input key to the character “t” in the third row and the fifth column of the text table 34. When the character string starting with the character connected to “TAG” in the pointer array 32 and the character string starting with the character connected to the pointer of the input key are sequentially compared, the 14th character of the tag key is “ e ”and the 14th character of the input key is“ d ”, the priority of the tag key is greater than the priority of the input key (step S77b).

  The trie tree generation unit 250a compares the input key and the tag key to determine the number of generations. This number of generations is a numerical value indicating whether the input key is the same as the tag key up to the character number. The trie tree generation unit 250a has a key “tp: //aaa.aaa/d” obtained by removing the tag part “ht” from the tag key “tp: //aaa.aaa/e/c” and the input key registered in the node t. When comparing "/", the 13 characters "tp: //aaa.aaa/" from the beginning match, so the number of generations is 13.

  The trie tree generation unit 250a advances the pointer of the input key “http://aaa.aaa/d/” by 13 characters from the current third character “t” and sets it to “d”. Then, the trie tree generation unit 250a moves the current node to the node h, adds 1 to the number of generations, and sets the number of generations to 14 (step S78a). This is because the character of the input key to be compared is increased by one character by transitioning to the node h that is the parent node, but the increased character matches the tag key of the parent node.

  On the actual data, the trie tree generation unit 250a connects the pointer of the input key to the character “d” in the third row and the 18th column of the text table 34. Also, the trie tree generation unit 250a determines the number of generations and registers “14” as the number of generations. Further, the pointer of the current node is connected to the pointer array 31 (step S78b).

  Subsequently, the flow proceeds to FIG. The trie tree generation unit 250a compares the priority of the tag key of the node h with the number of matches registered in the node h before comparing the priority of the input key “http://aaa.aaa/d/”. Compare the number of key generations. Since the number of matches of the tag key of the node h is “16” and the number of generations of the input key is “14”, the number of matches is larger than the number of generations.

  When the number of matches is larger than the number of generations, the trie tree generation unit 250a does not directly compare the priority of the tag key of the node h and the priority of the input key “http://aaa.aaa/d/”. However, it can be determined that the priority of the tag key of node h is higher.

  For example, the 14th generation input key indicates that the 13th character from the first character is the same as the tag key of the node t that is a child node of the node h, and the priority of the input key is the node at the 14th character. Less than t priority. And if the number of matches of node h is greater than the number of generations of input keys, the tag key of node h is at least the same until the character that made the priority of the tag key of node t greater than the priority of the input key. It is. Therefore, the trie tree generation unit 250a does not directly compare the priority of the tag key of the node h and the priority of the input key “http://aaa.aaa/d/”, and the priority of the tag key of the node h. Can be determined to be larger.

  Since the parent node of the node h is the root node, the trie tree generation unit 250a exchanges the data (number of matches, tag key, value) of the node h and input data (number of generations, input key, value). Specifically, the trie tree generation unit 250a registers the generation number “14” of the input key as the coincidence number in the node h, and also registers the input key value “3” in the node h. Further, the character string “d /” after the pointer of the input key “http://aaa.aaa/d/” is registered in the tag key of the node h.

  Then, the trie tree generation unit 250a sets the current input key to “http://aaa.aaa/e/”, the value “1”, and the number of generations “16”. In addition, the trie tree generation unit 250a sets the input key pointer to “/”, which is 16 characters shifted from the first character. The trie tree generation unit 250a shifts to the node t that is a child node of the node h, and sets the input key pointer to “empty” shifted by one character (step S79a).

  On the actual data, the trie tree generation unit 250a connects “TAG” in the pointer array 31 and “t” in the third row and eighth column of the text table 34, and “14” in “match” in the pointer array 31. Register. Further, the input key pointer is connected to “empty” in the first row and the 18th column of the text table 34. In addition, the trie tree generation unit 250a sets the current generation number to “16” (step S79b).

  The trie tree generation unit 250a sets the number of generations to “15” by subtracting 1 from the number of generations 16 when transitioning to the node t. Then, the trie tree generation unit 250a exchanges data (number of matches, tag key, value) of the node t and input data (number of generations, input key, value). Specifically, the trie tree generation unit 250a registers the generation number “15” of the input key as the coincidence number in the node t, and also registers the input key value “1” in the node t. Also, the character “empty” after the pointer of the input key “http://aaa.aaa/e/” is registered in the tag key of the node t.

  Then, the trie tree generation unit 250a sets the current input key to “http://aaa.aaa/e/c/”, the value “2”, and the number of generations “0”. In addition, the trie tree generation unit 250a sets the pointer of the input key to “t” of the third character corresponding to the trie part (step S80a).

  On the actual data, the trie tree generation unit 250a connects the pointer of the current node to the pointer array 32. The trie tree generation unit 250 a connects “TAG” in the pointer array 32 to “empty” in the first row and 18th column of the text table 34 and sets “match” to 15. In addition, the trie tree generation unit 250a connects the input key pointer to the second row and third column of the text table 34, and sets the number of generations to “0” (step S80b).

  Subsequently, the description shifts to the description of FIG. Since the node t corresponding to the third character of the input key “http://aaa.aaa/e/c/” does not exist under the node t, the trie tree generation unit 250a adds a new node under the node t. A node t is generated. Here, in order to distinguish each node t, in the following description, the node t on the parent side is expressed as node t (parent), and the node t on the child side is expressed as node t (child). Further, the trie tree generating unit 250a sets the pointer of the input key to “p” of the third character (step S81a).

  On the actual data, the trie tree generation unit 250a generates a pointer array 33 corresponding to the node t (child), and connects the pointer array 32 and the pointer array 33 with the key number “0 × 74” of the pointer array 32. . In addition, the trie tree generation unit 250a connects the pointer of the input key to “p” in the second row and fourth column of the text table 34 (step S81b).

  Subsequently, the description proceeds to FIG. The trie tree generation unit 250a transfers the remaining key “p: //aaa.aaa/e/c/” obtained by removing the trie portion from the input key “http://aaa.aaa/e/c/” to the node t ( To the child). Further, the trie tree generation unit 250a connects the value “2” corresponding to the input key “http://aaa.aaa/e/c/” to the node t (child) (step S82a).

  On the actual data, the trie tree generation unit 250a connects “TAG” in the pointer array 33 to “p” in the second row and fourth column of the text table 34, and releases the pointer of the input key. Further, the trie tree generating unit 250a connects the value “2” to “Data” of the pointer array 33 (step S82b).

  Subsequently, the case where the key “http://aaa.aaa/e/” and the value “4” are added to the trie tree created in steps S82a and 82b will be described with reference to FIG. The trie tree generation unit 250a sequentially reads characters from the head of the input key “http://aaa.aaa/e/”, and transitions to a node h, a node t (parent), and a node t (child). Then, the trie tree generation unit 250a sets the pointer of the input key “http://aaa.aaa/e/” to “p” of the fourth character (step S83a).

  On the actual data, the trie tree generating unit 250a leaves one key “http://aaa.aaa/e/d/” registered last in the text table 34 and the key “http: / /aaa.aaa/e/ ”. Then, the trie tree generating unit 250a connects the pointer of the input key to the character “p” in the fourth row and sixth column of the text table 34 (step S83b).

  Subsequently, the flow proceeds to FIG. Since there is no child node having “p” as a key in the node t (child), the trie tree generation unit 250a determines the priority of the tag key “p: //aaa.aaa/e/c/” of the node t. , The priority of the input key “p: //aaa.aaa/e/” from which “htt” in the trie portion is removed is compared. Since the number of matches of the node t (child) is “0”, the trie tree generation unit 250a performs comparison in order from the top of the input key.

  Then, since the 15th character excluding the trie portion of the input key is “empty” and the 15th character of the tag key is “c”, the trie generation unit 250a determines that the priority of the input key is the priority of the tag key. It is determined that it is smaller than the degree. Further, the trie tree generation unit 250a compares the input key and the tag key, and determines that the 14 characters “p: //aaa.aaa/e/” match.

  The trie tree generation unit 250a advances the pointer of the input key by 14 characters from the fourth character “p”. In addition, the trie tree generation unit 250a transitions to the node t (parent) as the parent node, and adds 1 to the generation number “14” to obtain “15” (step S84a).

  On the actual data, the trie tree generation unit 250a connects the pointer of the input key to the empty space in the fifth row and the second column of the text table 34. The trie tree generation unit 250a connects the current node to the pointer array 32 and sets the number of generations to “15” (step S84b).

  Subsequently, the description proceeds to FIG. 69. The trie tree generation unit 250a compares the number of matches of the node t (parent) with the number of generations, and both match with “15”, and the priority of the input key is equal to the priority of the tag key. The value “4” is registered in (parent) (step S85a).

  On the actual data, the trie tree generation unit 250a compares the match of the pointer array 31 with the number of generations, both are positioned at “15”, and the character connected to the pointer of the input key and the pointer array 32 Since the character connected to is “empty” and matches, the value “4” is connected to “Data” of the pointer array 32 (step S85b).

  Returning to the description of FIG. 56, the trie tree search unit 250b executes a process of extracting a total value of values registered in the trie tree 240b and a process of searching the trie tree 240b for a value corresponding to a predetermined key. Part.

  First, a process in which the trie tree searching unit 250b extracts a total value of values registered in the trie tree 240b will be described. FIG. 70 to FIG. 72 are diagrams for explaining the process of extracting the total value in the second embodiment. As shown in FIG. 70, in the trie tree 240b, a node h, a node t (parent), and a node t (child) are sequentially connected under the root node. The node h registers the number of matches “14”, the tag key “d / (http://aaa.aaa/d/)”, and the value “3”, and the node t (parent) has the number of matches “15”, the tag key Register “empty (http://aaa.aaa/e/)” and values “1, 4”. In addition, the node t (child) has a match number “0”, a tag key “p: //aaa.aaa/e/c/ (http://aaa.aaa/e/c/)”, and a value “2”. sign up.

  Further, in the description of FIGS. 70 to 72, a case where the total value is extracted in the order of the root node, the node h, the node t (parent), and the node t (child) will be described. In FIG. 70, the trie tree search unit 250b moves from the root node to the node h. Since the node h is registered with the tag key “d / (http://aaa.aaa/d/” and the value “3”, the trie tree search unit 250b uses the key “http://aaa.aaa/d”. / "And the value (total value)" 3 "are output (step S86a).

  On the actual data, the trie tree search unit 250b connects the current node to the pointer array 31 corresponding to the node h. The trie tree search unit 250b calculates a value “15” obtained by adding the number of hierarchies “1” and the match “14” of the node h, and returns 15 characters starting from the character “d” connected to “TAG”. Then, the trie tree searching unit 250b outputs the key “http://aaa.aaa/d/” from the returned characters “h” to “empty”. In addition, the trie tree search unit 250b outputs the value “3” connected to “Data” of the pointer array 31 (step S86b).

  The description shifts to the description of FIG. The trie tree search unit 250b moves from the node h to the node t (parent). Since the node t (parent) is registered with the tag key “empty (http://aaa.aaa/e/)” and the values “1, 4”, the trie tree search unit 250b uses the key “http: // A value “5”, which is the sum of “aaa.aaa/e/” and the values “1, 4”, is output (step S87a).

  On the actual data, the trie tree search unit 250b connects the current node to the pointer array 32 corresponding to the node t (parent). The trie tree search unit 250b calculates a value “17” obtained by adding the number of hierarchies “2” and the match “15” of the node t (parent), and returns 17 characters starting from “empty” connected to “TAG”. . Then, the trie tree searching unit 250b outputs the key “http://aaa.aaa/e/” from the returned characters “h” to “empty”. In addition, the trie tree search unit 250b outputs the total value “5” of the values “1, 4” connected to “Data” (step S87b).

  Shifting to the description of FIG. The trie tree search unit 250b moves from the node t (parent) to the node t (child). The node t (child) has the tag key “p: //aaa.aaa/e/c/ (http://aaa.aaa/e/c/)” and the value “2” registered. The search unit 250b outputs the key “http://aaa.aaa/e/c/” and the value “2” (step S88a).

  On the actual data, the trie tree search unit 250b connects the current node to the pointer array 33 corresponding to the node t (child). The trie tree search unit 250b calculates a value “3” obtained by adding the number “3” of the hierarchy of the node t (child) and the match “0”, and returns three characters starting from “p” connected to “TAG”. . Then, the trie tree searching unit 250b outputs the key “http://aaa.aaa/e/c/” from the returned characters “h” to “empty”. Further, the trie tree searching unit 250b outputs the value “2” connected to “Data” (step S88b).

  In FIG. 70 to FIG. 72, the case has been described in which the nodes are sequentially traced from the root node and the keys and values registered in each node are output. However, as shown in the first embodiment, a predetermined key may be designated, and the total value may be extracted based on the designated key.

  Next, a process in which the trie tree search unit 250b searches the trie tree 240b for a value corresponding to the designated input key will be described. Since the trie tree 240b is generated so that the tag keys are arranged in the depth-first search order, the trie tree search unit 250b may compare the tag key registered in the comparison target node with the input key. Similarly to the process of generating the trie tree shown in FIGS. 60 to 69, the number of characters to be compared can be reduced by using the number of matches and the number of generations.

  FIGS. 73 to 77 are diagrams for explaining the search processing according to the second embodiment. As shown in FIG. 73, in the trie tree 240b, node b, node a, node b, and node c are connected under the root node. Here, in order to distinguish each node b, the node b corresponding to the child node of the root node is expressed as node b (1), and the other node b is expressed as node b (2).

  Node b (1) registers the number of matches “1”, tag key “empty”, and value “1”, and node a registers the number of matches “0”, tag key “aa”, and value “3”. Node b (2) registers the number of matches “0”, tag key “c”, and value “1”, and node c registers the number of matches “0”, tag key “b”, and value “2”.

  73 to 77, search processing when the input key “baca” is designated will be described. In FIG. 73, the trie tree search unit 250b sets the pointer of the input key to the first character “b”, and transitions from the root node to the node b (1) by “b” designated by the pointer. Then, the trie tree searching unit 250b sets the pointer of the input key to “a” shifted by one character from “b” (step S89a).

  On the actual data, the trie tree search unit 250 b registers the input key “baca” in the text table 34 and connects the input key pointer to “b” in the second row and first column of the text table 34. The trie tree search unit 250b moves the pointer of the current node from the pointer array 40 to the pointer array 41 by “b” connected to the pointer of the input key, and changes the pointer of the input key to “a” shifted by one character. Setting is made (step S89b).

  Subsequently, the description proceeds to FIG. The trie tree search unit 250b transitions from the node b (1) to the node a by “a” designated by the pointer, and sets the pointer of the input key to “c” shifted by one character from “a” (step S90a). ).

  On the actual data, the trie tree search unit 250b shifts the pointer of the current node from the pointer array 41 to the pointer array 42 by “a” connected to the input key pointer, and shifts the input key pointer by one character. “C” is set (step S90b).

  Subsequently, the description proceeds to FIG. 75. The trie tree search unit 250b transitions from the node a to the node c by “c” designated by the pointer, and sets the pointer of the input key to “a” shifted by one character from “c” (step S91a).

  On the actual data, the trie tree search unit 250b shifts the pointer of the current node from the pointer array 42 to the pointer array 43 by “c” connected to the input key pointer, and shifts the input key pointer by one character. “A” is set (step S91b).

  Subsequently, the description proceeds to FIG. 76. Since the child node corresponding to “a” designated by the pointer does not exist in the node a, the trie tree searching unit 250b compares the number of matches of the node c with the number of generations. Since the number of matches is equal to the number of generations, the trie tree searching unit 250b compares the tag key “b” of the node c with the priority of the input key “a” from which the trie part “bac” is removed. Since the number of matches of node c is “0”, the trie tree search unit 250b performs comparison in order from the top of the key. As a result of the comparison, the trie tree search unit 250b determines that the priority of the tag key is higher than the priority of the input key (step S92a).

  On the actual data, the trie tree search unit 250b compares “match” in the pointer array 44 with the number of generations. Since the number of matches is equal to the number of generations, the trie tree search unit 250b determines the priority of the character “b” connected to “TAG” in the pointer array 44 and the priority of the character “a” connected to the pointer of the input key. Compare degrees. As a result of the comparison, the trie tree search unit 250b determines that the priority of the tag key is higher than the priority of the input key (step S92b).

  The description shifts to the description of FIG. Since the node c has the older brother node “node b (2)”, the trie tree search unit 250b has a node having a tag key that matches the input key in a node before the node c (node a, node b (1)). Is determined not to exist. The trie tree search unit 250b outputs that the corresponding data does not exist (step S93).

  Next, various processing procedures of the search device 200 according to the second embodiment will be described. First, the process in which the search device 200 according to the second embodiment generates the trie tree 240b will be described. FIG. 78 is a flowchart of the process procedure of the trie tree generation process according to the second embodiment.

  As shown in FIG. 78, the trie tree generation unit 250a generates a root node (step S500), and determines whether or not the next input data (key, value) exists in the registered data management table 240a (step S500). S501).

  If the trie tree generation unit 250a determines that the next input data does not exist in the registered data management table 240a (No in step S502), the process ends. On the other hand, when the next input data is registered in the registered data management table 240a (Yes in step S502), the trie tree generation unit 250a reads unread input data (step S503) and executes data addition processing. (Step S504).

  Next, the processing procedure of the data addition processing shown in step S504 in FIG. 78 will be described. Here, the case where the data addition process is executed without using the binary search method will be described, but the binary search method may be used in the same manner as in the first embodiment.

  FIGS. 79 to 81 are flowcharts illustrating the processing procedure of the data addition processing according to the second embodiment. As shown in FIG. 79, the trie tree generation unit 250a sets the current node as the root node (step S510), and determines whether or not the input key is empty (step S511).

  When the input key is empty (step S512, Yes), the trie tree generation unit 250a sets the number of generations to 0 (step S513), and proceeds to step S519 in FIG. On the other hand, when the input key is not empty (No in step S512), the trie tree generation unit 250a refers to the child node with the key of the first character of the input key, and determines whether or not the child node exists ( Step S514).

  If there is a child node (step S515, Yes), the trie tree generation unit 250a reads the first character of the input key, advances the pointer of the input key by one character, and transitions to the child node using the read character as a key. (Step S516), the process proceeds to Step S511.

  On the other hand, when there is no child node (step S515, No), the trie tree generation unit 250a determines whether the priority of the eldest son key is lower than the priority of the key of the first character of the input key (step S515). S517). When the priority of the eldest son key is not lower than the priority of the key of the first character of the input key (No in step S518), the trie tree generation unit 250a proceeds to step S513.

  On the other hand, when the priority of the eldest son key is lower than the priority of the key of the first character of the input key (step S518, Yes), the trie tree generation unit 250a proceeds to step 536 in FIG.

  Subsequently, the description proceeds to the description of FIG. 80. The trie tree generation unit 250a refers to the node information (step S519) and determines whether the number of matches is equal to the number of generations (step S520). When the number of matches is different from the number of generations (step S521, No), the trie tree generation unit 250a determines whether the number of matches is larger than the number of generations (step S522).

  If the number of matches is not greater than the number of generations (step S523, No), the trie tree generation unit 250a proceeds to step S538 in FIG. On the other hand, when the number of matches is larger than the number of generations (step S523, Yes), the trie tree generation unit 250a proceeds to step S530.

  By the way, if the priority of the tab key is equal to the priority of the input key in step S525 (step S525, Yes), the trie tree generating unit 250a adds the input value to the current node data (step S526). The data addition process is terminated (step S527).

  On the other hand, when the priority of the tag key is different from the priority of the input key (No in step S525), the trie tree generation unit 250a determines whether the priority of the tag key is higher than the priority of the input key ( Step S527). If the priority of the tag key is not higher than the priority of the input key (No at Step S528), the trie tree generation unit 250a proceeds to Step S533 in FIG.

  On the other hand, when the priority of the tag key is higher than the priority of the input key (Yes in step S528), the trie tree generation unit 250a adds the number of characters that match forward to the number of generations and matches the pointer of the input key forward. Advance by the number of characters (step S529).

  The trie tree generation unit 250a determines whether there is an older brother node or whether the parent node is a root node (step S530). The trie tree generation unit 250a adds 1 to the number of generations and transitions to the parent node when the brother node does not exist and the parent node is not the root node (when the condition is not satisfied) (step S531, No). (Step S532), and the process proceeds to Step S529.

  On the other hand, the trie tree generation unit 250a proceeds to step S539 in FIG. 81 when the brother node exists or the parent node is the root node (when the condition is satisfied) (step S531, Yes).

  Subsequently, the description proceeds to the description of FIG. 81. The trie tree generation unit 250a adds the number of characters that have been forward-matched to the number of matches in the current tag information, and advances the tag key pointer by the number of characters that have been forward-matched (step S533). Then, it is determined whether or not the number of generations is 0 (step S534).

  When the generation number is 0 (Yes in step S535), the trie tree generation unit 250a generates a new node, connects the current node to the new node using the first character of the input key as a key, and sets the input key pointer. Advance (step S536).

  The trie tree generation unit 250a adds the generation number and the input key as tag information to the new node (step S537), adds the input value to the new node (step S538), and ends the data addition process.

  On the other hand, when the number of generations is not 0 (step S535, No), the trie tree generation unit 250a subtracts 1 from the number of generations and transitions to the eldest node (step S538). The trie tree generation unit 250a exchanges the current node match number, tag key, value and generation number, input key, and input value (step S539), and determines whether the generation number is 0 or not. (Step S540).

  When the number of generations is 0 (step S541, Yes), the trie tree generation unit 250a refers to the child node with the key of the first character of the input key (step S542), and proceeds to step S536. On the other hand, when the number of generations is not zero (step S541, No), the trie tree generation unit 250a proceeds to step S538.

  Next, processing in which the search device 200 according to the second embodiment performs a search using the trie tree 240b will be described. Here, the case where the search process is executed without using the binary search method will be described, but the binary search method may be used in the same manner as in the first embodiment.

  FIG. 82 and FIG. 83 are flowcharts illustrating the processing procedure of the search processing according to the second embodiment. As shown in FIG. 82, the trie tree search unit 250b sets the current node as the root node (step S550), and determines whether or not an input key exists (step S551).

  When there is an input key (step S552, Yes), the trie tree search unit 250b refers to the child node with the key of the first character of the input key, and determines whether or not a child node of the key exists (step S52). S553).

  When there is a child node (Yes in step S554), the trie tree search unit 250b transitions to the child node with the top key, advances the pointer of the input key (step S555), and proceeds to step S551.

  On the other hand, when there is no child node (No in step S554), the trie tree search unit 250b determines whether the priority of the eldest son key is lower than the priority of the first key of the input key (step S556). ).

  When the priority of the eldest son key is lower than the priority of the first key of the input key (step S557, Yes), the trie tree search unit 250b outputs that there is no matching data (step S558). On the other hand, if the priority of the eldest son key is not lower than the priority of the first key of the input key (No at Step S557), the trie tree searching unit 250b proceeds to Step S559.

  By the way, if there is no input key in step S552 (step S552, No), the trie tree search unit 250b sets the number of generations to 0 (step S559), and proceeds to step S560 in FIG.

  Subsequently, the description proceeds to FIG. 83, and the trie tree searching unit 250b refers to the node information and determines whether or not the number of matches is equal to the number of generations (step S560). When the number of matches is not equal to the number of generations (No in step S561), the trie tree searching unit 250b determines whether the number of matches is larger than the number of generations (step S562).

  When the number of matches is not greater than the number of generations (step S563, No), the trie tree search unit 250b outputs that there is no match data (step S564). When the number of matches is greater than the number of generations (Yes in step S563), the trie tree search unit 250b proceeds to step S571.

  By the way, the trie tree search unit 250b determines whether the priority of the tag key is equal to the priority of the input key when the number of matches is equal to the number of generations in step S561 (step S561, Yes) (step S565). ).

  When the priority of the tag key is equal to the priority of the input key (Yes in step S566), the trie tree search unit 250b outputs the data of the current node (step S567). On the other hand, when the priority of the tag key and the priority of the input key are different (No in step S566), the trie tree search unit 250b determines whether the priority of the tag key is higher than the priority of the input key ( Step S568).

  When the priority of the tag key is not greater than the priority of the input key (No at Step S569), the trie tree search unit 250b proceeds to Step S564. On the other hand, when the priority of the tag key is higher than the priority of the input key (step S569, Yes), the trie tree search unit 250b adds the number of characters that match forward to the number of generations, and matches the input key pointer forward. Advance by the number of characters (step S570).

  The trie tree search unit 250b determines whether there is an older brother node or whether the parent node is a root node (step S571). When the brother node does not exist and the parent node is not the root node (when the condition is not satisfied) (step S572, No), the trie tree search unit 250b adds 1 to the number of generations and transitions to the parent node. (Step S573), the process proceeds to step S560.

  On the other hand, the trie tree searching unit 250b proceeds to step S564 when the brother node exists or the parent node is the root node (when the condition is satisfied) (step S572, Yes).

  Next, a summary value extraction process executed by the search device 200 according to the second embodiment will be described. FIG. 84 is a flowchart of a process procedure of a total value extraction process according to the second embodiment. As shown in FIG. 84, the trie tree search unit 250b sets the current node as the root node (step S600), and determines whether there is a child node (step S601).

  If there is no child node (No in step S602), the trie tree searching unit 250b determines whether there is a younger brother node (step S603). When there is no younger brother node (step S604, No), the trie tree search unit 250b transitions to the parent node (step S605), and proceeds to step S603.

  On the other hand, when the younger brother node exists (step S604, Yes), the trie tree search unit 250b transitions to the next younger brother node (step S606), and proceeds to step S609.

  By the way, if there is a child node in step S602 (step S602, Yes), the trie tree search unit 250b acquires a key from the position returned by the number of matches + the number of hierarchies from the tag key pointer (step S608). ). Then, the trie tree search unit 250b processes and outputs various values of the current node (step S609), and proceeds to step S601.

  Next, a processing procedure of deletion processing executed by the search device 200 according to the second embodiment will be described. 85 to 88 are flowcharts illustrating the processing procedure of the deletion processing according to the second embodiment. As shown in FIG. 85, the trie tree search unit 250b determines whether or not there is an input key (step S610). If the input key exists (if the character indicated by the pointer is not empty) (step S610). S611, Yes), the child node is referred to by the key of the first character of the input key, and it is determined whether or not the child node exists (step S612).

  If there is a child node (step S613, Yes), the trie tree search unit 250b transitions to the child node with the top key, advances the pointer of the input key (step S614), and proceeds to step S610.

  On the other hand, when there is no child node (No in step S613), the trie tree searching unit 250b determines whether the number of node matches is 0 (step S615). When the number of matches is not 0 (step S616, No), the trie tree search unit 250b determines whether the priority of the eldest son key is lower than the priority of the key of the first character of the input key (step S617). . When the priority of the eldest son key is lower than the priority of the key of the first character of the input key (step S618, Yes), the trie tree search unit 250b outputs that no deletion data exists (step S619).

  By the way, the trie tree search unit 250b sets the number of generations to 0 (step S620) when the input key does not exist in step S611 (when the pointer character is empty) (step S611, No). The process shifts to step S621 of 86.

  Subsequently, the trie tree search unit 250b refers to the node information in FIG. 86 (step S621), and determines whether or not the number of matches is equal to the number of generations (step S622). If the number of matches is not equal to the number of generations (step S623, No), the trie tree searching unit 250b determines whether the number of matches is greater than the number of generations (step S624).

  When the number of matches is greater than the number of generations (Yes in step S625), the trie tree search unit 250b proceeds to step S631. On the other hand, if the number of matches is not greater than the number of generations (No in step S625), the trie tree search unit 250b proceeds to step S634.

  By the way, when the number of matches is equal to the number of generations in step S623 (step S623, Yes), the trie tree search unit 250b determines whether the priority of the tag key is equal to the priority of the input key (step S626). ).

  If the priority of the tag key is equal to the priority of the input key (step S627, Yes), the trie tree search unit 250b proceeds to step S635 in FIG. On the other hand, when the priority of the tag key is not equal to the priority of the input key (No in step S627), the trie tree search unit 250b determines whether the priority of the tag key is higher than the priority of the input key. (Step S628).

  When the priority of the tag key is not higher than the priority of the input key (No at Step S629), the trie tree search unit 250b proceeds to Step S634. On the other hand, when the priority of the tag key is higher than the priority of the input key (step S629, Yes), the trie tree search unit 250b adds the forward-matched character to the number of generations and forward-matches the input key pointer. Advance by the number of characters (step S630).

  The trie tree search unit 250b determines whether there is an older brother node or whether the parent node is a root node (step S631). The trie tree search unit 250b adds 1 to the number of generations and transitions to the parent node when no brother node exists and the parent node is not the root node (when the condition is not satisfied) (No in step S632). (Step S633), the process proceeds to Step S621.

  On the other hand, the trie tree search unit 250b outputs that no deletion data exists (step S634) when there is an older brother node or when the parent node is the root node (step S632, Yes).

  Subsequently, the process proceeds to FIG. 87, and the trie tree search unit 250b determines whether or not deletion target data exists (step S635). The trie tree searching unit 250b outputs that no deletion data exists (step S637) when no deletion target data exists (step S636, No).

  On the other hand, when there is data to be deleted (step S638), the trie tree search unit 250b determines whether there is other data (whether another value is registered in the node) (step S638). S639). The trie tree search unit 250b ends the process when another node exists (step S640, Yes). On the other hand, if there is no other data (No at Step S640), the trie tree search unit 250b proceeds to Step S641 in FIG.

  Subsequently, the process proceeds to FIG. 88, and the trie tree searching unit 250b determines whether or not the current node is the eldest son (step S641). If the current node is not the eldest son (step S642, No), the trie tree searching unit 250b proceeds to step S647. To do.

  On the other hand, when the current node is the eldest son (step S642, Yes), the trie tree search unit 250b determines whether the number of matches of the parent node is larger than the number of matches of the current node (step S643). When the number of matches of the parent node is not greater than the number of matches of the current node (step S644, No), the trie tree search unit 250b proceeds to step S647.

  On the other hand, when the number of matches of the parent node is larger than the number of matches of the current node (step S644, Yes), the trie tree search unit 250b subtracts the number of matches of the current node from the number of matches of the parent node. Further, a value obtained by subtracting 1 is calculated as the difference coincidence (step S645).

  The trie tree search unit 250b sets the number of matches of the current node plus 1 as the number of matches of the parent node, and returns the pointer character string pointer of the parent node by the number of differences matched (step S646), and the child node Is determined (step S647).

  When there is a child node (step S648, Yes), the trie tree search unit 250b sets the current node data as the eldest node data and adds 1 to the number of matches (step S649). The trie tree search unit 250b transitions to the eldest son node (step S650), and proceeds to step S647.

  On the other hand, when there is no child node (No in step S648), the trie tree search unit 250b determines whether the current node is the eldest son (step S612). When the current node is not the eldest son (step S652, No), the trie tree search unit 250b proceeds to step S654.

  On the other hand, when the current node is the eldest node (step S652, Yes), the trie tree search unit 250b returns the tag character string pointer of the parent node by the number of matches of the parent node, and sets the number of matches of the parent node to 0. (Step S653). Then, the trie tree search unit 250b deletes the edge of the parent node to the current node, and deletes the current node (step S654).

  As described above, the search device 200 according to the second embodiment does not compare the characters of each key (tag key and input key) in order from the first character when comparing the tag key and input key of each node. Rather than skipping characters to be compared by the number of matches with the tag key registered in the child node, the process of registering the input key in the trie tree can be speeded up.

  In the second embodiment, as an example, when a character string that partially matches the character string of the child node is registered in the parent node, the length of the matching character string is used instead of registering the character string in the parent node as it is. The remaining character string was registered in the parent node. However, the present invention is not limited to this. For example, when registering a character string that partially matches the character string of the parent node to the child node, instead of registering the character string directly to the child node, the length of the matching character string and the remaining character string are set to the child node. You may register with.

  By the way, among the processes described in the present embodiment, all or part of the processes described as being automatically performed can be manually performed, or the processes described as being manually performed can be performed. All or a part can be automatically performed by a known method. In addition, the processing procedure, control procedure, specific name, and information including various data and parameters shown in the above-described document and drawings can be arbitrarily changed unless otherwise specified.

  Further, each component of each illustrated apparatus is functionally conceptual, and does not necessarily need to be physically configured as illustrated. In other words, the specific form of distribution / integration of each device is not limited to that shown in the figure, and all or a part thereof may be functionally or physically distributed or arbitrarily distributed in arbitrary units according to various loads or usage conditions. Can be integrated and configured. Further, all or any part of each processing function performed in each device may be realized by a CPU and a program analyzed and executed by the CPU, or may be realized as hardware by wired logic.

  FIG. 89 is a diagram illustrating a hardware configuration of a computer corresponding to the search device 200 illustrated in the second embodiment (or the search device 100 according to the first embodiment). As shown in FIG. 89, the computer (search device) 10 performs data communication with other devices via an input device 11, a monitor 12, a RAM (Random Access Memory) 13, a ROM (Read Only Memory) 14, and a network. A communication control device 15, a medium reading device 16, a CPU (Central Processing Unit) 17, and an HDD (Hard Disk Drive) 18 are connected by a bus 19.

  The HDD 18 stores a trie tree generation program 18b and a trie tree search program 18c that exhibit functions similar to the functions of the search device 200 described above. When the CPU 17 reads and executes the trie tree generation program 18b and the trie tree search program 18c, the trie tree generation process 17a and the trie tree search process 17b are activated.

  Here, the trie tree generation process 17a corresponds to the trie tree generation unit 250a illustrated in FIG. The trie tree search process 17b corresponds to the trie tree search unit 250b shown in FIG.

  The HDD 18 stores various data 18a corresponding to the data stored in the storage unit 240 shown in FIG. The CPU 17 reads various data 18a stored in the HDD 18 into the RAM 13, and executes construction of a trie tree using the various data 13a.

  The following supplementary notes are further disclosed with respect to the embodiments including the above examples.

(Supplementary note 1)
When a trie tree in which nodes corresponding to a predetermined character are connected in a tree structure is stored in the storage device and a new character string is registered in the trie tree, the characters of the new character string are read in order from the top. The node included in the trie tree is traced according to the character corresponding to the node, and a new character string is added to any of the traced nodes so that a single character string is registered for the single node. When registering, the character string registered in the child node of the registration target node is compared with the new character string to determine the matching character, and the remaining characters excluding the matching character from the new character string A storage medium that stores a program that implements a character string registration function that registers the number of characters that match a character string in a node to be registered.

(Supplementary Note 2) The character string registration function sets a priority based on a predetermined character order for each character string registered in each node, and registers each character string in each node based on the priority. The storage medium according to appendix 1, wherein

(Supplementary note 3) The character string registration function compares the priority of the character string registered in the node with the priority of the new character string, and is newer than the priority of the character string of the registered node. When the priority of the character string is lower, the determination function that determines the number of characters that match between the registered character string and the new character string, and the matching that is determined by the determination function by transitioning to the parent node of the node Appendix 1 or 2 storing a program for further realizing a registration function for determining whether or not to register a new node in the parent node based on the number of characters and the number of matching characters registered in the parent node The storage medium described in 1.

(Supplementary Note 4) When searching for a search character string, the character string registered in the node is compared with the search character string, and if the character strings do not match, the registered character string and the search character string A search determination function that determines the number of characters that match in the column, and a transition to the parent node of the node, and according to the number of matching characters determined by the search determination function, the search character string and a part of the character string of the parent node A storage medium storing a program for further realizing a coincidence determination function for determining whether or not each character string matches after removing.

(Supplementary Note 5) The search device is
Storing a trie tree in which nodes corresponding to predetermined characters are connected in a tree structure in a storage device;
When registering a new character string in the trie tree stored in the storage device, the characters of the new character string are read in order from the top, and the node included in the trie tree is determined according to the character corresponding to the node. If a new character string is registered in any of the traced nodes so that a single character string is registered for a single node, the characters registered in the child nodes of the registered node And comparing the new character string with the new character string to determine the matching character, and registering the remaining character string excluding the matching character from the new character string and the number of matching characters in the node to be registered. A trie tree generation method characterized by that.

(Supplementary note 6) When a trie tree in which nodes corresponding to a predetermined character are connected in a tree structure is stored in a storage device and a new character string is registered in the trie tree, the character of the new character string is Read from the top in order and follow the node included in the trie tree according to the character corresponding to the node, so that a single character string is registered for a single node. When registering a new character string, the character string registered in the child node of the node to be registered is compared with the new character string to determine a matching character, and the matching character is excluded from the new character string. A trie tree generating device, comprising: a character string registration unit that registers the number of matching characters with the remaining character string in a node to be registered.

10 Computer 11 Input Device 12 Monitor 13 RAM
13a, 18a Various data 14 ROM
15 Communication Control Device 16 Medium Reading Device 17 CPU
17a Trie tree generation process 17b Trie tree search process 18b Trie tree generation program 18c Trie tree search program 19 Bus 100, 200 Search unit 110, 210 Input unit 120, 220 Output unit 130, 230 Input / output control unit 140, 240 Storage unit 140a , 240a registered data management tables 140b, 240b trie trees 150, 250 control units 150a, 250a trie tree generation units 150b, 250b trie tree search units

Claims (5)

On the computer,
Of the character strings associated with the node, the number of matching characters that match the character string registered with the child node, and the remaining character string obtained by removing the character string associated with the child node from the character string associated with the node storing trie tree node that registered the door is connected by a tree structure in the storage device, to register a new string in the prefix tree, the said new string characters from the beginning are read sequentially Follow a node included in the trie tree according to the character corresponding to the node, and register a new character string in one of the traced nodes so that a single character string is registered for a single node. If a new character string skipped from the first character compared to the number of matching characters registered in the registration target node is compared with the character string registered in the child node of the registration target node character Determined, a new remaining string as matched characters excluding the character that matches the character string, storage medium storing a program for realizing the character string registration function of registering a node to be registered.   The character string registration function sets a priority based on a predetermined character order for each character string registered in each node, and registers each character string in each node based on the priority. The storage medium according to claim 1. The character string registration function compares the priority of the character string registered in the node with the priority of the new character string, and prioritizes the new character string over the priority of the character string of the registered node. When the degree is smaller, a determination function that determines the number of characters that match a registered character string and a new character string, a transition to the parent node of the node, and the number of matching characters determined by the determination function, 3. A program for further realizing a registration function for determining whether to register a new character string in the parent node based on the number of matching characters registered in the parent node is stored. Storage media. When searching for a search character string, the character string registered in the node is compared with the search character string. If the character strings do not match, the registered character string matches the search character string. A search determination function for determining the number of characters, and after transitioning to the parent node of the node, and excluding a part of the character string of the search character string and the parent node according to the number of matching characters determined by the search determination function The storage medium according to claim 1, 2 or 3, wherein a program for further realizing a match determination function for determining whether or not each character string matches is stored. The search device
Of the character strings associated with the node, the number of matching characters that match the character string registered with the child node, and the remaining character string obtained by removing the character string associated with the child node from the character string associated with the node Storing in a storage device a trie tree in which nodes that are registered in a tree structure are connected;
When registering a new character string in the trie tree stored in the storage device, the characters of the new character string are read in order from the top, and the node included in the trie tree is determined according to the character corresponding to the node. If a new character string is registered in any of the traced nodes so that a single character string is registered for a single node, the match registered in the registration target node from the first character A new character string that is skipped by the number of characters to be compared is compared with a character string that is registered in the child node of the registration target node to determine a matching character, and the matching character is excluded from the new character string. A trie tree generation method comprising: registering a remaining character string and the number of matching characters in a registration target node.

Images