Fast Compressed Tries through Path Decompositions

摘要: Tries are popular data structures for storing a set of strings, where common prefixes represented by root-to-node paths. More than 50 years usage have produced many variants and implementations to overcome some their limitations. We explore new succinct representations path-decomposed tries experimentally evaluate the corresponding reduction in space memory latency, comparing with state art. study following applications: compressed string dictionary monotone minimal perfect hash strings. In dictionary, we obtain that outperform other state-of-the-art dictionaries efficiency while obtaining predictable query times competitive preferred practitioners. On real-world datasets, our smallest (except one case) fastest lookup times, whereas access within 20p slower best-known solutions. perform several faster trie-based functions occupying nearly same space. approximately 2 5 previous solutions, occupancy less 10p larger.