共有辞書を用いた効率の良い圧縮アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2012-12-05
• タイトル: 共有辞書を用いた効率の良い圧縮アルゴリズム
• タイトル / 言語: en
• タイトル: Variable-to-Fixed-Length Encoding for Large Texts Using a Re-Pair Algorithm with Shared Dictionaries
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: データ処理の効率化
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属: 北海道大学大学院情報科学研究科／日本学術振興会特別研究員DC
• 著者所属: 北海道大学大学院情報科学研究科
• 著者名: 関根, 渓; 笹川, 裕人; 吉田, 諭史; 喜田, 拓也
• 著者名(英): Kei, Sekine; Hirohito, Sasakawa; Satoshi, Yoshida; Takuya, Kida
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 1999 年に Larsson と Moffat らによって提案された Re-Pair アルゴリズムは，単純なヒューリスティックに基づいた，非常に高い圧縮率を達成する文法圧縮の一つである．しかしながら， Re-Pair アルゴリズムはオフラインのアルゴリズムであり，また，線形サイズではあるものの多くのメモリを使用する．したがって，巨大なテキスト上でアルゴリズムを実行するためには，テキスト全体をいくつかのブロックに分割し，ブロック毎に圧縮を行う必要がある．このような状況において，圧縮時に用いる辞書の一部をブロック間で共有することは，圧縮パフォーマンスの向上に有効であると考えられる．本稿では，ブロック毎に Re-Pair アルゴリズムを行い，辞書式圧縮の辞書に相当する生成規則の一部をブロック間で共有する手法について論じる．ここでは，抽出された文法の符号化には固定長の符号化を用いている．圧縮パフォーマンスを決定する 3 つのパラメータ （ブロックサイズ，辞書サイズ，辞書における共有辞書の割合） の変化によって，圧縮時間と圧縮率がどのように変化するのかを実験的に示し，その傾向について議論する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 研究報告データベースシステム（DBS）; 巻 2012-DBS-156, 号 7, p. 1-6, 発行日 2012-12-05
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会