2026-07-23T15:50:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11500 2024-03-06T10:48:10Z ddc:004 open_access

Top Tree Compression of Tries Bille, Philip Gawrychowski, Paweł Gørtz, Inge Li Landau, Gad M. Weimann, Oren pattern matching tree compression top trees pointer machine We present a compressed representation of tries based on top tree compression [ICALP 2013] that works on a standard, comparison-based, pointer machine model of computation and supports efficient prefix search queries. Namely, we show how to preprocess a set of strings of total length n over an alphabet of size sigma into a compressed data structure of worst-case optimal size O(n/log_sigma n) that given a pattern string P of length m determines if P is a prefix of one of the strings in time O(min(m log sigma,m + log n)). We show that this query time is in fact optimal regardless of the size of the data structure. Existing solutions either use Omega(n) space or rely on word RAM techniques, such as tabulation, hashing, address arithmetic, or word-level parallelism, and hence do not work on a pointer machine. Our result is the first solution on a pointer machine that achieves worst-case o(n) space. Along the way, we develop several interesting data structures that work on a pointer machine and are of independent interest. These include an optimal data structures for random access to a grammar-compressed string and an optimal data structure for a variant of the level ancestor problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Philip Bille and Paweł Gawrychowski and Inge Li Gørtz and Gad M. Landau and Oren Weimann 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.4 urn:nbn:de:0030-drops-115000 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.4 eng https://creativecommons.org/licenses/by/3.0/legalcode