JavaScript: ブンポー圧縮

今回は文法圧縮の記事となります。より正確にはRePairと呼ばれる有名な手法の改良版の紹介です。本家はこの辺にあります。

本家の問題点

圧縮、伸長ともに再帰関数を利用しており、容易にstack overflow(segmentation fault)を起こす事が知られています。
ついでにその再帰の最も深い所で、不要な1 bitの符号化が毎回発生しており、圧縮率の低下を招いています。不要と言えば、まれに不要なpairingも発生します。
そしてもう1つ、単純にbit列を書き込んでいるだけなので、工夫すれば圧縮率はまだまだ良くなるという事。

実装

圧縮率を高めるためにCBT符号を利用します。例によってcompressが圧縮関数、decompressが伸長関数。compressの引数cutは0～3の数値を指定。大きい程計算量が増えます。速度が犠牲になりますが、僅かに圧縮率が上がる可能性があります。

{const primes=function(a,b){for(;b;)a[--b]+=8<<b;return a}(new Uint32Array([3,3,5,3,3,27,9,9,5,3,27,43,3,45,29,3,21,7,17,15,9,43,35,15,29,3,11,85]),28),
findPair=(H,l,r)=>{
	for(var p=H[~l*~r%H.length];p;p=p.link)
		if(p.left===l&&p.right===r)return p
},
reHash=(H,Q)=>{
	var h,i=H.length=0,p,n=H.length=primes[++H.hN];
	do for(p=Q[++i<Q.max?i:i=0];p;p=p.next)
		p.link=H[h=~p.left*~p.right%n],H[h]=p;
	while(i)
},
insertPairPQ=(Q,w,n,t)=>{
	t=Q[n<Q.max?n:n=0];Q[n]=w;w.prev=0;
	if(w.next=t)t.prev=w
},
cutPairPQ=(Q,w,n)=>{
	if(w.prev){
		if(w.prev.next=w.next)w.next.prev=w.prev;return}
	if(Q[n<Q.max?n:0]=w.next)w.next.prev=0
},
killPair=(H,Q,w)=>{
	var h=~w.left*~w.right%H.length,p=H[h],q;
	for(cutPairPQ(Q,w,w.hit);p.left-w.left||p.right-w.right;p=p.link)q=p;
	q?q.link=p.link:H[h]=p.link;
	Q.pairs--
},
hitUp=(Q,w)=>{
	if(w.hit>=Q.max)return++w.hit;
	cutPairPQ(Q,w,w.hit);
	insertPairPQ(Q,w,++w.hit)
},
hitDown=(H,Q,w)=>{
	if(w.hit>Q.max)return--w.hit;
	if(w.hit<2)return killPair(H,Q,w);
	cutPairPQ(Q,w,w.hit);
	insertPairPQ(Q,w,--w.hit)
},
makePair=(H,Q,l,r,p)=>{
	++Q.pairs<H.length||reHash(H,Q);
	insertPairPQ(Q,r={left:l,right:r,hit:1,top:p,pos:p,link:H[p=~l*~r%H.length]},1);
	return H[p]=r
},
resetPQ=(H,Q,n,p)=>{
	for(p=Q[n],Q[n]=0;n=p;)
		p=n.next,killPair(H,Q,n)
},
initRDS=(H,Q,C,P,N,cut)=>{
	for(var i=0,j,l=C.size-1,a,b,c=-1,pair;i<l;i++,c=a)
		if(pair=findPair(H,a=C[i],b=C[i+1]))
			N[P[i]=pair.pos]=pair.pos=i,
			cut&&a===b&&a===c&&i-1===j||hitUp(Q,pair,j=i);
		else makePair(H,Q,a,b,j=i);
	resetPQ(H,Q,1)
},
getMaxPair=Q=>{
	var p=Q[0],mp,m=0;
	if(p){do if(m<p.hit)m=p.hit,mp=p;while(p=p.next)}
	else{for(p=Q.i||Q.max-1;p>1&&!(mp=Q[p]);)p--;Q.i=p}
	return mp
},
cutLinkSQ=(P,N,p,u,n)=>{n=N[p];p=P[p];p<u?n<u?P[N[p]=n]=p:N[p]=u:n<u&&(P[n]=u)},

updateBlockSQ=(H,Q,C,P,N,n,i,skip)=>{
	var l=C.size,p=i,lc=p,u=-1>>>0,np=N[p],
		lp=lc?C[--lc]>-1?lc:N[lc]:u,
		rp=++p<l?C[p]>-1?p:P[p]:u,
		rp2=++rp<l?C[rp]>-1?rp:P[rp]:u,
		r=C[--rp];
	np-rp||(np=N[np]);
	if(lp<u)a:{
		cutLinkSQ(P,N,lp,u);if(skip)break a;
		if(p=findPair(H,lc=C[lp],C[i]))
			p.top-lp||(p.top=N[lp]),hitDown(H,Q,p);
		if(p=findPair(H,lc,n))N[N[P[lp]=p.pos]=p.pos=lp]=u,hitUp(Q,p);
		else P[lp]=N[lp]=u,makePair(H,Q,lc,n,lp)}
	cutLinkSQ(P,N,i,u);
	cutLinkSQ(P,N,rp,u);
	if(skip)return;
	C[i]=n,C[rp]=-1;
	if(rp2<u){
		if(p=findPair(H,r,r=C[P[i+1]=rp2]))p.top-rp||(p.top=N[rp]),hitDown(H,Q,p);
		if(i^rp2-2)N[i+1]=P[rp2-1]=u,N[rp2-1]=i;
		else N[i+1]=i;
		if(np>rp2)
			if(p=findPair(H,n,r))N[N[P[i]=p.pos]=p.pos=i]=u,hitUp(Q,p);
			else P[i]=N[i]=u,makePair(H,Q,n,r,i);
		else N[i]=P[i]=u}
	else if(++i<l)
		N[i]=i-1,P[i]=P[rp]=N[rp]=u
},
replace=(H,Q,C,P,N,m,n)=>{
	for(var c=0,h=m.hit,i=m.top,j,l=C.size,o=(C.up&3)+1,p,r=0,u=-1>>>0;i<u;i=j){
		j=N[p=i];i+o>j&&c++;
		if(j===(++p<l?C[p]>-1?p:P[p]:u))j=N[j];
		updateBlockSQ(H,Q,C,P,N,n,i,!r++&&j===u)}
	if((o<2?r^h:c)&&r>2){ // recompute pair count
		for(i=j=H.length=Q.length=0,p=C.size;i<p;)C[i]>-1?C[P[j]=N[j]=u,j++]=C[i++]:i=P[i];
		H.length=primes[H.hN];Q.max=0|Math.sqrt(C.size=j)+1;
		initRDS(H,Q,C,P,N,1)
	}else m.hit^1&&killPair(H,Q,m),resetPQ(H,Q,1);
	return r>1?r:0
};
function l2b(a,b,c){
	c=(65535<a)<<4,c|=b=(255<(a>>>=c))<<3,c|=b=(15<(a>>=b))<<2;return(c|=b=(3<(a>>=b))<<1)|a>>b>>1
}
this.Pairing=async(A,cut,as,rate)=>{
	var a=A.length,n=-1>>>0,z=a,C=new Int32Array(a),P=new Uint32Array(a),N=new Uint32Array(a),H=[],Q=[],L=C.L=[],R=C.R=[],U=C.U=new Uint8Array(as=as>>>0||256),T=new(as>256?Uint16Array:Uint8Array)(as),r=Q.pairs=H[primes[H.hN=15]-1]=0;
	if(!a)return C;
	for(Q.max=0|Math.sqrt(C.size=a)+1;a--;N[a]=P[a]=n)U[A[a]]=1;
	for(;++a<as;)U[a]&&(T[a]=L[r]=r++);
	for(a=0,as=r;a<z;)C[a]=T[A[a++]];
	initRDS(H,Q,C,P,N,C.up=cut&3);
	T=r=>setTimeout(a=>r(rate(z-n,z)),0);
	//shrink
	for(n=z,A=+new Date;m=getMaxPair(Q);(m>n*.01||!(r&31)&&Date.now()-A>200)&&await new Promise(T,A=+new Date))
		L[r]=m.left,R[r]=m.right,n-=m=replace(H,Q,C,P,N,m,r),m&&r++;
	for(C.cs=a=as,C.rs=r,C.n=n,C.T=T=[];T[--a]=a;);
	if(cut&4){for(a=n=0,r=C.size;n<r;)~C[n]?C[a++]=C[n++]:n=P[n];C.size=a}//remove empty cell
	else C.P=P;
	return C
}}
//// main ////
/*compress
@In: input(Array / Uint8Array)
@cut:
	if cut>0, pair count is correct in first pass
	if cut>1, recompute pair count in update block
@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:
	call with await: compressed array of @In
	without await: Promise object
*/
async function compress(In,cut,done,rate){
	function puts(n,l){//bit writer
		if(bits>l)return data|=n<<(bits-=l);
		bits=32-(l-=bits);
		Out[o++]=(data|=n>>l)>>>24;Out[o++]=data>>16&255;
		Out[o++]=data>>8&255;Out[o++]=data&255;
		if(bits<32)return data=n<<bits;data=0
	}
	function encodeCFG(L,R,c){
		for(var e=0,s=0,m,n,S=[];;c=S[--s])
			if(c<0){// add new rule
				puts(0,1);T[~c]=nc++;
				if(!s)return
			}else if(T[c]>-1){// known symbol/rule
				for(c=T[c];nc>>nl;)nl++;
				//CBT coding
				if(c<(n=(1<<nl)-nc))m=nl-1;
				else m=nl,c+=n;
				puts(e<<m|c,m+e);e=1;
				if(!s)return
			}else S[s++]=~c,S[s++]=R[c],S[s++]=L[c]// unknown rule
	}
	var c,d,e,bits=32,data,l=0,m,size=In.length,nl=0,n,o=0;
	if(!size){
		In=[0,0,0];done&&done(In,size,3);
		return In
	}
	var Out=[],Code=await Pairing(In,cut,256,rate),
		P=Code.P,Left=Code.L,Right=Code.R,T=Code.T,U=Code.U,nc=Code.cs;

	// write symbols by RLE+gamma code
	for(puts(U[0],1);n=l<256;puts(n,c)){
		for(m=U[l],d=l2b(256-l);m==U[++l]&&l<256;n++);
		c=e=l2b(m=+n);c<d||(n^=1<<c--);c-=m<256?~e:-1
	}
	for(m=0,l=Code.n;l>>++m;);
	puts(m,5);puts(l^1<<--m,m);// write size
	//encoding loop
	for(n=0,l=Code.size;n<l;)
		if(~Code[n])encodeCFG(Left,Right,Code[n++]),puts(e=0,1);
		else n=P[n];
	if(bits<32)for(;data;data<<=8)Out[o++]=data>>>24;

	if(o>size){// incompressible
		for(m=n=o=data=Out.length=0,bits=32;size>>++m;);
		for(puts(m,14),puts(size^1<<--m,m);n<size;)puts(In[n++],8)
		if(bits<32)for(;data;data<<=8)Out[o++]=data>>>24
	}
	done&&done(Out,size,o);
	return Out
}
/*decompress
@In: input(Array / Uint8Array)
@done: call back of last process
	done(A,a,z)
	@A: decompressed array of @In
	@a: last position
	@z: decompressed size
@return: decompressed array of @In
*/
function decompress(In,done){
	function gets(l,n){//bit reader
		n=B>>>32-l;
		if(l<b){if(!l)return 0;B<<=l;b-=l;return n}
		l-=b;b=32-l;
		B=In[a++]<<24|In[a++]<<16|In[a++]<<8|In[a++];
		if(l)n|=B>>>b,B<<=l;
		return n
	}
	var a=0,b=0,c,d=256,e=0,B,l=gets(1),m,n=0,o=0,p=0,r,s,size=In.length,
		Out=[],Left=[],Right=[],Stack=[],Pair=[],T=[];
	//read symbols
	for(;e<d;l^=1){
		for(r=0,c=l2b(d-e);r<c&&!gets(1);)r++;
		for(r=r<8?1<<r|gets(r):d;r--;e++)if(l)T[n++]=e}
	if(!size)return done(Out,size,o);
	//read loop counter
	r=gets(5);r=r&&gets(--r)|1<<r;
	//decoding loop
	if(m=n)for(;r--;)
		for(s=0;;)
			if(!s||gets(1)){// known symbol/rule
				for(;n>>l;)l++;
				if((c=gets(l-1))>=(d=(1<<l)-n))c+=c+gets(1)-d;//CBT coding
				for(Stack[s++]=c;;c=Pair[--p])
					if(c<m){Out[o++]=T[c];if(!p)break}
					else Pair[p++]=Right[c],Pair[p++]=Left[c]
			}else{
				if(s<2)break;
				Right[n]=Stack[--s];Left[n]=Stack[--s];
				Stack[s++]=n++ // add new rule
			}
	else for(;o<r;)Out[o++]=gets(8);//not compressed
	done&&done(Out,size,o);
	return Out
}

試し斬り

(async()=>{
let A=Array.from("That that is is that that is not is not is that it it is",a=>a.charCodeAt());
let c=await compress(A,0,a=>a,a=>a), d=decompress(c,a=>a);
console.log(A.length,"->",c.length, String.fromCharCode(...d))
})()

codepen召喚

See the Pen RePair compression by xezz (@xezz) on CodePen.

余談

Range符号等のentropy符号を使えばもっとも～っと圧縮率が上がる事も実証しましたが、それをここに書くには余白が狭過ぎます(^o^)