共有辞書を用いた効率の良い圧縮アルゴリズム Variable-to-Fixed-Length Encoding for Large Texts Using a Re-Pair Algorithm with Shared Dictionaries

この論文にアクセスする

この論文をさがす

抄録

1999 年に Larsson と Moffat らによって提案された Re-Pair アルゴリズムは,単純なヒューリスティックに基づいた,非常に高い圧縮率を達成する文法圧縮の一つである.しかしながら, Re-Pair アルゴリズムはオフラインのアルゴリズムであり,また,線形サイズではあるものの多くのメモリを使用する.したがって,巨大なテキスト上でアルゴリズムを実行するためには,テキスト全体をいくつかのブロックに分割し,ブロック毎に圧縮を行う必要がある.このような状況において,圧縮時に用いる辞書の一部をブロック間で共有することは,圧縮パフォーマンスの向上に有効であると考えられる.本稿では,ブロック毎に Re-Pair アルゴリズムを行い,辞書式圧縮の辞書に相当する生成規則の一部をブロック間で共有する手法について論じる.ここでは,抽出された文法の符号化には固定長の符号化を用いている.圧縮パフォーマンスを決定する 3 つのパラメータ (ブロックサイズ,辞書サイズ,辞書における共有辞書の割合) の変化によって,圧縮時間と圧縮率がどのように変化するのかを実験的に示し,その傾向について議論する.The Re-Pair algorithm proposed by Larsson and Moffat in 1999 is a simple grammar-based compression method that achieves an extremely high compression ratio. However, Re-Pair is an offine and very space consuming algorithm. Thus, to apply it to a very large text, we need to divide the text into smaller blocks. Consequently, if we share a part of the dictionary among all blocks, we expect that the compression speed and ratio of the algorithm will improve. In this paper, we implemented our method with exploiting variable-to-fixed-length codes, and empirically show how the compression speed and ratio of the method vary by adjusting three parameters: block size, dictionary size, and size of shared dictionary. Finally, we discuss the tendencies of compression speed and ratio with respect to the three parameters.

収録刊行物

  • 研究報告データベースシステム(DBS)

    研究報告データベースシステム(DBS) 2012-DBS-156(7), 1-6, 2012-12-05

各種コード

  • NII論文ID(NAID)
    110009490405
  • NII書誌ID(NCID)
    AN10112482
  • 本文言語コード
    JPN
  • 資料種別
    Technical Report
  • データ提供元
    NII-ELS  IPSJ 
ページトップへ