圧縮とかLZP改良2

LZP改良講座第2話をお送りします。前回は最長一致系列を複数のhash表から選定するという小細工を披露しました。今回はlinked listを辿ってお気に入りの最長一致系列を求めちゃいます。
LZ77系の高速化手法に似ていますが以下のような相違点があります。

• hash keyを直前の文字列から求める(LZ77は直後)
• 一致系列の精度は控えめ
• 一致位置との距離ではなくlinked listを辿った回数(探索回数)を出力

(2)の欠点を(3)の出力情報の少なさで補っています。

実装編

例によってJavaScript様で記述。Byte単位の処理となっています。一致flagで1 byte出力。直前何文字で予測するかは引数hsで指定。
LZPに選択幅を持たせるという意味でLZP+、関数名的にはLZPPとします。

/* LZPPenc(In,hs,bs,cs,done,rate)
@In: input(Array/Uint8Array)
@hs: hash size = 1<<~hs(0-2)*-8
@bs: ring buffer size = 1<<15+bs(0-15)
@cs: search times of longest match = 1<<1+cs(0-3)
@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: Promise object or compressed @A(Array) if call with await
*/
async function LZPPenc(In,hs,bs,cs,done=a=>a,rate=a=>a){
	let a=0,c=In.length,d=c,x=0,size=c,h,m=0,o=2,st=Date.now();
	const Out=[(hs&=3)<<2|(cs&=3)],
		H=new Uint32Array(hs=1<<++hs*8),
		cb=8-++cs, lm=(1<<cb)-3,
		fn=b=>setTimeout(c=>b(rate(a,size)));
	//buffer sizeが大き過ぎる場合は補正
	for(;size>>>m+15;)++m;
	bs&=15;if(bs>m)bs=m;
	//最低頻度の文字をmatch flagに選定
	for(Out[0]|=bs<<4;c;)H[In[--c]]++;
	for(;c<256;H[c++]=0)if(H[c]<d)d=H[x=c];

	const Link=new Uint32Array(bs=1<<bs+15);
	cs=1<<cs;bs--;hs--;
	for(Out[1]=x;a<size;a&8191||Date.now()-st<100||await new Promise(fn,st=Date.now())){
		//最長一致探索. 距離ではなく探索回数を記録
		//hash表を出発点にlinked listを辿る
		for(i=H[h],m=c=0;i&&c++<cs;i=Link[i&bs]){
			for(l=0;In[i+l]===In[a+l];)++l;
			if(l>m)m=l,d=c
		}
		if(m<3)x^(Out[o++]=In[a])||(Out[o++]=0),m=1;//literal出力. それがmatch flagの場合は0も出力
		else{
			Out[o++]=x;d=--d<<cb;l=m-2;
			if(l<lm)Out[o++]=d+l;
			else{//一致大
				Out[o++]=d+=c=(l-=lm)<256?lm:l<65792?lm+1:lm+2;
				for(;Out[o++]=l&255,c-->lm;)l=l-256>>8
			}
		}
		//hash表とlinked list更新
		for(;m--;h=h<<8&hs|In[H[h]=a++]) Link[a&bs]=H[h]
	}done(Out,size,o);
	return Out
}
async function LZPPdec(In,done=a=>a,rate=a=>a){
	let a=2,b,c=In[0],h,i,
		hs=1<<-8*~(c>>2&3), bs=1<<15+(c>>4), cs=c&3,o=0,st=Date.now();
	const Out=[], H=new Uint32Array(hs--), Link=new Uint32Array(bs--),
		cb=8-++cs, lm=(1<<cb)-4, x=In[1], size=In.length, fn=b=>setTimeout(c=>b(rate(a,size)));
	for(cs=(1<<cb)-1;a<size;a&8191||Date.now()-st<100||await new Promise(fn,st=Date.now()))
		if((c=In[a++])^x||!(l=In[a++]))
			Link[o&bs]=H[h], h=h<<8&hs|(Out[H[h]=o++]=c);//literal + update
		else{
			//linked list辿って位置求める
			for(i=H[h],c=l>>cb,l&=cs;c--;)i=Link[i&bs];
			if(l>lm)for(c=l,b=0;l+=In[a++]<<b,--c>lm;l+=(1<<b)-1)b+=8;
			//copy + update
			for(;l-->-2;h=h<<8&hs|(Out[H[h]=o++]=Out[i++]))
				Link[o&bs]=H[h]
		}
	done(Out,size,o);return Out
}

test

(async()=>{
let A=Array.from("He told me that that that that that boy said at that time is that that",a=>a.charCodeAt()),
	e=await LZPPenc(A,1,1,2),
	d=await LZPPdec(e);
document.write(A.length," to ",e.length,"<br>decoded<br>",String.fromCharCode(...d))
})()

hash表2個搭載

直前の2文字と3文字から次のbyte列を予測。引数は前述とほぼ同じなので説明省略。まあ圧縮処理に関してはhsが無いだけです(1と2に固定しているのと同じ)

async function LZPPenc2(In,bs,cs,done=a=>a,rate=a=>a){
	let a=0,c=In.length,d=c,mf=0,z=c,h,m=0,o=2,O=[cs=cs%5|0],m3=-1>>>8,m2=m3>>8,H2=new Uint32Array(1<<16),H3=new Uint32Array(1<<24),cb=8-++cs,lm=(1<<cb)-3,Link,fn=b=>setTimeout(c=>b(rate(a,z))),st=Date.now();
	for(bs&=15;z>>>m+15;)++m;
	if(bs>m)bs=m;
	for(O[0]|=bs<<4;c;)H2[In[--c]]++;
	for(Link=new Uint32Array(bs=1<<bs+15);c<256;H2[c++]=0)if(H2[c]<d)d=H2[mf=c];
	cs=1<<cs;bs--;
	for(O[1]=mf;a<z;a&8191||Date.now()-st<100||await new Promise(fn,st=Date.now())){
		for(i=H3[h&m3]||H2[h&m2],m=c=0;i&&c++<cs;i=Link[i&bs]){
			for(l=0;In[i+l]===In[a+l]&&a+l<z;)++l;
			if(l>m)m=l,d=c
		}
		if(m<3)mf^(O[o++]=In[a])||(O[o++]=0),m=1;
		else{
			O[o++]=mf;d=--d<<cb;l=m-2;
			if(l<lm)O[o++]=d+l;
			else for(O[o++]=d+=c=(l-=lm)<256?lm:l<65792?lm+1:lm+2;O[o++]=l&255,c-->lm;)l=l-256>>8;
		}
		for(;m--;h=h<<8|In[H2[h&m2]=H3[h&m3]=a++])
			Link[a&bs]=H3[h&m3]||H2[h&m2]
	}done(O,z,o);
	return O
}
async function LZPPdec2(In,done=a=>a,rate=a=>a){
	let a=2,b,c=In[0],i,mf=In[1],z=In.length,h,bs=1<<15+(c>>4),cs=c%5,cb=8-++cs,lm=(1<<cb)-4,m3=-1>>>8,m2=m3>>8,o=0,O=[],H2=new Uint32Array(1<<16),H3=new Uint32Array(1<<24),Link=new Uint32Array(bs--),fn=b=>setTimeout(c=>b(rate(a,z))),st=Date.now();
	for(cs=(1<<cb)-1;a<z;a&8191||Date.now()-st<100||await new Promise(fn,st=Date.now()))
		if((c=In[a++])^mf||!(l=In[a++]))Link[o&bs]=H3[h&m3]||H2[h&m2],h=h<<8|(O[H2[h&m2]=H3[h&m3]=o++]=c);
		else{
			c=l>>cb,l&=cs;
			for(i=H3[h&m3]||H2[h&m2];c--;)i=Link[i&bs];
			if(l>lm)for(c=l,b=0;l+=In[a++]<<b,--c>lm;l+=(1<<b)-1)b+=8;
			for(;l-->-2;h=h<<8|(O[H2[h&m2]=H3[h&m3]=o++]=O[i++]))
				Link[o&bs]=H3[h&m3]||H2[h&m2]
		}
	done(O,z,o);return O
}

test

(async()=>{
let A=Array.from("He told me that that that that that boy said at that time is that that",a=>a.charCodeAt()),
	e=await LZPPenc2(A,0,2),
	d=await LZPPdec2(e);
document.write(A.length," to ",e.length,"<br>decoded<br>",String.fromCharCode(...d))
})()

ROLZ

この手の戦略は圧縮界隈ではROLZ(Reduced offset LZ)と称しています。我が流派のLZPPとやらはへっぽこ系ROLZです。というのも圧縮率はもとより展開処理がへたくそ過ぎます(遅い)