Method for realizing dictionary search of Trie tree based on one-dimensional linear space

Abstract

The invention provides a method for realizing a dictionary search of Trie tree based on one-dimensional linear space. The method comprises the following steps: through generating dictionary data of the Trie tree of the one-dimensional linear space, determining a to-be-queried vocabulary entry key according to the user input, and realizing the query according to the current state of the vocabulary entry key. Building the dictionary data of the Trie tree under the one-dimensional linear space increases the dictionary loading and searching speed, and can quickly search all prefix words of the vocabulary entry; besides, realizing the dictionary search of Trie tree based on one-dimensional linear space can solve the collision problem caused by inserting a new state existing in the Trie tree building process by the traditional Trie tree dictionary data search, and can avoid the problem of the move of the vast dictionary data caused by the conflict.

Description

technical field [0001] The invention relates to a dictionary retrieval method, in particular to a dictionary retrieval method realizing a Trie tree based on a one-dimensional linear space. Background technique [0002] In the field of information retrieval and natural language processing, especially in the technical application based on the dictionary, the scale of the dictionary is generally very large, with tens of thousands or even hundreds of millions of records, especially the scale of the inverted index in the search engine is the largest . The search for massive data dictionaries is currently usually implemented using an indexed data structure. Commonly used index structures include linear index tables, inverted lists, hash tables, and search trees. For a record whose keyword (key) length is n and the size of the dictionary is N (where N>>n), the time complexity analysis of each index structure retrieval is as follows: [0003] The linear index structure or i...

AI Technical Summary

Problems solved by technology

Under the dictionary data of the Trie tree constructed in the one-dimensional linear space, the speed of dictionary loading and retrieval is improved, and all the prefix words of the entry can be quickly retrieved. In addition, the dictionary retrieval based on the Trie tree based on the one-dimensional linear space can solve the traditional Trie tree dictionary data retrieval has a conflict problem caused by inserting a new state during the construction of the Tire tree, and can avoid the problem of moving a large amount of dictionary data caused by the conflict

Images