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

Access this Article

Author(s)

    • 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

  • Information and Media Technologies

    Information and Media Technologies 8(4), 971-977, 2013

    Information and Media Technologies Editorial Board

Codes

  • NII Article ID (NAID)
    130003384067
  • Text Lang
    ENG
  • Data Source
    J-STAGE 
Page Top