JavaScript: 圧縮とかPPM star(2)

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

## 実装編
文脈情報に記号頻度合計値`sum`を追加。連結listの先頭は常に最高頻度の記号を配置。これはほぼ原作に近い変更。そして幾つかproperty改名。
```js
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)
	}
}
```
```js:使用例
(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
<p class=codepen data-height="300" data-default-tab="result" data-slug-hash="PorqgrL" data-pen-title="PPM* compressor(2)" data-user="xezz" style="height:300px;box-sizing:border-box;display:flex;align-items:center;justify-content:center;border:2px solid;margin:1em 0;padding:1em"> <span>See the Pen <a href="https://codepen.io/xezz/pen/PorqgrL">PPM* compressor(2)</a> by xezz (<a href="https://codepen.io/xezz">@xezz</a>) on <a href="https://codepen.io">CodePen</a>.</span></p><script async src="https://cpwebassets.codepen.io/assets/embed/ei.js"></script>

## benchmark
それでは[そんじょそこら](http://corpus.canterbury.ac.nz/)の馬の骨のようなfile群を圧縮してみます。御覧のようにほぼ全てのfileで圧縮率が向上しました
<table>
<tr><th>file名<th>元尺<th>SDC<th>SDC+LOE
<tr><td>alice29.txt<td>152089<td>41241<td>40392
<tr><td>asyoulik.txt<td>125179<td>38491<td>37689
<tr><td>cp.html<td>24603<td>6952<td>6937
<tr><td>fields.c<td>11150<td>2671<td>2671
<tr><td>grammar.lsp<td>3721<td>1086<td>1086
<tr><td>kennedy.xls<td>1029744<td>測定不能<td>166907
<tr><td>lcet10.txt<td>426754<td>102847<td>100365
<tr><td>plrabn12.txt<td>481861<td>143888<td>139730
<tr><td>ptt5<td>513216<td>測定不能<td>51465
<tr><td>sum<td>38240<td>12093<td>12119
<tr><td>xargs.1<td>4227<td>1535<td>1533
</table>

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