Please use this identifier to cite or link to this item:
Title: Tree Compression with Top Trees Revisited
Authors: Hübschle-Schneider, L.
Raman, Rajeev
First Published: 20-Jun-2015
Presented at: 14th International Symposium on Experimental Algorithms (SEA 2015) SEA 2015, Paris, France
Start Date: 29-Jun-2015
End Date: 1-Jul-2015
Publisher: Springer Verlag (Germany)
Citation: Lecture Notes in Computer Science, 2015, pp. 15-27 (12)
Abstract: We revisit tree compression with top trees (Bille et al. Information & Computation 2015), and present several improvements to the compressor and its analysis. By significantly reducing the amount of information stored and guiding the compression step using a RePair-inspired heuristic, we obtain a fast compressor achieving good compression ratios, addressing an open problem posed by Bille et al. We show how, with relatively small overhead, the compressed file can be converted into an in-memory representation that supports basic navigation operations in worst-case logarithmic time without decompression. We also show a much improved worst-case bound on the size of the output of top-tree compression (answering an open question posed in a talk on this algorithm by Weimann in 2012).
DOI Link: 10.1007/978-3-319-20086-6_2
ISSN: 0302-9743
ISBN: 978-3-319-20085-9
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Archived with reference to SHERPA/RoMEO and publisher website. The final publication is available at Springer via
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
paper.pdfPost-review (final submitted)454.04 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.