講義「情報知識ネットワーク特論」

講義「情報知識ネットワーク特論」

～情報検索とパターン照合

第７回

Re-Pair VF符号によるデータ圧縮

― ビッグデータ時代のデータ圧縮 ―

情報理工学専攻 情報知識ネットワーク研究室 喜田拓也

2018/11/22 講義資料

今日の内容

研究背景

新しいデータ圧縮へのアプローチ

・ VF 符号＋文法圧縮 Repair-VF

Adaptive LT-RePair Method ： Repair-VF のオンライン化

2

20120101000000,3,5.0,1,120,644132,00008,168933376,555574333,09853,168933408, ・・・

20120101000000,3,5.0,1,110,644132,00008,168933376,555574333,09853,168933408,・・・

20120101000000,3,5.0,1,120,644132,00009,168989212,555755788,00036,168990785,・・・

・・・

ログデータ Log data

GPSログ

ライフログ

Internet SNS

・市民からの情報提供

・市民への道路情報の提供 UGCデータ User Generated Content data

・気象衛星データ

・航空写真データ

リモートセンシングデータ Remote sensing data

ビッグデータ

データの検索や解析時に再利用しやすいデータ圧縮方式の開発

高速なデータ展開 圧縮したまま検索可能 優れた圧縮性能

研究背景

新しいデータ圧縮へのアプローチ

文法圧縮

データを高度に モデル化

VF符号化

アクセスしやすい 符号系列

圧縮率とアクセシビリティの両立！

圧縮データにアクセスしやすい符号化方式として，

可変長 - 固定長符号化（ VF 符号）に着目 テキストを高度にモデル化する方法として，

文法圧縮に着目

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

元のデータにおける長さの異なる部分系列に対して，

固定長の符号を割り当てる符号化方式

利点： 符号語の境界が明確で，圧縮データへのアクセスが容易 欠点： 可変長符号に比べて，圧縮率を向上させることが困難

圧縮テキスト（符号語）

固定長 可変長

入力テキスト

（情報源記号）

固定長

FF 符号

(Fixed length to Fixed length code)

FV 符号

(Fixed length to Variable length code)

可変長

VF 符号

(Variable length to Fixed length code)

VV 符号

(Variable length to Variable length code)

今の主流は VV符号

文法圧縮 [Kieffer&Yang2000]

ABDABCABCCABDABC

E → ABC F → ABDE σ → FECF

0101110011101 000011100 ・・・

入力テキスト：

文脈自由文法：

圧縮データ：

文法を符号化する

入力テキストを導出する 文脈自由文法を構築

入力テキストを，それと等価な文法に変換し，変換後の

文法を符号化するデータ圧縮法

関連研究

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符号の組み合わせ

目標： データ圧縮の効率を保ちつつ，データを復元すること なしにキーワード検索等の処理を高速に行えるデータ 圧縮の確立

Re-Pair アルゴリズム [ Larsson & Moffat 2000]

入力データ中の最頻の２文字ペア（bigram）を非終端記号に置換 し，その対応付けを生成規則として辞書に登録することを再帰的 に繰り返す

圧縮テキスト

辞書

辞書サイズ ３

𝑂𝑂 (𝑛𝑛)

bigram

𝑇𝑇 = a b c b a b c b c b a b c a a 𝑋𝑋 ₁ b a 𝑋𝑋 ₁ 𝑋𝑋 ₁ b a 𝑋𝑋 ₁ a

𝑋𝑋 ₂ b 𝑋𝑋 ₂ 𝑋𝑋 ₁ b 𝑋𝑋 ₂ a 𝑋𝑋 ₂ 𝑋𝑋 ₃ 𝑋𝑋 ₁ 𝑋𝑋 ₃ a

𝑋𝑋 ₁ → bc

𝑋𝑋 ₂ → a 𝑋𝑋 ₁

𝑋𝑋 ₃ → b 𝑋𝑋 ₂

Re-Pair-VF ： Re-Pair ＋固定長符号化

出力サイズ:

2𝑠𝑠 + 𝑛𝑛 ⌈log(𝑠𝑠 + |Σ|)⌉

AADAEBCFGEFFIGHI EIKJBCEFICEK

𝑠𝑠

𝑛𝑛

記号の種類数

𝑠𝑠 + |Σ|

->各記号は

log 𝑠𝑠 + Σ

圧縮テキスト：

辞書

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

EIKJBCEFICEK

2𝑠𝑠 + 𝑛𝑛

Re-Pair-VF ： Re-Pair ＋固定長符号化

圧縮テキスト：

E F F G E F F F F G B C E F F F C E G E F F

この部分を展開する 辞書

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

E IKJ BCEF I CE K

最適な辞書で圧縮した テキスト：

A A D A E B C F E F F G E F F F F G B C E F F F C E G E F F

Re-Pair-VF[Yoshida&Kida2013]

0 10 20 30 40 50 60 70 80

dazai.utf.txt dblp2003.xml gbhtg119 reuters21578

Compression ratio (%)

Re-Pair-VF best Re-Pair-VF Re-Pair Tunstall STVF gzip

よく知られたgzipという圧縮ツールよりも圧縮率が良い

新聞記事 (reuters21578) 上の検索速度

0 50 100 150 200

0 10 20 30 40 50

Throughput (MB/sec)

Pattern length

Re-pair-VF best Tunstall

gzip

Throughput = Original text length Pattern matching time

Repair-VF 上の照合は gzip に対する照合よりも高速！

Repair-VF の課題

Repair-VF [Yoshida & Kida 2013]

優れた文法圧縮である

Re-Pair [Larsson & Moffat 2000]

優れた圧縮性能とアクセスの容易さを両立

データ入力長

𝑛𝑛

𝑂𝑂 𝑛𝑛

データは一括してメモリ上にロードし，オフライン的に処理

大規模データに対しても適用させたい

数

GB

関連研究

Blocked-Repair-VF [Sekine ら 2013, 2014]

入力データをある長さのブロックに区切って

Re-Pair

事前に適切なパラメータ設定が必要

FOLCA [Maruyama ら 2013]

形式文法

(SLP)

入力テキストの文字集合にのみ依存した文法を構築

(LCA)

圧縮率は

Re-Pair

Re-Pair の文法変換は困難

Re-Pair をオンラインにするのはなぜ難しい？

たとえ，置き換えのための生成規則の集合（辞書）があらかじめ 与えられていたとしても，逐次に置き換えを実行するためには，

最悪時に入力データ長分のバッファが必要になる

𝑋𝑋 ₁ → ba 𝑋𝑋 ₂ → c𝑋𝑋 ₁ 𝑋𝑋 ₃ → d𝑋𝑋 ₂

𝑋𝑋 ₂₅ → z𝑋𝑋 ₂₄ ^𝑋𝑋

𝑋𝑋

a 𝑋𝑋

𝑋𝑋

b c

d

… y

z

𝑋𝑋

現時点で辞書に登録が無い部分でも，将来的にはまとまる可能性がある

構文木の高さ と left-tallなバイグラム

ℎ 𝜎𝜎 = 0 ℎ 𝑋𝑋

= 1 ℎ 𝑋𝑋

= 2 ℎ 𝑋𝑋

= 3

𝜎𝜎 ∈ {a, b, c}

バイグラム

𝑎𝑎

𝑎𝑎

ℎ 𝑎𝑎

≥ ℎ 𝑎𝑎

𝑎𝑎

𝑎𝑎

left-tall

left-tall

𝑋𝑋

→ bc 𝑋𝑋

→ 𝑋𝑋

a 𝑋𝑋

→ b𝑋𝑋

構文木

𝑋𝑋

a c

c b

b b

𝑋𝑋

𝑋𝑋

a c b

left-tall

辞書

非終端記号

𝑋𝑋

ℎ(𝑋𝑋 )

（便宜的に終端記号

𝑎𝑎

ℎ(𝑎𝑎) = 0

left-tall

left-tall

LT-Repair (left-tall-Repair)

入力データ中の ｌ

eft-tall

ℎ a < ℎ 𝑋𝑋₁ より，

a𝑋𝑋₁はleft-tallでない

𝑇𝑇 = a b c b a b c b c b a b c a

圧縮テキスト

𝑋𝑋 ₁ → bc 𝑋𝑋 ₂ → ba 𝑋𝑋 ₃ → 𝑋𝑋 ₁ 𝑋𝑋 ₂ 𝑋𝑋 ₄ → 𝑋𝑋 ₃ 𝑋𝑋 ₁

辞書

a 𝑋𝑋 ₁ b a 𝑋𝑋 ₁ 𝑋𝑋 ₁ b a 𝑋𝑋 ₁ a

a𝑋𝑋 ₄ 𝑋𝑋 ₄ a

a 𝑋𝑋 ₃ 𝑋𝑋 ₁ 𝑋𝑋 ₃ 𝑋𝑋 ₁ a a 𝑋𝑋 ₁ 𝑋𝑋 ₂ 𝑋𝑋 ₁ 𝑋𝑋 ₁ 𝑋𝑋 ₂ 𝑋𝑋 ₁ a

left-tall条件

オンライン置換アルゴリズム (ORA)

辞書は与えられるものとする

入力データを先頭から逐次に読み出しながら，

LT-Repair

辞書中の

bigram

left-tall

置換か出力が確定できる部分を再帰的に決定する

バッファ上で置換可能な

bigram

（

RMQ

→ 𝑂𝑂 𝑛𝑛 log �ℎ

, 𝑂𝑂 𝑔𝑔

（𝑛𝑛：入力長，�ℎ：非終端記号の構文木の高さの最大，𝑔𝑔：辞書サイズ）

確定するための 条件を見出した

output

input text

置換確定ならば置換 出力確定ならば

追い出す バッファ

Adaptive LT-RePair Method (ALT)

長さ

𝑚𝑚

LT-RePair

ORA

Head1′

Head1 Rest1

Head2 Rest2

Head2′

⋯

⋯

ORA

LT-RePair LT-RePair

ORA

圧縮しながら 詰め込む

Input

追加

𝑚𝑚

Dic1

Dic1’

Dic1

Dic1′

𝑚𝑚

Input Text

ALTアルゴリズム全体像

ブロックを適用的に伸長することで，バッファ長

𝑚𝑚

1

Dic1*

ORA 𝑚𝑚

Head

Comp1

𝑚𝑚

Dic2*

Head

Comp2

𝑚𝑚

Dic3*

Head

Comp3 LT-RePair

ORA LT-RePair

ORA LT-RePair

１ブロック目 ２ブロック目 ３ブロック目

ALTアルゴリズムの時間計算量

あるブロックで実質的に読み込むテキスト長を

𝑙𝑙

LT-RePair

𝑂𝑂 𝑙𝑙

全ブロックの

LT-RePair

𝑂𝑂 𝑛𝑛

このブロック内での

ORA

𝑂𝑂 𝑙𝑙 − 𝑚𝑚 log ℎ

ℎ

全ブロックの

ORA

𝑂𝑂 𝑛𝑛 log �ℎ

�ℎ

したがって，提案手法の時間計算量は

𝑂𝑂 𝑛𝑛 log �ℎ

ALTアルゴリズムの領域計算量

LT-RePair

𝑛𝑛

𝑂𝑂 𝑛𝑛 + 𝑏𝑏 = 𝑂𝑂 𝑛𝑛

𝑏𝑏

bigram

bigram

ブロック内の

LT-RePair

𝑏𝑏

𝑚𝑚

𝑂𝑂 𝑚𝑚 + 𝑏𝑏

ORA

𝑂𝑂 𝑔𝑔

𝑔𝑔

ブロック切り替え時，前のブロックで使用した領域は解放するとして，

領域計算量は

𝑂𝑂 𝑚𝑚 + �𝑏𝑏 + �𝑔𝑔 = 𝑂𝑂 𝑚𝑚 + �𝑏𝑏

�𝑏𝑏

�𝑔𝑔

実験結果 （英文テキスト2GB）

Eng2GB

(%)

時間

(s)

展開 時間

(s)

メモリ

(MB)

数

�𝒉𝒉 𝑔𝑔

Re-Pair NA NA NA

FOLCA 37.2 601 52.4 6398

LZD NA NA NA NA

提案手法

(1MB) 42.8 667 53.4 198 334 39 1373137

提案手法

(5MB) 41.0 768 45.2 532 58 41 3186999

提案手法(10MB) 40.6 837 38.9 942 28 49 4440561

まとめ

Re-Pair

オフラインな

LT-Repair

ORA

適応的にブロック長を伸長する

計算機実験により，実際に

GB

圧縮時 時間 領域

Re-Pair 𝑂𝑂 𝑛𝑛 𝑂𝑂 𝑛𝑛

提案手法

𝑂𝑂 𝑛𝑛 𝑙𝑙𝑙𝑙𝑔𝑔 �ℎ 𝑂𝑂 𝑚𝑚 + �𝑏𝑏

𝑛𝑛：入力データ長，𝑚𝑚：初期ブロック長

�ℎ：全ブロックでの非終端記号の構文 木の高さの最大

�𝑏𝑏：各ブロックでの出現したbigramの 種類数のうちの最大

今後の課題

固定長符号化や辞書共有の導入，および展開ルーチンの改良 高速な圧縮データ解析の実装