JavaScript: binary PPM

bit単位のPPMを紹介します。byteではなくbitを予測するため、escape記号は導入しません。各bit単位の文脈が次のbit予測と確率に紐づけられるという点で[DMC]()に似ています。性能はDMC以上です。
おっと、CodePen様がしゃしゃり出てきたようです。file圧縮の絶好機到来。

<p class=codepen data-height="300" data-default-tab="result" data-slug-hash="eYaaroq" data-pen-title="binary PPM compression" 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/eYaaroq">binary PPM compression</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>

## 実装
```js
//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);
const ARI_P_BITS=12,
	DIVISOR_BITS=10,
	DIVISOR_LIMIT=1<<DIVISOR_BITS,
	RECIPROCAL_BITS=15,
	RECIPROCAL_LIMIT=1<<RECIPROCAL_BITS,

//probabilities and counts in the model
	PPM_P_BITS=22,
	PPM_C_BITS=10,
	PPM_P_SCALE=1<<PPM_P_BITS,
	PPM_C_LIMIT=1<<PPM_C_BITS,
	PPM_C_SCALE=32,
	PPM_P_MASK=PPM_P_SCALE-1<<PPM_C_BITS,
	PPM_C_MASK=PPM_C_LIMIT-1,
	PPM_P_START=PPM_P_SCALE>>1,
	PPM_C_START=PPM_C_SCALE*12,//these were hand-tuned
	PPM_C_INC=PPM_C_SCALE,

	ReciprocalTable=new Int16Array(DIVISOR_LIMIT).map((a,b)=>RECIPROCAL_LIMIT/(b+2));

function initModel(E,P){
	var c=P[0]=(PPM_P_START<<PPM_C_BITS)+PPM_C_START,i=2,n=E[0]=E[1]=1;
	for(;256>i;P[n++]=c)E[n*2]=i++,E[n*2+1]=i++;
	for(;256>n;)P[n++]=c
}
/*compress
@In: input(Array / Uint8Array)
@order: use at most `order` previous bytes as context(0-15)
@mem: use at most 4<<16+mem bytes of memory(0-15)
@p0: new node's probability bonus(0-31)
@done: call back of last process
	done(A,a,z)
	@A: compressed array of input
	@a: input size
	@z: compressed size
@rate: call back of progress
	rate(a,z)
	@a: current position
	@z: last position
@return:
	call with await: compressed array of @In
	without await: Promise object
*/
async function BPPMing(In,order,mem,p0,done=a=>a,rate){
	var a=In.length,o=1,size=a,Out=[(order&=15)|(mem&=15)<<4,p0&=31],
		Cache,FF=1,Range=-1>>>0,Low=0, // range coder
		m=256,n=1,oN=0,pb=PPM_P_BITS,ab=ARI_P_BITS,cb=PPM_C_BITS,
		pass="function"!=typeof rate?-1:8191,fn=b=>wait0(c=>b(rate(a,size))),st=+new Date;

	for(p0+=8;a;a>>>=8)Out[++o]=Cache=255&a,Out[1]+=32;// write size

	order=order*8+7,mem=1<<16+mem>>>0;
	var Extend=new Uint32Array(mem*4),Suffix=Extend.subarray(mem*2),Hit=Suffix.subarray(mem);

	for(initModel(Extend,Hit);a<size;a&pass||Date.now()-st<200||await new Promise(fn,st=+new Date))
		for(let c=In[a++],i=8,f,s;i;){
			// prediction
			let b=c>>--i&1,e=Hit[n],p=e>>>cb,l=n,r=(Range>>>ab)*((pb>ab?p>>pb-ab:p<<ab-pb)+1-(p>>pb-1));
			if(b)Range=r;
			else Range-=r,Low+=r;
			// encoding normalize
			if(Range<16777216){
				if(255>Low>>>24){
					for(r=0xffffffff<Low;Out[o++]=255&Cache+r,--FF;)Cache=255;
					Cache=Low>>>24
				}
				FF++;Low=Low<<8>>>0;Range*=256
			}
			// update models
			for(;e&=PPM_C_MASK,r=pb+RECIPROCAL_BITS-32,
				f=r>0?r:0,r=cb-DIVISOR_BITS,
				s=r>0?r:0,r=RECIPROCAL_BITS+s-f,
				s=ReciprocalTable[(e<PPM_C_LIMIT-PPM_C_INC?e+=PPM_C_INC:e=PPM_C_LIMIT-1)>>s],
				b?p+=PPM_C_SCALE*((PPM_P_SCALE-p>>f)*s>>r):p-=PPM_C_SCALE*((p>>f)*s>>r),
				Hit[n]=p<<cb|e,!Extend[n*2+b];oN-=8)
				e=Hit[n=Suffix[l=n]],p=e>>>cb;

			p=n;n=Extend[n*2+b];oN++;
			if(l^p&&oN+7<order&&m<mem)
				Hit[m]=(Hit[Suffix[m]=n]&PPM_P_MASK)+p0,
				Extend[l*2+b]=n=m++,oN+=8
		}
	for(a=5;a--;FF++,Low=Low<<8>>>0)
		if(255>Low>>>24){
			for(n=0xffffffff<Low;Out[o++]=255&Cache+n,--FF;)Cache=255;
			Cache=Low>>>24
		}
	done(Out,size,o+!size);return Out
}
/*decompress
@In: input(Array / Uint8Array)
@done: call back of last process
	done(A,a,z)
	@A: decompressed array of @In
	@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 @In
	without await: Promise object
*/
async function BPPMed(In,done=a=>a,rate){
	var a=2,o=In[0],order=(o&15)*8+7,mem=1<<16+(o>>4)>>>0,z=In.length,p0=In[1],size=0,Out=[],
		Range=-1>>>0,Low=1,
		m=256,n=1,oN=0,pb=PPM_P_BITS,ab=ARI_P_BITS,cb=PPM_C_BITS,
		pass="function"!=typeof rate?-1:8191,fn=b=>wait0(c=>b(rate(a,z))),st=+new Date;

	for(o=p0>>5;o--;Low*=256)size+=In[a++]*Low;
	if(size)for(Low=0;++o<4;)Low=(Low<<8|In[a++])>>>0;

	var Extend=new Uint32Array(mem*4),Suffix=Extend.subarray(mem*2),Hit=Suffix.subarray(mem);
	initModel(Extend,Hit);p0=(p0&31)+8;o=0;

	for(let b,c,f,s;o<size;Out[o++]=c&255){
		for(c=1;c<256;c+=c+b){
			// prediction
			let l=n,e=Hit[n],p=e>>>cb,r=(Range>>>ab)*((pb>ab?p>>pb-ab:p<<ab-pb)+1-(p>>pb-1));
			if(Low<r)Range=r,b=1;
			else Range-=r,Low-=r,b=0;
			// decoding normalize
			if(Range<16777216)Low=(Low<<8|In[a++])>>>0,Range*=256;
			// update models
			for(;e&=PPM_C_MASK,r=pb+RECIPROCAL_BITS-32,
				f=r>0?r:0,r=cb-DIVISOR_BITS,
				s=r>0?r:0,r=RECIPROCAL_BITS+s-f,
				s=ReciprocalTable[(e<PPM_C_LIMIT-PPM_C_INC?e+=PPM_C_INC:e=PPM_C_LIMIT-1)>>s],
				b?p+=PPM_C_SCALE*((PPM_P_SCALE-p>>f)*s>>r):p-=PPM_C_SCALE*((p>>f)*s>>r),
				Hit[n]=(p<<cb)+e,!Extend[n*2+b];oN-=8)
				e=Hit[n=Suffix[l=n]],p=e>>>cb;

			p=n;n=Extend[n*2+b];oN++;
			if(l^p&&oN+7<order&&m<mem)
				Hit[m]=(Hit[Suffix[m]=n]&PPM_P_MASK)+p0,
				Extend[l*2+b]=n=m++,oN+=8
		}
		o&pass||Date.now()-st<200||await new Promise(fn,st=+new Date)
	}
	done(Out,z,o);return Out
}
```
圧縮関数の引数`order`で文脈の長さ指定(0-15)。引数`mem`で記憶空間の量を指定(0-15)。大体`4<<16+mem bytes`と見積もっております。引数`p0`で確率初期値のようなものを指定。以下は圧縮と伸長の例
```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 BPPMing(A,4,6,16,done,rate), d=await BPPMed(e,done,rate);
console.log(e.length, String.fromCharCode(...d))
})()
```
## 参考文献
C++で書かれている[本家](https://github.com/valdmann/crook)。いつの間にか消滅([残骸](https://web.archive.org/web/20170217015740/https://github.com/valdmann/crook))。[某掲示板]()ではかつて生暖かい議論が展開され、痕跡を拝む事が可能