Nearly optimal static Las Vegas succinct dictionary

Given a set S of n (distinct) keys from key space [U ], each associated with a value from Σ, the static dictionary problem asks to preprocess these (key, value) pairs into a data structure, supporting value-retrieval queries: for any given x ∈ [U ], valRet(x) must return the value associated with x if x ∈ S, or return ⊥ if x / ∈ S. The special case where |Σ| = 1 is called the membership problem. The "textbook" solution is to use a hash table, which occupies linear space and answers each query in constant time. On the other hand, the minimum possible space to encode all (key, value) pairs is only OPT := ⌈lg 2 U n + n lg 2 |Σ|⌉ bits, which could be much less. In this paper, we design a randomized dictionary data structure using OPT + poly lg n + O(lg lg lg lg lg U ) bits of space, and it has expected constant query time, assuming the query algorithm can access an external lookup table of size n 0.001 . The lookup table depends only on U , n and |Σ|, and not the input. Previously, even for membership queries and U ≤ n O(1) , the best known data structure with constant query time requires OPT + n/poly lg n bits of space (Pagh [Pag01a] and Pǎtras ¸cu [Pǎt08]); the best known using OPT + n 0.999 space has query time O(lg n); the only known non-trivial data structure with OPT + n 0.001 space has O(lg n) query time and requires a lookup table of size ≥ n 2.99 (!). Our new data structure answers open questions by Pǎtras ¸cu and Thorup [Pǎt08, Tho13] . We also present a scheme that compresses a sequence X ∈ Σ n to its zeroth order (empirical) entropy up to |Σ| • poly lg n extra bits, supporting decoding each X i in O(lg |Σ|) expected time.