Optimal Dynamic Sequence Representations

We describe a data structure that supports access, rank and select queries, as well as symbol insertions and deletions, on a string S [1, n ] over alphabet [1‥σ] in time O (lg n /lg lg n ), which is optimal. The time is worst-case for the queries and amortized for the updates. This complexity is better than the best previous ones by a Θ(1 + lg σ/lg lg n ) factor. Our structure uses nH 0 ( S ) + O ( n + σ(lg σ + lg n )) bits, where H 0 ( S ) is the zero-order entropy of S and 0 < ε < 1 is any constant. This space redundancy over nH 0 ( S ) is also better, almost always, than that of the best previous dynamic structures, o ( n lg σ) + O (σ(lg σ + lg n )). We can also handle general alphabets in optimal time, which has been an open problem in dynamic sequence representations.

Authors

• Gonzalo Navarro 0001
• Yakov Nekrich

Keywords

No keywords are indexed for this paper.