|
Abstract |
We describe a data structure that supports access, rank and select operations on a dynamic string S[1,n] over alphabet [1..s] in worst-case time O(lg n / lglg n), which is optimal. Symbols can be inserted into and deleted from S in O(lg n / lglg n) amortized time. Those times are better than the best previous dynamic time complexities by a Theta(1 + lg s / lglg n) factor. Our structure uses nH_0(S) + o(n(1+H_0(S))) + O(s (lg s+lg^(1+e) n)) bits, where H_0(S) is the zero-order entropy of S and 0 < e < 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 s) + O(s (lg s+lg n)). We can also handle unbounded alphabets in optimal time, which has been an open problem in dynamic sequence representations. |
