JavaScript: BWTとか混合法とか圧縮

BWTと文脈混合法、どちらも高圧縮な手法として有名です。それらをうまく組み合わせると、当然スンバラスィー性能になります。
その代表格としてbcmを紹介します。高速高圧縮、ついでに単純設計で移植も容易と文句の付け所がありません。
開発者はIlya Muravyov氏。他にも多数の圧縮programを公開されています。

実装編

BWTの処理についてはこの記事で触れているものと同じになります。符号化にはBinary Range符号を利用。圧縮と伸長は以下の通り。
ちなみに本家とは仕様が異なるので互換性は皆無

//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);
/* compressor
@In: 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 BCMenc(In,bs,done=a=>a,rate){
	function encBit(b){
		var m=l+(h-l>>>0)*32768/262144>>>0;
		for(b?h=m:l=m+1;!((l^h)>>24);h=h<<8|255)O[o++]=l>>>24,l<<=8
	}
	function body(){
		var b,c,step=goal,f,n,ctx,p,p0,p1,p2,i,x1,x2,ssep,m,C,d=Date.now();
		for(rate(a,z);a<size;c1=c){
			if(!--step&&Date.now(step=goal)-d>200)return wait(body);
			c=In[a++],run=c1===c2&&++run,f=run>2&&256,ctx=1;
			for(n=8;n;ctx+=ctx+b){
				// prediction
				p0=C0[ctx];
				p1=C1[ctx|c1<<8];
				p2=C1[ctx|c2<<8];
				p=p0+p0+p0+p0+p1+p1+p1+p2>>3;
				C=C2[f+ctx];x1=C[i=p>>12];x2=C[i+1];
				ssep=x1+((x2-x1)*(p&4095)>>12);
				p+=ssep+ssep+ssep;
				m=l+(h-l>>>0)*p/262144>>>0;
				(b=c>>--n&1)?h=m:l=m+1,m=b<<16,
				C0[ctx]-=(p0-m>>2)+b,
				C1[ctx|c1<<8]-=(p1-m>>4)+b,
				C[i]-=(x1-m>>6)+b;
				// encoding normalize
				for(C[i+1]-=(x2-m>>6)+b;!((l^h)>>24);h=h<<8|255)O[o++]=l>>>24,l<<=8
			}c2=c1
		}return wait(head);
	}
	function head(){
		var U=In.subarray(a,a+bs),n=U.length,i=31,bp;
		if(a&&n==bs)encBit(0);
		else{if(a)for(i=0,encBit(1);bm>>++i;);
			for(;i;)encBit(n>>--i&1)
		}if(!n){for(;l;l<<=8)O[o++]=l>>>24;done(O,z,o);return O}
		bp=BWTe(U.slice(),U)-1;size+=bm=n;
		if(n>2){
			for(i=0;n-1>>++i;);
			for(;i;)encBit(bp>>--i&1);
		}return wait(body)
	}
	In instanceof Uint8Array||(In=new Uint8Array(In));
	var goal="function"!=typeof rate?0:8192,wait=wait0,bm=-1>>>1,
		l=0,h=-1>>>0,a,o=512,c1=0,c2=0,run=0,size=1<<15,z=In.length,
		C,C0=new Uint16Array(65792).fill(32768),C1=C0.subarray(256),C2=[],O=[];

	bs&=-1>>>1;if(bs<size)bs=size;if(bs>z)bs=z;size=0;
	if(!goal)wait=a=>a(),rate=a=>a;// not async

	// initialize model
	for(;o;)for(C=C2[--o]=new Uint16Array(a=17);a;)
		C[--a]=a-(a>15)<<12;
	return head()
}
/* decompressor
@In: 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 BCMdec(In,done=a=>a,rate){
	function decBit(){
		for(;!((l^h)>>24);h=h<<8|255)v=(v<<8|In[a++])>>>0,l<<=8;
		var m=l+(h-l>>>0)*32768/262144>>>0,b=v<=m;b?h=m:l=m+1;
		return b
	}
	function body(){
		var b,c,step=goal,f,ctx,p,p0,p1,p2,i,x1,x2,ssep,m,C,d=Date.now();
		for(rate(a,z);u<size;P[u]=F[U[u++]=c1=255&ctx]++){
			if(!--step&&Date.now(step=goal)-d>200)return wait(body);
			run=c1===c2&&++run,f=run>2&&256;
			for(ctx=1;ctx<256;ctx+=ctx+b){
				// decoding normalize
				for(;!((l^h)>>24);h=h<<8|255)v=(v<<8|In[a++])>>>0,l<<=8;
				// prediction
				p0=C0[ctx];
				p1=C1[ctx|c1<<8];
				p2=C1[ctx|c2<<8];
				p=p0+p0+p0+p0+p1+p1+p1+p2>>3;
				C=C2[f+ctx];x1=C[i=p>>12];x2=C[i+1];
				ssep=x1+((x2-x1)*(p&4095)>>12);
				p+=ssep+ssep+ssep;
				m=l+(h-l>>>0)*p/262144>>>0,b=0;
				v>m?l=m+1:(h=m,b=1),m=b<<16;
				C0[ctx]-=(p0-m>>2)+b,
				C1[ctx|c1<<8]-=(p1-m>>4)+b,
				C[i]-=(x1-m>>6)+b,C[i+1]-=(x2-m>>6)+b
			}c2=c1
		}
		if(size==2)bp=U[1]<U[0]?1:2;
		for(b=f=0;b<u;b+=c)c=F[f],F[f++]=b;
		for(c=0;u;c<bp&&c++)c=P[c]+F[O[o+--u]=U[c]];
		o+=b;F.fill(0);return wait(head)
	}
	function head(i){
		if(!o||decBit()){
			if(o)for(i=0;size>>++i;);else i=31;
			for(size=0;i;)size|=decBit()<<--i;
			if(!size)return done(O,z,o),O;
			if(!o)U=new Uint8Array(size),P=new Uint32Array(size);
		}bp=1;
		if(size>2){
			for(i=0;size-1>>++i;);
			for(;i;)bp+=decBit()<<--i;
		}
		return wait(body)
	}
	var goal="function"!=typeof rate?0:8192,l,h,v,a,o=512,u=0,size,z=In.length,bp,c1=0,c2=0,run=0,
		C,C0=new Uint16Array(65792).fill(32768),C1=C0.subarray(256),C2=[],O=[],P,F=new Uint32Array(256),U,wait=wait0;

	if(!goal)wait=a=>a(),rate=a=>a;// not async
	// initialize model
	for(;o;)for(C=C2[--o]=new Uint16Array(a=17);a;)
		C[--a]=a-(a>15)<<12;
	return head()
}

BCMencの第2引数には圧縮元配列の分割区間幅を指定。通常大きい方が圧縮率が高くなり、空間消費量が増え、速度が犠牲になります。
doneとrateはcallback関数ですが、指定するほどのものではありません。面倒臭いだけです。非同期関数のように振る舞い、CPU負荷が若干減るかもしれない程度のもの。

使用例

let A=Array.from("That that is is that that is not is not is that it it is",a=>a.charCodeAt());
let e=BCMenc(A,A.length), d=BCMdec(e);
console.log(A.length,"->",e.length, String.fromCharCode(...d))

具現化系codepen

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

突っ込みなど

本家は元々divsufsortを使ってBWTをしていましたが、この記事では実装していません。pointer乱舞のprogramなんてJavaScriptで書いてられるかってんだ! まあ書きはしましたが、長くなる上に一般的なfileの処理では今回の実装の方が高速という結末に…