今回紹介するのは超単純で超軽量な圧縮伸長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は予測表の大きさに影響。具体的には213+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.