Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Space-Efficient Construction of LZ-Index
verfasst von : Diego Arroyuelo, Gonzalo Navarro
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
A
compressed full-text self-index
is a data structure that replaces a text and in addition gives indexed access to it, while taking space proportional to the compressed text size. The LZ-index, in particular, requires 4
uH
k
(1+
o
(1)) bits of space, where
u
is the text length in characters and
H
k
is its
k
-th order empirical entropy. Although in practice the LZ-index needs 1.0-1.5 times the text size, its construction requires much more main memory (around 5 times the text size), which limits its applicability to large texts. In this paper we present a practical space-efficient algorithm to construct LZ-index, requiring (4+
ε
)
uH
k
+
o
(
u
) bits of space, for any constant 0 <
ε
< 1, and
O
(
σu
) time, being
σ
the alphabet size. Our experimental results show that our method is efficient in practice, needing an amount of memory close to that of the final index.