LOUDSによるTrieが実装できたことで、木構造を保持するのに必要なメモリは大幅に削減されました。そうなると今度は、TAIL配列の大きさが気になってきます。最新のTailLOUDSTrieの各構成要素をファイルに書きだしてサイズをみてみると、こんな感じ。
| サイズ(KB) | 説明 | |
|---|---|---|
| 木構造(LOUDS) | 756.8 | Trie木構造をLOUDSで表現したもの |
| 終端フラグ | 189.3 | 木の各ノードが文字列の終端となるかどうかを表すフラグ |
| ラベル配列 | 3,054.9 | 木の各ノードに対応するラベル |
| TAILIndex配列 | 6,053.9 | 木の各ノードに対応する、TAIL配列へのインデックス |
| TAIL配列 | 9,302.8 | 全ノードのTAILを繋いだ文字列 |
| 合計 | 19,329.6 |
木は十分に小さくなり、ラベル配列以降の文字関連データで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') |
上記の処理番号と、元の文字列の対応は次の通り。処理によって圧縮された部分を赤字にしています。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| h | e | l | lo | s | ha | llow |
処理の結果、(位置, 文字数, 不一致文字)の3つ組は8個出力されたことになります。それぞれ2byteとしても、3*8*2で48byte、元の文字列は13文字で、1文字2byteとすると26byteです。これからわかるように、LZ77は同じパターンがある程度現れないと、効率よく圧縮できません。ただし長いテキストデータにはある程度同じパターンが出てくるものが多く、一定の圧縮効果は期待できます。
また、大規模なテキストを考えると、一致を先頭から順に探していては、膨大な時間がかかってしまいます。そのため構築方法に工夫が必要ですが、一般的には
- 一致を検索するために遡る文字数を制限する
- 文字の出現位置をハッシュで保持する
これらの対応を行い、上記TrieのTAIL配列(9.3MB)に対してLZ77を行なってみると、約85%に圧縮されました。但しTAIL配列は既に先頭一致で重複を省いた後の文字列なので、一般的にはもっと小さくなります。実際、Trieに格納する前のWikipedia日本語タイトル約1千万文字に対して適用すると、約70%になりました。
コードは下記を参照して下さい。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.io.IOException; | |
| import java.util.HashMap; | |
| import java.util.Iterator; | |
| import java.util.LinkedList; | |
| import java.util.List; | |
| import java.util.Map; | |
| public class LZ77 { | |
| public static void compress1(CharSequence src, Appendable out, int windowSize) | |
| throws IOException{ | |
| int n = src.length(); | |
| for(int i = 0; i < n; i++){ | |
| char target = src.charAt(i); | |
| // find longest match | |
| boolean found = false; | |
| int start = 0; | |
| int matchLen = 0; | |
| char nonMatchChar = 0xff; | |
| for(int s = Math.max(0, i - windowSize); s < i; s++){ | |
| if(target == src.charAt(s)){ | |
| int len = getMatchedLen(src, s + 1, i + 1, n) + 1; | |
| if(len > matchLen){ | |
| start = i - s; | |
| matchLen = len; | |
| nonMatchChar = (char)0xff; | |
| if((i + matchLen) < n){ | |
| nonMatchChar = src.charAt(i + matchLen); | |
| } | |
| } | |
| found = true; | |
| } | |
| } | |
| if(found){ | |
| out.append((char)start) | |
| .append((char)matchLen) | |
| .append(nonMatchChar); | |
| i += matchLen; | |
| } else{ | |
| out.append((char)0x00).append((char)0x00).append(target); | |
| } | |
| } | |
| } | |
| public static void compress2(CharSequence src, Appendable out, int windowSize) | |
| throws IOException{ | |
| Map<Character, List<Integer>> startPoss = new HashMap<Character, List<Integer>>(); | |
| int n = src.length(); | |
| for(int i = 0; i < n; i++){ | |
| char target = src.charAt(i); | |
| // find longest match | |
| boolean found = false; | |
| int start = 0; | |
| int matchLen = 0; | |
| char nonMatchChar = 0xff; | |
| List<Integer> poss = startPoss.get(target); | |
| if(poss != null){ | |
| Iterator<Integer> it = poss.iterator(); | |
| while(it.hasNext()){ | |
| int s = it.next(); | |
| if((i - s) > windowSize){ | |
| it.remove(); | |
| continue; | |
| } | |
| int len = getMatchedLen(src, s + 1, i + 1, n) + 1; | |
| if(len > matchLen){ | |
| start = i - s; | |
| matchLen = len; | |
| nonMatchChar = (char)0xff; | |
| if((i + matchLen) < n){ | |
| nonMatchChar = src.charAt(i + matchLen); | |
| } | |
| } | |
| found = true; | |
| } | |
| poss.add(i); | |
| int jn = Math.min(i + matchLen + 1, n); | |
| for(int j = i + 1; j < jn; j++){ | |
| List<Integer> p = startPoss.get(src.charAt(j)); | |
| if(p == null){ | |
| p = new LinkedList<Integer>(); | |
| startPoss.put(src.charAt(j), p); | |
| } | |
| p.add(j); | |
| } | |
| } else{ | |
| poss = new LinkedList<Integer>(); | |
| poss.add(i); | |
| startPoss.put(target, poss); | |
| } | |
| if(found){ | |
| out.append((char)start) | |
| .append((char)matchLen) | |
| .append(nonMatchChar); | |
| i += matchLen; | |
| } else{ | |
| out.append((char)0x00).append((char)0x00).append(target); | |
| } | |
| } | |
| } | |
| private static int getMatchedLen(CharSequence src, int i1, int i2, int end){ | |
| int n = Math.min(i2 - i1, end - i2); | |
| for(int i = 0; i < n; i++){ | |
| if(src.charAt(i1++) != src.charAt(i2++)) return i; | |
| } | |
| return 0; | |
| } | |
| public static void decompress(CharSequence src, StringBuilder out){ | |
| int n = src.length(); | |
| for(int i = 0; i < n; i += 3){ | |
| int start = src.charAt(i); | |
| int matchedLen = src.charAt(i + 1); | |
| char nonMatchChar = src.charAt(i + 2); | |
| if(start != 0){ | |
| int s = out.length() - start; | |
| int e = s + matchedLen; | |
| for(; s < e; s++){ | |
| out.append(out.charAt(s)); | |
| } | |
| } | |
| if(nonMatchChar != 0xff){ | |
| out.append(nonMatchChar); | |
| } | |
| } | |
| } | |
| } |
LZ77はシンプルながら強力なアルゴリズムで、その派生がたくさんあります。一般的に使われるのはLZSSという拡張のようで、これは常に3つ組を出力するのではなく、一致する場合は(true, 先頭位置, 文字数)、一致しない場合は(false, 不一致文字)を出力する事により、さらにムダを省くものとなっています。しかしこれもランダムアクセスが難しいため、Trie4JではLZSSをさらに拡張するか、LZ-Endを使うかのどちらかにしようと考えています。
