Top Tree Compression of Tries

Philip Bille, Paweł Gawrychowski, Inge Li Gørtz, Gad M. Landau, Oren Weimann

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

37 Downloads (Pure)

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 languageEnglish
Title of host publicationProceedings of 30th International Symposium on Algorithms and Computation
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date2019
Pages4:1--4:18
ISBN (Print)978-3-95977-130-6
DOIs
Publication statusPublished - 2019
Event30th International Symposium on Algorithms and Computation - 1st Floor at SUFE Research Lab Center, No.100 Wudong Road, Shanghai, China
Duration: 9 Dec 201911 Dec 2019
http://itcs.shufe.edu.cn/isaac2019/

Conference

Conference30th International Symposium on Algorithms and Computation
Location1st Floor at SUFE Research Lab Center, No.100 Wudong Road
CountryChina
CityShanghai
Period09/12/201911/12/2019
Internet address
SeriesLeibniz International Proceedings in Informatics
Volume149
ISSN1868-8969

Keywords

  • Pattern matching
  • Tree compression
  • Top trees
  • Pointer machine

Fingerprint Dive into the research topics of 'Top Tree Compression of Tries'. Together they form a unique fingerprint.

Cite this