It is well-known that, given a probability distribution over @math characters, in the worst case it takes ( (n n)) bits to store a prefix code with minimum expected codeword length. However, in this paper we first show that, for any @math n^ 1 c n @math c @math 1 $ time.
A technique we will use to obtain our result is the wavelet tree of @cite_3 , and more precisely the multiary variant due to @cite_11 . The latter represents a sequence @math over an alphabet @math of size @math such that the following operations can be carried out in @math time on the RAM model with a computer word of length @math : (1) Given @math , retrieve @math ; (2) given @math and @math , compute @math , the number of occurrences of @math in @math ; (3) given @math and @math , compute @math , the position in @math of the @math -th occurrence of @math . The wavelet tree requires @math bits of space, where @math is the empirical zero-order entropy of @math , defined as @math , where @math is the number of occurrences of @math in @math . Thus @math is a lower bound to the output size of any zero-order compressor applied to @math . It will be useful to write @math .
@cite_3 @cite_11
2134696992 2107082304
We present a novel implementation of compressed suffix arrays exhibiting new tradeoffs between search time and space occupancy for a given text (or sequence) of n symbols over an alphabet σ, where each symbol is encoded by lgvσv bits. We show that compressed suffix arrays use just nH h + σ bits, while retaining full text indexing functionalities, such as searching any pattern sequence of length m in O(m lg vσv + polylog(n)) time. The term H h ≤ lg vσv denotes the hth-order empirical entropy of the text, which means that our index is nearly optimal in space apart from lower-order terms, achieving asymptotically the empirical entropy of the text (with a multiplicative constant 1). If the text is highly compressible so that H n = o(1) and the alphabet size is small, we obtain a text index with o(m) search time that requires only o(n) bits. Further results and tradeoffs are reported in the paper. Given a sequence S e s1s2…sn of integers smaller than r e O(polylog(n)), we show how S can be represented using nH0(S) p o(n) bits, so that we can know any sq, as well as answer rank and select queries on S, in constant time. H0(S) is the zero-order empirical entropy of S and nH0(S) provides an information-theoretic lower bound to the bit storage of any sequence S via a fixed encoding of its symbols. This extends previous results on binary sequences, and improves previous results on general sequences where those queries are answered in O(log r) time. For larger r, we can still represent S in nH0(S) p o(n log r) bits and answer queries in O(log r log log n) time. Another contribution of this article is to show how to combine our compressed representation of integer sequences with a compression boosting technique to design compressed full-text indexes that scale well with the size of the input alphabet Σ. Specifically, we design a variant of the FM-index that indexes a string T[1, n] within nHk(T) p o(n) bits of storage, where Hk(T) is the kth-order empirical entropy of T. This space bound holds simultaneously for all k ≤ α logvΣv n, constant 0 Compared to all previous works, our index is the first that removes the alphabet-size dependance from all query times, in particular, counting time is linear in the pattern length. Still, our index uses essentially the same space of the kth-order entropy of the text T, which is the best space obtained in previous work. We can also handle larger alphabets of size vΣv e O(nβ), for any 0