JavaScript:圧縮とかtiny codec(BWT+MTF+RLE+RC)

BWT+MTF+RCの改良版です。MTFにより大量発生した0を連長圧縮させます。そうする事で圧縮率が向上します。
program自体もできる限り小さくなるように設計します。現状では圧縮と展開の関数合わせて704 bytesぽっちです。いささか大き過ぎますが、これが作者の性能の限界なのです

base64符号化(復号後704 bytes)

Zm9yKFc9JzIpfj1pSHA9R2ZvcihGO0ZFLS1EW0RpXUMrK0JCJW5dQSk7QCxpH1tpXR5UHj0dZigcaRxpG0Y7GhxTLH4pGTw8GFthXRc9MCwWZWxzZRUsOEAUMjUTHGM9EzQ8aRI7KRE9W10sEBg4fFNbQmFdOw9PW29CXT0OPj4+DDQ7cj1yGDh8EzUpC3JldHVybiAJO2kRHVRDOx1wfQhjO0dsKyhyLWwMMX4qZh4sYj0HfTthRBFmW1QXPWFdPTgYOEUGDnIMMjQFO2lEEUkeSEVJLnNvcnQoKGEfKT0+BD0oUyxjKT0+e0Z2YXIgcBZpAyxJEE8QVBBhPRM3LGIsZRZsFm5ILHYsbxZyLGYDPTE7AixmHi09Zh4tKGIYMX4+PjUsYj9yPXA6bD1wKzEfK0grYikabAwyND09cgwyC2wYPTgsAVcDPVMubGVuZ3RoAgdTDERjJjEBBQYEe0ZjPW47Y0QRaRxHU1thQS1TW2lBKQlwfUBCYTxuO0kXPVNDKWk9SRcffHwocj1hHz1uQBpvPAsFRWFIPTA7cF4TNhF7RkdJW2FCXT8/EzY7cF5UHhFpQjsbKXsaZTtlPj49MSkcMSZEZRQbPBM0KRwxK2kUFXscEzUUEiwxQGMmJhwTNTxpLDEpfUYIFUJlfRpyO3IYPTgpBTsJT307WAMCaTwHdgwwPD1wDDABdj12DwlpXmMGO2M9YTwzEW49bg8aERs9HFMsEzYpHzx+ZSs9QmkYY0I7FXtpHGUpGg5wLERlETtpEkQmJhM0PChpKz0ZJiYZYnJlYWtFDkdUHghGVBBpPW8ETxctTx5AQmk8bxEdT1tuPUlbbl1dOwlUfSc7WD0vW14gLT9JLX1dLy5leGVjKFcpOyl3aXRoKFcuc3BsaXQoWCkpVz1qb2luKHNoaWZ0KCkpO2V2YWwoVyk

上記のprogramを実行すると2つの関数が爆誕。

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

Wが圧縮関数、Xが展開関数。第1引数は配列、第2引数は無意味(関数を圧縮する為にでっち上げられたごみ)。少しだけ可読性を上げて解説も加えておきます。

/*compress
@S: array of byte
@c: empty
@return: array of byte
*/
W=(S,c)=>{
	for(var p=0,i=S.length,I=[],O=[],T=[],a=257,b,e=0,l=0,n=i,v,o=0,r,
		// binary Range Decoder
		f=(S,c)=>{for(var p=0,i=1;c;p=l+(r-l>>>12)*f[i],b=S>>>--c&1,f[i]-=f[i]-(b<<12)>>5,b?r=p:l=p+1,i+=i+b)for(;l>>>24==r>>>24;r=r<<8|255)l<<=8,O[o++]=r>>>24};a--;)f[T[a]=a]=8<<8;
	for(;i--;)I[i]=i;
	// BWT
	for(I.sort((a,i)=>{for(c=n;c--;)if(p=S[a++%n]-S[i++%n])return p});++a<n;I[a]=S[--i])i=I[a],i||(r=a,i=n);
	// BWT復元位置刻印
	for(;o<4;r=r<<8|255)O[o++]=r>>>24;
	for(a=i=0;p^256;){
		for(p=I[a++]??256;p^T[i];)i++;// 記号の順位求める
		if(i){
			for(;e;e>>=1)f(1&--e,8);// 0の連長出力
			if(i<254)f(1+i,8);
			else{f(255,8);f(c=254<i,1);c&&f(255<i,1)}
			for(;i;)T[i]=T[--i];T[i]=p // MTF
		}else++e
	}
	for(;r;r<<=8)O[o++]=r>>>24;return O
};
/*decompress
@S: array of byte
@c: empty
@return: array of byte
*/
X=(S,c)=>{
	for(var p=0,i,I=[],O=[],T=[],a=257,b,e=0,l=0,n=i,v,o=0,r,
		// binary Range Decoder
		f=(S,c)=>{for(var p=0,i=1;i<c;p=l+(r-l>>>12)*f[i],b=v>>>0<=p>>>0,f[i]-=f[i]-(b<<12)>>5,b?r=p:l=p+1,i+=i+b)for(;l>>>24==r>>>24;r=r<<8|255)l<<=8,v=v<<8|S[++a];return i^c};a--;)f[T[a]=a]=8<<8;
	for(;c=a<3;)n=n<<8|S[++a];// BWT復元位置
	for(;;)
		if(i=f(S,256),i<2)e+=++i<<c++;// 2未満は連長flag
		else{
			if(e)for(;O[o++]=p,--e;);// 連長分pを出力
			// 255+0=254, 255+1=255, 255+1+1=end
			if(c=254<i--&&254<(i+=f(S,2))&&f(S,2))break;
			for(O[o++]=p=T[i];i;)T[i]=T[--i];T[i]=p
		}
	for(T=[],i=o;i--;)I[i]=i;// index生成
	for(I.sort((a,i)=>O[a]-O[i]);++i<o;)T[i]=O[n=I[n]];// BWT復元
	return T
}

test

const A=Array.from("Peter piper picked a peck of pickled peppers. A peck of pickled peppers Peter Piper picked. If Peter Piper picked a peck of pickled peppers, Where's the peck of pickled peppers Peter Piper picked",a=>a.charCodeAt()),
enc=W(A), dec=X(enc);
console.log(A.length,"->",enc.length," decode-> ",String.fromCharCode(...dec))

ついでに展開関数のみを縮めたもの

remove dead code+minify 490 bytes

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

圧縮+base64(463 bytes)

Zm9yKFg9Jy0tFWFdFGZvcigTEzsSKysRPXAQMikPMjUOZigMOykLPDwJcmV0dXJuIAg9MCwHPT57E3ZhciBpBj4+PgU9W10sBAk4fFNbERQ7A09bSVtvXT1vEV0QAltpXQFYPVMGLEkETwRUBGE9DjYsYixjB2UHcAdsLG4sdixvB3IsZj1jBj0xLHA7aTxjO3A9bCsoci1sBTEPKmYBLGI9dgUwPBAFMCxmAS09ZgEtKGIJMQ8+PjUsYj9yEDpsECsxLGkrPWkrYikSbAUyND09cgUyNDtyPXIJOHwONSlsCT04LHY9dgMIY15pfTthFQtmW1RbFD0UPTgJODsSYTwzC249bgMSC2kMaT0MDjYpLGk8D2UrPRFpCWMRO2Vsc2V7aQxlKRICLBVlCztpDGM9DjQ8aRUmJg40PChpKz0MDykmJgwPKWJyZWFrOxMCPVQBO2kLVAE9VFsVaV07VAEQfRNUBEkuc29ydCgoYSxpKT0+T1sULU8BKTtlPG8LVFtlEV09T1tuPUlbbl1dOwhUfSc7Xz0vWwEtFV0vLmV4ZWMoWCk7KXdpdGgoWC5zcGxpdChfKSlYPWpvaW4oc2hpZnQoKSk7ZXZhbChYKQ

性能

圧縮率はbzip2を凌ぎます。ただし速度は大した事ありません。programが小さ過ぎて速度の最適化する余裕無し

用途

codegolf、外部js file爆縮、js13kgames等