JavaScript: 哀れな圧縮力だ!

今回紹介するのは超単純で超軽量な圧縮伸長programです。あの有名っぽいhuffman符号様を遥かに凌がないかもしれない程の圧縮率を誇っています。率にして約50～60%という貧弱っぷりですが、記述量的に仕方がありません。実装は以下の通り。

//圧縮
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
}

おっといけない、手が滑って可読性のかけらも無いものを記ってしまった。人語訳すると以下のようになるかもしれません。

/*圧縮
@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^13+mとなります。圧縮する配列が大きい程増やすと良いかもしれません。ちなみに前述の手が滑ったprogramではm=4で固定されています。
さて、本当にこんな変てこな処理で圧縮できるのでしょうか?

benchmark

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

file名	元尺	圧縮後
alice29.txt	152089	98136(64.52%)
asyoulik.txt	125179	86243(68.89%)
cp.html	24603	14362(58.37%)
fields.c	11150	5983(53.65%)
grammar.lsp	3721	2238(60.12%)
kennedy.xls	1029744	266393(25.86%)
lcet10.txt	426754	258254(60.51%)
plrabn12.txt	481861	338953(70.34%)
ptt5	513216	135495(26.4%)
sum	38240	22189(58.02%)
xargs.1	4227	3094(73.17%)

js file

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

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

実演

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

哀れじゃない感じの圧縮系記事

続編
web素材を超圧縮
789 bytesのFile圧縮伸長program