JavaScript: 圧縮とかPPM star(2)

前回に引き続きPPM starの記事となります。前回は最短の決定性文脈(SDC)を選択して符号化を開始していました。しかしこの方法は巨大連長や巨大反復の処理に莫大な時間を要するという問題があります。
そこでLocal Order Estimation(LOE)も導入します。何じゃそら? 大雑把に言うと、幾つかの値を評価して、低次数を目指すかどうか決めます。

実装編

文脈情報に記号頻度合計値sumを追加。連結listの先頭は常に最高頻度の記号を配置。これはほぼ原作に近い変更。そして幾つかproperty改名。

function Suffix(){this.root=this.point={size:0,sum:0,cs:-1}}

// 木更新
function update(sa,s){
	var e,f=sa.fit,p=sa.max,q=sa.med,l=sa.min,m,n,r,t,u,
		c={size:p.size+1, sum:0, cs:-1};// new context
	// maxからmedまでのstateに新規edge追加
	for(;p!==q;p=p.dad){
		t={symbol:s, hit:0, son:c},
		p.sum++;p.cs++;
		if(e=p.next)
			if(e.hit)t.next=e.next,e.next=t;
			else p.next=t,t.next=e;
		else p.next=t
	}
	if(p){n=f;// medからminまでのstateがsymbolのedgeを持っていないか探索.無ければ新しいedgeを追加
		s:for(m=l;p!==l;p=p.dad){
			t=p.next;
			do if(e=t,e.symbol===s){m=p;n=e;break s}while(t=e.next);
			e.next={symbol:s, hit:0, son:c};
			p.sum++;p.cs++
		}
		e=n,q=e.son;
		if(~p.size+q.size){// eの後続 qが不正なものならqを複製
			let a=0,b;

			u=r={dad:q.dad, size:p.size+1, cs:q.cs};
			for(t=q;t=t.next;a+=b)
				u=u.next={symbol:t.symbol, hit:b=t.hit>>1, son:t.son};
			r.sum=a;
			for(q.dad=c.dad=r;e.son=r,p=p.dad;){
				for(e=p.next;e.symbol^s;)e=e.next;
				if(e.son!==q)break
			}
		}else c.dad=q;
		// update hit count
		if(m!==l)
			for(p=m,e=n;;){
				if(e.hit>254)for(t=p.next,p.sum=0;p.sum+=t.hit>>=1,t=t.next;);
				t=p.next;p.sum++;
				if(++e.hit>t.hit)
					u=e.hit,e.hit=t.hit,t.hit=u,
					u=e.symbol,e.symbol=t.symbol,t.symbol=u,
					u=e.son,e.son=t.son,t.son=u;
				if((p=p.dad)===l)break;
				for(e=p.next;e.symbol^s;)e=e.next
			}
		if(f.hit>254)for(t=l.next,l.sum=0;l.sum+=t.hit>>=1,t=t.next;);
		t=l.next;l.sum+=2;
		if((f.hit+=2)>t.hit)
			u=f.hit,f.hit=t.hit,t.hit=u,
			u=f.symbol,f.symbol=t.symbol,t.symbol=u,
			u=f.son,f.son=t.son,t.son=u;
	}else c.dad=sa.root;
	sa.point=c
}
//setImmediateもどき
(function(a){
	var F=[],hit="\0";
	a.wait0=function(f){
		F[F.length]=f;a.postMessage(hit,"*")
	};
	a.onmessage=function(e){
		if(e.source===a&&e.data===hit)
			e.stopPropagation(),F[0]&&F.shift()()
	}
})(this);
/* compressor
@A	:input(Array / Uint8Array)
@done: call back of last process.
	done(A,a,z)
	@A: compressed array of input
	@a: last position
	@z: compressed size
@rate: call back of progress
	rate(a,z)
	@a: current position
	@z: last position
@return:
	call with await: decompressed array of @A
	without await: Promise object
*/
async function PPMSenc(A,done=a=>a,rate){
	var a=-1,e,f,h,l,m,o=-1,p,q,r,s,t,u,x,z=A.length,
		L=0,R=-1>>>0,B=0,C=0,O=[],
		E=[],sa=new Suffix,st=+new Date;

	const pass=typeof rate=="function"?8191:-1,fn=b=>wait0(c=>b(rate(a,z)));

	for(;a<z;update(sa,s)){
		p=sa.max=sa.point;
		sa.med=sa.min=sa.fit=u;
		s=++a<z?A[a]:256;E.length=x=0;
		do{
			if(p=p.dad){
				// deside order by Shortest Deterministic Context / Local Order Estimation
				for(m=q=p;(q=q.dad)&&(q.size*2>p.size?~p.next.hit*(~q.cs*2-q.sum)<=~q.next.hit*(~p.cs*2-p.sum):q.cs===p.cs);)p=q;

				for(q=p.next,e=t=0;q;q=q.next)
					if(!E[r=q.symbol])
						f=q.hit+1,r^s||(l=f,h=t),t+=f,e++,E[r]=q;
				if(!e)continue;

				x+=e;e=p.cs+1;
				e=(e+1<<8)-e*e>>8;// P(escape)
				if(q=E[s])sa.min=p,sa.med=m,sa.fit=q,t+=e;
				else h=t,t+=l=e
			}else for(l=q=1,h=r=s,t=257-x;r;)E[--r]&&h--;
			R=R/t>>>0;L+=R*h;
			for(R*=l;R<16777216;R*=256,L=L<<8>>>0)
				if((f=L>0xffffffff)||255>L>>>24)
					for(O[o++]=255&f--+B,B=L>>>24;C;C--)O[o++]=255&f;
				else++C;
		}while(!q);
		a&pass||Date.now()-st<200||await new Promise(fn,st=+new Date)
	}
	for(a=5;a--;L=L<<8>>>0)
		if((f=L>0xffffffff)||255>L>>>24)
			for(O[o++]=255&f--+B,B=L>>>24;C;C--)O[o++]=255&f;
		else++C;
	done(O,z,o);return O
}
/* decompressor
@A	:input(Array / Uint8Array)
@done: call back of last process.
	done(A,a,z)
	@A: decompressed array of input
	@a: last position
	@z: decompressed size
@rate: call back of progress
	rate(a,z)
	@a: current position
	@z: last position
@return:
	call with await: decompressed array of @A
	without await: Promise object
*/
async function PPMSdec(A,done=a=>a,rate){
	var a=0,e,m,o=0,p,q,r,s,t,u,x,z=A.length,
		L=0,R=-1>>>0,O=[],
		C=new Uint16Array(257),s2r=new Uint8Array(256),r2s=new Uint8Array(256),
		E=[],sa=new Suffix,st=+new Date;

	const pass=typeof rate=="function"?8191:-1,fn=b=>wait0(c=>b(rate(a,z)));

	for(;a<4;)L=(L<<8|A[a++])>>>0;
	for(;;update(sa,O[o++]=s)){
		p=sa.max=sa.point;
		sa.med=sa.min=sa.fit=u;
		E.length=x=C[0]=0;
		do{
			if(p=p.dad){
				for(m=q=p;(q=q.dad)&&(q.size*2>p.size?~p.next.hit*(~q.cs*2-q.sum)<=~q.next.hit*(~p.cs*2-p.sum):q.cs===p.cs);)p=q;
				for(q=p.next,e=0;q;q=q.next)
					if(!E[r=q.symbol])
						C[e+1]=C[s2r[r2s[e]=r]=e++]+q.hit+1,E[r]=q;
				if(!e)continue;

				x+=e;t=C[e];r=p.cs+1;r=(1+r<<8)-r*r>>8;
				s=L/(R=R/(t+r)>>>0)>>>0;
				if(s<t){
					for(t=1;t<e;)C[r=t+e>>1]>s?e=r:t=r+1;
					r=C[t];sa.min=p;sa.med=m;sa.fit=E[s=r2s[--t]];r-=t=C[t]
				}else s=-1
			}else{
				e=L/(R=R/(257-x)>>>0)>>>0;
				for(s=t=-1;E[++s]||e>++t;);
				if(s>255)return done(O,z,o),O;r=1
			}
			for(L-=R*t,R*=r;R<16777216;R*=256)L=(L<<8|A[a++])>>>0
		}while(s<0);
		o&pass||Date.now()-st<200||await new Promise(fn,st=+new Date)
	}
}

使用例

(async()=>{
let A=Array.from("That that is is that that is not is not is that it it is",a=>a.charCodeAt());
let rate=(a,b)=>{console.log((a/b*1e4|0)/100,"%")}, done=(a,b,c)=>{console.log(b,"->",c,a)};
let e=await PPMSenc(A,done,rate), d=await PPMSdec(e,done,rate);
console.log(e.length, String.fromCharCode(...d))
})()

いつものCodPen

See the Pen PPM* compressor(2) by xezz (@xezz) on CodePen.

benchmark

それではそんじょそこらの馬の骨のようなfile群を圧縮してみます。御覧のようにほぼ全てのfileで圧縮率が向上しました

file名	元尺	SDC	SDC+LOE
alice29.txt	152089	41241	40392
asyoulik.txt	125179	38491	37689
cp.html	24603	6952	6937
fields.c	11150	2671	2671
grammar.lsp	3721	1086	1086
kennedy.xls	1029744	測定不能	166907
lcet10.txt	426754	102847	100365
plrabn12.txt	481861	143888	139730
ptt5	513216	測定不能	51465
sum	38240	12093	12119
xargs.1	4227	1535	1533

js file

file名	元尺	SDC	SDC+LOE
angular-1.8.2.min.js	177366	51113	50813
bootstrap-3.3.6.min.js	36868	8115	8107
jquery-3.7.1.min.js	87526	25949	25867
react-0.13.3.js	600572	92529	91934
vue-2.7.16.js	434871	74304	73664