2006/09/29 by Daisuke Okanohara, Okanohara, Daisuke, Kunihiko Sadakane +1 · 5 citations
Computer Science · #Advanced Data Compression Techniques #Algorithms and Data Compression #Cellular Automata and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.cs/0610001
openalex publication_date 2006/09/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Rank/Select dictionaries are data structures for an ordered set S ⊂ \0,1,...,n-1\ to compute \rank(x,S) (the number of elements in S which are no greater than x), and \select(i,S) (the i-th smallest element in S), which are the fundamental components of succinct data structures of strings, trees, graphs, etc. In those data structures, however, only asymptotic behavior has been considered and their performance for real data is not satisfactory. In this paper, we propose novel four Rank/Select dictionaries, esp, recrank, vcode and sdarray, each of which is small if the number of elements in S is small, and indeed close to nH0(S) (H0(S) ≤ 1 is the zero-th order empirical entropy of S) in practice, and its query time is superior to the previous ones. Experimental results reveal the characteristics of our data structures and also show that these data structures are superior to existing implementations in both size and query time.