Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Succinct Index for Dynamic Dictionary Matching
verfasst von : Wing-Kai Hon, Tak-Wah Lam, Rahul Shah, Siu-Lung Tam, Jeffrey Scott Vitter
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
In this paper we revisit the dynamic dictionary matching problem, which asks for an index for a set of patterns
P
1
,
P
2
, ...,
P
k
that can support the following query and update operations efficiently. Given a query text
T
, we want to find all the occurrences of of these patterns; furthermore, as the set of patterns may change over time, we also want to insert or delete a pattern. The major contribution of this paper is the first succinct index for dynamic dictionary matching. Prior to our work, the most compact index is given by Chan
et al.
(2007), which is based on the compressed suffix arrays (Grossi and Vitter (2005) and Sadakane (2003)) and the FM-index (Ferragina and Manzini (2005)), and it requires
O
(
n
σ
) bits where
n
is the total length of patterns and
σ
is the alphabet size. We develop a dynamic succinct index using a different (and simpler) paradigm based on suffix sampling. The new index not only improves the space complexity to (1 +
o
(1))
n
log
σ
+
O
(
k
log
n
) bits, but also the time complexity of the query and update operations. Specifically, the query and update operations respectively take
O
(|
T
|log
n
+
occ
) and
O
(|
P
|log
σ
+ log
n
) times, where
occ
is the number of occurrences.