The Adaptive Trie Tree And The Improved Algorithms Of GPERF

"Searching" appears in every algorithm. So it's very important to decrease the time and space needed for searching. The trie tree is a data structure supporting fast searching. Traditional trie tree is a searching tree according to the key byte by byte. It's faster than the hash algorithm. The main disadvantage of trie is that its branch nodes are so big that its using rate of space is too low. A link pointer of a branch node of a traditional trie tree can point to only one leaf node, and usually most of the link pointers are null. Only 2,5% of the link pointers are not null. For the traditional hash algorithm, the time complexity of search, insert and delete is O(n) in the worst cases. The time complexity of search in the extendible hash table is O(maxkeysize) in the worst cases (maxkeysize is the max size of the keys, and it's usually a constant in practice.). But the time complexity of insert and delete in the extendible hash table is O(n) in the worst cases, and the space complexity is beyond linear with the number of the keys. Its using rate of space is low when the number of the keys is large. For the "perfect" adaptive hash algorithms, although the time complexity of search is low, the time complexity of collision solution after insert is beyond O(n2) in the worst cases. The article mainly does two things. First, we improve the adaptive hash algorithm, "gperf, speed up its collision solution procedure by hundreds of times, and decrease the time of search less. Second, after analyzing the ideas and the advantages of trie tree, hash and extendible hash, we present the algorithm of adaptive trie tree. The time complexity of insert, search and delete, which the algorithm supports, is O(maxkeysize), and the space complexity of the algorithm is O(n).The creative work of the article is the following:1. After studying the traditional trie tree, we present the data structure and algorithm of the adaptive trie tree that support ADT dictionary. On the premise that we don't increase the time complexity of the algorithm, we greatly reduce the space complexity, and reduce the space coefficient from about 40 to 3. Two things embody the adaptivity of the algorithm. The first is that the size of the branch node is extendible and shrinkable for the needs. The second is that every link pointer of a branch node can point to a singly linked list of dictionary elements, and the length of the linked list equals to 1 plus the level of the branch node. The two aspects of the adaptivity greatly reduce the proportion of null links for the whole tree, so enormously decrease the space complexity of the trie tree.2. Aiming at the efficiency problem of GPERF (perfect hash function generator), we take the measures such as fully searching and taking use of the information of the keys, decreasing collisions, avoiding inefficient computing, limiting the maximum of collisions of each bucket, apportioning the work of collision solution procedure to the search procedure, grading hash, etc. We present the improved algorithm for gperf, and prove that the effect is notable by the experiments.