2015/01/01 by Lorenz Hübschle-Schneider, Rajeev Raman, Hübschle-Schneider, Lorenz +1
Computer Science · #Advanced Database Systems and Queries #Algorithms and Data Compression #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #E.2 #E.4 #F.2.2 #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1506.04499
SEA 2015
openalex publication_date 2015/01/01 · arxiv created 2015/06/15 · arxiv updated 2015/06/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We revisit tree compression with top trees (Bille et al, ICALP'13) 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).