2016/11/04 by Philip Bille, Bille, Philip, Inge Li Gørtz +3 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1611.01479
arxiv created 2016/11/04 · arxiv updated 2016/11/07
Re-Pair is an effective grammar-based compression scheme achieving strong compression rates in practice. Let n, σ, and d be the text length, alphabet size, and dictionary size of the final grammar, respectively. In their original paper, the authors show how to compute the Re-Pair grammar in expected linear time and 5n + 4σ2 + 4d + √(n) words of working space on top of the text. In this work, we propose two algorithms improving on the space of their original solution. Our model assumes a memory word of \lceillog2 n\rceil bits and a re-writable input text composed by n such words. Our first algorithm runs in expected \mathcal O(n/ε) time and uses (1+ε)n +√ n words of space on top of the text for any parameter 0<ε≤ 1 chosen in advance. Our second algorithm runs in expected \mathcal O(nlog n) time and improves the space to n +√ n words.