読者です 読者をやめる 読者になる 読者になる

Byte Pair Encodingの拡張

下の論文を読んだのでメモ

Shirou Maruyama, Youhei Tanaka, Hiroshi Sakamoto, Masayuki Takeda:
Context-Sensitive Grammar Transform: Compression and Pattern Matching.
IEICE Transactions 93-D(2): 219-226 (2010)

Byte Pair Encodingとは文法圧縮で有名なRe-Pairのシンプルな実装の1つである.BPEはパターン照合に適している反面,他の圧縮法に比べて圧縮率が悪いことが知られている[1].
上記の論文では文脈自由文法であるByte Pair Encodingを文脈依存文法に拡張したBPEXなる圧縮法を提案している.
BPEXはBPEと比べ圧縮率が向上しているばかりか,BPEX上のパターン照合も高速に行う事ができ,一挙両独な性能を持つ.
(圧縮率はRe-Pairやgzip, bzip2には負けるが,Re-PairからBPEの圧縮率の低下と比べるとずいぶん改善されている)

Re-Pair

Re-Pairは反復の多いテキストに対して劇的に効果を発揮する文法圧縮の1つで,その文法圧縮の中でも実用的に圧縮率が良いことが知られている.

入力テキストの再頻出のbigramを新しい記号に置き換え,置き換えたテキストで同様に再頻出のbigramを新しい記号に置き換る.この処理を同じbigramが2回以上出現しなくなるまで繰り返す.


T = ababbabab
abが4回出現し再頻出,A=abで置き換え
T = AAbAA
AAが2回出現し再頻出,B=AAで置き換え
T = BbB
2回以上出現するbigramが出現しないので終了

ここでA=ab, B=AAという規則と,置き換え後のテキストBbBを持っておけば,元のテキストを復元できる.

Byte Pair Encoding

Re-Pairの置き換え回数を256に限定した圧縮法.
(多分1つの記号を1バイトで表現できることが圧縮パターン照合の高速化につながっている)

Byte Pair Encodingの文脈依存文法化

Σ-依存文法をまず説明する.
アルファベットをΣとし,VをΣの要素ではない記号の集合とした時,次のような規則のみからなる文脈依存文法をΣ-依存文法と呼ぶ.
aX→aAB
or X→AB (a ∈ Σ, A, B ∈ Σ or V, X ∈ V)

BPEを次のようにΣ-依存文法に拡張する.
各文字ai ∈ Σについて,aiに後続する再頻出のbigramをAi Biとする.(iは添字,Ai, Bi ∈ Σ or V)
この時ai X → ai Ai Biなる規則を作成する.
このような規則を全ての文字aiについて作成し,全てのai Ai Biをai Xに置き換えた後,作成した記号の数が256に達するか,2個以上出現するbigramがなくなるまで繰り返す.

Σ-依存文法の場合,Xが導出するbigramはそれに先行する文字によって変化するため,Xという一つの記号により|Σ|個の規則を表現することが出来る事に注意する.
BPEは文脈自由文法なので256個の記号で,256個の規則しか表現できない.
これに対し,BPEXは256個の記号で|Σ|*256個の規則を表すことが出来る.
使う記号数は同じにもかかわらずBPEよりも表現力が高くなっていることが分かる.

またBPEXは全ての記号を1バイトで表すことが出来るという圧縮パターン照合に適した性質を保っている.
実験ではBPEX上のパターン照合がBPE上のパターン照合よりも高速に動作することが確認されている.(圧縮率が良くなった分高速になっている)

感想

文脈依存文法に拡張するアイディアは目から鱗だった.
自分にとって想像の範疇を超えたアイディアだったので,一読した時は意味がわからず,再度読み返してやっと理解できた.

参考文献

[1] Yusuke Shibata, Takuya Kida, Shuichi Fukamachi, Masayuki Takeda, Ayumi Shinohara, Takeshi Shinohara, Setsuo Arikawa: Speeding Up Pattern Matching by Text Compression. CIAC 2000: 306-315