JavaScript: 圧縮力は大丈夫か?

先日の記事で紹介した[哀れな圧縮力](https://qiita.com/mashuel/items/2353b0b9fe6887c33f41)とやらに多少味付けをして、圧縮力を高めようという企画になります。
手法自体は全く同じです。違いは固定bitから可変bitで符号化する点です。
そのためにRange Coderを使います(桁上がり無しの変形版)。実装は以下のようになります。
```js
/*
@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
それでは[そんじょそこら](http://corpus.canterbury.ac.nz/)の馬の骨のようなfile群を圧縮してみます(圧縮設定は全てm=13,n=4)
<table>
<tr><th>file名<th>元尺<th>哀れな圧縮<th>今回の圧縮
<tr><td>alice29.txt<td>152089<td>98136<td>61546
<tr><td>asyoulik.txt<td>125179<td>86243<td>54330
<tr><td>cp.html<td>24603<td>14362<td>10386
<tr><td>fields.c<td>11150<td>5983<td>4599
<tr><td>grammar.lsp<td>3721<td>2238<td>1694
<tr><td>kennedy.xls<td>1029744<td>266393<td>69537
<tr><td>lcet10.txt<td>426754<td>258254<td>159178
<tr><td>plrabn12.txt<td>481861<td>338953<td>200261
<tr><td>ptt5<td>513216<td>135495<td>65089
<tr><td>sum<td>38240<td>22189<td>16897
<tr><td>xargs.1<td>4227<td>3094<td>2382
</table>

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

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

## 実演
進捗表示の為に少し改造 & 非同期関数化。
<p class=codepen data-height="300" data-default-tab="result" data-slug-hash="LYvrOWW" data-user="xezz" style="height:300px;box-sizing:border-box;display:flex;align-items:center;justify-content:center;border:2px solid;margin:1em 0;padding:1em"> <span>See the Pen <a href="https://codepen.io/xezz/pen/LYvrOWW">P1 file compressor/decompressor</a> by xezz (<a href="https://codepen.io/xezz">@xezz</a>) on <a href="https://codepen.io">CodePen</a>.</span></p><script async src="https://cpwebassets.codepen.io/assets/embed/ei.js"></script>