圧縮とか区間分割

Data圧縮の前処理として、Dataの「種類が変わる境界」を統計的に検出する方法を紹介します。entropy(情報量)、文脈の統計等を計算する事により、ぼちぼちええ感じに圧縮区間を分割する事が可能。文法圧縮やBWT等に効果的。

実装編

例によってJavaScript

const ALPHABET_SIZE=256,LOWER_BOUNDARY=24576,
	//対数近似表。n*log(n) のような情報量計算を高速化するために事前計算
	nlog2=new Int32Array(4096).map((a,b)=>Math.log2(b)*65536),
	//1変化したときのentropy変化量を事前計算. (n+1)*log2(n+1) - n*log2(n)
	Deltab=((a,b=new Int32Array(a))=>{for(let c=a=>(Math.log2(a)*65536|0)*a;a;)b[--a]=c(a+1)-c(a);return b})(4096),

getEntropy=n=>{
	if(n<0x1000)return nlog2[n]*n;
	if(n<0x100000)return(524288+nlog2[n>>8])*n;
	if(n<0x10000000)return(1048576+nlog2[n>>16])*n;
	return(1310720+nlog2[n>>>20])*n
},
getDelta=n=>{
	if(n<0x1000)return Deltab[n];
	if(255&n^255){
		if(n<0x100000)return 524288+nlog2[n>>8];
		if(n<0x10000000)return 1048576+nlog2[n>>16];
		return 1310720+nlog2[n>>>20]
	}
	return getEntropy(n+1)-getEntropy(n)
}
blockSize=(model,In,n)=>{
	let{Ctx,CtxHit}=model,bs=n,e=0;
	Ctx.fill(0);CtxHit.fill(0);
	//文脈modelの構築
	for(let c=0,i=0,s;i<n;c=255&c<<5^s)
		s=In[i++],Ctx[c<<8|s]++;
	//初期entropy計算
	for(let a=ALPHABET_SIZE,c,f,s;a--;e+=getEntropy(CtxHit[a]=c))
		for(c=0,s=ALPHABET_SIZE;s;e-=getEntropy(f))c+=f=Ctx[a<<8|--s];
	//最適分割点の探索
	for(let c=0,i=0,s,E=e-(e/32)-805306368;i<n;c=255&c<<5^s){
		if(e<E)E=e,bs=i;
		s=In[i++];
		e+=getDelta(--Ctx[c<<8|s])-getDelta(Ctx[c<<8|s|65536]++);
		e-=getDelta(--CtxHit[c])-getDelta(CtxHit[c|256]++)
	}
	return bs
},
getSegment=(model,In,n,segments,k)=>{
	if(n<LOWER_BOUNDARY||k<2){segments[0]=n;return 1}
	let bs=blockSize(model,In,n);
	if(bs==n){segments[0]=n;return 1}
	let l=getSegment(model,In,bs,segments,k-1);
	return l+getSegment(model,In.subarray(bs),n-bs,segments.subarray(l),k-l)
},
blockSplit=(In,n,segments,k)=>{
	if(n<LOWER_BOUNDARY||k<2){segments[0]=n;return 1}
	if(n>In.length)n=In.length;
	return getSegment({Ctx:new Int32Array(1<<17),CtxHit:new Int32Array(1<<9)},In,n,segments,k)
}

blockSize

1. 入力値を1byteずつ読み、5 bit shiftした文脈ごとに各byteの出現頻度を求める
2. 全体のentrypy(情報量)を計算
3. 先頭から1byteずつ進みながら、残り区間のentropyを差分更新。entropyが最も小さくなる位置(最も均質になる点)を block size として返す。閾値 entropy - entropy/32 - 805306368 を下回る最初の位置が最良分割点

getSegment

• 再帰的に入力を二分割していきます
• blockSize()で最良の分割点を見つけ、左右それぞれを再帰処理
• k(最大segment数)に達するか、区間が小さすぎると再帰を停止

blockSplit

処理の大元。

• In

  区間分割対象。TypedArray(今回の実装ではUint8Array)を指定

• n

  最大区間幅。In.length以下を指定

• segments

  区間分割の幅を格納する配列。TypedArray(今回の実装ではInt32Array)を指定

• k

  segments.length的なものを指定(最大分割数)

無圧縮のtar file等をぶち込んでみて下さい。text file(js, css, html等)、binary file(exe, dll, wav等)を混合しておくと効果は顕著。textareaに分割幅を表示します。input要素には分割総数を表示

test

document.write`<input id=f type=file>分割数<input id=bn><textarea id=bs style="display:block;width:99%;height:80%"></textarea>`;
f.onchange=A=>{
	with(new FileReader)
		readAsArrayBuffer(f.files[0]),onload=A=>{
			A=new Uint8Array(result);
			let z=A.length,B=new Uint32Array(256);
			bn.value=blockSplit(A,z,B,B.length);
			bs.value=B
		}
}

benchmark

我が流派が生み出したヘッポコ圧縮programで試してみます。複数fileを個別圧縮、書庫にして単区間圧縮、書庫にして可変区間圧縮(今回の実装)、3種の結果の一例。ちなみに書庫は無圧縮独自形式で作成

files	個別圧縮	書庫単区間	書庫可変区間
canterbury(12 file)	503287	526115	503881
calgary(19 file)	858328	879783	850626

可変区間にした効果は充分に出ているようです

参考program

libbsc