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.