JavaScript: 圧縮とかLZP(2)

過去記事の改良版もどきを紹介。過去版より大量の記憶空間を消費して圧縮率向上を目論むそうです。と言っても微々たるものですが…。

原理

今回は3文字によるhash表(TypedArray)に加え、4文字によるhash表(Map)を使い倒して広大な範囲を検索対象にします。
そこから得た位置を基準に次の文字列と一致する長さが一定以上あれば、一致成功と判定します。
最短一致長を大きめにすると、後段に他の圧縮programと組み合わせた時に圧縮率が良くなるかもです(BWT系等)

実装編

/*encode
@In: Array/Uint8Array
@x: match flag(0-255). larger than 255 means auto detect
@min: minmum match length(0-63)
@lv: parsing level.
	0: greedy(worst compression)
	1: lazy(almost best compression)
	2: flexible(sometimes best compression)
@return: Array
*/
function LZPo34enc(In,x,min,lv){
	var a=0,c,d,e,c3,i=In.length,l=1/0,n=i,o=2,p,z=i,Out=[min&=63],
		H3=new(z>>16?Uint32Array:z>>8?Uint16Array:Uint8Array)(1<<24),H4=new Map;
	Out[0]|=z>>24?128:z>>8&&64;
	for(min+=2;a<3&&a<n;)Out[o++]=In[a++];
	if(x>>>0>255){ // decide match flag
		for(;i--;)++H3[In[i]];
		for(x=0;i<255;H3[i]=0)if((c=H3[++i])<l)l=c,x=i
	}
	for(Out[1]=x&=255;a<z;){
		p=H3[c3=In[a-1]|In[a-2]<<8|In[a-3]<<16];//get by order3
		p=H4.get(i=c3|In[a-4]<<24)||p;//get by order4
		H4.set(i,H3[c3]=a),c=In[a];
		if(p){
			for(l=0;In[p++]===In[a+l];)l++;
			if(l>=min)lz:{
				if(lv>1){// flexible parsing
					c=l,e=0,i=min>l-24?min:l-24;
					do{
						p=H3[c3=In[d=c+a-1]|In[d-1]<<8|In[d-2]<<16];
						p=H4.get(c3|In[d-3]<<24)||p;
						for(n=0;In[p++]===In[++d];n++);
						if(n+c>e&&n>min||!e)e=n+c+1,l=c
					}while(c-->i)
				}else if(lv&&a+min<z){//lazy parsing
					p=H3[c3=In[d=a]|In[a-1]<<8|In[a-2]<<16];
					p=H4.get(c3|In[d-3]<<24)||p;
					for(n=0;In[p++]===In[++d];n++);
					if(l<n)break lz
				}
				a+=l,Out[o++]=x,l-=min-1;
				if(l<253)Out[o++]=l;
				else for(Out[o++]=c=(l-=253)<256?253:l<65792?254:255;Out[o++]=l&255,--c>252;)l=l-256>>8;
				continue
			}a++,Out[o++]=c;if(c===x)Out[o++]=0
		}else a++,Out[o++]=c
	}return Out
}
/*decode
@In: Array/Uint8Array
@return: Array
*/
function LZPo34dec(In){
	var a=2,b,c=In[0],c3,i,l,o=-1,p,x=In[1],min=(c&63)+1,z=In.length,Out=[],
		H3=new(c>>7?Uint32Array:c>>6?Uint16Array:Uint8Array)(1<<24),H4=new Map;
	for(;a<z&&o<2;)Out[++o]=In[a++];
	for(;a<z;){
		c=In[a++],p=H3[c3=Out[o]|Out[o-1]<<8|Out[o-2]<<16];
		p=H4.get(i=c3|Out[o-3]<<24)||p,H4.set(i,H3[c3]=o);
		if(!p||c-x||!(l=In[a++]))Out[++o]=c;//literal
		else{// copy
			if(l>252)for(c=l,b=0;l+=In[a++]<<b,--c>252;l+=(1<<b)-1)b+=8;
			for(l+=min;l--;)Out[++o]=Out[++p]
		}
	}return Out
}

test

let a=Array.from("Peter piper picked a peck of pickled peppers. A peck of pickled peppers Peter Piper picked. If Peter Piper picked a peck of pickled peppers, Where's the peck of pickled peppers Peter Piper picked",a=>a.charCodeAt()),
	c=LZPo34enc(a), d=LZPo34dec(c);

document.write(a.length,"->",c.length,"<hr>",d)