Abstract
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.
Original language | English |
---|---|
Title of host publication | Proceedings of 30th International Symposium on Algorithms and Computation |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publication date | 2019 |
Pages | 4:1--4:18 |
ISBN (Print) | 978-3-95977-130-6 |
DOIs | |
Publication status | Published - 2019 |
Event | 30th International Symposium on Algorithms and Computation - 1st Floor at SUFE Research Lab Center, No.100 Wudong Road, Shanghai, China Duration: 9 Dec 2019 → 11 Dec 2019 http://itcs.shufe.edu.cn/isaac2019/ |
Conference
Conference | 30th International Symposium on Algorithms and Computation |
---|---|
Location | 1st Floor at SUFE Research Lab Center, No.100 Wudong Road |
Country/Territory | China |
City | Shanghai |
Period | 09/12/2019 → 11/12/2019 |
Internet address |
Series | Leibniz International Proceedings in Informatics |
---|---|
Volume | 149 |
ISSN | 1868-8969 |
Keywords
- Pattern matching
- Tree compression
- Top trees
- Pointer machine