高階圧縮の高速化と効率の良い符号化  [in Japanese] Efficient Algorithm and Coding for Higher-Order Compression  [in Japanese]

Search this Article

Author(s)

Abstract

高階圧縮とは,与えられたデータを生成する高階関数型プログラムを構成する圧縮法であり,圧縮したままのデータ操作が可能であるという文法圧縮の利点を持つと同時に,従来手法では扱えないパターンの発見や高い圧縮率が期待される.本論文では、高階圧縮の既存研究では未解決であった(1)高速な圧縮アルゴリズムおよび(2)高階関数型プログラムのビット列への簡潔な符号化方法を提案し,その有効性を実験的に示す.

Higher-order compression is a scheme for compressing data in the form of functional programs that generate the data.This compression scheme can be viewed a generalization of grammar-based compression, and retains its advantage that the compressed data can be manipulated without decompression.Furthermore, the higher-order compression can achieve a high compression ratio and also discover patterns that cannot be found by traditional grammar-based compression.In this paper, we propose an efficient algorithm and a bit-coding scheme for higher-order compression and evaluate their effectiveness through experiments.

Journal

  • IEICE technical report. Theoretical foundations of Computing

    IEICE technical report. Theoretical foundations of Computing 113(252), 13-20, 2013-10-11

    The Institute of Electronics, Information and Communication Engineers

Codes

  • NII Article ID (NAID)
    110009820601
  • NII NACSIS-CAT ID (NCID)
    AN10013152
  • Text Lang
    JPN
  • Data Source
    NII-ELS 
Page Top