JavaScript: 圧縮とかPPM star

今回の圧縮法解説もどきは、PPM starを紹介します(以後PPM*と表記)。基本的なPPMは探す記号列の長さ(文脈の次数)の最大値を設定して処理しますが、PPM*ではほぼ無制限です。
つまりその時点で存在する最長の文脈から探索処理を開始するのです。そのため、より高い精度で記号の予測が行えると考えられます。
しかし次数がどこまでも伸びる分、空間消費量が激しくなりそうな、ヤバげな気配を感じます。速度的にも不安にならざるを得ません。

実装編

そんなPPM*をどのように実装するかと言うと、context trieや接尾辞木のようものを使います。
文脈の次数はShortest Deterministic Context(SDC)により選択します。
通常は、最長一致文脈から符号化を行いますが、最長一致文脈が決定性文脈(予測される記号が1種類だけ)であり、かつ低次の文脈においても決定性文脈が存在する場合、これらの文脈における最小次数の文脈から符号化を開始するという作戦です。
それでは素人でも分かりずらくJavaScriptに翻訳していきます。

構造体的な奴

// 文脈
context={
	s:null, // 下位の文脈
	n:null, // 先頭node
	l:0, // 文脈長
	cs:-1 // 記号数
}
// 内部節点(連結list)
node={
	s:NaN, // 記号
	c:0, // 頻度
	n:null, // 後続のnode
	son:null // 後続の文脈
}

全貌

//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);

function Suffix(){this.root=this.point={l: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={l:p.l+1,cs:-1};
	// maxからmedまでのstateに新規edge追加
	for(;p!==q;p=p.s){
		t={s:s,c:0,son:c},p.cs++;
		if(e=p.n)t.n=e.n,e.n=t;
		else p.n=t
	}
	if(p){n=f;// medからminまでのstateがsymbolのedgeを持っていないか探索.無ければ新しいedgeを追加
		s:for(m=l;p!==l;p=p.s){
			t=p.n;
			do if(e=t,e.s===s){m=p;n=e;break s}while(t=e.n);
			e.n={s:s,c:0,son:c},p.cs++
		}
		e=n,q=e.son;
		if(~p.l+q.l){// eの後続 qが不正なものならqを複製
			u=r={s:q.s,l:p.l+1,cs:q.cs};
			for(t=q;t=t.n;)u=u.n={s:t.s,c:t.c>>1,son:t.son};
			for(q.s=c.s=r;e.son=r,p=p.s;){
				for(e=p.n;e.s^s;)e=e.n;
				if(e.son!==q)break
			}
		}else c.s=q;
		// update hit count
		if(m!==l)
			for(p=m,e=n;;){
				if(e.c>254)for(t=p.n;t.c>>=1,t=t.n;);
				e.c++;
				if((p=p.s)===l)break;
				for(e=p.n;e.s^s;)e=e.n
			}
		if(f.c>254)for(t=l.n;t.c>>=1,t=t.n;);
		f.c+=2
	}else c.s=sa.root;
	sa.point=c
}
/* 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.s){
				// deside order by Shortest Deterministic Context
				for(m=q=p;(q=q.s)&&q.cs===p.cs;)p=q;

				for(q=p.n,e=t=0;q;q=q.n)
					if(!E[r=q.s])
						f=q.c+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--;

			// encoding by range coder
			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=[],E=[],s2r=[],r2s=[],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.s){
				for(m=q=p;(q=q.s)&&q.cs===p.cs;)p=q;
				for(q=p.n,e=0;q;q=q.n)
					if(!E[r=q.s])
						C[e+1]=C[s2r[r2s[e]=r]=e++]+q.c+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))
})()

file処理実験

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

参考文献

最古の実装?
本記事の元ねた