@inproceedings{86e5311d3f034973a69ee44ab340893d,

title = "Space-Efficient Re-Pair Compression",

abstract = "Re-Pair [5] 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 [log2 n] bits and a re-writable input text composed by n such words. Our first algorithm runs in expected 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 O(n log n) time and improves the space to n + √n words.",

author = "Philip Bille and G{\o}rtz, {Inge Li} and Nicola Prezza",

year = "2017",

doi = "10.1109/DCC.2017.24",

language = "English",

isbn = "978-1-5090-6721-3",

volume = "Part F1",

series = "Data Compression Conference. Proceedings",

publisher = "IEEE",

pages = "171--80",

booktitle = "Proceedings of 2017 Data Compression Conference",

address = "United States",

note = "2017 Data Compression Conference, DCC 2017 ; Conference date: 04-04-2017 Through 07-04-2017",

}