JavaScript: 圧縮とかNeural Network

Neural network(神経回路網?)を利用した圧縮法を紹介します。かつて最強を誇ったPAQ系列の始祖にあたる`p12`。厳密には`p5`や`p6`もありますが、まあ放置の方向で。

## やぶからぼうに実装
```js
const G=new Uint16Array(11265),Sigma2=new Uint16Array(1<<16);
(function(g,s,i,j){// initialize above
	for(;i--;)for(j=256;j;)
		s[i<<8|--j]=389.12*(i+j+1)/((.5+i)*(.5+j))|0;
	for(i=11328;i;)
		g[i-=64]=65536/(1+Math.exp(-i/1024))|0;
	for(;i<11201;i+=j)for(j=1;j<64;)
		g[i+j]=g[i]+((g[i+64]-g[i])*j++>>6)}
(G,Sigma2,256));
// setImmediateもどき
(function(a){
	var F=[],hit="\0";
	a.wait0=function(fn){
		F[F.length]=fn;
		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)
@rs: short term learning rates(0-255)
@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
*/
function P12enc(A,rs,done=a=>a,rate){
	var a=A.length,z=a,o=2,O=[rs&=255,a&31],q=32768,
		T=new Uint32Array(6),U=new Uint16Array(1<<22),V=new Int16Array(1<<22),
		s0=1,s3=0,s7=0,sw0=0,sw1=0,x1=0,x2=-1,
		wait=wait0;

	if(typeof rate!="function")rate=a=>a,wait=a=>a();

	for(a>>>=5;a;a>>=8)O[o++]=a&255,O[1]+=32;
	rs=++rs*10.24;
	function fn(){
		var b,c,d,i,j,p,n,g=G,S=Sigma2,st=+new Date;
		for(rate(a,z);a<z&&(a&4095||Date.now()-st<200);)for(j=8,c=A[a++];j;){
			p=~q&65535,n=x1,d=x2-n>>>0,
			n+=d>0xfffffff?(d>>>16)*p:d>0xffffff?(d>>12)*p>>>4:d>0xfffff?(d>>8)*p>>>8:d>65535?(d>>4)*p>>>12:d*p>>>16,
			(p=c>>--j&1)?x1=++n:x2=n,q=(p<<16)-q,b=p<<8|p^1;
			for(i=6;i;V[n]+=q*(rs+S[U[n]=d])>>16){
				d=U[n=T[--i]+s0]+b;
				if((d&255)>250||d>64255)d=d>>1&32639}
			if((s0=s0<<1|p)>255){
				if((n=s0&255)<91&&n>64||n<123&&n>96)
					sw0=sw0*997+s0>>>0;
				else{if(sw0)sw1=sw0;sw0=0}
				s7=s7<<8|s3>>>24,
				T[0]=4128768|(s3=(s3|n)<<8>>>0)&65535,
				T[s0=1]=(s3&0xffffff)%4128511,
				T[2]=s3%4128493,
				T[3]=(s3+s7*0x3000000>>>0)%4128451,
				T[4]=(sw1+sw0*29>>>0)%4128401,
				T[5]=sw0%4128409}
			for(n=0;i<6;)n+=V[T[i++]+s0];
			for(q=n>11264?65535:n<-11264?0:n<0?65535-g[-n]:g[n];!((x1^x2)>>24);x2=x2<<8|255)
				O[o++]=x2>>>24,x1<<=8
		}
		if(a<z)return wait(fn);
		for(;!((x1^x2)>>24);x2=x2<<8|255)
			O[o++]=x2>>>24,x1<<=8;O[o]=x2>>>24;
		done(O,a,o);return O
	}return fn()
}
/* 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
*/
function P12dec(A,done=a=>a,rate){
	var a=2,x=A[1],z=A.length,r=(A[0]+1)*10.24,l=x&31,o=5,O=[],q=32,
		T=new Uint32Array(6),U=new Uint16Array(1<<22),V=new Int16Array(1<<22),
		s0=1,s3=0,s7=0,sw0=0,sw1=0,x1=0,x2=-1,
		wait=wait0;

	if(typeof rate!="function")rate=a=>a,wait=a=>a();

	x>>=5;
	for(;x--;q*=256)l+=A[a++]*q;
	for(x=0,q=32768;--o;)x=x<<8|A[a++];
	function fn(){
		var b,c,d,i,p,g=G,S=Sigma2,st=+new Date;
		for(rate(a,z);o<l&&(o&4095||Date.now()-st<200);){
			p=~q&65535,c=x1,d=x2-c>>>0,
			c+=d>0xfffffff?(d>>>16)*p:d>0xffffff?(d>>12)*p>>>4:d>0xfffff?(d>>8)*p>>>8:d>65535?(d>>4)*p>>>12:d*p>>>16,
			(p=x>>>0>c)?x1=++c:x2=c,q=(p<<16)-q,b=p<<8|p^1;
			for(i=6;i;V[c]+=q*(r+S[U[c]=d])>>16){
				d=U[c=T[--i]+s0]+b;
				if((d&255)>250||d>64255)d=d>>1&32639}
			if((s0=s0<<1|p)>255){
				if((O[o++]=c=s0&255)<91&&c>64||c<123&&c>96)
					sw0=sw0*997+s0>>>0;
				else{if(sw0)sw1=sw0;sw0=0}
				s7=s7<<8|s3>>>24,
				T[0]=4128768|(s3=(s3|c)<<8>>>0)&65535,
				T[s0=1]=(s3&0xffffff)%4128511,
				T[2]=s3%4128493,
				T[3]=(s3+s7*0x3000000>>>0)%4128451,
				T[4]=(sw1+sw0*29>>>0)%4128401,
				T[5]=sw0%4128409}
			for(c=0;i<6;)c+=V[T[i++]+s0];
			for(q=c>11264?65535:c<-11264?0:c<0?65535-g[-c]:g[c];!((x1^x2)>>24);x2=x2<<8|255)
				x=x<<8|A[a++],x1=x1<<8>>>0
		}
		if(o<z)return wait(fn);
		done(O,z,o);return O
	}return fn()
}
```
`P12enc`は引数`A`を圧縮し、圧縮結果を返す。引数`rs`は学習率で0～255指定。
`P12dec`は引数`A`を展開して返す。両関数に備わっている引数`done`と`rate`は終了後処理と途中処理の関数。`rate`が関数なら非同期っぽく振る舞い、さもなければ同期処理(再帰)。
非同期になると戻り値がごみになるので、`done`で終了処理を担当。
```js:使用例
let A=Array.from("That that is is that that is not is not is that it it is",a=>a.charCodeAt());
let c=P12enc(A,5), d=P12dec(c)
console.log(c.length, String.fromCharCode(...d))
```
やぶからぼうにcodepen
<p class="codepen" data-height="300" data-default-tab="result" data-slug-hash="poXjQLV" data-pen-title="P12a compressor" 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/poXjQLV">P12a compressor</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>

## 参考文献
[Fast Text Compression with Neural Networks](https://mattmahoney.net/dc/mmahoney00.pdf)