圧縮とかLZPの改良法

LZPは辞書式圧縮の一種で「直前の文脈を使って次のbyte列を予測し、予測が当たった場合は一致長だけを出力する」という方式です。LZ77の変種に近いですが、位置を出力しない点が特徴です。

本題

今回はLZPの圧縮率を向上させる方法を紹介します。方法は至って簡単で、文脈と位置を格納する配列(hash表)を複数用意し、別々に最長一致を求めます。そして最も長く一致させる事に成功したhash表を選択します。
そんな事をすると余計な情報を出力する羽目になりそうですが、byte単位のLZPならそうでもありません。出力する一致長の中に選択したhash表の情報も詰め込むのです。
例えばhash表を4個使う場合、一致長の上位2bitに0～3を格納し、下位6bitに一致長自体を格納。一致長が6bitに収まらなかった場合は1 byte以上余計に出力。

他にも一致flagに割り当てる記号を複数用意するという手もあります。文書fileだとその方が良いかもしれません

実装編

これは4つのhash表を気まぐれに選択する方式(hash[key]がfalsyな候補を除外)。直前の1、2、4、8文字から次のbyte列を予測(長い文脈優先)。昔ながらのLZPですが、やや高度です。

/*
usage:
LZPo1248encode(A,x,ml,lv,done):compressor
@A: input
@x: match flag. 0-255 means its value. 256 means fewest symbol.
@ml: minimum match length is ml(0-127)+2
@lv: parser. 0=greedy, 1=lazy, 2=flexible
@done: call back of last process.
	done(A,a,z)
	@A: compressed array of input.
	@a: input size
	@z: compressed size
@rate: call back of progress
	rate(a,z)
	@a: current position
	@z: last position
@return: Array/
*/
async function LZPo1248encode(A,x,ml,lv,done,rate){
	var T=new Uint32Array(256),T2=new Uint32Array(65536),T4=new Map,T8=new Map,a=0,z=A.length,c,c2,c4,c8,e,l=z,o=2,p,r=z,t,O=[ml&=127],fn=b=>wait0(c=>b(rate(a,z))),st;
	//最低頻度の文字を一致flagに選定
	if((x|=0)<0||x>255){
		for(;r--;)++T[A[r]];
		for(x=0;r<255;T[r]=0)if((c=T[++r])<l)l=c,x=r
	}
	for(O[1]=x&=255;a<z&&a<8;)O[o++]=A[a++];
	for(st=Date.now(ml+=2);a<z;a&8191||Date.now()-st<200||await new Promise(fn,st=Date.now())){
		//直前数文字をkeyとしてhash表から位置を求める
		t=T[c=A[a-1]],
		t=T2[c2=A[a-2]|c<<8]||t;
		c4=A[a-4]|A[a-3]<<8|c2<<16;
		c8=A[a-8]|A[a-7]<<8|A[a-6]<<16|A[a-5]<<24;
		t=T4.get(c4^=c4>>>12^c4<<11^c4>>>20^c4<<3)||t;
		t=T8.get(c8^=c8>>>11^c8<<12^c8>>>19^c8<<4^c4)||t;
		//hash表更新
		T8.set(c8,a),T4.set(c4,T2[c2]=T[c]=a);
		//最長一致求める
		for(l=0;A[t++]===A[a+l];)l++;
		if(l>=ml)lz:{
			if(lv>1){//数byte先読みして今L文字取るか少し短く取って次で伸ばすか選択
				c=l,e=0,p=ml>l-24?ml:l-24;
				do{
					t=T[c2=A[r=c+a-1]],
					t=T2[c2=A[r-1]|c2<<8]||t;
					c4=A[r-3]|A[r-2]<<8|c2<<16;
					c8=A[r-7]|A[r-6]<<8|A[r-5]<<16|A[r-4]<<24;
					t=T4.get(c4^=c4>>>12^c4<<11^c4>>>20^c4<<3)||t;
					t=T8.get(c8^c8>>>11^c8<<12^c8>>>19^c8<<4^c4)||t;
					for(n=0;A[t++]==A[++r];)n++;
					if(n+c>e&&n>ml||!e)l=c,e=n+c+1
				}while(c-->p)
			}else if(lv){//1 byte先読みして最長一致探索
				t=T[c=A[r=a]],
				t=T2[c=A[a-1]|c<<8]||t;
				c=A[a-3]|A[a-2]<<8|c<<16;
				c2=A[a-7]|A[a-6]<<8|A[a-5]<<16|A[a-4]<<24;
				t=T4.get(c^=c>>>12^c<<11^c>>>20^c<<3)||t;
				t=T8.get(c2^=c2>>>11^c2<<12^c2>>>19^c2<<4^c)||t;
				for(;A[t++]===A[++r];);r+=~a;
				if(l<r)break lz//長い一致が見つかったので保留
			}
			//一致長を出力
			O[o++]=x;a+=l;l-=ml-1;
			if(l<253)O[o++]=l;
			else for(O[o++]=c=(l-=253)<256?253:l<65792?254:255;O[o++]=l&255,--c>252;)l=l-256>>8;
			continue
		}if((O[o++]=A[a++])===x)O[o++]=0//記号出力。match flagと同じなら0も出力
	}return done(O,z,o),O
}
/*
LZPo1248decode(A,done,rate):decompressor
@A: input (Array/Uint8Array)
@done: call back of last process.
	done(A,a,z)
	@A: decompressed array of input.
	@a: input size
	@z: decompressed size
@rate: call back of progress
	rate(a,z)
	@a: current position
	@z: last position
@return: Array/
*/
async function LZPo1248decode(A,done,rate){
	var T=new Uint32Array(256),T2=new Uint32Array(65536),T4=new Map,T8=new Map,a=2,b,c,c2,c4,c8,i,l,o=-1,p,s,ml=A[0]+1,x=A[1],z=A.length,O=[],fn=b=>wait0(c=>b(rate(a,z))),st=Date.now();
	for(;a<z&&a<8;)O[++o]=A[a++];
	for(;a<z;a&8191||Date.now()-st<200||await new Promise(fn,st=Date.now())){
		s=A[a++],c=O[p=o],c2=O[o-1]|c<<8;
		c4=O[o-3]|O[o-2]<<8|c2<<16;
		c8=O[o-7]|O[o-6]<<8|O[o-5]<<16|O[o-4]<<24;
		c4^=c4>>>12^c4<<11^c4>>>20^c4<<3;
		c8^=c8>>>11^c8<<12^c8>>>19^c8<<4^c4;
		if(s^x||!(l=A[a++]))O[++o]=s;
		else{
			if(l>252)
				for(b=l,s=0;l+=A[a++]<<s,--b>252;l+=(1<<s)-1)s+=8;//long match
			i=T8.get(c8)||T4.get(c4)||T2[c2]||T[c];//position
			for(l+=ml;l--;)O[++o]=O[++i]//copy
		}T8.set(c8,p),T4.set(c4,T2[c2]=T[c]=p)//update table
	}return done(O,z,++o),O
}

改良編

ここからが本番。引数とかの説明は上記と被るので省略。

async function LZPo1248encode2(A,x,ml,lv,done,rate){
	var T=new Uint32Array(256),T2=new Uint32Array(65536),T4=new Map,T8=new Map,a=0,z=A.length,c,c2,c4,c8,e,f,l=z,n,o=2,p,r=z,s,t,t2,t4,t8,O=[ml&=127],fn=b=>wait0(c=>b(rate(a,z))),st;
	if((x|=0)<0||x>255){
		for(;r--;)++T[A[r]];
		for(x=0;r<255;T[r]=0)if((c=T[++r])<l)l=c,x=r
	}
	for(O[1]=x&=255;a<z&&a<8;)O[o++]=A[a++];
	for(st=Date.now(ml+=2);a<z;a&8191||Date.now()-st<200||await new Promise(fn,st=Date.now())){
		t=T[c=A[a-1]],
		t2=T2[c2=A[a-2]|c<<8];
		c4=A[a-4]|A[a-3]<<8|c2<<16;
		c8=A[a-8]|A[a-7]<<8|A[a-6]<<16|A[a-5]<<24;
		t4=T4.get(c4^=c4>>>12^c4<<11^c4>>>20^c4<<3);
		t8=T8.get(c8^=c8>>>11^c8<<12^c8>>>19^c8<<4^c4);
		T8.set(c8,a),T4.set(c4,T2[c2]=T[c]=a);

		for(f=l=0;A[t++]===A[a+l];)l++;//order1の最長一致
		if(t2&&t^t2){for(n=0;A[t2++]===A[a+n];)n++;if(n>l)l=n,f=1}//order2の最長一致
		if(t4&&t4^t2){for(n=0;A[t4++]===A[a+n];)n++;if(n>l)l=n,f=2}//order4の最長一致
		if(t8&&t4^t8){for(n=0;A[t8++]===A[a+n];)n++;if(n>l)l=n,f=3}//order8の最長一致

		if(l>=ml)lz:{
			if(lv>1){//数byte先読み
				c=l,e=0,p=ml>l-24?ml:l-24;
				do{
					t=T[c2=A[r=s=c+a-1]],
					t2=T2[c2=A[r-1]|c2<<8];
					c4=A[r-3]|A[r-2]<<8|c2<<16;
					c8=A[r-7]|A[r-6]<<8|A[r-5]<<16|A[r-4]<<24;
					t4=T4.get(c4^=c4>>>12^c4<<11^c4>>>20^c4<<3);
					t8=T8.get(c8^c8>>>11^c8<<12^c8>>>19^c8<<4^c4);

					for(n=0;A[t++]===A[++r];)n++;
					if(t2&&t^t2){for(r=s;A[t2++]===A[++r];);r+=~s;if(r>n)n=r}
					if(t4&&t4^t2){for(r=s;A[t4++]===A[++r];);r+=~s;if(r>n)n=r}
					if(t8&&t4^t8){for(r=s;A[t8++]===A[++r];);r+=~s;if(r>n)n=r}
					if(n+c>e&&n>ml||!e)l=c,e=n+c+1
				}while(c-->p)
			}else if(lv){//1 byte先読み
				t=T[c=A[r=a]],
				t2=T2[c=A[a-1]|c<<8];
				c=A[a-3]|A[a-2]<<8|c<<16;
				c2=A[a-7]|A[a-6]<<8|A[a-5]<<16|A[a-4]<<24;
				t4=T4.get(c^=c>>>12^c<<11^c>>>20^c<<3);
				t8=T8.get(c2^=c2>>>11^c2<<12^c2>>>19^c2<<4^c);

				for(;A[t++]===A[++r];);r+=~a;
				if(t2&&t^t2){for(n=a;A[t2++]===A[++n];);n+=~a;if(n>r)r=n}
				if(t4&&t4^t2){for(n=a;A[t4++]===A[++n];);n+=~a;if(n>r)r=n}
				if(t8&&t4^t8){for(n=a;A[t8++]===A[++n];);n+=~a;if(n>r)r=n}
				if(l<r)break lz
			}
			O[o++]=x;a+=l;l-=ml-1;f*=64;
			if(l<61)O[o++]=l+f;
			else for(O[o++]=f+=c=(l-=61)<256?61:l<65792?62:63;O[o++]=l&255,--c>60;)l=l-256>>8;
			continue
		}if((O[o++]=A[a++])===x)O[o++]=0
	}return done(O,z,o),O
}
//decode
async function LZPo1248decode2(A,done,rate){
	var T=new Uint32Array(256),T2=new Uint32Array(65536),T4=new Map,T8=new Map,a=2,b,c,d,c2,c4,c8,i,l,o=-1,p,s,ml=A[0]+1,x=A[1],z=A.length,O=[],fn=b=>wait0(c=>b(rate(a,z))),st=Date.now();
	for(;a<z&&a<8;)O[++o]=A[a++];
	for(;a<z;a&8191||Date.now()-st<200||await new Promise(fn,st=Date.now())){
		s=A[a++],c=O[p=o],c2=O[o-1]|c<<8;
		c4=O[o-3]|O[o-2]<<8|c2<<16;
		c8=O[o-7]|O[o-6]<<8|O[o-5]<<16|O[o-4]<<24;
		c4^=c4>>>12^c4<<11^c4>>>20^c4<<3;
		c8^=c8>>>11^c8<<12^c8>>>19^c8<<4^c4;
		if(s^x||!(l=b=A[a++]))O[++o]=s;
		else{
			if((d=l&=63)>60)
				for(s=0;l+=A[a++]<<s,--d>60;l+=(1<<s)-1)s+=8;//long match
			i=b>191?T8.get(c8):b>127?T4.get(c4):b>63?T2[c2]:T[c];//position
			for(l+=ml;l--;)O[++o]=O[++i]//copy
		}T8.set(c8,p),T4.set(c4,T2[c2]=T[c]=p)//update table
	}return done(O,z,++o),O
}

LZP系列の出力は match flag(8bit) + context(2bit) + length(6bit) で詳細は以下の通り。

• mf+[00]: mf自体を表す
• mf+[01-3f]: order1
• mf+[41-7f]: order2
• mf+[81-bf]: order4
• mf+[c1-ff]: order8

mf+[40]、mf+[80]、mf+[C0]、は未使用符号

benchmark

canterbury(12 file)に対する圧縮測定

file	従来版	改良版
alice29.txt	113083	108071
asyoulik.txt	101290	97047
cp.html	13462	13076
fields.c	5787	5540
grammar.lsp	2076	2003
kennedy.xls	444136	435384
lcet10.txt	288472	272589
plrabn12.txt	409486	392892
ptt5	91798	86592
sum	21480	20668
xargs.1	2979	2947
total	1494059	1436809

参考文献

1話目
2話目