JavaScript: Markov連鎖と圧縮

Dynamic Markov Compression(DMC)、1987年にGordon. V. CormackとR. Nigel. S. Horspoolによって考案された圧縮手法。bit単位のMarkov Modelを構築し、次のbitを予測します。PPMに似たような手法です。圧縮率は高い方で、ナメクジ並みの加速力で突き抜けていくほど速度にも定評があるかどうか定かではありません。
こんな所に誰かがCodePen様を究極召喚してやがるので、気の済むまで動作検証の限りを尽くしてもらって構いません。

See the Pen Dynamic Markov Coding by xezz (@xezz) on CodePen.

原理

wikipediaに丸投げなのじゃ。ついでにコイツでも食らっておきな!
大雑把に言うと、情報の流れ全体をMarkov連鎖で表します。符号化の過程でMarkov連鎖の構造と確率を変化させていき、各状態における次状態への遷移確率を元に符号化します(通常算術符号を用います)。
圧縮率を高めるためには、各状態における遷移確率が偏るようにMarkov連鎖の構造を変化させていく必要があります。そのため、DMCではCloningという仕組みを導入しています。

実装

本家の設計図。とっても単純明快で他言語への移植も容易でしょう。試しにIE6が全盛期の頃にJavaScriptで書いてみたんですが、初期化処理に10秒以上かかって全く使えたものではありませんでした(工夫すれば多少改善しますが)。
高速な方を晒しておきます。圧縮率は犠牲になっておられます。元ねたはPAQ8系列に組み込まれているDMC modelです。符号化には桁上がり無しの変形Range符号を使用

//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);
/*compress
@In: input(Array / Uint8Array)
@mem: memory usage(0-15). about 32<<mem+16 bytes
@p0: initial porbability(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
@return:
	call with await: compressed array of @In
	without await: Promise object
*/
async function DMCencode(In,mem,p0,done=a=>a,rate){
	var sync="function"!=typeof rate,pass=sync?-1:8191,Out=[p0&=255,mem&=15],
		a=In.length,z=a,x1=0,x2=-1>>>8,h=0,base=256,ms=mem=1<<mem+16>>>0,o=2,m=ms*=3,
		Next=new Uint32Array(m*2),Hit=new Uint32Array(m*2),
		fn=b=>wait0(c=>b(rate(a,z))),st=+new Date;

	for(Hit[0]=Hit[m]=1;a;a>>>=8)Out[o++]=255&a,Out[1]+=16;

	for(p0++;a<z;a&pass||Date.now()-st<200||await new Promise(fn,st=+new Date))
		for(let c=In[a++],i,j,k=8;k;h=Next[h]){
			let b=c>>--k&1, n=x1+(x2-x1)*Hit[ms+h]/(Hit[ms+h]+Hit[h])>>>0;
			if(n<x1)n=x1;if(n>=x2)n=x2-1;
			b?x2=n:x1=n+1;

			// encoding & normalize
			for(h+=b*ms;(x1^x2)<65536;x1=x1<<8>>>0)
				 Out[o++]=255&x2>>>16,x2=(x2<<8|255)>>>0;

			// cloning
			if(m<ms&&(i=Hit[h])>=base*2&&(j=Hit[n=Next[h]]+Hit[n+ms])-i>=base*3)
				i=i*4096/j|0,
				Hit[n]-=Hit[m]=Hit[n]*i>>12,
				Next[m]=Next[n],
				Hit[n+=ms]-=Hit[j=m+ms]=Hit[n]*i>>12,
				Next[j]=Next[n],Next[h]=m++,
				m-mem||(base=512),m-mem*2||(base=768);

			// reset models
			if(m>=ms)for(i=base=256,m=65536,h=b*ms;i--;)
				for(j=256;j;){
					Hit[n=--j<<8|i]=Hit[n+ms]=p0;
					if(i<127)Next[n]=n+i+1,Next[n+ms]=n+i+2;
					else Next[n]=i-127<<8,Next[n+ms]=i+1<<8
				}
			Hit[h]<3800&&(Hit[h]+=256)
		}
	for(;x2>255;x2<<=8)Out[o++]=255&x2>>16;
	done(Out,z,o);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 DMCdecode(In,done=a=>a,rate){
	var sync="function"!=typeof rate,pass=sync?-1:8191,Out=[],
		a=2,o=In[1],z=In.length,size=0,p0=In[0]+1,v,x1=1,x2=3,h=0,
		base=256,mem=1<<(o&15)+16>>>0,m=mem*3,ms=m,
		Next=new Uint32Array(m*2),Hit=new Uint32Array(m*2),
		fn=b=>wait0(c=>b(rate(a,z))),st=+new Date;
	for(o>>=4;o--;)size+=In[a++]*x1,x1*=256;

	for(Hit[0]=Hit[m]=1;x2--;)v=v<<8|In[a++];x2>>>=8;x1=0;

	for(;++o<size;o&pass||Date.now()-st<200||await new Promise(fn,st=+new Date)){
		let b,c=1,i,j,n;
		for(;c<256;h=Next[h]){
			n=x1+(x2-x1)*Hit[ms+h]/(Hit[ms+h]+Hit[h])>>>0;
			if(n<x1)n=x1;if(n>=x2)n=x2-1;
			if(v>n)x1=n+1,b=0,c+=c;
			else x2=n,b=1,c-=~c;

			// decoding & normalize
			for(h+=b*ms;(x1^x2)<65536;x1=x1<<8>>>0)
				v=(v<<8|In[a++])>>>0,x2=(x2<<8|255)>>>0;

			// cloning
			if(m<ms&&(i=Hit[h])>=base*2&&(j=Hit[n=Next[h]]+Hit[n+ms])-i>=base*3)
				i=i*4096/j|0,
				Hit[n]-=Hit[m]=Hit[n]*i>>12,
				Next[m]=Next[n],
				Hit[n+=ms]-=Hit[j=m+ms]=Hit[n]*i>>12,
				Next[j]=Next[n],Next[h]=m++,
				m-mem||(base=512),m-mem*2||(base=768);

			// reset models
			if(m>=ms)for(i=base=256,m=65536,h=b*ms;i--;)
				for(j=256;j;){
					Hit[n=--j<<8|i]=Hit[n+ms]=p0;
					if(i<127)Next[n]=n+i+1,Next[n+ms]=n+i+2;
					else Next[n]=i-127<<8,Next[n+ms]=i+1<<8
				}
			Hit[h]<3800&&(Hit[h]+=256)
		}Out[o]=255&c
	}
	done(Out,z,o);return Out
}

圧縮と伸長の例

(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 DMCencode(A,4,63,done,rate), d=await DMCdecode(e,done,rate);
console.log(e.length, String.fromCharCode(...d))
})()