Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Succinct Suffix Arrays Based on Run-Length Encoding
verfasst von : Veli Mäkinen, Gonzalo Navarro
Erschienen in: Combinatorial Pattern Matching
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
A succinct full-text self-index is a data structure built on a text
T
=
t
1
t
2
...
t
n
, which takes little space (ideally close to that of the compressed text), permits efficient search for the occurrences of a pattern
P
=
p
1
p
2
...
p
m
in
T
, and is able to reproduce any text substring, so the self-index replaces the text. Several remarkable self-indexes have been developed in recent years. They usually take
O
(
nH
0
) or
O
(
nH
k
) bits, being
H
k
the
k
th order empirical entropy of
T
. The time to count how many times does
P
occur in
T
ranges from
O
(
m
) to
O
(
m
log
n
).
We present a new self-index, called run-length FM-index (RLFM index), that counts the occurrences of
P
in
T
in
O
(
m
) time when the alphabet size is
$\sigma=O(\textrm{polylog}(n))$
. The index requires
nH
k
log
2
σ
+
O
(
n
) bits of space for small
k
. We then show how to implement the RLFM index in practice, and obtain in passing another implementation with different space-time tradeoffs. We empirically compare ours against the best existing implementations of other indexes and show that ours are fastest among indexes taking less space than the text.