0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@mashuel(恵瑠 真珠)Team Coffee

圧縮とかContext Mixing(5)

0
Posted at

Context Mixing(文脈混合法)、その手の界隈では略してCMを利用した圧縮programを紹介します。
bit単位で確率表を組み合わせた方が圧縮率は高まりやすいですが、今回の実装ではByte単位で確率表を使います。そして速度を上げる為に木構造で確率表を構築。

  1. Memory管理

    • JavaScriptのgarbage collectionによる処理負荷を避けるため、ArrayBuffer と DataView を使いまくってC言語のような手動memory管理を行っています
    • alloc(l) で固定長の空間を確保し、free(p,l) で Free配列に戻します
    • pointerもどき(整数値 p)により、getU16 / setI32 などのmethodでmemoryを直接読み書きします

  2. 文脈木

    • 多分木(Trie)とbitmapping: 各nodeは 32 bitの頻度情報と16bitのmask(high mask, low mask)を持ち、bitcountを利用して子nodeや葉の位置を配列内の座標として計算します。これにより、memory消費量を抑えつつ高速な要素参照を実現しています
    • mixupNode で過去の統計情報(重み付けされた確率)を混合(context mixing)し、次のbyteの出現確率を動的に計算します

実装編

木構造をproperty名で表現すべき所を単にmemory上の位置で表現している為、非常に可読性が低いごみです

/*
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,MAX_TOTAL=(1<<23)-CNUM,
	MIN_ALLOC=8,LEAF_FLAG=0x80000000,HEADER_SIZE=6,//uint32 count+uint16 mask1
	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
};
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,1<<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);//prepare the next one from the list
		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){
	if(!(A instanceof Uint8Array))A=new Uint8Array(A);
	if(typeof done!="function")done=a=>a;
	let a=0,z=A.length,y=z,o=0,on=0,undo=!(mo<MAXORDER_LIMIT&&mo>=0),st=Date.now(),
		L=0,R=-1>>>0,B,C=0,N=z,O=[mo&=31];//RangeCoder
	//header
	if(undo){
		for(C=A[z=0],mo=C&31,C>>=a=5,N=1;z+=A[++o]*N,C--;)N*=256;//read size
		for(O=new Uint8Array(z);--a;)L=(L<<8|A[++o])>>>0
	}else for(;N-=B=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(CNUM).fill(1),G=new Uint8Array(mo+=2),I=new Int32Array(mo),P=new Int32Array(mo--);

	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);
			M.setU32(p,t+1,0)//update symbol count
		}
		for(t=0,i=CNUM;i;)t+=F[--i];
		if(t>MAX_TOTAL){
			for(s=0;t>>>++s>MAX_TOTAL;);
			c=(1<<s)-1;
			for(t=0,i=CNUM;i;)t+=F[--i]=F[i]+c>>>s
		}
		if(undo){//decode
			c=L*t/R>>>0;
			for(s=0;f=F[i],s+f<=c;F[i++]=1)s+=f;
			R/=t;L-=t=s*R+1>>>0;O[a++]=c=i;
			for(R=(s+f)*R-t>>>0;R<16777216;R*=256)L=(L<<8|A[++o])>>>0
		}else{//encode
			f=F[c=A[a++]];
			for(s=0;i<c;F[i++]=1)s+=F[i];
			R/=t;t=s*R+1>>>0;
			(L>>>0)+t>0xffffffff&&C++;L+=t;
			for(R=(s+f)*R-t>>>0;R<16777216;L=L<<8>>>0,R*=256)
				if(L>>24^-1||C){
					for(O[o++]=255&C--+B;N;N--)O[o++]=255&C;
					B=L>>>24;C=0
				}else++N
		}
		F.fill(1,i);
		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)for(a=5;a--;L=L<<8>>>0)
		if(L>>24^-1||C){
			for(O[o++]=255&C--+B;N;N--)O[o++]=C;
			B=L>>>24;C=0
		}else++N;
	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))
})()

codepenによる実演

See the Pen TreeCM codec by xezz (@xezz) on CodePen.

参考文献

green_v3.rar

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?