Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Improved Practical Compact Dynamic Tries
verfasst von : Andreas Poyias, Rajeev Raman
Erschienen in: String Processing and Information Retrieval
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
We consider the problem of implementing a
dynamic trie
with an emphasis on good practical performance. For a trie with
n
nodes with an alphabet of size
$$\sigma $$
, the information-theoretic lower bound is
$$n \log \sigma + O(n)$$
bits. The Bonsai data structure [
1
] supports trie operations in
O
(1) expected time (based on assumptions about the behaviour of hash functions). While its practical speed performance is excellent, its space usage of
$$(1+\epsilon ) n (\log \sigma + O(\log \log n))$$
bits, where
$$\epsilon $$
is any constant
$$> 0$$
, is not asymptotically optimal. We propose an alternative,
m-Bonsai
, that uses
$$(1 + \epsilon ) n (\log \sigma + O(1))$$
bits in expectation, and supports operations in
O
(1) expected time (again based on assumptions about the behaviour of hash functions). We give a heuristic implementation of m-Bonsai which uses considerably less memory and is slightly faster than the original Bonsai.