DEIM Forum 2013 C10-2

大規模テキストに対する共有辞書を用いた Re-Pair 圧縮法
関根渓†

笹川 裕人†

吉田 諭史†

喜田拓也†† 北海道大学大学院情報科学研究科 〒 060–0814 北海道札幌市北区北 14 条西 9 丁目
E-mail: †{k sekine, sasakawa, syoshid, kida}@ist.hokudai.ac.jp
あらまし1999 年に Larsson と Moffat らによって提案された Re-Pair アルゴリズムは，高い圧縮率を達成する文法

圧縮の一つである．しかし，Re-Pair アルゴリズムはオフラインアルゴリズムであり，多くのメモリを使用する．よって，巨大なテキスト上でアルゴリズムを実行するためには，テキスト全体をいくつかのブロックに分割し，ブロック毎に圧縮を行う必要がある．このとき，圧縮時に用いる辞書の一部をブロック間で共有することは，圧縮パフォーマンスの向上に有効であると考えられる．本稿では，テキスト全体からサンプリングしたテキストをもとに，共有辞書を構築した際のパフォーマンスについて論じる．
キーワード

可逆データ圧縮，Re-Pair，文法圧縮，VF 符号

Variable-to-Fixed-Length Encoding for Large Texts Using Re-Pair
Algorithm with Efficient Shared Dictionaries
Kei SEKINE† , Hirohito SASAKAWA† , Satoshi YOSHIDA† , and Takuya KIDA†† Grad. School of Inform. Sci. and Tech., Hokkaido University, N14 W9, Sapporo 060–0814, JAPANE-mail: †{k sekine, sasakawa, syoshid, kida}@ist.hokudai.ac.jp
Abstract A Re-Pair algorithm proposed by Larsson and Moffat in 1999 is a simple grammar-based compression
method, which achieves an extremely high compression ratio. However, since the Re-Pair algorithm is offline andvery space consuming, we need to divide a very large text into smaller blocks to apply the algorithm on the verylarge text. In such case, it is expected that we can improve the compression speed and ratio by sharing a part ofthe dictionaries among all the blocks. In this paper, we show empirically how the compression speed and ratio varywith constructing the shared dictionary on the text constructed by sampling uniformly from the whole input text.
Key words Lossless Data Compression, Re-Pair, Grammer-Based Compression, VF Coding

1. は じ め にような何らかの巧妙な工夫が必要である．例えば，Lemple-Ziv
符号化の派生プログラム [14], [15] の多くは，辞書を作成するとメモリ装置の性能向上により，数ギガバイトから数十ギガバ

きに，参照するテキストや辞書のサイズを制限する工夫がなさ

イト程度のメモリが個人でも容易に手に入れられるようになっれている．一方，Bzip2 のように Burrows-Wheeler 変換に基た．このため，以前は採用が困難であったメモリ消費の激しいづく圧縮法では，入力テキストを独立した小さいブロックに分

アルゴリズムを採用できる場面が増え，データを一旦メモリ上割して，ブロック毎に圧縮を行うことで一度に扱うテキストのに置いてから処理を行うオフライン処理が当たり前のものに長さを制限している．

なっている．データ圧縮技術においても，かつては適応的な処

入力テキストをブロックに分割して辞書式圧縮アルゴリズム

理方式が好ましいとされたが，Burrows-Wheeler 変換 [1] に基を用いる場合，全てのブロック間で辞書の一部を共有するこづく圧縮法のように，オフライン的な処理をしてでも高い圧縮とで圧縮性能が改善されることが予想される．Wan と Moffat率を得ることを目的とするアルゴリズムが注目されるようにら [13] は，Larsson と Moffat らによって提案された圧縮法でなった．

ある Re-Pair アルゴリズム [6] を基に，ブロック毎に作成されしかしながら，計算機に搭載されるメモリ容量には限界があた辞書を全体で統合する手法を提案している．Re-Pair アルゴ

り，圧縮プログラムが数百メガバイトを超える巨大なテキスト

リズムは文法変換に基づくシンプルなオフライン圧縮アルゴリ

を一度に取り扱うことはやはり困難である．したがって，そのよ

ズムであり，非常に高い圧縮率を達成する．Wan と Moffat らうな巨大なテキストを処理する上で，メモリ使用量を節約する

は，Re-Pair の高い圧縮率を保ったままメモリ消費量をうまく—1—削減できることを実験的に示した [13]．その反面，圧縮速度に

タの組み合わせで実験を行った．結果としては，実験よって，大きな犠牲を払っている．

ほぼ全てのパラメータにおいて，旧手法よりも良い圧縮率を本研究では，より簡単な辞書共有方法を提案し，その圧縮パ達成することを確認できた．また，適切なパラメータにおいフォーマンスについて論じる．我々の方法では，あらかじめ準て，bzip2 に匹敵する圧縮率 (27 ％程度) を達成することがわ

備した共有辞書を全てのブロックで共有する．この方法においかった．

て圧縮速度と圧縮率は，ブロックサイズ，辞書サイズ，共有辞
書サイズ，の 3 つのパラメータに依存する．例えば，共有辞書

2. 関 連 研 究

サイズを大きくすることで，ブロック毎に別々に作られる辞書

これまで，多くの文法圧縮手法が開発されている．LZ78 [15]（ローカル辞書）のサイズは小さくなるが，一方で各ブロック

や，LZW 法 [14]，Bisection [3] は，扱う文法が straight lineの圧縮率は悪化するということが予想される．

program のクラスに属する文法圧縮アルゴリズムである．さら

本稿では特に，入力テキストを独立したブロックに分割し，に，文法を文脈自由文法（CFG）に限定したアルゴリズムもRe-Pair アルゴリズムで圧縮する場合に，辞書の共有化が圧縮提案されている [4], [6], [8], [9]. それらのうち，特に Re-Pair [6]性能に与える影響について議論する．この共有辞書の構成法

や，SEQUITUR [8] は圧縮率に優れている．また，Maruyama

として，関根らは，入力テキストの最初のブロックに対してら [7] は，文脈依存文法に基づく圧縮手法を提案している．

Re-Pair アルゴリズムを適用して辞書を構築し，以降のブロック

VF 符号においては，Klein と Shapira ら [5] や， Kida [2] がでは，その一部を共有辞書として継続的に使用する，Blocked-

それぞれ独立に，接尾辞木 [12] に基づく VF 符号（STVF 符

Re-Pair-VF [16] を提案した．この Blocked-Re-Pair-VF では，号）を提案した．STVF 符号では，頻度に基づいて枝刈りをテキストをブロック化することにより，Re-Pair-VF 従来の圧行った接尾辞木を分節木として用いている．STVF 符号は，古縮率を殆ど悪化させることなく，メモリの消費を抑えることに典的な VF 符号である Tunstall 符号 [10] と比べると圧縮率を成功した．しかし Blocked-Re-Pair-VF では，共有辞書はテキ

大幅に向上させたが，gzip などのよく知られた既存ツールにはストの最初のブロックから構築されるため，文脈が途中から大依然およばない．VF 符号の圧縮率を向上するために，Uemura

きく変わるようなテキストを圧縮する際は，共有辞書の効果がら [11] は入力テキストを繰り返し読み，分節木をトレーニング

得られなくなる可能性がある．本稿ではその問題を解決するたする手法を提案している．この手法は，Gzip なみの圧縮率をめに，入力テキストの部分文字列を繋げ合わせてブロックと同達成するが，圧縮に非常に時間がかかることが難点である．実程度のサイズのサンプリングテキストを生成し，そのサンプリ

際，文献 [11] では，Tunstall 符号の 100 倍程度の時間を要する

ングテキストに対して Re-Pair アルゴリズムを適用して辞書をことが示されている．

構築し，その辞書を共有辞書としてテキスト全体で使用する，サンプル法を提案する．

Wan と Moffat [13] によって提案された Re-Merge アルゴリ
ズムは，大規模テキストに対して Re-Pair アルゴリズムを適オリジナルの Re-Pair アルゴリズムでは文法変換後にエン用するための拡張手法の一つである，Re-Merge アルゴリズム

トロピー符号化を行うが，今回の手法では辞書のそれぞれのは，入力テキストを独立なブロックに分割し，各ブロックに対エントリを固定長の符号語で符号化を行う．辞書のあるエント

して Re-Pair アルゴリズムを適用して，ブロック毎の辞書を構

リ（文法の生成規則）はテキスト中の部分文字列に対応してい築する．その後，それらの辞書の統合を段階的に行う．最終的る．すなわち，このような符号化方式は，いわゆる variable-には，統合した辞書を用いて，入力テキスト全体を再度圧縮す

lengh-to-fixed-length 符号（VF 符号）になっている．VFる．彼らの実験結果によると，Re-Merge アルゴリズムによる符号とは，入力テキストを部分文字列の列に分解し，それぞれ圧縮率はきわめて良好であり，英語の自然言語テキストデータの部分文字列に対し固定長の符号を割り当てる符号化方式のこである WSJ508 に対して，およそ 20% の圧縮率を達成していとである．VF 符号は，可変長の符号語を用いる圧縮方式と比る．実験に用いられた WSJ508 とは，508MB の SGML による

べて圧縮率の観点から不利であるが，工学的観点から見るといマークアップがなされた新聞記事であり，1987 年から 1992 年

くつか有益な点が存在する．例えば，VF 符号は符号語間の境までの記事が含まれている．一方で，圧縮時間に関しては芳し界が明白なので，圧縮されたテキスト上の任意のブロックに対くなく，彼らの実験環境（2.8GHz の Intel Xeon，2GB メモリ，

してランダムに高速なアクセスが可能となる．実際，VF 符号

Debian GNU/Linux）において 4400 秒かかっている．

は，圧縮テキストに対するパターン照合の高速化という観点か
ら再評価されている [2], [5]．さらに，副次的な効果ではあるが，VF 符号では共有辞書の効果の分析が容易になるという利点もある．複雑なエントロピー符号化を用いると良い圧縮率を得る

3. 圧縮アルゴリズム
本節では，Re-Pair アルゴリズム [6] と，提案手法のサンプル法について説明する．

ことができるが，最終的な出力サイズから共有辞書の効果のみ

3. 1 Re-Pair アルゴリズムを議論することが煩雑なものとなる．一方，VF 符号は全てのRe-Pair アルゴリズムはオフラインの文法圧縮アルゴリズム

符号語長が等しいため，その効果を圧縮率として直接に観察でであり，入力としてテキストが与えられると，その入力テキス

きる．

トを一意に生成するような文脈自由文法を生成することでテ

今回，我々は提案手法を計算機上で実装し，様々なパラメー

キストを圧縮する．文脈自由文法とは，句構造文法の一つで，—2—

(Σ, V, σ, R) の四つ組で表される．Σ = {a1 , a2 , · · · , a|Σ| } は終端記号，V = {α1 , α2 , · · · , α|V | } は非終端記号，σ ∈ V は開始{記号である．R は，V から (Σ ∪ V )∗ への関係であり，生成規

Input Text則とよばれる．以下ではこの生成規則の集合 R を辞書と呼ぶこ
Block Separationとにする．なお，Σ と V は互いに素な集合である．

{{

Re-Pair アルゴリズムによって，構築される文脈自由文法は

Text1

以下のようなルールから構成される：

Text2

Text3

σ ⇒ αi1 αi2 · · · αim (∀ik ∈ {1, · · · , |Σ| + |V | − 1}),ai
if 1 <=i<= |Σ|,
αi ⇒
α α
(1 <
j k
= j, k < i) if i > |Σ|.

{Sampling & Merge

なお，全ての生成規則の右辺にある 2-gram はユニークである．

Re-Pair-VF

Re-Pair アルゴリズムは，文字列上に出現する最頻の 2-gramを新しい非終端記号に置き換え，置き換えられた 2-gram を生{成規則として R に追加する．この手続きを，文字列上の全ての

2-gram がユニークになるまで繰り返す．開始記号 σ は，この繰り返しが終わった後に得られる文字列に対応している．最後に，辞書 R と σ の内容を適当なエントロピー符号化法を用いて符号化する．

3. 2 サンプル法
本論文の提案手法であるサンプル法は，テキストを固定長のブ

Text4

図1

SharedDic

共有辞書の構築過程．テキストをブロック化した後，各ブロックから一様に部分文字列を抜き出し結合，サンプリングテキストを生成する．そして，サンプリングテキストに対して Re-Pair-VF（Re-Pair でテキストを圧縮した後に，固定長の符号で符号化す

ロックに分割し，各ブロックにおいて共有辞書を用いた Re-Pair

るアルゴリズム）を適用し，共有辞書を構築する．なお，共有辞

アルゴリズムを行う．また，後段の符号化には VF 符号を用い

書サイズ S は 2L 個のエントリのうち，共有辞書が占めるエンる．ここで，B, S, L, C をそれぞれ，ブロック長，共有辞書サ

トリ数の割合を表す．

イズ，符号語長，サンプリングテキストサイズとする．また，
入力テキストを T とおき，それは非負の整数 {0, . . . , |Σ| − 1}

辞書を用いて，テキストの左から順に 2-gram の置換を行って上で表されているものとする．このアルゴリズムは B, S, L,

いく．共有辞書による置換が終わると，ローカル辞書の構築を

C, T を入力として受け取り，圧縮テキスト T 0 および辞書 D

行う．ローカル辞書の構築は以下の手順で行われる．

を出力する．サンプル法は，ブロック間で共有する辞書（共有（ 1 ） ブロック内から最頻出の 2-gram を発見する，辞書）の構築（図 1）と，ブロック毎に固有な辞書（ローカル（ 2 ） その 2-gram を辞書 D に登録する，辞書）の構築（図 2）の 2 ステップからなる．以下に，これら（ 3 ） 登録した 2-gram のブロック内の全ての出現を新しいのステップの詳細を述べる．

非終端記号で置き換える．

アルゴリズムは，最初に入力テキスト T を長さ B のブロッ

なお，ローカル辞書の構築は，ブロック内の全ての 2-gram がクに分割する．T のサイズを N とおくと，入力テキストはユニークになった時点または，全体の辞書サイズが 2L になっ

dN/Be 個のブロックに分割される．次に，出来上がったブロッ

た時点で終了し，辞書と現在のブロック上の文字列を符号化す

ク列において，各ブロックの先頭からサイズ c の部分文字列をる．符号化終了後，次のブロックの処理に移る．

抜き出し，それらを順に繋げ合わせてサンプリングテキストと辞書の符号化は，文字列の符号化とは別に行われる．符号化する．このとき，c = C/dN/Be とする．このサンプリングテされた共有辞書に続けて，各ブロックに対する符号化された

キストに対し，辞書のサイズが S となるまで以下を繰り返す：

ローカル辞書を出力する．共有辞書とローカル辞書に登録され（ 1 ） サンプリングテキストから最頻出の 2-gram (α, β) をた 2-gram の各文字は，L ビットの符号語で符号化される．な

見つける，

お，辞書の各エントリに対する符号語の長さが L ビットの固（ 2 ） 2-gram (α, β) を辞書 D に追加する，定長なので，エントリや記号を区切る特殊な文字は必要ない．

（ 3 ） サンプリングテキストのすべての 2-gram (α, β) を新

文字列上の各文字も同様に，L ビットの符号語により符号化さしい記号に置き換える．

れる．

以上の処理によって共有辞書の構築が完了する．繰り返しの途中でサンプリングテキスト中のすべての 2-gram がユニークになった場合，そのときの共有辞書のサイズが S に達していない場合であっても共有辞書の構築を終了する．
共有辞書の構築後，各ブロックでの処理を行う．まず，共有

4. 実

験

提案手法であるサンプル法を計算機上で実装し，実験を行った．なお，実装は C 言語で行い，コンパイラは GCC version

4.6.3 を用いた．
—3—

{

{

Shared
Dic

Text3

Text2

Text1

and so on...

replace

Comp1

Re-Pair-VF

Re-Pair-VF

Re-Pair-VF

Local
Dic1

Text3'

Text2'

Text1'

{

Text4

Local
Dic2

Comp2

Local
Dic3

Comp3

図 2 ローカル辞書の構築およびアルゴリズムの圧縮過程．各ブロックの 2-gram を共有辞書で置き換えた後，個々のブロックに対して Re-Pair-VF を適用し，ローカル辞書と圧縮テキストを生成する．

4. 1 実験環境とデータ
実験は，以下の計算機上で行った．

•

CPU : Intel Xeon processor 3.6GHz•

メモリ : 32GB•

OS : Ubuntu OS 12.04

本実験では，途中で文脈が大きく変わるようなテキストを人為的に作成し入力データとした．具体的には，Pizza & Chili

corpus（注 1） から取得した，DNA のテキストデータ dna，XMLのテキストデータ dblp.xml および英文テキストデータ english
を順に，サイズがちょうど 2GB になるように繋ぎ合わせた自作
テキストデータを生成した．以下の全ての実験はこの自作テキストデータを用いて行った．また，以降は Blocked-Re-Pair-VF
を旧手法と呼ぶ．

4. 2 旧手法との比較実験
本実験の目的は，文脈が途中で大きく変化するテキストを圧縮する際に，改良された共有辞書が与える効果を実験的に調査することである．実験では，サンプル法に対し，ブロックサイ
ズ B ，符号語長 L，共有辞書サイズ S ，およびサンプリングテ
キストサイズ C の 4 つのパラメータを変化させながら，圧縮
時間および圧縮率をそれぞれ計測し，旧手法との比較を行った．
圧縮時間と圧縮率の結果をそれぞれ，図 3，図 4 にまとめた．
図 4 より，圧縮時間に関しては，サンプル法と比べて，旧手法がほぼ全てのパラメータにおいて速い，ということがわかる．

図3

サンプル法および旧手法の圧縮率のパラメータによる変化．圧縮率の良い方が緑色，悪い方が赤色となるように色付けを行った．
中でも，特に良い値は青字にして下線を引いた．列 B はブロッ
クサイズを，列 L は符号語長を，列 S は共有辞書サイズを，列旧手法が先頭ブロックから共有辞書を構築するのに対し，サンNEW (xM) はサンプル法においてサンプリングサイズ C = x

プル法は共有辞書を構築する前に，そのためのサンプリングテ(MB) を入力として与えた場合の実験結果を，列 OLD は旧手法

キストを生成するため，余計に時間がかかっていると思われる．

の実験結果を表す．なお，共有辞書サイズ S は 2L 個のエント

図 3 より，圧縮率に関しては，旧手法と比べて，サンプル法がリのうち，共有辞書が占めるエントリ数の割合を表す．

ほぼ全てのパラメータの組み合わせで優れていることがわかる．また，サンプル法ではパラメータを変化させても圧縮率の異なるブロックにおいて，ブロックの文脈に合わない共有辞書

数値が安定しているのに対し，旧手法は共有辞書サイズが大きでブロックを圧縮する．したがって，圧縮率が著しく悪化して

くなりすぎると圧縮率が極端に悪化している．本実験では，圧いる．なお，本実験において最も良い圧縮率は，ブロックサイ

縮対象としたテキストデータは文脈が途中で大きく変わるテキズ B = 128，符号語長 L = 19，共有辞書サイズ S = 1/8 のとストを使用しているため，旧手法では，先頭ブロックと文脈がき得られ，その値は 27.78 % であった．

4. 3 サンプル法の挙動の調査（注 1）：Pizza & Chili corpus :texts.html

http://pizzachili.dcc.uchile.cl/

本小節では，ブロックサイズ B と，符号語長 L，共有辞書サ
イズ S ，サンプリングテキストサイズ C の 4 つのパラメータ

—4—

図5

サンプリングテキストサイズ C (MB) を変化させたときの，各符号語長 L (bit) における圧縮時間の変化．ブロックサイズはB = 128 (MB) に，共有辞書サイズは S = 3/8 に固定している．

図 6 サンプリングテキストサイズ C(MB) を変化させたときの，各符号語長 L (bit) における圧縮率の変化．ブロックサイズはB = 128(MB) に，共有辞書サイズは S = 3/8 に固定している．

成時間は，その対象となるテキストサイズに比例するためである．また，図 6 より，圧縮率は殆どの場合において，サンプリ
ングテキストサイズが大きくなるほど，ほんの僅かずつではあるが，改善されていくことが観察できる．これは，共有辞書作成の対象となるサンプリングテキストサイズが増加することによって，より多くの異なる文脈の 2-gram を辞書に登録することが出来るようになり，圧縮率が改善されていると考えられる．
図 4 サンプル法および旧手法の圧縮時間（sec）のパラメータによるまた，圧縮率の変化が僅かであるのは，符号語長，共有辞書サ

変化．圧縮率の良い方が緑色，悪い方が赤色となるように色付イズを固定した状態でサンプリングサイズを変化させているたけを行った．中でも，特に良い値は青字にして下線を引いた．列め，辞書に登録できるエントリ数に限りがあり，圧縮率に限界

B はブロックサイズを，列 L は符号語長を，列 S は共有辞書
サイズを，列 NEW (xM) はサンプル法においてサンプリング
サイズ C = x (MB) を入力として与えた場合の実験結果を，列OLD は旧手法の実験結果をそれぞれ表す．

があるためである．

4. 3. 2 ブロックサイズを変化させたときの挙動
サンプル法においてブロックサイズ B を変化させながら，圧縮率，圧縮時間を計測した．圧縮時間と圧縮率の結果をそれぞを変化させたときの圧縮時間および圧縮率の変化について考察する．

4. 3. 1 サンプリングテキストサイズを変化させたときの挙動
サンプル法において，サンプリングテキストサイズ C を変化させながら，圧縮率，圧縮時間を計測した．圧縮時間と圧縮率の結果をそれぞれ，図 5，図 6 にまとめた．
図 5 より，サンプリングテキストサイズを大きくするほど圧縮時間が長くなっていることがわかる．これは，共有辞書の作れ，図 7，図 8 に示す．
図 7 より，ブロックサイズが大きくなるにしたがって，圧縮時間が大きくなっていることがわかる．これは，ブロックサイズが大きくなるにつれ，ブロック内へのランダムアクセスの増加による，キャッシュミスの発生によって引き起こされる速度低下であると考えられる．図 8 より，圧縮率はブロックサイズ
が大きくなるにしたがって改善していくことがわかる．出力される圧縮テキストのサイズと辞書のサイズについて調査を行ったところ，圧縮テキストのサイズは，ブロックサイズが小さく

—5—

図7

ブロックサイズ B (MB) を変化させたときの，各共有辞書サイ

図 9 共有辞書サイズ S を変化させたときの，各ブロックサイズ B

ズ S における圧縮時間の変化．サンプリングテキストサイズは(MB) における圧縮時間の変化．サンプリングテキストサイズはC = 128 (MB) に，符号語長は L = 19 (bit) に固定している．

C = 128 (MB) に，符号語長は L = 19 (bit) に固定している．

図 8 ブロックサイズ B (MB) を変化させたときの，各共有辞書サ

図 10

共有辞書サイズ S を変化させたときの，各ブロックサイズ

イズ S における圧縮率の変化．サンプリングテキストサイズはB における圧縮時間の変化．サンプリングテキストサイズはC = 128 (MB) に，符号語長は L = 19 (bit) に固定している．

C = 128 (MB) に，符号語長は L = 19 (bit) に固定している．

なるほど大きくなるということがわかった．これは，ブロックなることがわかった．これは，共有辞書サイズが大きくなるこ

サイズを小さくするほどテキストのブロック分割が増え，各ブとで，ローカル辞書サイズが減少し，ブロック特有の 2-gram

ロックに対してよりきめ細やかな圧縮ができるためである．一を辞書のエントリーに格納できないため，圧縮テキストが大き方，辞書のサイズはブロックサイズが小さくなるほど大きくな

くなる．また，共有辞書サイズが大きくなるにつれ，辞書サイるということがわかった．これは，ブロックサイズが小さいと，ズは小さくなることがわかった．これは，各ブロックで構築さ構築されるローカル辞書の数が増えることで辞書サイズが増加れるローカル辞書のサイズが小さくなることで，結果として全してしまうことに起因する．以上から，ブロックサイズが増大

体の辞書サイズが小さくなるためである．以上から，圧縮テキ

していくとき，圧縮テキストサイズは減少し，辞書サイズは増

ストサイズと辞書サイズはトレードオフの関係にあり，さらに大していくが，圧縮テキストサイズの減少分の方が大きいため，

圧縮ファイルのサイズは圧縮テキストと辞書サイズの合計で表

結果として圧縮率が改善されているということがわかった．

されるため，圧縮率は共有辞書サイズの変化に対して一様には

4. 3. 3 共有辞書サイズを変化させたときの挙動変化しない．また，共有辞書サイズ S のいくつかのパラメータ

サンプル法において，共有辞書サイズ S を変化させながら，では，共有辞書を用いない場合（S = 0/8）よりも，圧縮率が圧縮率，圧縮時間を計測した．圧縮時間と圧縮率の結果をそれぞれ，図 9，図 10 に示す．

良くなることが観察できた．

4. 3. 4 符号語長を変化させたときの挙動

図 9 より，共有辞書サイズが大きくなるにつれて，圧縮時間

サンプル法において，符号語長 L を変化させながら，圧縮は短くなっていくことがわかる．これは，共有辞書サイズが大率，圧縮時間を計測した．圧縮時間と圧縮率の結果をそれぞれ，

きくなることにより，ローカル辞書サイズが小さくなり，ロー

図 11，図 12 に示す．

カル辞書を作成する時間が減少したためである．図 10 より，圧図 11 より，符号語長が大きくなるほど圧縮時間が増加する

縮率の変化は，ブロックサイズを固定した場合，共有辞書サイ

ことがわかる．符号語長の増加により，辞書に登録できるエンズの変化に関して一様ではなく，ある値で最小となっているこ

トリー数の増加し，辞書構築および出力に時間がかるためであとが観察できる．共有辞書サイズの変化による，圧縮テキスト

る．また，図 12 より，圧縮率に関しては符号語長の変化に一サイズと辞書サイズの変化について調査を行ったところ，共有様ではなく，ある一定の値で最小になっていることがわかる．

辞書サイズが増加するにつれて，圧縮テキストサイズが大きく

符号語長が短い場合，辞書のエントリーが少なくなるため圧縮—6—

図 11 符号語長 L を変化させたときの，各共有辞書サイズ S におけ

図 13

る圧縮時間の変化．サンプリングテキストサイズは C = 128

サンプル法および既存手法の圧縮率．OLD は旧手法を，NEWはサンプル法を表す．

(MB) に，ブロックサイズは B = 128 (MB) に固定している．

図 14
図 12

サンプル法および既存手法の圧縮時間．OLD は旧手法を，NEWはサンプル法を表す．

符号語長 L を変化させたときの，各共有辞書サイズ S における圧縮率の変化．サンプリングテキストサイズは C = 128 (MB)に，ブロックサイズは B = 128 (MB) に固定している．

テキストのサイズは大きくなってしまうが，逆に出力される辞書のサイズは小さくなる．符号語長が長い場合，辞書のエントリーが多くなるため圧縮テキストサイズは小さくなるが，辞書のエントリーが多くなるため出力される辞書のサイズが大きくなってしまう．このように，圧縮率において，圧縮テキストサ
イズと出力される辞書のサイズはトレードオフの関係にあるため，両者がうまくバランスがとれるパラメータで，最良の圧縮率を得ることができる．

4. 4 サンプル法の圧縮パフォーマンスの評価

図 15

サンプル法および既存手法の伸展時間．OLD は旧手法を，NEWはサンプル法を表す．

サンプル法の圧縮パフォーマンスの一般的な性能を検査するため，上記の自作テキストデータに対して，既存の圧縮手法

他手法と比べても多くかかっている．一方，図 15 より，伸展を適用し，圧縮率，圧縮時間，および伸展時間を計測した．サ

時間は圧縮時間の 1/10 程度であり，bzip2 よりも高速である．

ンプル法との比較に用いたのは，gzip（注 2）と, bzip2（注 3）, LZMA

サンプル法は VF 符号で符号化を行うため，圧縮テキストが非(7-Zip)（注 4）, 旧手法の 4 つである．旧手法以外のプログラムは常に扱いやすいという特性がある．したがって，圧縮ファイル

どれも Ubuntu 12.04 に搭載されているパッケージ（gzip 1.4，を展開せずにパターン照合やデータマイニングなどの処理を行

bzip2 1.0.6，および LZMA 5.1.0 alpha）を使用した．圧縮率，うのであれば，サンプル法は有用となる．

圧縮時間，および伸展時間の結果を図 13，図 14，および図 15にまとめた．図 13 より，サンプル法は bzip2 に匹敵する圧縮

5. お わ り に率を達成していることがわかる．また，図 14 より，サンプル

本論文では，大規模テキストに対して，VF 符号による圧縮法は bzip2 と比べると 2，3 倍程度の圧縮時間がかかっており，を行うためのアルゴリズムである Blocked-Re-pair-VF に対して，その共有辞書構築法を改良したサンプル法を提案した．提（注 2）：zip : http://www.gzip.org/（注 3）：bzip2 : http://www.bzip.org/（注 4）：LZMA : http://www.7-zip.org/

案手法では，途中で文脈が変わるテキストを入力とした場合でも圧縮率を悪化させないように，入力テキストに対して一様に—7—サンプリングを行って生成したサンプリングテキストから共有辞書を構築するように改良を行った．実験では，ほぼ全てのパラメータにおいて，旧手法よりも良い圧縮率を達成することを確認できた．また，提案手法は固定長の符号語を用いる圧縮手法であるにも関わらず，適切なパラメータにおいて，bzip2 並
みの圧縮率を達成することがわかった．
今回，我々の提案手法では，全てのパラメータは，ユーザが3–14, January 2007.
[14] T. A. Welch. A technique for high performance data compression. IEEE Comput., Vol. 17, pp. 8–19, June 1984.
[15] J. Ziv and A. Lempel. Compression of individual sequences
via variable-length coding. IEEE Trans. on Inform. Theory,
Vol. 24, No. 5, pp. 530–536, Sep 1978.
[16] 関根渓, 笹川裕人, 吉田諭史, 喜田拓也. 共有辞書を用いた効率の良い圧縮アルゴリズム. 第 156 回データベースシステム研究会,
2012 年 12 月.

入力として与えていた．しかし，現実的には，入力テキストの情報から，適切なパラメータが自動的に決定されることが求められる．
また，今回は，提案手法と Re-Merge アルゴリズム [13] との直接の比較は行っていないが，Re-Merge アルゴリズムは，辞書の統合手法はやや複雑なものであるので，提案手法の辞書を共有する簡単な手法は，圧縮時間において有利であると考えられる．今回の提案手法と Re-Merge アルゴリズムとの直接の比較を行うことも今後の課題である．
文

献[1] M. Burrows and D. J. Wheeler. A block-sorting losslessdata compression algorithm. Technical Report 124, Digital
Equipment Corporation, Palo Alto, California, 1994.
[2] T. Kida. Suffix tree based VF-coding for compressed pattern matching. In Proc. of Data Compression Conference
2009 (DCC 2009), p. 449, Mar. 2009.
[3] J. C. Kieffer, G. Nelson E.-H. Yang, and P. Cosman. Universal lossless compression via multilevel pattern matching.
IEEE Trans. Inform. Theory, Vol. 46, No. 4, pp. 1227–1245,
2000.
[4] J. C. Kieffer and E.-H. Yang. Grammar-based codes: a newclass of universal lossless source codes. IEEE Trans. on
Inform. Theory, Vol. 46, No. 3, pp. 737–754, 2000.
[5] S. T. Klein and D. Shapira. Improved variable-to-fixed
length codes. In Proc. of the 15th International Symposiumon String Processing and Information Retrieval (SPIRE2008), pp. 39–50, 2008.
[6] N. J. Larsson and A. Moffat. Off-line dictionary-based compression. Proceedings of the IEEE, Vol. 88, No. 11, pp.
1722–1732, 2000.
[7] S. Maruyama, Y. Tanaka, H. Sakamoto, and M. Takeda.
Context-sensitive grammar transform: Compression andpattern matching. In Proc. of 15th International Symposium on String Processing and Information Retrieval(SPIRE 2008), pp. 27–38, Nov. 2008.
[8] C. Nevill-Manning, I. Witten, and D. Maulsby. Compression by induction of hierarchical grammars. In Proc. of theData Compression Conference 1994 (DCC ’94), pp. 244–
253. IEEE, 1994.
[9] H. Sakamoto, T. Kida, and S. Shimozono. A space-saving
linear-time algorithm for grammar-based compression. In
String Processing and Information Retrieval, Vol. 3246 of
Lecture Notes in Computer Science, pp. 218–229. Springer
Berlin / Heidelberg, 2004.
[10] B. P. Tunstall. Synthesis of noiseless compression codes.
PhD thesis, Georgia Institute of Technology, Atlanta, GA,
1967.
[11] T. Uemura, S. Yoshida, T. Kida, T. Asai, and S. Okamoto.
Training parse trees for efficient VF coding. In Proc. of
the 17th international conference on String processing andinformation retrieval (SPIRE 2010), pp. 179–184, 2010.
[12] E. Ukkonen. On-line construction of suffix trees. Algorithmica, Vol. 14, No. 3, pp. 249–260, 1995.
[13] R. Wan and A. Moffat. Block merging for off-line compression. J. Am. Soc. Inf. Sci. Technol., Vol. 58, No. 1, pp.

—8—