LZ77によるテキスト圧縮

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

　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

※元データは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')

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

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%になりました。
　コードは下記を参照して下さい。

	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);
	}
	}
	}
	}

view raw LZ77.java hosted with ❤ by GitHub

　LZ77はシンプルながら強力なアルゴリズムで、その派生がたくさんあります。一般的に使われるのはLZSSという拡張のようで、これは常に3つ組を出力するのではなく、一致する場合は(true, 先頭位置, 文字数)、一致しない場合は(false, 不一致文字)を出力する事により、さらにムダを省くものとなっています。しかしこれもランダムアクセスが難しいため、Trie4JではLZSSをさらに拡張するか、LZ-Endを使うかのどちらかにしようと考えています。