情報圧縮編、今回はPolar codeを紹介します。適応型huffman符号より圧縮性能が少しだけ劣り、少しだけ遥かに高速らしいっぽいそうですが…。
実際に試してた所、速度については疑問が残ります…。詳細は作者のpageをご覧下さい。
実装
例によってJavaScriptで書き殴っておきます。本家とは一味違います。
// log2
function l2b(a,b,c){
c=(65535<a)<<4,c|=b=(255<(a>>>=c))<<3,c|=b=(15<(a>>=b))<<2;
return(c|=b=(3<(a>>=b))<<1)|a>>b>>1
}
//this is entropy coder
function Hit(){}
function Sym(){}
function CLen(){}
!function(o,p,q,r){for(;o;r[o]=8)p[q[--o]=o]=0}(256,Hit.prototype,Sym.prototype,CLen.prototype);
function init(cs){
var i=cs--,p=CLen.prototype;
for(PolarCode.prototype.ml=cs=l2b(cs)+1;i;)p[--i]=cs
}
/*
@cs: 記号種類
@n: 記号頻度への加算値
@max: 記号頻度最大値
@d: 真ならdecode
*/
function PolarCode(cs,n,max,d){
if(n)this.n=n;
if(max)this.max=max;
this.size=cs;
this.F=new Hit;
this.S=new Sym;
this.Inv=new Sym;
this.code=new Sym,
this.cLen=new CLen;
//for decode only
if(d)this.shift=[0],this.offset=[0],this.lowC=[0],this.fLen=[cs]
}
PolarCode.prototype={
n:2,cnt:16,max:800,ml:8,tsize:1,asize:16,maxSA:4096,
update:function(v){
for(var F=this.F,I=this.Inv,S=this.S,p,r=this.n;r--;){
if(++F[v]>this.max)
for(i=this.size;i;)F[--i]-=F[i]>>1; // may be F[i]>>=1
if(p=S[v]){
for(var n=-1,i=p,f=F[v];i&&f>F[I[--i]];)n=i;
if(~n)f=S[i=I[p]],S[i]=S[p=I[p]=I[n]],S[p]=f,I[n]=i}}
},
BuildTree:function(d){
for(var F=[],C=this.F,L=this.Inv,c,l=this.size,n=0,i=l,s=0,p=0,t=1,T;i;p+=F[i]=1<<l2b(t))
s+=t=C[L[--i]]||1;
T=1<<l2b(s);
for(T<<=T<s;t;)for(t=0,i=n;i<l;)
if(p+F[i]<=T)p+=F[i],F[i++]<<=t=1;
else n=++i;
for(C=this.code,L=this.cLen,s=C[0]=i=0;i<l;L[i++]=n){
for(n=1,t=T,p=F[i];(t>>=1)>p;)++n;
if(n>s)s=n}
for(i=1;i<l;)C[i]=C[i-1]+1<<L[i++]-L[i-2];
if(!d)return;
for(n=1,--i;i;)L[i]^L[--i]&&++n;
this.ml=s;this.tsize=n;F=this.fLen,T=this.offset;
for(c=C[n=p=s=0],t=L[0];i<l;++i)
if(L[i]^t)
F[s]=n,this.lowC[s]=c,T[s]=p,
this.shift[s++]=this.ml-L[i-1],
n=1,t=L[p=i],c=C[i];
else++n;
F[s]=n,this.lowC[s]=c,T[s]=p,this.shift[s]=this.ml-L[--l]
}};
/*
@In: Array. 圧縮元配列
@cs: 記号最大値(0-255)
@up: 記号頻度への加算値(0-15)
@max: 記号頻度最大値(0-15)
@mo: 文脈の次数(0-2)
@done: 終了時のcallback関数. 省略時は圧縮結果を返す関数になる
@rate: 進捗用callback関数
@return: @done実行結果
*/
function POLARe(In,cs,up,max,mo,done,rate){
PolarCode.prototype.encode=function(c,s){
s=this.S[c];this.update(c);c=this.code[s];
for(s=this.cLen[s];s>=b;b=8)O[o++]=B|(1<<b)-1&c>>(s-=b),B=0;
B|=((1<<s)-1&c)<<(b-=s);
if(!--this.cnt)
this.BuildTree(),
this.cnt=this.asize<<=this.asize<this.maxSA
};
var sync="function"!=typeof rate,a=In.length,b=6,B=(mo&=3)<<6,o=3,m=(1<<mo*8)-1,x=0,z=a,O=[a&31,cs&=255,(up&=15)<<4|(max&=15)],P=[];
done=done||function(O){return O};
rate=rate||function(){};
if(!a)return done([0],0,1);
for(a-=a&31,a/=32;a;a/=256)a-=O[o++]=a&255,O[0]+=32;
max=++max*100,++up,++cs^256&&init(cs);
function F(){
var c,d=sync?-1:4095,p,t=sync?1/0:+new Date;
for(rate(a,z);a<z&&(a&d||new Date-t<200);p.encode(c=In[a++]),x=x<<8|c)
p=P[x&=m]||(P[x]=new PolarCode(cs,up,max));
if(a==z){if(b<8&&B)O[o++]=B;return done(O,a,o)}
setTimeout(F,0)
}return F()
}
/*
@In: Array. 伸長元配列
@done: 終了時のcallback関数. 省略時は伸長結果を返す関数になる
@rate: 進捗用callback関数
@return: @done実行結果
*/
function POLARd(In,done,rate){
PolarCode.prototype.decode=function(p){
var c=this.ml,i=-1,s=0;
if(b<c)B=B<<16|In[a++]<<8|In[a++],b+=16;
for(c=(1<<c)-1&B>>>b-c;;){
p=(c>>this.shift[++i])-this.lowC[i];
if(p<this.fLen[i]){
s=this.Inv[p+this.offset[i]];
b-=this.ml-this.shift[i];
break}}
this.update(s);
--this.cnt||this.BuildTree(this.cnt=this.asize<<=this.asize<this.maxSA);
return s
};
if(!In[0])return done([],1,0);
done=done||function(O){return O};
rate=rate||function(){};
var sync="function"!=typeof rate,a=In[2],b=In[0],cs=In[1],B=32,y=In.length,z=b&31,m,o=0,x,up=a+16>>4,max=((a&15)+1)*100,P=[],O=[];
for(a=3,b>>=5;b--;B*=256)z+=In[a++]*B;
B=In[a++],b=6,m=(1<<(B>>6)*8)-1,++cs^256&&init(cs);
function F(){
var d=sync?-1:4095,p,t=sync?1/0:+new Date;
for(rate(a,y);o<z&&(o&d||new Date-t<200);x=x<<8|(O[o++]=p.decode()))
p=P[x&=m]||(P[x]=new PolarCode(cs,up,max,1));
if(o==z)return done(O,y,o);
setTimeout(F,0)
}return F()
}
codepen実践
See the Pen Polar Code by xezz (@xezz) on CodePen.