Global optimization and construction method and system of TRIE double-array

Abstract

The invention provides a global optimization and construction method of a TRIE double-array, comprising the following steps of: 1. representing each node in a TRIE structure by using binary strings, wherein each bit in each binary string from left to right is in one-to-one correspondence with each subnode in each node, 1 represents that the subnodes are contained, and 0 represents that the subnodes are not contained, then rightwards shifting each binary string until the 0 bit is 1, and respectively recording the shifted binary representations and the shifted digits; 2. mapping all nodes in the TRIE to the corresponding class according to the binary representations of the nodes; 3. determining the stored sequence of each nodes of the TRIE in the double-array and recording the shifted basic value of each node in the double-array; and 4. setting a check and a base arrays according to the shifted basic value stored in each node, the parent-child relationships among the nodes in the TRIE and the shifted step length corresponding to each subnode.

Description

technical field [0001] The present invention relates to the construction of TRIE tree double arrays, more specifically to the global optimization construction method and system of TRIE tree double arrays. Background technique [0002] TRIE tree is an important index structure for dictionaries and large-scale keywords. It is widely used in natural language processing, information retrieval, electronic dictionary management and other fields, and its search efficiency is very high. The time to find a keyword in the TRIE tree is related to the composition of the keyword itself, its own length, and the depth of the tree. The fastest speed is O(1), and the worst is the number of layers of the TRIE tree. Although the search efficiency of the TRIE tree is high, in most cases the TRIE tree has fewer branches (even 1), resulting in a huge waste of storage space. Based on Johnson's theory that deterministic finite automata can be represented by quadruples, some researchers expressed T...

AI Technical Summary

Problems solved by technology

[0008] The double-array structure and algorithm effectively reduce the space waste of the TRIE storage structure, but there is still a big problem of data sparseness using this method

In the related technology, it is proposed to add an optimized sorting strategy in the construction of the array, that is, to prioritize the nodes with more branches in a certain local range. This method further improves the data sparsity problem of the double array, but due to this optimization strategy It is a local optimization strategy, which may not be able to achieve very good optimization results in most cases

Moreover, in the above method, the child nodes of each node are detected one by one, which increases the construction time

Images