透過的データアクセスを実現する新しいデータ圧縮法

2013年度 ERATO秋のWS

ブロック間の辞書共有による

Re-Pairアルゴリズムの

大規模テキスト圧縮への適用

北海道大学大学院情報科学研究科 コンピュータサイエンス専攻

喜田拓也

1 2013/09/13 登別温泉 第一滝本館 本館会議室

2

研究の背景と目的

・気象衛星データ ・航空写真データ Internet SNS ・市民からの情報提供 ・市民への道路情報の提供 GPSログ・ライフログデータ GPS ・_GPSログ ・ライフログ

UGC（User Generated Content）データ

リモートセンシングデータ オープン･スマート･フェデレーション･ アーキテクチャ 多種多様で大量なストリームデータを取り扱わなければならない RDBに格納して索引付けするほど個々のデータは重要ではないし，重複も多い データ検索やデータ解析時に再利用しやすいデータ圧縮方式の開発 クラウド Big Data

∗ 元のデータにおける長さの異なる部分系列に対して， 固定長の符号を割り当てる符号化方式 ∗ 利点： 符号語の境界が明確なので，圧縮データへの アクセスが容易 ∗ 欠点： 可変長符号に比べて，圧縮率を向上させることが 難しい 3

可変長

-固定長符号化（VF符号）

文法圧縮

データを高度に モデル化

VF符号化

アクセスしやすい 符号系列 圧縮率とアクセシビリティの両立！

VF符号について

∗ 今の主流の圧縮法は，ほぼ_VV符号 ∗ VF符号は符号語が固定長で，圧縮率を上げにくい ∗ 既存の手法で実用的に使われているものは皆無 圧縮テキスト（符号語） 固定長 可変長 入力テキスト （情報源記号） 固定長

FF符号

(Fixed length to Fixed length code) (Fixed length to

FV符号

Variable length code)

可変長

VF符号

(Variable length to Fixed length code)

VV符号

(Variable length to Variable length code)

ハフマン 符号など

∗ 既存手法の問題点： 既存手法は，データ量の削減効率 のみに主眼が置かれているため，データの再利用には 必ず復元の手間がかかる．

5

関連研究

Amir & Benson ‘92 Kida et al.’98, ’99, ’00

Kieffer & Yang ‘00 Larsson & Moffat ‘99

Brisaboa et al. ’03, ‘10 Kida ’09, ‘10 Tunstall ‘67

Klein & Shapira ‘08

Yoshida & Kida ‘12

圧縮照合処理の幕開け 実用的な圧縮照合法 Dence coding系データ圧縮 Re-Pair：超高圧縮 文法圧縮の幕開け 可変長-固定長符号の始祖 Suffix treeを用いたVF符号 効率よい_STVF符号 文法圧縮とVF符号の組み合わせ ∗ 独自技術： テキストデータにおいて，データ圧縮の効率 を保ちつつ，データを復元することなしにキーワード検索 等の処理を高速に行えるデータ圧縮技術を持つ．

Grammar-based compression

ABDABCABCCABDABC E → ABC F → ABDE FECF 0101110011101 000011100・・・ Input text Grammar Compressed text

Encode the grammar

Construct a (context free) grammar that generates

Replace most frequent bigram into a new symbol

Re-pair algorithm

dictionary

D → AA

E → DA

F → EB

G → CF

Encode with

variable length code

(a Huffman variation) 7

sum: bits

(

2s+ n

)



log

(

s + Σ

)



AADAEBCFGEFFIGHI EIKJBCEFICEK

s

n s + 2

The number of sort of symbols: s + Σ

We need bits for each symbol. log

(

s + Σ

)



Compressed sequence: Dict. D → AA E → DA G → CF F → EB H → GE I → FF K → HI J → IG EIKJBCEFICEK

Calculate this value for each substitution to store the size of dictionary that gives the highest compression ratio.

Dictionary D → AA E → DA G → CF F → EB H → GE I → FF K → HI J → IG

Compressed sequence：

EIKJBCEFICEK

AADAEBCF EFFGEFFFFFFGBCEFFFCEGEFF

Compressed sequence by the best dictionary:

EFFGEFFFFFFGBCEFFFCEGEFF

expand this part

9

Re-Pair-VF[Yoshida&Kida2013]

0 10 20 30 40 50 60 70 80 dazai.utf.txt dblp2003.xml gbhtg119 reuters21578 Co m pr es sio n ratio ( % ) Re-Pair-VF best Re-Pair-VF Re-Pair Tunstall STVF gzip よく知られたgzipという圧縮ツールよりも圧縮率が良い

11

新聞記事

(reuters21578)上の検索速度

0 50 100 150 200 0 10 20 30 40 50 Thr oug hp ut ( M B /s ec) Pattern length Re-pair-VF best Tunstall gzip

Text

CompText

Dictionary

Re-Pair-VF:

O(n)だがオフライン的

GBを超える テキストには 適用が難しい

Re-Pair-VF の問題点

Text Re-Pair-VF 13

Dic1

Comp1

Dic2

Comp2

Dic3

Comp3

Dic4

Comp4 出力される辞書の一部が同じエントリを持ってしまう． （予備実験では，各ブロックで30%程度の2-gramの重複を確認）

対策１：テキストのブロック化

Text4 Text3 Text2 Text1

対策２：辞書の共有化

－ Re-Use

Text4 Text3 Text2 Text1 Local Dic1 Comp1 Replace Text2’ Local Dic2 Comp2 Re-Pair-VF Text3’ Local Dic3 Comp3 Re-Pair-VF Text1’ Shared DIC Re-Pair-VF 以下同様

Text1 Text2 Text3 Text4 𝐵 Re-Pair Shared DIC 𝑆

Re-Use (1stBlock)

Text1 Text2 Text3 Text4 𝐵 𝑐 Re-Pair Shared DIC 𝐶

Sampling & Merge

𝑆

Text1 𝑐 Re-Pair Shared DIC 𝐶

Sampling & Merge

𝑆

∗ 注目ブロックが変わる度に自動的に辞書を更新 有用なルールを抽出 ERATO合宿 Text1 Text2 DIC1 Comp1 SDIC2 Replace Text2’ Local Dic2 Comp2 Re-Pair-VF Re-Pair-VF 以降繰り返し

Adaptive-Dictionary-Sharing (ADS)

∗ 辞書の更新（_{Extraction）フェイズ} ∗ _𝐷𝑛: 辞書エントリを格納する配列，_{𝐿: エントリ数，𝑙: 符号語長，𝑡: 閾値} ERATO合宿 DIC 𝒏 Re-Pair-VF ･･･ A→ab B→Aa C→cB X→Dy Y→zH Z→KY ･･･ ock 𝑛 − 1 𝐷_𝑛[0] 𝐷_𝑛[1] 𝐷_𝑛[2] ･･･ 𝐷𝑛[𝐿 − 2] 𝐷_𝑛[𝐿 − 1] 𝐷_𝑛[𝐿] (𝐿 = 2𝑙)

Check the numbers

Block 𝑛 Block 𝑛 + 1 ･･･

Entry’s State: Previous

①前ブロックで構築した辞書の各ルールの， 次ブロックにおける出現数を調べる．

ERATO合宿 DIC 𝒏 Re-Pair-VF A→ab B→Aa C→cB X→Dy Y→zH Z→KY ･･･ 𝐷_𝑛[0] 𝐷_𝑛[1] 𝐷_𝑛[2] ･･･ 𝐷𝑛[𝐿 − 2] 𝐷_𝑛[𝐿 − 1] 𝐷_𝑛[𝐿] (𝐿 = 2𝑙) A→ab B→Aa NULL X→Dy NULL NULL ･･･ SDIC 𝒏+1 Share Share Share Discard Discard Discard ･･･

ock 𝑛 − 1 Block 𝑛 Block 𝑛 + 1 ･･･

②出現数が閾値𝒕以上のルール を次ブロックの辞書のエント リとして引き継ぎ， 𝒕未満のルールを破棄．

ADSの辞書更新アルゴリズム

∗ 辞書の更新（_{Extraction）フェイズ} ∗ _𝐷𝑛: 辞書エントリを格納する配列，_{𝐿: エントリ数，𝑙: 符号語長，𝑡: 閾値}

ERATO合宿 21 DIC 𝒏 Re-Pair-VF A→ab B→Aa C→cB X→Dy Y→zH Z→KY ･･･ 𝐷_𝑛[0] 𝐷_𝑛[1] 𝐷_𝑛[2] ･･･ 𝐷𝑛[𝐿 − 2] 𝐷_𝑛[𝐿 − 1] 𝐷_𝑛[𝐿] (𝐿 = 2𝑙) A→ab B→Aa NULL X→Dy NULL NULL ･･･ SDIC 𝒏+1 Share Share Share Discard Discard Discard ･･･

ock 𝑛 − 1 Block 𝑛 Block 𝑛 + 1 ･･･

Replace

Text 𝑛 + 1

Shared

Entry’s State: Previous

③引き継いだルールで 次ブロックの置き換えを行い， 半圧縮テキストを得る．

ADSの辞書更新アルゴリズム

∗ 辞書の更新（_{Extraction）フェイズ} ∗ _𝐷𝑛: 辞書エントリを格納する配列，_{𝐿: エントリ数，𝑙: 符号語長，𝑡: 閾値}

ERATO合宿 DIC 𝒏 Re-Pair-VF A→ab B→Aa C→cB X→Dy Y→zH Z→KY ･･･ 𝐷_𝑛[0] 𝐷_𝑛[1] 𝐷_𝑛[2] ･･･ 𝐷𝑛[𝐿 − 2] 𝐷_𝑛[𝐿 − 1] 𝐷_𝑛[𝐿] (𝐿 = 2𝑙) A→ab B→Aa C→AA X→Dy Y→XK Z→GY ･･･ SDIC 𝒏+1 Share Share Share Discard Discard Discard ･･･

ock 𝑛 − 1 Block 𝑛 Block 𝑛 + 1 ･･･

Replace Text 𝑛 + 1 Re-Pair-VF And so on… ④再度圧縮し， 新たに生成したルールを 辞書の空きエントリへ格納

ADSの辞書更新アルゴリズム

∗ 辞書の更新（_{Extraction）フェイズ} ∗ _𝐷𝑛: 辞書エントリを格納する配列，_{𝐿: エントリ数，𝑙: 符号語長，𝑡: 閾値}

∗

環境

∗ CPU: 3.6 GHz Intel Xenon processor

∗ Memory: 32GB ∗ Language: C

∗

テキスト

∗ _{𝑃𝑃𝑃𝑃𝑃 & 𝐶𝐶𝑃𝑙𝑙𝑃 𝑐𝑐𝑐𝑐𝑐𝑐*より入手した，𝑒𝑛𝑒𝑙𝑃𝑐𝐶 (英文),} 𝑑𝑑𝑙𝑐. 𝑥𝑥𝑙 (XML), 𝑑𝑛𝑃 (DNA配列), 𝑐𝑐𝑐𝑡𝑒𝑃𝑛 (タンパク質配列) を組み合わせた，以下の自作テキストを用いた． ∗ _{𝑒𝑛𝑒𝑙𝑃𝑐𝐶:} 2GBの英文テキスト． ∗ _{𝑐𝑐𝑛𝑐𝑃𝑡: 𝑒𝑛𝑒𝑙𝑃𝑐𝐶, 𝑑𝑑𝑙𝑐. 𝑥𝑥𝑙, 𝑑𝑛𝑃を繋げて2GBとしたテキスト．} ∗ _{𝑐𝐶𝑃𝑐𝑐: 𝑒𝑛𝑒𝑙𝑃𝑐𝐶, 𝑑𝑑𝑙𝑐. 𝑥𝑥𝑙, 𝑑𝑛𝑃, 𝑐𝑐𝑐𝑡𝑒𝑃𝑛を128MBずつ交互に繋} げて，_{2GBとしたテキスト．}

∗

手法

∗ ADS (proposed method)

∗ Re-Use（1stBlock，Head，Random）

∗ Others (bzip2, gzip, lzma)

実験

100 200 300 400 500 600 700 1 5 10 50 100 500 1000 5000 D at a siz e ( M B ) Threshold total text dictionary

∗

閾値

𝑡を変化させたときの圧縮データサイズ

∗ Input text: _{𝑐𝑒𝑟𝑒𝑐𝑐𝑒, 𝐵 =128MB, 𝑙 =19bit,}

∗ 圧縮率は𝑡が小さくなるほど改善．

∗ _{𝑡が小さくなるほど辞書サイズ減．}

実験

∗

_{Re-USEとの比較：圧縮率}

∗

ADSは

_{𝑒𝑛𝑒𝑙𝑃𝑐𝐶と𝑐𝑐𝑛𝑐𝑃𝑡において最も良い圧縮率}

を達成した．

Methods/Texts english concat chaos Re-Use (1stBlock) 30.84 28.25 36.14 Re-Use (Head) 30.19 28.20 35.47 Re-Use (Random) 30.46 28.14 35.38

実験

∗

_{Re-USEとの比較：圧縮時間}

∗

_{ADSはHeadおよびRandomよりも高速．}

Methods/Texts english concat chaos Re-Use (1st-Block) 587.71 488.41 516.53 Re-Use (Head) 620.50 517.48 547.39 Re-Use (Random) 623.70 523.00 554.81

実験

∗ 既存手法との比較 手法 圧縮率 (%) 圧縮時間 (sec)展開時間 (sec) ADS 27.23 494.71 33.80 Re-Merge 22.66 7907.85 51.18 gzip -1 38.91 33.22 16.47 gzip -9 32.42 360.55 13.55 bzip2 -1 28.76 156.23 60.07 bzip2 -9 25.18 169.23 65.27 lzma -1 34.68 134.20 42.81 lzma -9 21.56 1994.18 23.32

∗ データ検索やデータ解析時に再利用しやすいデータ圧縮 方式として_VF符号化に着目し，文法圧縮と組み合わせた 圧縮率の良いデータ圧縮法を実現した ∗ ブロック間で辞書を共有化する手法（_{Re-Use）を提案} ∗ 共有する辞書を適応的に変化させる手法（_{ADS）を提案} ∗ 高速なキーワード検索が行えることに加え，部分的な展 開や，修正を加えたうえでの再圧縮などが容易に行える 今後の課題： ∗ 圧縮時間の改善 ∗ センサデータ，トラジェクトリデータ等への対応 ∗ 原テキストでの位置を指定した高速なデータ参照の実現

まとめ