Compressed string dictionaries via Rear coding and succinct Patricia Trie

In this thesis, we will illustrate a two-level approach to compress and index string dictionaries, which are a crucial component of many software platforms for big data applications. The approach, which combines a succinctly-encoded Patricia Trie and some data compression techniques, is proposed with the aim of being simple but efficient in occupied space and query time, on par with state-of-the-art solutions. The performance of the approach is experimentally evaluated by considering several datasets and two state-of-the-art solutions: the Fast Succinct Trie and the Path Decomposed Trie. We will show that despite its simplicity, the proposed solution obtains space and time performance that are on the Pareto frontier of the best approaches, thus contributing to the corresponding literature with new interesting trade-offs