Advertisement
Published in:
2010 | OriginalPaper | Chapter
CST++
Authors : Enno Ohlebusch, Johannes Fischer, Simon Gog
Published in: String Processing and Information Retrieval
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
Let
A
be an array of
n
elements taken from a totally ordered set. We present a data structure of size 3
n
+
o
(
n
) bits that allows us to answer the following queries on
A
in constant time, without accessing
A
: (1) given indices
i
<
j
, find the position of the minimum in
A
[
i
..
j
], (2) given index
i
, find the first index to the left of
i
where
A
is strictly smaller than at
i
, and (3) same as (2), but to the right of the query index. Based on this, we present a new compressed suffix tree (CST) with
O
(1)-navigation that is smaller than previous CSTs. Our data structure also provides a new (practical) approach to compress the LCP-array.