Tree compression with top trees

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

Research output: Contribution to journalJournal articleResearchpeer-review

400 Downloads (Pure)

Abstract

We introduce a new compression scheme for labeled trees based on top trees. Our compression scheme is the first to simultaneously take advantage of internal repeats in the tree (as opposed to the classical DAG compression that only exploits rooted subtree repeats) while also supporting fast navigational queries directly on the compressed representation. We show that the new compression scheme achieves close to optimal worst-case compression, can compress exponentially better than DAG compression, is never much worse than DAG compression, and supports navigational queries in logarithmic time.
Original languageEnglish
JournalInformation and Computation
Volume243
Pages (from-to)166-177
ISSN0890-5401
DOIs
Publication statusPublished - 2015

Keywords

  • Tree compression
  • Top trees
  • Pattern matching

Fingerprint

Dive into the research topics of 'Tree compression with top trees'. Together they form a unique fingerprint.

Cite this