A simple storage scheme for strings achieving entropy bounds
Paolo Ferragina, Rossano Venturini, Paolo Ferragina, Rossano Venturini · UnipiEprints Open Archive (Università di Pisa) · 2006
We propose a storage scheme for a string S[1, n], drawn from an alphabet Σ, that requires space close to the k-th order empirical entropy of S, and allows to retrieve any l-long substring of S in optimal O(1 + l/log|Σ| n) time. This matches the best known bounds, via the use of binary encodings and tables only. We also apply this storage scheme to prove new time vs space trade-offs for compressed self indexes and the Burrows-Wheeler Transform.