Blended Dictionaries for Reduced-Memory Lempel-Ziv Corpus Compression
Jiancong Tong, Anthony I. Wirth, Justin Zobel · 2014
Relative Lempel-Ziv (RLZ) compression has been shown to be effective for compression of large text repositories. It provides high compression ratios with extremely fast atomic decompression of individual documents. However, it depends on a large in-memory dictionary, which is implemented as a contiguous string that must be accessed randomly during the decompression process. In this paper we explore how compressed suffix arrays might reduce the size of the dictionary. These suffix arrays drastically increase the cost of accessing individual characters, however, so we propose splitting of the dictionary: an uncompressed structure for frequently accessed dictionary elements, with compression for the remainder. Our results show that splitting provides a smoothly tuneable trade-off between access time and memory requirements, but does not overcome the inherent limitations of compressed suffix arrays for this application, with decompression time growing by a factor of 10 for even the best combination of parameters. Suffix arrays comprise an attractive option where memory is limited, high compression is paramount, and decompression speed is unimportant.