Advertisement
Published in:
2005 | OriginalPaper | Chapter
Space-Efficient Construction of LZ-Index
Authors : Diego Arroyuelo, Gonzalo Navarro
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.