前回の続編。圧縮率を高めるためにSecondary Symbol Estimationを導入。
今回の実装では出現率の高い記号順に頻度表を整列して、その先頭から次の文字に一致するかどうか判定していきます(判定のたびに1 bit符号化/復号)。
不一致なら頻度表からその記号分の確率を引いて、次の判定に移ります。整列処理が重くのしかかり、前作より低速ですが圧縮率は若干良くなる傾向があります。
ちなみに整列処理に組み込み関数を使わなかったのは、自前のquick sortもどきの方が高速だったため(Windows7 google chromeの場合)
/*
usage:
TreeCM(A,mo,done,rate)
@A: array of byte
@mo: context order. 0-15 meas compression, otherwise decompression
@done: call back of last process.
done(A,a,z)
@A: (de)compressed array of input
@a: last position
@z: (de)compressed size
@rate: call back of progress
rate(a,z)
@a: current position
@z: last position
@return:
call with await: (de)compressed array
otherwise: Promise
*/
const CNUM=256,MAXORDER_LIMIT=16,
MIN_ALLOC=8,LEAF_FLAG=0x80000000,HEADER_SIZE=6,//uint32 count+uint16 mask1
SCALElog=15,SCALE=1<<SCALElog,mSCALE=SCALE-1,S_wrA=1,S_wrB=0,S_mw=1040,
coef=new Uint32Array([34304,33348,240,0,29273,128512,24,1,64128,125986,8,0,13316,40448,1,5,8768,36872,0,14,7364,65306,0,20,8716,73216,0,21,6848,88138,0,31,8145,86156,0,28,12297,84480,0,22,4864,81952,0,54,2,106496,0,232,15826,127776,0,31,20,130560,0,252,5464,130816,0,160,10368,130816,0,124,102720,130944,0,253]),
bitcount=new Uint8Array(1<<16),bitlength=new Uint8Array(1<<16),
newNode=(M,c=0)=>{
const p=M.alloc(HEADER_SIZE);
M.setU32(p,c,0);M.setU16(p,0,4);
return p
},
addNode=(M,p,c,o)=>{
const m=M.getU16(p,4),hm=1<<(c>>4),lm=1<<(c&15);
let i=0,cb,cc=0,h=m&hm,
gc=bitcount[m],// total vectors
gb=bitcount[m&hm-1],// symbol's vector index
b=HEADER_SIZE-2;
for(;i<gb;i++)cc+=bitcount[M.getU16(p,b+=2)];// count symbols
for(c=b,cb=cc;i<gc;i++)cc+=bitcount[M.getU16(p,b+=2)];// count all symbols
if(h){// high nibble exists
c=M.getU16(p,c+2);
cb+=bitcount[c&lm-1];// symbol's own index
if(c&lm)return{p,s:cb,g:gc}
}
// need to create a new node, it has to be reallocated due to growth anyway
c=gc+!h;b=HEADER_SIZE;
const l=(gc<<1)+b+(cc<<2),n=M.alloc(l+(h?4:6));
M.setU32(n,M.getU32(p,0),i=0);
M.setU16(n,m|hm,4);
if(h)for(;i<gc;b+=2)h=M.getU16(p,b),M.setU16(n,h|=gb===i++&&lm,b);// low nibble vector already exists, so just copy all
else{// insert a new nibble vector
for(;i<gb;i++)M.setU16(n,M.getU16(p,b),b),b+=2;
for(M.setU16(n,lm,b);i<gc;i++)M.setU16(n,M.getU16(p,b),b+=2)
}
gc=(gc<<1)+HEADER_SIZE-4;gb=(c<<1)+HEADER_SIZE-4;
// insert the symbol itself
for(i=0;i<cb;i++)M.setI32(n,M.getI32(p,gc+=4),gb+=4);
M.setI32(n,o|LEAF_FLAG,gb+=4);
for(;i<cc;i++)M.setI32(n,M.getI32(p,gc+=4),gb+=4);
M.free(p,l);
return{p:n,s:cb,g:c}
},
mixupNode=(M,F,p,w)=>{
for(let m=M.getU16(p,4),c=bitcount[m],h=HEADER_SIZE-2,i=c*2+h-2;c--;m&=m-1)
for(let b=bitlength[m&-m]<<4,l=M.getU16(p,h+=2),e;l;l&=l-1)
e=M.getI32(p,i+=4),F[b+bitlength[l&-l]]+=e<0?w:M.getU32(e,0)*w
},
getSlotValue=(M,P,G,I,i)=>{
if(P[i])return M.getI32(P[i],(G[i]<<1)+HEADER_SIZE+(I[i]<<2));
return P.root
},
setSlotValue=(M,P,G,I,i,v)=>{
if(P[i])return M.setI32(P[i],v,(G[i]<<1)+HEADER_SIZE+(I[i]<<2));
P.root=v
},
isort=(A,i,l)=>{
for(let a=i,c,j,k;i<l;A[j]=c)
if((c=A[j=k=++i])>A[a])for(;A[j]=A[--j],j>a;);
else for(;c>A[--k];)A[j]=A[j=k]
},
qsort=(A,a,b)=>{
if(b-a<9)return isort(A,a,b);
let c=A[a],d,i=A[b],j=a,k=b,p=A[a+b>>1];
c>i?i>p?p=i:c>p||(p=c):c>p?p=c:p>i&&(p=i);
for(i=a;j<=k;)
if((c=A[j])<p)A[j]=A[k],A[k--]=c;
else{if(c>p)d=A[i],A[i++]=c,A[j]=d;j++}
a<--i&&qsort(A,a,i);++k<b&&qsort(A,k,b)
},
SSEi=(sseq,Wi)=>{
var P=new Uint16Array(sseq),i=0,p1=0|Wi/2+8192,SCw=0|(SCALE-Wi)/(sseq-1);
for(;i<sseq;p1+=SCw)P[i++]=p1;P.sseq=i;return P
},
SSEip=(P,p,X,f)=>{
p*=(P.sseq-1),f=p>>SCALElog;
X.sw=p&=mSCALE;
X.C1=P.subarray(f,f+2);
f=((SCALE-p)*X.C1[0]+p*X.C1[1]>>SCALElog)-8192;
if(f<1)f=1;
if(f>mSCALE)f=mSCALE;
return X.P=f
},
SSEiup=(c,wr0,X)=>{
wr0=(X.P*(SCALE-wr0)>>SCALElog)+wr0*!c;
c=X.C1[0]-X.C1[1];
X.C1[0]=wr0+=(X.sw*c+mSCALE>>SCALElog)+8192;
X.C1[1]=wr0-c
};
for(let i=1,b=0;i<65536;i>>b&&b++,bitlength[i++]=b-1)bitcount[i]=bitcount[i>>1]+(i&1);
class MemoryPool extends Array{
constructor(z=1<<15){//@z: pushed memory size
let a=0;
for(z=Math.max(z,4<<MIN_ALLOC);z>>>++a;);
if(a>16)a=16;z=1<<a;
super().Free=new Int32Array(z+1);
this.L=a,this.S=z,this.M=z-1;
this.cost=0
}
getI32(p,o=0){return this[--p>>>this.L].getInt32((p&this.M)+o)}
setI32(p,v,o=0){this[--p>>>this.L].setInt32((p&this.M)+o,v|0)}
getU32(p,o=0){return this[--p>>>this.L].getUint32((p&this.M)+o)}
setU32(p,v,o=0){this[--p>>>this.L].setUint32((p&this.M)+o,v>>>0)}
getU16(p,o=0){return this[--p>>>this.L].getUint16((p&this.M)+o)}
setU16(p,v,o=0){this[--p>>>this.L].setUint16((p&this.M)+o,v&0xffff)}
alloc(l){
let h=this.Free[l<MIN_ALLOC?l=MIN_ALLOC:l];// get next free node
if(l>this.S)throw Error("Allocation too large");
if(!h){
// no blocks of nodes of this length, allocate one
let o=this.S,p=h=this.length<<this.L|1;
this.push(new DataView(new ArrayBuffer(o)));
for(this.cost+=o;(o-=l)>-1;)this.setI32(p,p+=l,0);// pointer to next free block
p-l>h&&this.setI32(p-l,0,0)
}
this.Free[l]=this.getI32(h,0);
return h
}
free(p,l){
this.setI32(p,this.Free[l<MIN_ALLOC?l=MIN_ALLOC:l],0);
this.Free[l]=p
}
}
//(de)compressor
async function TreeCM(A,mo,done,rate=a=>a){
function pb(c){
B=B<<1|c&1;
if(B>-1)O[o++]=255&B,B=255<<24
}
function gb(){
if((B<<=1)>-1)B=255<<24|A[o++];
L=(L*2|B>>7&1)>>>0
}
if(!(A instanceof Uint8Array))A=new Uint8Array(A);
if(typeof done!="function")done=a=>a;
let a=0,z=A.length,y=z,o=1,on=0,p0=3,undo=!(mo<MAXORDER_LIMIT&&mo>=0),st=Date.now(),
L=0,R=0x80000000,B=255<<24,C=192<<24,N=z,O=[mo&=31];//RangeCoder
//header
if(undo){
for(C=A[z=B=0],mo=C&31,C>>=5,N=1;z+=A[o++]*N,C--;)N*=256;//read size
for(O=new Uint8Array(z),a=32;--a;)gb()
}else for(;N-=O[o++]=255&N;N/=256)O[0]+=32;//write size
const M=new MemoryPool(z),wait=self.wait0||setTimeout,fn=a=>wait(a),pass=typeof rate=="function"?4095:-1,
T=undo?O:A,F=new Float64Array(a=CNUM),SSE=[],G=new Uint8Array(mo+=2),I=new Int32Array(mo),P=new Int32Array(mo--),
//bit coder
rcBit=undo?(S,f,t)=>{//decode
f=f*SCALE/t>>>0||1;t=SCALE;
if(f>mSCALE)f=mSCALE;
let X={};
f=SSEip(S,t-f,X);
let c=L*t/R>>>0,b=0|c>=f;
if(c=b)c=f,f=t-f;
let r=R-((t-c)*R/t>>>0)>>>0,n=R-((t-c-f)*R/t>>>0)>>>0;
for(L-=r,R=n-r;R<0x80000000;R+=R)gb();
SSEiup(b,S_wrA*128+S_wrB,X);
return b
}:(S,f,t,b)=>{//encode
f=f*SCALE/t>>>0||1;t=SCALE;
if(f>mSCALE)f=mSCALE;
let X={},c=0;
f=SSEip(S,t-f,X);
if(b)c=f,f=t-f;
let r=R-((t-c)*R/t>>>0)>>>0,n=R-((t-c-f)*R/t>>>0)>>>0;
for(L+=r,R=n-r;R<0x80000000;L=L<<1>>>0,R+=R)
if((r=L>0xffffffff)||L>>0>-1){
C>>0>-1&&pb(r^C);
for(r^=1;N;N--)pb(r);
C=2*(C&0xff000000)|L>>0<0
}else++N;
SSEiup(b,S_wrA*128+S_wrB,X)
};
for(;a;)SSE[F[--a]=a]=SSEi(13,S_mw);
for(P.root=newNode(M,0);a<z;on<mo&&on++){
let i=-1,c,f,p,s,t;
for(;i<on;){//context mixing
p=getSlotValue(M,P,G,I,++i);
c=bitcount[M.getU16(p,4)];
if(c===1)c=bitcount[M.getU16(p,HEADER_SIZE)];
if(t=M.getU32(p,0))
s=i<<2,s=coef[s|c===1]/(1+coef[s+2]+t/(coef[s+3]+1))>>>0,
s&&mixupNode(M,F,p,s*CNUM);
M.setU32(p,t+1,0)
}
for(i=s=CNUM,t=p0*i;i&&!f;t+=(f-=255&f)/256)f=F[--i];
for(s=i;i;t+=(f-(255&f))/256)f=F[--i];
qsort(F,0,s+=s<255);
if(undo)for(;;t-=f){//decode
f=F[i],f-=c=255&f,f/=256;
if(rcBit(SSE[c],f+=p0,t)){O[a++]=c;break}
F[i]=i++
}else for(c=A[a++];;t-=f){//encode
f=F[i],f-=s=255&f,f/=256;
rcBit(SSE[s],f+=p0,t,p=s===c);
if(p)break;F[i]=i++
}
for(;i<CNUM;)F[i]=i++;//reset
for(i=on+1;i;I[s]=p.s){
p=addNode(M,getSlotValue(M,P,G,I,--i),c,a);
setSlotValue(M,P,G,I,i,p.p);
s=M.getI32(p.p,(p.g<<1)+HEADER_SIZE+(p.s<<2))
if(s<0){
s&=0x7fffffff;
if(s<a-1){
s=addNode(M,newNode(M,1),T[s],s+1).p;
M.setI32(p.p,s,(p.g<<1)+HEADER_SIZE+(p.s<<2))
}else on=i-1
}
P[s=i+1]=p.p;G[s]=p.g
}
a&pass||Date.now()-st<200||await new Promise(fn,st=Date.now(rate(a,z)))
}
if(!undo){
let c=L,h=c+R,s=1,t,x=L>0xffffffff,d=x*0x100000000,i=32,p=i;
for(;i--;s+=s+1)if(d+(t=(c|s)>>>0)<h&&-t<h)c=t,p--;
i=C^x;L=c;C>>0>-1&&(p||1^i)&&pb(i);
if(p||x)for(;N--;)pb(x^1);
for(;p--;L<<=1)pb(L>>>31);
for(;B>>24^-1;)pb(1)
}
done(undo?O:O=new Uint8Array(O),y,undo?z:o);return O
}
test
(async()=>{
let A=new TextEncoder().encode("じゅげむじゅげむごこうのすりきれかいじゃりすいぎょのすいぎょうまつうんらいまつふうらいまつくうねるところにすむところやぶらこうじのぶらこうじぱいぽぱいぽぱいぽのしゅーりんがんしゅーりんがんのぐーりんだいぐーりんだいのぽんぽこぴーのぽんぽこなーのちょうきゅうめいのちょうすけ"),
c=await TreeCM(A,15),
d=await TreeCM(c,-1);
console.log(A.length,"->",c.length,"->",new TextDecoder().decode(d))
})()