Faster searching in tries and quadtrees -- an analysis of level compression

Arne Andersson and Stefan Nilsson

We analyze the behavior of the level-compressed trie, LC-trie, a compact version of the standard trie data structure. Based on this analysis, we argue that level compression improves the performance of both tries and quadtrees considerably in many practical situations. In particular, we show that LC-tries can be of great use for string searching in compressed text.
     Both tries and quadtrees are extensively used and much effort has been spent obtaining detailed analyses. Since the LC-trie performs sigificantly better than standard tries, for a large class of common distributions, while still being easy to implement, we believe that the LC-trie is a strong candidate for inclusion in the standard repertoire of basic data structures.

In Proc. of Second Annual European Symp. on Algorithms, pp. 82-93, 1994.

Complete text: ps,  pdf