Research On String Retrieval Algorithm Based On Trie Tree

In recent years,with the rapid development of Internet technology and the popularity of smart mobile devices,the string data resources on the network are growing exponentially.For people,how to effectively store and retrieve massive information has become an urgent problem in the field of data management.Firstly,string text retrieval must be able to store as much string data as possible with minimal space.These string collections often contain millions or even tens of millions of information and are growing.Secondly,the time efficiency of searching information should be considered in string retrieval.Whether to find the required information at the fastest speed is an important criterion for users to evaluate the performance of various information retrieval algorithms.Therefore,it is meaningful to develop a new type of storage structure and indexing algorithm for string resources.The main work of this thesis is as follows:1.The research status and performance evaluation indicators of Trie tree algorithms are summarized.The traditional string retrieval algorithm and the principle of retrieval strings are described.We propose a string retrieval algorithm based on Trie tree and a scheme to improve its performance.2.According to the performance optimization strategy,the construction of the new Trie tree structure that can be used to retrieve string information,namely 16-bit Trie tree,is completed.This paper uses the software Visual C++6.0 to encode the16-bit Trie tree algorithm,which realizes the storing,retrieving,deleting and other functions of string data.3.Coding the original Trie tree structure and Std map of VC++ standard library,and comparing their temporal performance and spatial performance with the 16-bit Trie tree algorithm proposed in this paper.Through the analysis of experimental data,it is proved that the 16-bit Trie tree algorithm proposed in this paper can reduce the memory space of information storage and achieve higher construction speed and index speed on the premise of maintaining the time complexity when retrieving string data.The string retrieval algorithm based on 16-bit Trie tree proposed in this paper has the characteristics of high spatial efficiency,being able to modify and traversetext data at any time.It solves the time and space balance problem of Trie tree structure well.