GRZipII編第2話。

原理

BlockSort -> WFC -> RLE -> Range符号という流れで圧縮。MTFより強力なWeighted Frequency Coding(WFC)搭載で圧縮率向上となりやすい(MTFより低速)。

実装

function compare(R,a,b,i,n,r){
	for(n-=a<b?b:a;i<n&&!(r=R[a+i]-R[b+i]);)i+=2;return r||b-a
}
function subsort(R,A,l,h,d,n){
	if(10<h-l)
		for(var i=l+2,j,m=i,t;i<h;A[j]=t)
			for(t=A[j=++i];m<j&&compare(R,t,A[j-3],d,n)<0;)A[j]=A[j-=3];
	for(i=l;i<h;A[j]=t)
		for(t=A[j=++i];l<j&&compare(R,t,A[j-1],d,n)<0;)A[j--]=A[j]
}
function median(R,A,a,b,c,d,z){
	var r=A[a]+d,s=A[b]+d;
	r=r<z?R[r]:-1,s=s<z?R[s]:-1,d+=A[c],d=d<z?R[d]:-1;
	return r<s?s<d?b:r<d?c:a:r<d?a:s<d?c:b
}
function getPivot(R,A,r,l,h,d,z){
	if(r<65)var m=l+(r>>1),p;
	else r>>=3,
		l=median(R,A,l,p=l+r,p+=r,d,z),
		m=median(R,A,p+=r,p+=r,p+=r,d,z),
		h=median(R,A,p+=r,p+=r,h,d,z);
	p=A[m=median(R,A,l,m,h,d,z)];A[m]=A[l];A[l]=p;
	return R[p+d]
}
function mqsort(R,I,l,h,d,n,L,H,D){
	for(var a,b,i,j,o,p,r,s=0,t;;){
		if(h-l<20){
			for(l<h&&subsort(R,I,l,h,d,n);l<=h;)R[I[l]]=l++;
			if(!s)break;
			l=L[--s];h=H[s];d=D[s];
			continue}
		p=getPivot(R,I,h-l+1,l,h,d,n);
		for(i=a=l,j=b=h;;I[j--]=t){
			for(;i<=j&&(r=((t=I[i]+d)<n?R[t]:-1))<=p;i++)
				r^p||(I[i]=I[a],I[a++]=t-d);
			for(;i<=j&&(r=((t=I[j]+d)<n?R[t]:-1))>=p;j--)
				r^p||(I[j]=I[b],I[b--]=t-d);
			if(i>j)break;
			t=I[i],I[i++]=I[j]}
		if((p=a-l)<(r=i-a))r=p;o=j;
		for(p=l;r--;I[o--]=t)t=I[p],I[p++]=I[o];
		if((p=h-b)<(r=b-j))r=p;o=h;
		for(p=i;r--;I[o--]=t)t=I[p],I[p++]=I[o];
		i+=l-a;j-=~h+b;
		if(j<=h)L[s]=j,H[s]=h,D[s++]=d;
		if(i<j)L[s]=i,H[s]=j-1,D[s++]=d+2;
		h=i-1}
}
//sort type B*
function sortTypeBstr(B,I,C,R,n){
	for(var A=C.slice(),p=1,r,i=n-1,j=0|Math.sqrt(n*2)+1,L=new Int32Array(j*3+3),H=L.subarray(j+1),D=H.subarray(j+1);i--;)
		if(r=B[i]-B[i+1])
			r<0&&p>0&&(I[A[B[i]<<8|B[i+1]]++]=i),p=r;
	for(;i<255;)
		for(j=++i;j<255;p-r>1&&mqsort(R,I,r,--p,2,n,L,H,D))
			p=A[r=i<<8|++j],r=C[r]
}
//set type A,B
function setTypeAB(B,I,C,n){
	var i=255,j,p,A=new Uint32Array(256),E=A.slice();
	for(A[i]=n;j=i;A[i]=E[i]){
		for(;j;)E[--j]=C[j<<8|i];
		for(j=C[i--<<8];j>E[i];)
			if((p=I[--j])>0&&B[p]>=B[--p])
				I[--E[B[p]]]=p}
	for(I[C[B[n-1]<<8]++]=n-1;j<n;)
		if((i=I[j++])>0&&B[i]<=B[--i]&&C[p=B[i]<<8|B[i+1]]<A[B[i]])
			I[C[p]++]=i
}
/* suffix sort
@T: input (Uint8Array / Array)
@A: suffix array (Int32Array / Array / null)
@n: input size (Number / null)
*/
function I2SRsort(T,A,n){n=n||T.length;
	var I=A||new Int32Array(n);
	if(n<2)return n?I[0]=0:0,I;
	if(n<3)return I[n=0|T[0]<T[1]]=1,I[1-n]=0,I;
	if(n<512&&!A)return I.map((a,b)=>b).sort((a,b,c,d)=>{for(c=a<b?n-b:n-a;c--;)if(d=T[a++]-T[b++])return d;return b-a});
	for(var i=n,c,C=new Uint32Array(65537),R=I.slice();i;)C[c|(c=T[--i])<<8]++;
	for(n=0;i<65537;n+=c)c=C[i],C[i++]=n;
	for(i=n,c=0;i;)R[--i]=C[(c|(c=T[i])<<8)+1]-1;
	sortTypeBstr(T,I,C,R,n);setTypeAB(T,I,C,n);
	return I
}
/* BWT
@T: input (Uint8Array / Array)
@U: output (Uint8Array / Array / null)
@n: input size (Number / null)
*/
function BWTe(T,U,n){n=n||T.length;
	var i=0,a=n<257?1:n<65537?2:n<16777217?3:4,p,SA=I2SRsort(T,0,n),B=U||new Uint8Array(n+a);
	for(B[0]=T[n-1];p=SA[i++];)B[i]=T[--p];
	for(p=i;i<n;)B[i]=T[SA[i++]-1];
	if(U)return p;--p;
	for(;a--;p>>=8)B[i++]=p&255;
	return B
}
//setImmediateもどき
(function(a){
	var F=[],hit="\0";
	a.wait0=function(f){
		F[F.length]=f;a.postMessage(hit,"*")
	};
	a.onmessage=function(e){
		if(e.source===a&&e.data===hit)
			e.stopPropagation(),F[0]&&F.shift()()
	}
})(this);
const R2N=new Uint8Array(256),R2M=new Uint8Array(256),R2P=new Uint8Array(257);
// initialize
!function(N,M,P,a,b,c){for(P[4]=1;b<255;N[++b]=c-2)for(c=0;b>>++c;);for(;--b>1;M[b+1]=1<<c-2)for(c=0;b>>++c;);for(;b<7;)for(c=256>>b++;c;)P[a--]=--c}(R2N,R2M,R2P,256,4);

function update03(M,V,U,r){
	M[r]+=2,U[r]+=2,V[r]+=2;
	if((M[4]+=2)>58)M[4]=(M[0]-=M[0]>>1)+(M[1]-=M[1]>>1)+(M[2]-=M[2]>>1)+(M[3]-=M[3]>>1);
	if((V[4]+=2)>62)V[4]=(V[0]>>=1)+(V[1]>>=1)+(V[2]>>=1)+(V[3]>>=1);
	if((U[4]+=2)>204)U[4]=(U[0]>>=1)+(U[1]>>=1)+(U[2]>>=1)+(U[3]>>=1)
}
/* compressor
@A: input(Uint8Array)
@bs: block size(32768 - 0x7fffffff)
@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
*/
function GRZ2WFCenc(A,bs,done=a=>a,rate){
	function encode(t,f,c){L+=c*(R=R/t>>>0);
		for(R*=f;R<16777216;R*=256,L=L<<8>>>0)
			if((c=L>0xffffffff)||255>L>>>24)
				for(O[o++]=255&c--+C,C=L>>>24;N;N--)O[o++]=255&c;
			else++N;
	}
	// EndOfMark
	function EOM(){
		var V=S0[c],U=S1[c0<<2|cr&3],i=S[3]+U[3]+V[3],j=S[4]+U[4]+V[4],n;
		encode(j,i,j-i>>>0),update03(S,V,U,3);
		V=S2,U=S3[c1];
		for(i=j=0;i<cb;)
			encode(max,max-(n=V[i]+U[i]>>1),n),
			V[i]-=V[i]>>4,U[i]-=U[i++]>>6;
		for(V=S4[i];j<1<<cb;V[j]-=V[j]>>7)
			encode(max,max-V[j+=++j],V[j])
	}
	function block(){
		var b,e=E,i,j,l,n,m,p,r,d=Date.now(),U,V;
		for(rate(a,z);a<y;){
			if(!--e&&Date.now(e=E)-d>200)return wait(block);
			V=S0[c],U=S1[c0<<2|cr&3];
			r=CI[c=B[w]=A[a]]-1&255,CW[c]+=131072;
			for(l=1;c===A[++a]&&a<y;)l++;
			if(i=CI[c])for(;i;)CI[M[i]=M[--i]]=i+1;
			for(CI[M[0]=c]=0;i<12;i++)
				if(w>=(p=1<<i)){n=CW[b=B[w-p]]-=W[i];
					if(b^c){
						for(j=p=CI[b];CW[M[++j]]>n;)CI[M[j-1]=M[j]]=p++;
						CI[M[p]=b]=p}}w++;
			if(r<3){
				for(i=n=0;i<r;)n+=U[i]+V[i]+S[i++];
				encode(S[4]+U[4]+V[4],S[r]+U[r]+V[r],n);
				update03(S,V,U,r)
			}else{
				encode(j=S[4]+U[4]+V[4],i=S[3]+U[3]+V[3],j-i);
				update03(S,V,U,3);
				V=S2,U=S3[c1],
				m=R2M[r],n=c1=R2N[r],p=R2P[r];
				for(i=0;i<n;)
					encode(max,max-(j=V[i]+U[i]>>1),j),
					V[i]-=V[i]>>4,U[i]-=U[i++]>>6;
				if(n<cb)
					encode(max,V[i]+U[i]>>1,0),
					V[i]+=max-V[i]>>4,U[i]+=max-U[i]>>6;
				V=S4[n];
				for(j=1;m;m>>=1)
					if(p&m)
						encode(max,max-V[j],V[j]),
						V[j]-=V[j]>>7,j+=j+1;
					else
						encode(max,V[j],0),
						V[j]+=max-V[j]>>7,j+=j
			}
			if(r>3)r=3;
			c0=c0<<2&255|r;
			if(l<2)b=0;
			else for(b=m=1;l>>b>1;b++)m<<=1;
			V=R0[cr|r<<4],U=R1,j=c*32;
			for(i=0;i<b;)
				encode(max,max-(n=V[i]+U[j]>>1),n),
				V[i]-=V[i++]>>6,U[j]-=U[j++]>>3;
			encode(max,V[i]+U[j]>>1,0);
			V[i]+=max-V[i]>>6,U[j]+=max-U[j]>>3;
			V=R2[b],cr=cr<<1&15|b>1;
			for(i=0;m;m>>=1)
				if(l&m)encode(max,max-V[i],V[i]),
					V[i]-=V[i++]>>6;
				else encode(max,V[i],0),
					V[i]+=max-V[i++]>>6
		}
		EOM();
		// write pidx
		for(i=c=c0=c1=cr=0;x>>++i;);
		if(x>1)for(;i;)encode(max,1024,(bp>>--i&1)<<10);
		return wait(head)
	}
	function head(){
		if(a>=z){EOM();
			for(L+=R>>>1,x=6;--x;L=L<<8>>>0)
				if((c=L>0xffffffff)||255>L>>>24)
					for(O[o++]=255&c--+C,C=L>>>24;N;N--)O[o++]=255&c;
				else++N;
			done(O,z,o);return O
		}
		var U=A.subarray(a,a+bs);y+=x=U.length;
		bp=BWTe(U.slice(),U);
		return wait(block)
	}
	A instanceof Uint8Array||(A=new Uint8Array(A));
	var E="function"!=typeof rate?0:4096,bp,cb=6,a=1024,o=257,w=0,x,y=1<<15,z=A.length,
		B=new Uint8Array(z),W=new Uint32Array([114688,7272,4240,2364,1263,649,320,153,70,31,14,8]),M=new Int32Array(o),CI=M.slice(),CW=M.slice(),
		R0=[],R1=new Uint16Array(8192).fill(1024),R2=[],S=new Uint8Array([1,1,1,1,4]),S0=[],S1=[],S2=R1.slice(-6),S3=[],S4=[],
		L=0,R=-1>>>0,N=0,C=0,O=[],
		c=0,c0,c1=0,cr,max=2048,wait=wait0;

	if(!E)rate=a=>a,wait=a=>a();
	bs&=-1>>>1;if(bs<y)bs=y;if(bs>z)bs=z;y=0;
	for(;o--;)S0[M[o]=CI[o]=o]=new Uint8Array(5);
	for(CW[256]=-1;a;)S1[--a]=new Uint8Array(5);
	for(;a<8;S3[a++]=R1.slice(-6))S4[a]=R1.slice(-128);
	for(a=64;a;)R0[--a]=R1.slice(-32);
	for(a=24;a;)R2[--a]=R1.slice(-32);
	return head()
}
/* decompressor
@A: input (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
*/
function GRZ2WFCdec(A,done=a=>a,rate){
	function decode(f,c){
		for(L-=R*c,R*=f;R<1<<24;R*=256)L=(L<<8|A[a++])>>>0
	}
	function block(){
		var b,e=E,f,i,j,l,n,r,U,V,d=Date.now();
		for(rate(a,z);;){
			if(!--e&&Date.now(e=E)-d>200)return wait(block);
			V=S0[c],U=S1[t<<2|s&3];
			b=L/(R=R/(S[4]+U[4]+V[4])>>>0)>>>0;
			for(n=r=0;b>=n;)n+=S[r]+U[r]+V[r++];
			decode(b=S[--r]+U[r]+V[r],n-b);

			S[r]+=2,U[r]+=2,V[r]+=2;
			if((S[4]+=2)>58)S[4]=(S[0]-=S[0]>>1)+(S[1]-=S[1]>>1)+(S[2]-=S[2]>>1)+(S[3]-=S[3]>>1);
			if((V[4]+=2)>62)V[4]=(V[0]>>=1)+(V[1]>>=1)+(V[2]>>=1)+(V[3]>>=1);
			if((U[4]+=2)>204)U[4]=(U[0]>>=1)+(U[1]>>=1)+(U[2]>>=1)+(U[3]>>=1);

			if(r>2){
				V=S2,U=S3[u];
				for(i=r=0;i<cb;){
					if(L/(R>>>=11)>>>0<(c=V[i]+U[i]>>1)){
						decode(c,0);
						V[i]+=2048-V[i]>>4;
						U[i]+=2048-U[i]>>6;
						break}
					decode(2048-c,c);
					V[i]-=V[i]>>4;
					U[i]-=U[i++]>>6}
				V=S4[u=i],i=2<<i;
				for(f=1;f<i;)
					if(L/(R>>>=11)>>>0<(c=V[f]))
						decode(c,0),
						V[f]+=2048-c>>7,
						f+=f,r+=r;
					else
						decode(2048-c,c),
						V[f]-=c>>7,
						f+=f+1,r+=r+1;
				if(u==cb&&r>cs)break;
				r+=2<<u|1
			}
			CW[c=B[w]=M[r+1&255]]+=131072;
			if(i=CI[c])while(i)CI[M[i]=M[--i]]=i+1;
			for(CI[M[0]=c]=0;i<12;i++)
				if(w>=(V=1<<i)){n=CW[b=B[w-V]]-=W[i];
					if(b^c){
						for(j=V=CI[b];CW[M[++j]]>n;)CI[M[j-1]=M[j]]=V++;
						CI[M[V]=b]=V}}w++;

			if(r>3)r=3;
			t=t<<2&255|r,V=R0[s|r<<4],U=R1,f=c*32;
			for(i=0;L/(R>>>=11)>>>0>=(n=V[i]+U[f]>>1);U[f]-=U[f++]>>3)
				decode(2048-n,n),V[i]-=V[i++]>>6;
			decode(n,0);
			V[i]+=2048-V[i]>>6;
			U[f]+=2048-U[f]>>3;
			V=R2[i],s=s<<1&15|i>1;
			for(f=l=0;f<i;)
				if(L/(R>>>=11)>>>0<(n=V[f]))
					decode(n,0),
					V[f++]+=2048-n>>6,l+=l;
				else decode(2048-n,n),
					V[f++]-=n>>6,l+=++l;
			for(l+=1<<f;l--;)P[p]=N[T[p++]=c]++
		}
		if(!p)return done(O,z,o);
		for(i=r=f=0;r<p;r+=c)c=N[f],N[f++]=r;
		for(c=0;p>>++c;);
		if(p>1)for(;c--;)
			if(L/(R>>>=11)>>>0<1024)decode(1024,0);
			else decode(1024,1024),i|=1<<c;
		for(c=0;p;c<i&&c++)c=P[c]+N[O[o+--p]=T[c]];
		o+=r;B.fill(s=t=u=c=0);
		return wait(block)
	}
	var E="function"!=typeof rate?0:4096,cb=6,cs=(2<<cb)-2,a=1024,c=0,w=0,P=[],o=257,p=0,z=A.length,O=[],T=[],N=new Uint32Array(a),
		B=[],W=new Uint32Array([114688,7272,4240,2364,1263,649,320,153,70,31,14,8]),M=new Int32Array(o),CI=M.slice(),CW=M.slice(),
		R0=[],R1=new Uint16Array(8192).fill(1024),R2=[],S=new Uint8Array([1,1,1,1,4]),S0=[],S1=[],S2=R1.slice(-6),S3=[],S4=[],
		L,R=-1>>>0,s,t,u=0,wait=wait0;

	if(!E)rate=a=>a,wait=a=>a();

	for(;o;)S0[M[--o]=CI[o]=o]=new Uint8Array(5);
	for(CW[256]=-1;a;)S1[--a]=new Uint8Array(5);
	for(;a<8;S3[a++]=R1.slice(-6))S4[a]=R1.slice(-128);
	for(a=64;a;)R0[--a]=R1.slice(-32);
	for(a=24;a;)R2[--a]=R1.slice(-32);
	for(;a<4;)L=(L<<8|A[a++])>>>0;
	return block()
}

使用例

let A=Array.from("That that is is that that is not is not is that it it is",a=>a.charCodeAt());
let c=GRZ2WFCenc(A,A.length),d=GRZ2WFCdec(c)
console.log(c.length, String.fromCharCode(...d))

file compression test

See the Pen GRZipII(wfc) compressor by xezz (@xezz) on CodePen.