乱数圧縮もどき #JavaScript

乱数列の圧縮についてべらべらと白状していこうと思います。今回は特定の条件を満たす乱数列が対戦相手となります。その条件とは…

乱数は重複なく出現(同じ数は出現しない)
出現順はどうでもいい

例えば以下のような乱数列。256要素あります。211 bytes程度に圧縮できます。

176,83,245,139,239,183,10,26,96,253,111,7,121,59,100,160,86,51,193,181,17,166,67,203,171,161,25,243,237,196,194,62,73,184,226,167,112,34,118,128,174,0,60,195,169,173,211,113,94,145,119,244,123,198,15,68,214,156,109,131,165,140,107,134,150,168,218,240,191,201,197,180,210,44,58,22,35,5,187,47,202,9,78,52,75,163,13,14,27,222,246,16,252,92,200,132,21,114,48,143,110,84,170,190,81,79,90,249,33,158,122,76,251,70,85,102,56,254,217,80,98,72,179,147,223,3,106,129,61,105,37,45,164,104,103,18,49,19,208,28,93,192,212,149,233,236,209,232,231,248,130,152,38,213,146,219,157,64,29,182,199,230,57,71,178,220,115,206,36,46,186,127,235,151,42,89,133,238,162,11,87,148,172,188,23,117,2,8,250,88,126,6,144,155,225,221,39,97,177,55,135,229,234,136,66,54,137,142,255,215,24,108,30,175,205,91,50,138,12,63,124,1,227,53,31,242,185,74,120,125,41,241,141,69,32,207,159,204,101,43,82,224,154,95,65,189,20,99,228,77,40,116,4,216,153,247

log2(1) + log2(2) + … + log2(255) + log2(256) で計算されます(1683.9962872242131 bits)。JavaScript風に書くと以下のようになります。

for(let a=256,b=0,c;a;)
	console.log(c=b+=Math.log2(a--)," bits, ",Math.ceil(c/8)," bytes")

この処理は席替え等で行うくじ引きに例えられます。1度引いたくじは元に戻さず続行され、次はに引き当てる座席の候補はどんどん少なくなっていきます。最後のくじは引くまでもなく、どこの座席になるか確定しています。これを圧縮に当てはめると、最後の乱数は0 bitで符号化できる事を意味します。

勿論そんなどうでもいい前置きはとっととうせろ、と思われているでしょうから圧縮programにすり替えてみます。

// 圧縮
function ranCom(In){
	const CB=16,Q2=1<<CB-1,Q1=Q2>>1,Q3=Q1|Q2,Out=[],Join=[];
	let a=0,c,o=0,r,s,sum,size=In.length,
		bits=8,data=0,u=0,Low=0,High=(1<<CB)-1;// for arithmetic coder

	for(;c=a<size;Join[s]=1){
		for(s=In[a++],r=sum=size;r;)Join[--r]?sum--:r<s&&c++;
		// encoding
		r=High-Low+1;High=Low+r*c--/sum-1|0;
		for(Low+=r*c/sum|0;;Low+=Low){
			if(High<Q2){
				if(!--bits)Out[o++]=data,data=0,bits=8;
				for(;u;u--){
					data|=1<<--bits;
					if(!bits)Out[o++]=data,data=0,bits=8
				}
			}else if(Low>=Q2){
				Low-=Q2,data|=1<<--bits;
				if(!bits)Out[o++]=data,data=0,bits=8;
				for(High-=Q2;u;u--)if(!--bits)Out[o++]=data,data=0,bits=8
			}else{
				if(Low<Q1||High>=Q3)break;
				u++,Low-=Q1,High-=Q1
			}
			High+=++High
		}
	}
	u+=8,data|=(c=Low>=Q1)<<--bits;
	if(!bits)Out[o++]=data,data=0,bits=8;
	for(c^=1;u--;){data|=c<<--bits;
		if(!bits&&data)Out[o++]=data,data=0,bits=8}
	return Out}

// 復号
function ranDom(In,size){
	const CB=16,Q2=1<<CB-1,Q1=Q2>>1,Q3=Q1|Q2,Out=[],Join=[];
	let a=0,c=CB,o=0,r,s,sum,v,
		bits,data,Low=0,High=(1<<CB)-1;// for arithmetic coder

	for(;c--;)v=v<<1|(bits?data>>--bits:(data=In[a++])>>(bits=7))&1;// initialize

	for(;o<size;Join[Out[o++]=s]=1){
		for(s=sum=size;s--;)Join[s]&&sum--;

		c=r=((v-Low+1)*sum-1)/(High-Low+1)+1>>>0;
		for(;r;)Join[++s]||r--;
		// decoding
		r=High-Low+1;High=Low+r*c--/sum-1|0;
		for(Low+=r*c/sum|0;;Low+=Low){
				if(High>=Q2)if(Low>=Q2)v-=Q2,Low-=Q2,High-=Q2;
				else{
					if(Low<Q1||High>=Q3)break;
					v-=Q1,Low-=Q1,High-=Q1
				}
				High+=++High;
				v=v<<1|(bits?data>>--bits:(data=In[a++])>>(bits=7))&1
		}
	}return Out
}

実に生臭いprogramですね。ぷんぷん臭ってきやがります。非常に古典的な算術符号が垣間見えます。出現済みの数値は配列Joinに登録して、後続の数値の確率を上げていこうって寸法です。

使用例

let A=[1,11,10,13,6,4,2,12,3,0,7,5,14,9,15,8], l=A.length;
let c=ranCom(A), d=ranDom(c,l);
console.log(l,"->",c.length,d)