TCS-TR-A-12-61

Date: Mon Nov 12 11:00:18 2012

Title: Effective Variable-Length-to-Fixed-Length Coding via a Re-Pair Algorithm

Authors: Satoshi Yoshida and Takuya Kida

Contact:

First name: Takuya
Last name: Kida
Address: Graduate School of Information Science and Technology, Hokkaido University. Kita 14-jo, Nishi 9-chome, Kita-ku, 060-0814 Sapporo, Japan.
Email: kida@ist.hokudai.ac.jp

Abstract. We address the problem of improving variable-length-to-fixed-length codes (VF codes). A VF code is an encoding scheme that uses a fixed-length code, and thus, one can easily access the compressed data. However, conventional VF codes usually have an inferior compression ratio to that of variable-length codes. Although a method proposed by T. Uemura~\etal ~in 2010 achieves a good compression ratio comparable to that of gzip, it is very time consuming. In this study, we propose a new VF coding method that applies a fixed-length code to the set of rules extracted by the Re-Pair algorithm, proposed by N. J. Larsson and A. Moffat in 1999. The Re-Pair algorithm is a simple off-line grammar-based compression method that has good compression-ratio performance with moderate compression speed. Moreover, we present several experimental results to show that the proposed coding is superior to the existing VF coding.