Storage medium, trie tree generation method, and trie tree generation device

Patent metadata

Field	Value
Publication number	US-9465860-B2
Application number	US-201113137818-A
Country	US
Kind code	B2
Filing date	Sep 14, 2011
Priority date	Mar 19, 2009
Publication date	Oct 11, 2016
Grant date	Oct 11, 2016

Abstract

A retrieval device according to the present embodiment associates one tag key with one node and removes a node not having a tag key when a trie tree generating unit generates a trie tree. Moreover, because a tag key having a low priority is registered in a node close to a root node when the trie tree generating unit registers tag keys in the nodes of the trie tree, the retrieval device can narrow down a node region that is a comparison target when a trie tree searching unit performs a retrieval process.

First claim

What is claimed is:

1. A non-transitory computer-readable storage medium that stores a program making a computer realize a character string registration function, the character string registration function comprising:
storing in a storage device a trie tree in which nodes corresponding to predetermined characters are connected in accordance with a tree structure;
reading out, characters of a new character string in sequence one-by-one from a head thereof to trace nodes included in the trie tree in accordance with characters corresponding to the nodes and determining a specific node that is located at a lowest side from nodes having an elder node among the traced nodes, the elder node and the specific node being located in a same layer and being connected to a same node that is directly located in a layer above the elder node and the specific node, the elder node being located at an upper side of the specific node;
reading out the characters of the new character string from the specific node sequentially;
determining whether a child node of the specific node exists by using a key of an initial character of the new character string when a priority of character string registered in the specific node is smaller than the priority of the new character string;
adding a new node as a child node of the specific node to be corresponded with the read character when the child node does not exist; and
registering the new character string and the priority to the child node of the specific node, wherein
a previous character string, registered previously in a last node that registered a character string most recently, is registered into the child node traced by the previous character string from the last node when the new character string, that is different from the character string previously registered and the previous character string can trace a child node from the last node, has registered into one of traced nodes, and
the previous character string in the last node is registered into the new node that is added below the last node when the new character string, that is different from the character string previously registered and the previous character string cannot trace any child node from the last node, has registered into one of traced nodes.

2. The non-transitory computer-readable storage medium according to claim 1 , wherein the character string registration function further comprises setting a priority to each character string registered in each node and registering each character string in each node on the basis of the priority.

3. The non-transitory computer-readable storage medium according to claim 2 , wherein the program making the computer further realize a character string search function comprises:
reading out, when retrieving a search character string, characters of the search character string in sequence from a head thereof to trace the nodes of the trie tree;
determining a specific node that is located at a lowest side from nodes having an elder node among the traced nodes; and
sequentially reading out the characters of the search character string from the specific node to retrieve a character string identical with the search character string from character strings registered in nodes included in a route up to a finally arriving node to arrive at finally.

4. The non-transitory computer-readable storage medium according to claim 3 , wherein the character string registration function includes reading out the characters of the new character strings in sequence from the head to trace the nodes of the trie tree and determining a child node of a root node as the specific node when a node having an elder node does not exist among the traced nodes.

5. The non-transitory computer-readable storage medium according to claim 1 , wherein the character string registration function includes reading out the characters of the new character strings in sequence from the head to trace the nodes of the trie tree and determining a child node of a root node as the specific node when a node having an elder node does not exist among the traced nodes.

6. The non-transitory computer-readable storage medium according to claim 1 , wherein the character string registration function further comprises dividing the predetermined characters expressed with a bit stream into several bit streams and storing in the storage device the trie tree in which nodes corresponding to the divided bit streams are connected in accordance with the tree structure.

7. A trie tree generation method comprising:
storing in a storage device a trie tree in which nodes corresponding to predetermined characters are connected in accordance with a tree structure;
reading out characters of a new character string in sequence one-by-one from a head thereof to trace nodes included in the trie tree in accordance with characters corresponding to the nodes and determining a specific node that is located at a lowest side from nodes having an elder node among the traced nodes,
the elder node and the specific node being located in a same layer and being connected to a same node that is directly located in a layer above the elder node and the specific node, the elder node being located at an upper side of the specific node;
reading out the characters of the new character string from the specific node sequentially;
determining whether a child node of the specific node exists by using a key of an initial character of the new character string when a priority of character string registered in the specific node is smaller than the priority of the new character string;
adding a new node as a child node of the specific node to be corresponded with the read character when the child node does not exist; and
registering the new character string and the priority to the child node of the specific node, wherein
a previous character string, registered previously in a last node that registered a character string most recently, is registered into the child node traced by the previous character string from the last node when the new character string, that is different from the character string previously registered and the previous character string can trace a child node from the last node, has registered into one of traced nodes, and
the previous character string in the last node is registered into the new node that is added below the last node when the new character string, that is different from the character string previously registered and the previous character string cannot trace any child node from the last node, has registered into one of traced nodes.

8. The trie tree generation method according to claim 7 , further comprising: setting a priority to each character string registered in each node and registering each character string in each node on the basis of the priority.

9. A trie tree generation device comprising:
a memory; and
a processor coupled to the memory, wherein the processor executes a process comprising:
storing in a storage device a trie tree in which nodes corresponding to predetermined characters are connected in accordance with a tree structure;
reading out, characters of a new character string in sequence one-by-one from a head thereof to trace nodes included in the trie tree in accordance with characters corresponding to the nodes and determining a specific node that is located at a lowest side from nodes having an elder node among the traced nodes, the elder node and the specific node being located in a same layer and being connected to a same node that is directly located in a layer above the elder node and the specific node, the elder node being located at an upper side of the specific node;
reading out the characters of the new character string from the specific node seq

Assignees

• Tago Shinichiro
• Asai Tatsuya
• Fujitsu Ltd

Inventors

• Tago Shinichiro
• Asai Tatsuya

Classifications

• G06F16/322 Primary

  Trees · CPC title

• G06F17/30625 Primary

  Physics · mapped topic