2010 | OriginalPaper | Buchkapitel
Alphabet Partitioning for Compressed Rank/Select and Applications
verfasst von : Jérémy Barbay, Travis Gagie, Gonzalo Navarro, Yakov Nekrich
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present a data structure that stores a string
s
[1..
n
] over the alphabet [1..
σ
] in
nH
0
(
s
) +
o
(
n
)(
H
0
(
s
) + 1) bits, where
H
0
(
s
) is the zero-order entropy of
s
. This data structure supports the queries
access
and
rank
in time
$({\mathcal O}{{\rm lg lg}\sigma})$
, and the
select
query in constant time. This result improves on previously known data structures using
$nH_0(s)+o(n\lg\sigma)$
bits, where on highly compressible instances the redundancy
$o(n\lg\sigma)$
cease to be negligible compared to the
nH
0
(
s
) bits that encode the data. The technique is based on combining previous results through an ingenious partitioning of the alphabet, and practical enough to be implementable. It applies not only to strings, but also to several other compact data structures. For example, we achieve (
i
) faster search times and lower redundancy for the smallest existing full-text self-index; (
ii
) compressed permutations
π
with times for
π
() and
π
− 1
() improved to log-logarithmic; and (
iii
) the first compressed representation of dynamic collections of disjoint sets.