JavaScript: 565 bytesの圧縮展開program

たかが565 bytesですが圧縮率は概ねgzipを超えるという代物です。圧縮原理はBlock sorting(BWT) + Move to front + 2値Range coderとなります。
BWTは組み込み関数のArray.prototype.sortだけで実装しているので、反復だらけの入力に対しては低速です。まあ一般的な文書に対してはそれなりに高速じみています。

実装編

ちょっと読みやすいかもしれないですが、以下のようなprogramだ! 制御文字てんこ盛りなのでbase64符号化してあります。

base64

Zm9yKFc9J1tpRisrRUlbRGZvcihDO0NCQjtBYV1APWkfe0MeMjUdPXAcT1sbLGkaPj4+GRkyNBg8PDgXU1thRRYtLRU9bhRsPDw9OCwTPURAGhI7KRFbFWldEEVdPQ89Uz0+HnZhciBpDjtyPXIXfB01KQxGXQs9W10sCXJldHVybiAISS5zb3J0KChhGik9PgcXfBZdBjtpEVQLPVQQO1QLHAUbbw9yGAQ7cD1sKyhyLWwZMTIpKlALLGI9dhkDLEkJTwlQCVQJYT0dNixiLGMscCxsLG4fLHYsbz0wLHIUO2ERUFtUWxVAPUA9OBdBAixQCy09UAstKGI8PDEyKT4+NSxiP3IcOmwcKzEaKx8rYilDOyEoKGxecikYKQwTAVcOPVMubGVuZ3RoAmkRSRAfQgcebBQ7bBURaWYocD0WJW5dLVNGRSVuXSkIcH0pO2E8bjtEYQ9TEClpEnx8KGw9YRoUKUFvPDgMG28PbBgsEwRBYRURHnASPTA7VAtecBFpRUJ2HwVCYz04Gj0xO2MDFWMmMQEEfQQ7CE99O1gOAmE8ODtvFBQGKWM9YwZBbhEeaT0xO2k8HTYDMDwcGTABdj12BkIbRBVuXRRdHD1URiY9HTVdBX1DUwkHG0AtTwspO2k8bxFTRg8bYz1EY11dOwhTfSc7WD0vWwEtH0AtRl0vLmV4ZWMoVyk7KXdpdGgoVy5zcGxpdChYKSlXPWpvaW4oc2hpZnQoKSk7ZXZhbChXKQ

base64復号すると565 bytesのprogramが降臨し、eval(...)の中を展開すると以下のような884 bytesの圧縮関数と展開関数が具現化。

W=S=>{for(var i=S.length,I=[],O=[],P=[],T=[],a=256,b,c,p,l,n=i,v,o=0,r=n;a;)P[T[--a]=a]=8<<8;for(;i;)I[--i]=i;for(I.sort((a,i)=>{for(l=n;l--;)if(p=S[a++%n]-S[i++%n])return p});a<n;I[a++]=S[--i])i=I[a],i||(l=a,i=n);for(;o<8;r=r<<8|255)O[o++]=l>>>24,l<<=8,O[o++]=r>>>24;for(;a--;){for(p=I[a],i=0;T[i]^p;)i++;for(v=i;i;)T[i]=T[--i];T[i]=p;for(c=8,i=1;c;p=l+(r-l>>>12)*P[i],b=v>>>--c&1,P[i]-=P[i]-(b<<12)>>5,b?r=p:l=p+1,i+=i+b)for(;!((l^r)>>>24);r=r<<8|255)l<<=8,O[o++]=r>>>24}O[o++]=r>>>24;return O};
X=S=>{for(var i,I=[],O=[],P=[],T=[],a=256,b,c,p,l,n=i,v,o=0,r=n;a;)P[T[--a]=a]=8<<8;for(;a<8;o=n=n<<8|S[a++])c=c<<8|S[a++];for(;n;){for(i=1;i<256;p=l+(r-l>>>12)*P[i],b=v>>>0<=p>>>0,P[i]-=P[i]-(b<<12)>>5,b?r=p:l=p+1,i+=i+b)for(;!((l^r)>>>24);r=r<<8|255)l<<=8,v=v<<8|S[a++];for(O[I[--n]=n]=p=T[i&=255];i;)T[i]=T[--i];T[i]=p}for(S=[],I.sort((a,i)=>O[a]-O[i]);i<o;)S[i++]=O[c=I[c]];return S}

関数Wが圧縮、関数Xが展開を担って下さいます。無駄な初期化がちらほら見受けられますが、関数を圧縮する為の小細工です。WとXの引数はArrayかUint8Array、返り値はArrayです(要素は0～255の整数)。
web application(html)にすると765 bytes。file圧縮と展開を実装。例によってbase64符号化してあります(復号すると制御文字てんこ森沢山)。undoを有効にすると展開処理、無効なら圧縮処理。newをclickすると成果物をdonwloadできます。多分。

base64

PHN2ZyBvbmxvYWQ9J2ZvcihfPWBbaX4rK1pJW1lmb3IoWDtYV1c7VmFdTj1pTXtYSzI1SnJyYXlIZmlsZUcgaWQ9Rj1wRU9bRCxpQz4+Ph8fMjQePDw4HVNbYVocY2hlY2sbaW5wdXQaLS0ZPW4YbDw8PTgsFyB0eXBlPRZuZXcgFT1ZTkMUOykTWxlpXRJaXT0RPBpGED1TPT5LdmFyIGkPO3I9ch18SjUpDn5dDD1bXSwLcmV0dXJuIAlJLnNvcnQoKGFDKT0+CBVVaW50OEFIKAcdfBxdBjtpE1QMPVQSO1QMRQVEbxFyHgQ7cD1sKyhyLWwfMTIpKlAMLGI9dh8DLEkLTwtQC1QLYT1KNixiLGMscCxsLG5NLHYsbz0wLHIYO2ETUFtUWxlOPU49OB1WAixQDC09UAwtKGI8PDEyKT4+NSxiP3JFOmxFKzFDK00rYilYOyEoKGxecikeKQ4XARBrFhtib3g+dW5kbxBmFkcgb24aPSJBDz1TLmxlbmd0aAJpE0kSTVcIS2wYO2wZE2lmKHA9HCVuXS1Tflolbl0pCXB9KTthPG47WWERUxIpaRR8fChsPWFDGClWbzw4DkRvEWweLBcEVmEZE0twFD0wO1QMXnATaVpXdk0FV2M9OEM9MTtjAxljJjEBBH0EOwlPfTtCDwJhPDg7bxgYBiljPWMGVm4TS2k9MTtpPEo2AzA8RR8wAXY9dgZXRFkZbl0YXUU9VH4mPUo1XQV9WFMLCEROLU8MKTtpPG8TU34RRGM9WWNdXTsJU307R3NbMF0uYUhCdWZmZXIoKS50aGVuKFM9PmMuaHJlZj10b3AuVVJMLmNyZWF0ZU9iamVjdFVSTCgVQmxvYihbByhrLhtlZD9COkEpKAdTKSkpXSkpKSI+PGFGYyBkb3dubG9hZD4VYDtBPS9bXiAtQklMTy1VWy19XS8uZXhlYyhfKTspd2l0aChfLnNwbGl0KEEpKV89am9pbihzaGlmdCgpKTt3cml0ZShfKSc+

codepen召喚

See the Pen BWT+MTF+RC compressor by xezz (@xezz) on CodePen.

解説編

では変数を改名して関数どもを現代語訳していきます。Range coderは桁上がりの無い亜種を使用。圧縮処理はBWTの逆順に行います。理由は圧縮率が良くなる場合があるからです。ついでに言うと関数を圧縮しやすかったから(本音)。
元配列の大きさやBWT復元位置をRange coder用の変数に代入している点が不可解に見えますが、これも関数を圧縮しやすくするための工夫。

W=In=>{
	var Index=[],Out=[],Hit=[],MTF=[],
		i=In.length,a=256,bit,c,p,size=i,v,o=0,
		Low,Range=size;// range coder
	for(;a;)Hit[MTF[--a]=a]=8<<8;// bit統計表と記号順位表を初期化
	// BWT
	for(;i;)Index[--i]=i;
	Index.sort((a,i)=>{
		for(Low=size;Low--;)
			if(p=In[a++%size]-In[i++%size])return p
	});
	for(;a<size;Index[a++]=In[--i])
		i=Index[a],i||(Low=a,i=size);

	//元配列の大きさとBWT復号用の位置を刻印
	for(;o<8;Range=Range<<8|255)
		Out[o++]=Low>>>24,Low<<=8,
		Out[o++]=Range>>>24;

	//圧縮処理(BWTの逆順)
	for(;a--;){
		// move to front
		for(p=Index[a],i=0;MTF[i]^p;)i++;
		for(v=i;i;)MTF[i]=MTF[--i];MTF[i]=p;
		// bit単位で記号順位を符号化
		for(c=8,i=1;c;i+=i+bit){
			p=Low+(Range-Low>>>12)*Hit[i];
			bit=v>>>--c&1;
			Hit[i]-=Hit[i]-(bit<<12)>>5;
			bit?Range=p:Low=p+1;
			// normalize
			for(;!((Low^Range)>>>24);Range=Range<<8|255)
				Low<<=8,Out[o++]=Range>>>24
		}
	}
	Out[o++]=Range>>>24;return Out
};
X=In=>{
	var Index=[],Out=[],Hit=[],MTF=[],
		i,a=256,bit,pidx,p,size,v,o=0,
		Low,Range;// range coder
	for(;a;)Hit[MTF[--a]=a]=8<<8;// bit統計表と記号順位表を初期化
	// 元配列の大きさとBWT復号用の位置読み取り
	for(;a<8;o=size=size<<8|In[a++])
		pidx=pidx<<8|In[a++];
	// 展開処理
	for(;o;){
		// bit単位で記号順位を復号
		for(i=1;i<256;i+=i+bit){
			// normalize
			for(;!((Low^Range)>>>24);Range=Range<<8|255)
				Low<<=8,v=v<<8|In[a++];
			p=Low+(Range-Low>>>12)*Hit[i];
			bit=v>>>0<=p>>>0;
			Hit[i]-=Hit[i]-(bit<<12)>>5;
			bit?Range=p:Low=p+1
		}
		Out[Index[--o]=o]=p=MTF[i&=255];
		// move to front
		for(;i;)MTF[i]=MTF[--i];MTF[i]=p
	}
	// BWT復号
	Index.sort((a,i)=>Out[a]-Out[i]);
	for(In=[];i<size;)In[i++]=Out[pidx=Index[pidx]];
	return In
}

用途

js13kgames等の作品に利用したりcode golfに利用できるかも