JavaScript: 圧縮力は大丈夫か?

先日の記事で紹介した哀れな圧縮力とやらに多少味付けをして、圧縮力を高めようという企画になります。
手法自体は全く同じです。違いは固定bitから可変bitで符号化する点です。
そのためにRange Coderを使います(桁上がり無しの変形版)。実装は以下のようになります。

/*
@In: Array/Uint8Array
@m: model size. 0-31
@n: hash size. 0-7
@return: Array
*/
function compress(In,m,n){
	// bit encoder
	function eBit(P,c,b){
		var p=P[c],m=x1+(x2-x1>>>12)*(p>>4);
		P[c]+=((b<<16)-p)*15>>9;
		// normalize
		for(b?x2=m:x1=m+1;!((x1^x2)>>24);x2=x2<<8|255)
			x1<<=8,Out[o++]=x2>>>24
	}
	var a=0,b,c,d,e,hash=0,i,o=1,z=In.length,
		// carryless binary range coder
		x1=0,x2=-1>>>0,Out=[(m&=31)<<3|(n&=7)],
		// predictor
		Context=new Uint8Array(n=1<<13+n),
		// models
		Flag=new Uint16Array(m=Math.min(1<<m,n)).fill(1<<15),
		Code=new Uint16Array(1<<16).fill(1<<15);
    // start
	for(m--,n--;a<z;hash=hash*32+c&n){
		c=In[a++];d=Context[hash];
		if(c===d)
			eBit(Flag,hash&m,0);// hit
		else{
			eBit(Flag,hash&m,e=1);// miss
			Context[hash]=c;
			// encode symbol
			for(i=8;i;e+=e+b)
				eBit(Code,e|d<<8,b=c>>--i&1)
		}
	}
	// mark EOF
	eBit(Flag,hash&m,e=1),c=Context[hash];
	for(i=8;i;e+=e+b)eBit(Code,e|c<<8,b=c>>--i&1);
	// last output
	Out[o++]=x2>>>24;
	return Out
}
/*
@In: Array/Uint8Array
@return: Array
*/
function decompress(In){
	// bit decoder
	function dBit(P,c,b){
		//normalize
		for(;!((x1^x2)>>24);x2=x2<<8|255)
			x1=x1<<8>>>0,x=(x<<8|In[a++])>>>0;
		var p=P[c],m=x1+(x2-x1>>>12)*(p>>4);
		x>m?(x1=m+1,b=0):(x2=m,b=1);
		P[c]+=((b<<16)-p)*15>>9;
		return b
	}
	var a=1,c=In[0],e=c>>3,hash=0,o=0,
		x,x1,x2,// range coder
		m=1<<e,n=c&7,Out=[],
		// predictor
		Context=new Uint8Array(n=1<<13+n),
		// models
		Flag=new Uint16Array(m=m<n?m:n).fill(1<<15),
		Code=new Uint16Array(1<<16).fill(1<<15);
    // start
	for(m--,n--;;hash=hash*32+c&n){
		c=Context[hash];
		if(e=dBit(Flag,hash&m,0)){ // miss
			for(;e<256;)e+=e+dBit(Code,e|c<<8); // decode symbol
			if(Context[hash]===(e&=255))return Out;
			Context[hash]=c=e
		}Out[o++]=c
	}
}

相変わらず読みにくいなコイツのprogram…。それはどうでもいいとして、圧縮率を上げるための地味な工夫は次の3点。

1. 文脈ごとに一致flagの確率表を用意する
2. 予測失敗時の文字ごとに確率表を用意する
3. 復号の終了判定用に最後は特殊な符号化をする

(1)と(2)の目的は確率を偏らせる事です。偏る程に圧縮しやすくなります。
最後にRange Coder単体では終了判定できないため(3)の処理が必要になります。そのカラクリは予測失敗と見せ掛けて実は予測表にある文字を符号化している、というものです。

benchmark

それではそんじょそこらの馬の骨のようなfile群を圧縮してみます(圧縮設定は全てm=13,n=4)

file名	元尺	哀れな圧縮	今回の圧縮
alice29.txt	152089	98136	61546
asyoulik.txt	125179	86243	54330
cp.html	24603	14362	10386
fields.c	11150	5983	4599
grammar.lsp	3721	2238	1694
kennedy.xls	1029744	266393	69537
lcet10.txt	426754	258254	159178
plrabn12.txt	481861	338953	200261
ptt5	513216	135495	65089
sum	38240	22189	16897
xargs.1	4227	3094	2382

js file

file名	元尺	哀れな圧縮	今回の圧縮
angular-1.4.0.min.js	144729	88541	62485
bootstrap-3.3.6.min.js	36868	19066	13754
jquery-3.7.1.min.js	87526	54285	38582
react-0.13.3.js	600572	267342	171897
vue-2.7.16.js	434871	191293	122359

どのfileも大幅に圧縮率が向上していますね。Range Coder様の恐ろしさを垣間見たような気がします。特にkennedy.xlsの圧縮はバグってんじゃないかってくらいの縮みっぷり。

実演

進捗表示の為に少し改造 & 非同期関数化。

See the Pen P1 file compressor/decompressor by xezz (@xezz) on CodePen.