2013/05/19

LZ77によるテキスト圧縮

 ちょこちょこと改良を続けているTrie4Jでの話。

 LOUDSによるTrieが実装できたことで、木構造を保持するのに必要なメモリは大幅に削減されました。そうなると今度は、TAIL配列の大きさが気になってきます。最新のTailLOUDSTrieの各構成要素をファイルに書きだしてサイズをみてみると、こんな感じ。

サイズ(KB)説明
木構造(LOUDS)756.8Trie木構造をLOUDSで表現したもの
終端フラグ189.3木の各ノードが文字列の終端となるかどうかを表すフラグ
ラベル配列3,054.9木の各ノードに対応するラベル
TAILIndex配列6,053.9木の各ノードに対応する、TAIL配列へのインデックス
TAIL配列9,302.8全ノードのTAILを繋いだ文字列
合計19,329.6
※元データは2012年2月20日のWikipedia日本語タイトル(jawiki-20120220-all-titles-in-ns0.gz)。

 木は十分に小さくなり、ラベル配列以降の文字関連データで95%以上を占める状態になっています。その中でも一番容量を食っているTAIL配列をターゲットに、圧縮方法を考えます。(ちなみにTAILIndex配列は、完備辞書により大幅に圧縮することが可能で、既にTrie4Jで実装していますが、これはまたの機会に)

 いろいろと圧縮方法を調べてみると、少し前に買ってた書籍、「高速文字列解析の世界」 で解説されているLZ-Endという手法が良さそうです。
 LZ-Endは、その論文のタイトル「LZ77-like Compression with Fast Random Access」からもわかるように、LZ77をベースに、高速にランダムアクセス出来るよう拡張されたアルゴリズムです。少々複雑なので、まずはベースとなったLZ77を見てみます(LZ77も同書籍に説明があります)。

 LZ77では、文字列中の同じパターンを見つけ、より後に表れるものを過去のパターンを参照する情報に置き換えることで、圧縮を行います。具体的には、先頭から1文字ずつ見ていき、一致が無い場合は(-1, 0, 不一致文字)、あった場合は一致する文字数を調べて(先頭位置, 文字数, 不一致文字)を出力します(-1, 0の部分は、不一致を表す値であれば他のものでも構いません)。例えば

hello shallow

 という文字列があった場合の処理と出力結果は、以下のようになります。

処理
番号
処理内容出力
1'h'は以前に現れないので、一致しない。(-1, 0, 'h')
2'e'は以前に現れないので、一致しない。(-1, 0, 'e')
3'l'は以前に現れないので、一致しない。(-1, 0, 'l')
4'l'は元文字列の2番目に現れ、1文字だけ一致し、次の'o'は一致しない。(2, 1, 'o')
5' 'は以前に現れないので、一致しない。(-1, 0, ' ')
6's'は以前に現れないので、一致しない。(-1, 0, 's')
7'h'は元文字列の0番目現れ、1文字だけ一致し、次の'a'は一致しない。(0, 1, 'a')
8'l'は元文字列の2番目に現れ、さらに2文字一致し、次の'w'は一致しない。(2, 3, 'w')

 上記の処理番号と、元の文字列の対応は次の通り。処理によって圧縮された部分を赤字にしています。
12345678
helloshallow

 処理の結果、(位置, 文字数, 不一致文字)の3つ組は8個出力されたことになります。それぞれ2byteとしても、3*8*2で48byte、元の文字列は13文字で、1文字2byteとすると26byteです。これからわかるように、LZ77は同じパターンがある程度現れないと、効率よく圧縮できません。ただし長いテキストデータにはある程度同じパターンが出てくるものが多く、一定の圧縮効果は期待できます。

 また、大規模なテキストを考えると、一致を先頭から順に探していては、膨大な時間がかかってしまいます。そのため構築方法に工夫が必要ですが、一般的には
  • 一致を検索するために遡る文字数を制限する
  • 文字の出現位置をハッシュで保持する
 という方法がとられます。
 これらの対応を行い、上記TrieのTAIL配列(9.3MB)に対してLZ77を行なってみると、約85%に圧縮されました。但しTAIL配列は既に先頭一致で重複を省いた後の文字列なので、一般的にはもっと小さくなります。実際、Trieに格納する前のWikipedia日本語タイトル約1千万文字に対して適用すると、約70%になりました。
 コードは下記を参照して下さい。
 LZ77はシンプルながら強力なアルゴリズムで、その派生がたくさんあります。一般的に使われるのはLZSSという拡張のようで、これは常に3つ組を出力するのではなく、一致する場合は(true, 先頭位置, 文字数)、一致しない場合は(false, 不一致文字)を出力する事により、さらにムダを省くものとなっています。しかしこれもランダムアクセスが難しいため、Trie4JではLZSSをさらに拡張するか、LZ-Endを使うかのどちらかにしようと考えています。