JavaScript: 哀れな圧縮力だ!

今回紹介するのは超単純で超軽量な圧縮伸長programです。あの有名っぽいhuffman符号様を遥かに凌がないかもしれない程の圧縮率を誇っています。率にして約50～60%という貧弱っぷりですが、記述量的に仕方がありません。実装は以下の通り。
```js
//圧縮
function comp(A){
	for(var a=0,b=1,c,d=0,e,f=1,B=[0],C=[];(e=A[a++])>-1;c=c*32+e)
    	C[c&=131071]^e?B[b++]=C[c]=e:B[d]|=f,(f<<=1)>128&&(B[d=b++]=0,f=1);
	return~d+b||--B.length,B
}
//伸長
function decomp(A){
	for(var a=0,b=0,c=0,d=A.length,f,B=[],C=[];a<=d;c=c*32+(B[b++]=f&1?C[c]:C[c]=A[a++])&131071)
        if((f>>=1)<2)f=A[a++]|256;
	return--B.length,B
}
```
おっといけない、手が滑って可読性のかけらも無いものを記ってしまった。人語訳すると以下のようになるかもしれません。
```js
/*圧縮
@In: Array / Uint8Array. 圧縮元配列
@m: memory size. 0-7指定.
@return: Array
*/
function comp(In,m){
	var i=0,o=1,p=2,c,e=In.length,hash=0,flag=1,Out=[m&=7,0],Context=new Uint8Array(m=1<<13+m);
	for(m--;;hash=hash*32+c&m){
		c=In[i++];
		if(Context[hash]^c)
			Out[p++]=Context[hash]=c;
		else Out[o]|=flag;
		if(i===e)return Out;
		if((flag<<=1)>128)Out[o=p++]=0,flag=1
	}
}
/*伸長
@In: Array / Uint8Array. 圧縮済み配列
@return: Array
*/
function decomp(In){
	var i=1,o=0,c,e,hash=0,flag,m=1<<13+In[0],Out=[],Context=new Uint8Array(m--);
	for(;;hash=hash*32+c&m){
		if((flag>>=1)<2)flag=In[i++]|256;
		if(flag&1)c=Context[hash];
		else{
			c=Context[hash]=In[i++];
			if(c===e)return Out
		}Out[o++]=c
	}
}
//example
var e=comp([1,2,3,1,2,3,1],0),d=decomp(e)
```
手法を大雑把に言うと、直前の数文字から次の文字を予測しています。予測が一致すれば1 bitで符号化。さもなければ9 bitsで符号化し予測表も更新。などという事を繰り返しまくっています。
**hash**は直前数文字から求められたhash値、**Context**は予測表、**flag**は予測一致かどうかのbit。
関数compの**引数m**は予測表の大きさに影響。具体的には2<sup>13+m</sup>となります。圧縮する配列が大きい程増やすと良いかもしれません。ちなみに**前述の手が滑ったprogram**ではm=4で固定されています。
さて、本当にこんな変てこな処理で圧縮できるのでしょうか?

## benchmark
それでは[そんじょそこら](http://corpus.canterbury.ac.nz/)の馬の骨のようなfile群を圧縮してみます(圧縮設定は全てm=4)
<table>
<tr><th>file名<th>元尺<th>圧縮後
<tr><td>alice29.txt<td>152089<td>98136(64.52%)
<tr><td>asyoulik.txt<td>125179<td>86243(68.89%)
<tr><td>cp.html<td>24603<td>14362(58.37%)
<tr><td>fields.c<td>11150<td>5983(53.65%)
<tr><td>grammar.lsp<td>3721<td>2238(60.12%)
<tr><td>kennedy.xls<td>1029744<td>266393(25.86%)
<tr><td>lcet10.txt<td>426754<td>258254(60.51%)
<tr><td>plrabn12.txt<td>481861<td>338953(70.34%)
<tr><td>ptt5<td>513216<td>135495(26.4%)
<tr><td>sum<td>38240<td>22189(58.02%)
<tr><td>xargs.1<td>4227<td>3094(73.17%)
</table>

js file
<table>
<tr><th>file名<th>元尺<th>圧縮後
<tr><td>angular-1.4.0.min.js<td>144729<td>88541(61.17%)
<tr><td>bootstrap-3.3.6.min.js<td>36868<td>19066(51.71%)
<tr><td>react-0.13.3.js<td>600572<td>267342(44.51%)
<tr><td>vue-2.7.16.js<td>434871<td>191293(43.98%)
</table>

御覧の通りhuffman符号風の性能です。素晴らしきぽんこつなり。

## 実演
<p class="codepen" data-height="300" data-default-tab="result" data-slug-hash="wvZyPjM" 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/wvZyPjM">simple file compressor</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>

## 哀れじゃない感じの圧縮系記事
[続編](https://qiita.com/mashuel/items/caec42f7738d5610037b)
[web素材を超圧縮](https://qiita.com/mashuel/items/4fee3a4de93b18d85629)
[789 bytesのFile圧縮伸長program](https://qiita.com/mashuel/items/9b76e0c9585dd46a834e)