Practical Entropy-Compressed Rank/Select Dictionary

Details Practical Entropy-Compressed Rank/Select Dictionary Practical Entropy-Compressed Rank/Select Dictionary

2006-09-29

arxiv.org/abs/cs/0610001v1

Computer Science

Data Structures and Algorithms

Scientific paper

Rank/Select dictionaries are data structures for an ordered set $S \subset \{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 \emph{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 $nH_0(S)$ ($H_0(S) \leq 1$ is the zero-th order \textit{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.

Affiliated with

Also associated with

No associations

Rating

Practical Entropy-Compressed Rank/Select Dictionary does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Practical Entropy-Compressed Rank/Select Dictionary, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Practical Entropy-Compressed Rank/Select Dictionary will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-616165