A Variable-length-to-fixed-length Coding Method Using a Re-Pair Algorithm

DOI Web Site
  • Yoshida Satoshi
    Graduate school of Information Science and Technology, Hokkaido University
  • Kida Takuya
    Graduate school of Information Science and Technology, Hokkaido University

Abstract

In this study, 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, which provides easy access to compressed data. However, conventional VF codes generally have an inferior compression ratio compared with variable-length codes. A method proposed by Uemura et al. in 2010 delivered a good compression ratio that was comparable with that of gzip, but it was very time consuming. In this study, we propose a new VF coding method that applies a fixed-length code to a set of rules extracted using the Re-Pair algorithm, which was proposed by Larsson and Moffat in 1999. The Re-Pair algorithm is a simple offline grammar-based compression method, which has good compression-ratio performance with moderate compression speed. We also present experimental results, which demonstrates that our proposed coding method is superior to the existing VF coding method.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top