Paper Info
Title
LZRR: LZ77 Parsing with Right Reference
Abstract
Lossless data compression has been widely studied in computer science. One of the most widely used lossless data compressions is Lempel-Ziv (LZ) 77 parsing, which achieves a high compression ratio. Bidirectional (a.k.a. macro) parsing is a lossless data compression and computes a sequence of phrases copied from another substring (target phrase) on either the left or the right position in an input string. Gagie et al. (LATIN 2018) recently showed that a large gap exists between the number of smallest bidirectional phrases of a given string and that of LZ77 phrases. In addition, finding the smallest bidirectional parse of a given text is NP-complete. Several variants of bidirectional parsing have been proposed thus far, but no prior work for bidirectional parsing has achieved high compression that is smaller than that of LZ77 phrasing for any string. In this paper, we present the first practical bidirectional parsing named LZ77 parsing with right reference (LZRR), in which the number of LZRR phrases is theoretically guaranteed to be smaller than the number of LZ77 phrases. Experimental results using benchmark strings show the number of LZRR phrases is approximately five percent smaller than that of LZ77 phrases.
Year
DOI
Venue
2019
10.1109/DCC.2019.00029
2019 Data Compression Conference (DCC)
Keywords
DocType
Volume
Lossless data compression,Lempel Ziv 77,Bidirectional parsing
Conference
abs/1812.04261
ISSN
ISBN
Citations 
1068-0314
978-1-7281-0658-8
0
PageRank 
References 
Authors
0.34
9
2
Name
Order
Citations
PageRank
Takaaki Nishimoto1233.54
Yasuo Tabei221519.46