Space-Efficient Re-Pair Compression

Publication: Research - peer-reviewConference article – Annual report year: 2017

DOI

View graph of relations

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.
Original languageEnglish
JournalData Compression Conference. Proceedings
VolumePart F1
Issue number27767
Pages (from-to)171-80
ISSN1068-0314
DOIs
StatePublished - 2017
Event2017 Data Compression Conference - Snowbird, United States

Conference

Conference2017 Data Compression Conference
CountryUnited States
CitySnowbird
Period04/04/201707/04/2017
CitationsWeb of Science® Times Cited: 0
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

ID: 134060481