Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
CST++
verfasst von : Enno Ohlebusch, Johannes Fischer, Simon Gog
Erschienen in: String Processing and Information Retrieval
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
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.