導入
最近、応用情報の勉強を始めたため、アウトプットとして自分なりの理解をまとめて投稿しています。誤りなどがあればご指摘いただけると助かります。この記事で4本目です。
１．Re-pair
Re-pairは最頻出の2-gram(隣接する2文字)を新しい１文字の記号に置換する圧縮であり、文法圧縮の１種である。文法圧縮とは文脈自由文法によって生成された文字列の圧縮である。
Re-pairの特徴
- 可逆圧縮：圧縮データから元のデータに一意に復元可能
- 文法圧縮：文脈自由文法によって生成された文字列の圧縮
- トレードオフ：記憶メモリと実行時間が依存関係にある
Re-pairの流れ
- 文字列中の最頻出の2-gramを1文字に置換し、文字列を更新する
- 文字列中のすべての2-gramの出現頻度＝１になるまで１の操作を続ける
- 置換後の文字列と置換した文字列の文脈自由文法を出力する
Re-pairの例
T = ababaababbについてRe-pairを行う。
- 入力：T = ababaababb
- 出力：T = yayb, D = [x→ab,y→xx]
2．高速なRe-pair
Re-pairは記憶メモリと実行時間がトレードオフの関係である。文字列をブロックに分け、ブロックごとにRe-pairを行うことでより実行時間を短縮することができる。
高速なRe-pairの特徴
- 可逆圧縮：圧縮データから元のデータに一意に復元可能
- 文法圧縮：文脈自由文法によって生成された文字列の圧縮
- トレードオフ：記憶メモリと実行時間が依存関係
- 通常のRe-pairに比べて実行が高速であるが、圧縮率が悪い
※ブロック分割することで、文字列全体の最頻出を見逃すことや、ブロックごとに似たような辞書の生成が起こるため、圧縮率が悪化する。
高速なRe-pairの流れ
- 文字列をブロックに分ける
- 全てのブロックに対してRe-pairを行う
- ブロックごとの圧縮後の文字列と生成規則を出力する
高速なRe-pairの例
T = ababaababbについてブロック分割によるRe-pairを行う。今回は１ブロックを５バイトとする。
※今回は、最頻度が等しいものは文字列上で先に出てきたものを置換している
- 入力：T = ababaababb
- 出力：T1 = xxa, D1 = [x → ab], T2 = xxb, D2 = [x → ab]
まとめ
- Re-pairは最頻出の2-gramを１文字に置換する圧縮である
- 高速なRe-pairはブロックごとにRe-pairを行うことで実行時間を短くする
- Re-pairは、可逆圧縮・文法圧縮である
次回は、BWTについてまとめたいと思う。
参考
以下のサイトが分かりやすく、参考にさせていただきました。
https://en.wikipedia.org/wiki/Re-Pair