Affiliations: Department of Computer Science, University of Kuopio,
P.O. Box 1627, 70211 Kuopio, Finland. kimmo.fredriksson@uku.fi | Saint-Petersburg State University, Faculty of Applied
Mathematics and Control Processes, Universitetskii prospekt 35, Petergof,
Saint-Petersburg, Russia 198504. fedor.nikitin@gmail.com
Note: [] Address for correspondence: Department of Computer Science,
University of Kuopio, P.O. Box 1627, 70211 Kuopio, Finland
Abstract: Given a sequence S of n symbols over some alphabet Σ of size
σ, we develop new compression methods that are (i) very simple
to implement; (ii) provide O(1) time random access to any symbol (or short
substring) of the original sequence. Our simplest solution uses at most 2h+o(h)
bits of space, where h = n(H_{0}(S)+1), and
H_{0}(S) is the zeroth-order empirical
entropy of S. We discuss a number of improvements and trade-offs over the basic
method. For example, we can achieve n(H_{k}(S)+1)+o(n(H_{k}(S)+1))
bits of space, for
k = o(log_{σ}(n)). Several applications are discussed, including text compression,
(compressed) full-text indexing and string matching.
Keywords: succinct data structures, text compression, string matching, full-text indexing
