乱択アルゴリズムを用いた頻出文字列の近似数え上げに基づく省スペース文法圧縮

乱択アルゴリズムを用いた頻出文字列の近似数え上げに基づく省

スペース文法圧縮

Online Grammar Compression based on Frequency Information by

Randomized Algorithm

宮木亮洋

1∗

_{坂本比呂志}

1,2

Akihiro Miyagi

1

_{Hiroshi Sakamoto}

1,2 1

_{九州工業大学大学院情報工学府}

1

_{Graduate School of Computer Science and Systems Engineering, Kyushu Institute of}

Technology

2

_{九州工業大学大学院情報工学研究院}

2

_{Graduate School of Computer Science and Systems Engineering, Kyushu Institute of}

Technology

Abstract: We propose a faster online grammar compression based on frequent information in constant space. The online grammar compression based on frequent information[2] is slow due to the cost of dynamic updating of frequency table. Using the fast updatable counting frequency algo-rithm proposed by Ogata et al [4], we quickly update frequency in constant space. We experiment this algorithm for several texts and achieve faster grammar compression than [2].

1

はじめに

近年，ツイッターのつぶやきデータや POS システ ムなど，大規模データを出力する計算機は増加傾向に あり，これらの大規模データの解析が盛んに行われて いる．大規模データを備蓄する方法としてデータ圧縮 を用いることが考えられるが，一般的な圧縮手法の場 合，入力データを全てメモリ上に読み込むためメモリ のオーバーフローを招くという問題がある．そこで 1 度に全てのデータをメモリ上に読み込ませなくても圧 縮が可能なオンライン圧縮を用いる必要がある． データ圧縮の手法の一つである文法圧縮は，入力デー タの文脈を崩さないという特徴からオンライン圧縮に 比較的適した手法といる．文法圧縮は，入力文字列中に 出現する連続する２文字のペアを１文字に置換すること で，入力文字列を一意に導き出す文脈自由文法 (CFG) を構築する圧縮手法である．文法圧縮の詳細について は２章で述べる． ペアの出現頻度に基づき CFG を構築する RePair[1] と呼ばれる文法圧縮の手法があり，高い圧縮率を誇る． しかし，この RePair はオフライン圧縮であり，必要な 記憶領域も大きい．これに対し，Maeda らはペアの出 ∗_{連絡先：九州工業大学大学院情報工学府}       〒 820-8502 福岡県 飯塚市 川津 680-4        E-mail: a [email protected] 現頻度に基づき CFG を構築する，一定のメモリ領域 で動作するオンライン圧縮手法を提案している [2]．こ の手法では SpaceSaving[3] と呼ばれる，一定のメモリ 領域でストリーム中のアイテムの出現頻度の近似計算 を行うアルゴリズムを用いている． 一方で SpaceSaving と同様の目的を持つアルゴリズ ムとして，乱択アルゴリズムを用いてストリーム中のア イテムの出現頻度を疑似的に数え上げる，一定のメモリ 領域で動作するアルゴリズムが Ogata らにより提案され ている [4]．このアルゴリズムは SpaceSaving よりも単 純で，時間計算量の削減が期待できる．この手法に必要 な記憶領域は入力長を N としたとき O(log log N ) ビッ トで，時間計算量はあらゆる入力に対し，平均 O(N ) である． 本研究では，Maeda らの提案した文法圧縮における CFG の構築に際し，[4] の手法を用いて 文字列の出現 頻度を近似的に数え上げ，より出現頻度の高い文字列 を生成規則として置き換えるように CFG を構築する， 一定のメモリ領域で動作する手法を提案する． また， 複数種類のテキストデータに対し，本手法による圧縮 を実行し，圧縮アルゴリズムの性能を検証する． 人工知能学会研究会資料 SIG-FPAI-B401-10 − 41 −

2

準備

2.1

文法圧縮

文法圧縮とは，連続する２文字を１文字に置き換え ることで入力文字列データを一意に導き出す CFG を 構築する圧縮手法である．生成された CFG G は次の ように表される． G = (V, Σ, D, S) (V : 変数 (非終端記号) の有限集合 , Σ : アルファベット (終端記号) の有限集合, D : 生成 規則の有限集合, S : 開始記号) 例えば，入力文字列データ Input = aabababba としたと き，図 1 のような CFG が構築されることが考えられる． この場合，G の各要素はそれぞれ，V = (X1, ..., X7), Σ =

(a, b), D = (X1→ aa, X2→ ba, X3→ bb, X4→ X1X2, X5 → X2X3, X6 → X4X5, X7 → X6X2), S = X7と なる．生成規則が少なくなるほど CFG のサイズは小 さくなり圧縮率は高くなるがサイズが最小となる CFG 構築アルゴリズムは NP-hard であることが知られてお り，PePair などの近似アルゴリズムを用いる． 図 1: CFG の例

2.2

オンライン CFG 構築

RePair では，入力文字列中のペアの出現頻度を全て 数え上げ，最も出現頻度の高いペアを変数に置き換え る．さらに置き換えた文字列にも同様に最も出現頻度の 高いペアを変数に置き換えることを繰り返すことで高い 圧縮率を達成している．本項では，RePair の考え方に 基づきＣＦＧを構築する，[2] のオンライン CFG 構築の アルゴリズムについて説明する．このアルゴリズムはペ アの出現頻度に基づき，より出現頻度の高いペアを動的 に変数に置き換える．入力文字列 S = x1, x2, ..., xnと

すると，まずは４文字分に当たる xi, xi+1, xi+2, xi+3の

みを取得し，４文字中に存在する３つのペア (xi, xi+1),

(xi+1, xi+2), (xi+2, xi+3) のそれぞれの出現頻度を取得

する．取得した出現頻度に応じて以下のようにペアを 生成し，CFG を構築する．

• ペア (xi+1, xi+2) の出現頻度が最も多い場合

(xi+1, xi+2) が生成規則として辞書，および逆辞書

に登録されていなければ登録し，対応する変数に 置き換える．その後，続く文字列 xi+3xi+4xi+5xi+6

を取得し，その中のペアに対して同様の処理を 行う．

• それ以外の場合

(xi, xi+1) が生成規則として辞書，および逆辞書に

登録されていなければ登録し，対応する変数に置 き換える．その後，続く文字列 xi+2xi+3xi+4xi+5

を取得し，その中のペアに対して同様の処理を 行う． 実装では，サイズ４のキューを複数用いており，置 き換えなかったアルファベットおよび変数，置き換え後 の変数を一つ上位のキューに enqueue し，置き換えた ペア自身は dequeue する．各キューに対し，キューが いっぱいになった時点で上記のアルゴリズムにより出 現頻度の高いペアの置き換えを行う．例えば，図 2 の qiにおいてペア (xi+1, xi+2) の出現頻度が最も多い場 合，qi+1に xiと置き換え後の変数 Xiが enqueue され， qiからは置き換えられたペア (xi+1, xi+2) が dequeue

される． 図 2: キューの例

2.3

乱択アルゴリズムによるストリーム中

のアイテムの近似数え上げ

本項では，[4] の手法について説明する．この手法は O(loglogN ) のメモリ領域でアイテムの出現頻度を近似 的に数え上げる．入力ストリーム x = (x1, ..., xn+1) と し，K をアイテムとアイテムの出現頻度のペア (s, K[s]) を最大 2b_{個持つデータ構造とする．s は σ ビット，K[s]} は b ビットの記憶領域を必要とする．また，出現頻度 の指数部を h で表す．アルゴリズムを以下に示す． − 42 −

Algorithm 1 1. K を初期化し， h := 0． 2. x からアイテム xiを読み込む．便宜上，xi= s∗ とする． これ以上アイテムがなければ終了する． 3. 1/2h_{の確率で以下の “record” 操作を行う．} • s∗_{が K になければ (s}∗_{, K[s}∗_{] = 1) を K に} 登録する． • s∗_{が K＄にすでにある場合は K[s}∗_{] + +．} ∑ s∈K = 2 b_{なら，以下の “flush” 操作を行う．} (i) h + +． (ii) K の各 s に対し，確率 1/2 で true を返す* ベルヌーイ試行を K[s] 回行い，true が返っ てきた回数を K[s] に代入する． (iii) K[s] = 0 となる s を K から削除する． 4. 手順１に戻る． * ・・・ture か false のどちらかしか返さない事象を起 こさせること． [4] より，このアルゴリズムは K に (b+σ)2b+⌈(log h)⌉ ビット，その他の作業領域に O(log h) ビット用いる．手 順３で用いる確率 2−hは h 回のベルヌーイ試行を行う ことで O(log h) で実現できる．つまり，読み込んだア イテム xiは h 回投げたコインがすべて表だった場合に 乱択される．2h_{K[s] はアイテム s の出現数 f (s) を近} 似している．また，ストリーム (x1, ..., xn+1) を最後ま で読み込んだ時，それぞれのアイテム xiが乱択されて いる確率は等しく 2−hである．

3

提案手法

提案する CFG 構築のアルゴリズムを以下に示す．節 2.2 の CFG 構築アルゴリズムにおける出現頻度の計算 を [4] の乱択アルゴリズムを用いた手法で行う．長さ N の入力文字列 S = (x1, x2, ..., xN) とし，２文字のペア p とそのペアの出現頻度 K[p] のペア (p, K[p]) を持つ データ構造を K とする．K の要素の最大値 M をパラ メータとしてあらかじめ設定しておく． Algorithm 2 1. K を初期化し，h := 0． 2. 入力文字列 S から xiを読み込み，キューに en-queue する． (xi−1, xi) = pi, (xi−2, xi−1) = pi−1, (xi₋₃, xi₋₂) = pi₋₂とする． これ以上読み込む文字がなければ，終了する． 3. 1/2h_{の確率で以下の “record” 操作を行う．} • p∗_{が K になければ (p}∗_{, K[p}∗_{] = 1) を K に} 登録する． • p∗_{が K＄にすでにある場合は K[p}∗_{] + +．} ∑ s_∈K = M なら以下の”flush” 処理を行う． (i) h + +． (ii) K の各 p に対し, 確率 1/2 で true を返す* ベルヌーイ試行を K[p] 回行い，true が返っ てきた回数を K[p] に代入する． m = M なら K[p] = 0 となる p を K から削除 する． 4. pi, pi₋₁, pi₋₂を比較し，節 2.2 のアルゴリズムに 従い，最も出現頻度の大きいペアを変数に置き換 える．置き換え後の変数は上位のキューに enqueue し，上位のキューに対しても同様の出現頻度数え 上げ，ペアの置き換えを行う． 5. 手順１に戻る． 指定したメモリ領域を最大限活用するため，m = M となった時に K[p] = 0 の p を K から削除する．時間 計算量は [4] に基づき，O(N ) である．

4

実験

英文テキスト，繰り返しの多いテキストに対してそれ ぞれ提案手法の圧縮を実行し，圧縮率，時間計算量を測 定し，RePair[1]，および Maeda らの提案した Space-Saving を用いた手法 [2] と比較した．英文テキストで の圧縮率を図 3，時間計算量を図 4 に，繰り返しの多い テキストでの圧縮率を図 5，時間計算量を図 6 に示す． 実験結果としては，提案手法は flush 操作により，乱 択したペアを捨てていることからどちらのテキストに 対しても圧縮率は SpaceSaving を用いた手法に劣る結 果となった．しかし，提案手法は実装が SpaceSaving に比べシンプルであり，時間計算量を削減することが できた．特に，英文テキストに対する実行での時間計算 − 43 −

量 (図 4) は SpaceSaving を用いた手法を大きく下回っ ている． 図 3: 英文テキストでの圧縮率 図 4: 英文テキストでの時間計算量 図 6: 繰り返しの多いテキストでの時間計算量 図 5: 繰り返しの多いテキストでの圧縮率

5

まとめ

乱択アルゴリズム [4] を用いた一定のメモリ領域で 動作するオンライン文法圧縮を提案した．結果として は，圧縮率は SpaceSaving を用いた手法 [2] に劣るも の，時間計算量を削減することができた．今後の課題 は更なる時間計算量の削減であり，方法としてはラン ダム性を保ったまま乱択の試行回数を減らすことが考 えられる．

参考文献

[1] N. Jesper Larsson and Alistair Moffat. Of-fline Dictionary-Based Compression. Proc. of the IEEE, 88:17221732, 2000.

[2] Koji Maeda, Yoshimasa Takabatake and Hiroshi Sakamoto. Online Grammar Compression based on Frequency Information SIG-FPAI 92, 89-93, 2014.

[3] Ahmed Metwally, Divykant Agrawal and Amr Ab-badi. Efficient Computation of Frequent and Topk Elements in Data Streams. Database Theory -ICDT 2005 Lecture Notes in Computer Science, Volume. 3363, pp. 398-412 (2005).

[4] Masatora Ogata, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita. A Randomized Algo-rithm for Finding Frequent Elements Streams Us-ing O(log log N ) Space. ISAAC 2011, LNCS 7074, pp. 514-523, 2011.