JavaScript: 重みつきSplay木による圧縮

1991年4月頃にPhilip G. Gageが考案(作者はこの手法をAdaptive Huffman frequency compressionと呼称)。木の変形法はsplay符号風ですが、節点に重みを加えることで適応型huffman符号並みに均衡がとれた木となります。符号長の変化が素早いため情報の変化に追随しやすいです。いい事ずくめで人気を独占しそうですが、多分 DDJ Data Compression Contest(1991年)以外での使用例はないでしょう。

実装

そんな前置きはどうでもいいかもしれないので、本題にすり替えていきます。何はともあれ、木を表すobjectの定義から。

// 配列もどき
function Hit(){}//頻度
function Up(){}//親節

/*
重みつきsplay木
@max: 重み最大値
@up: 加重値
@cs: 記号の最大値
*/
function Tree(max,up,cs){
	this.F=new Hit;
	this.U=new Up;
	this.inc=up||1;
	this.max=max||1000;
	if(cs)this.cs=cs>>>0
}

Hit()とUp()は木の初期化を高速化するためだけのごみです。これらのprototypeに予め初期値を放り込んでおけば、new Hit、new Upとするだけで初期値の詰まった擬似配列が降臨します。木を何本も生成する場合は多大な恩恵を受けることでしょう。

符号木の節は配列で表します。cs が記号の種類、this.Uが親節の番号、this[i] が左の子の番号、this[i+cs] が右の子の番号を表します。記号の種類が cs の場合、葉の個数が cs になるので、節の個数は cs-1 個になります。U の大きさは 2*cs-1 になりますが、左と右は節の部分だけが必要なので大きさは cs-1 になります。

で、ただのsplay木との違いは重みがある点。this.Fがそうです。this.incで加重値、this.maxで限界重量を指定します。これらは圧縮率や速度に大きく影響します。因みに重みは整数でも小数でも構いませんが、負数にするととんでもない目に遭います。小数の方が若干圧縮率は良くなるかもしれません。

符号木は均一に初期化します。節の番号を N とすると、次式で初期化すると、木は均衡になります。

節 N :
左の子	:2*N+1
右の子	:2*N+2
親	:N-1>>1

例えば、記号の種類が 256 の場合、0～254 が節で、255～510 が葉になります。節の番号を x とすると、x が 0～254 の範囲では、親を (x-1)/2 に、左 を 2x+1 に、右 を 2x+2 に初期化します。255～510 の範囲では、親 を (x-1)/2 に初期化します。これで記号 0～255 の符号語長は 8 に初期化されます。

全貌

// 配列もどき
function Hit(){}//頻度
function Up(){}//親節

/*
重みつきsplay木
@max: 重み最大値
@up: 加重値
@cs: 記号の最大値
*/
function Tree(max,up,cs){
	this.F=new Hit;
	this.U=new Up;
	this.inc=up||1;
	this.max=max||1000;
	if(cs)this.cs=cs>>>0
}
/*
初期化関数. 符号長を均一にする
@cs: 扱う記号の最大値
*/
function init(cs){
	var i=0,l=cs*2+1,U="prototype",H=Hit[U],T=Tree[U];
	for(U=Up[U];i<cs;T[i++]=i*2)
		T[i+cs]=i*2+1, U[i]=i-1>>1, H[i]=1;
	for(T.cs=cs;i<l;H[i++]=1)U[i]=i-1>>1
}
Tree.prototype={
// 木の更新
update:function(a){ // a:記号
	var b,c,e,n=this.cs, U=this.U, F=this.F, u=U[a+=n];
	F[a]+=this.inc;
	if(u){ // aの親が根ではない
		this.sum(a,this[(this[u]==a)*n+u],F,U);
		do if(F[a]>F[b=this[(this[e=U[u]]===u)*n+e]]){
			this[(this[e]===u)*n+e]=a;
			if(this[u]==a)this[u]=b,c=this[u+n];
			else this[u+n]=b,c=this[u];
			U[a]=e;U[b]=u;
			this.sum(a=b,c,F,U)
		}while(u=U[a=U[a]]); // 根に到達したか
		if(F[0]>this.max) // 累積頻度が限界. 全ての重みを半減
			for(a=n*2;a--;)F[a]/=2 // F[a]>>=1やF[a]-=F[a]>>1 とすれば整数化(圧縮率は変化)
	}
},
// 内部節点の重み計算
sum:function(a,b,F,U){
	for(var n=this.cs;;b=this[(a===this[b=U[a]])*n+b]){
		F[U[a]]=F[a]+F[b];a=U[a];
		if(!a)break // 根に到達
	}
}};
/*
圧縮関数
@In: Array/Uint8Array等. 圧縮元配列
@up: 加重値(0-63)
@max: 重み最大値(0-255)
@order: 次数(0-3)
@cs: 記号の最大値(0-255)
@return: Array
*/
function compress(In,up,max,order,cs){
	//bit列書き込み
	function puts(l,n){
		for(;l>=bits;bits=8)
			Out[o++]=data|=(1<<bits)-1&n>>(l-=bits),data=0;
		data|=((1<<l)-1&n)<<(bits-=l)
	}
	var a=0,o=4,h=In.length,size=h,bits=8,data,
		Out=[(order&=3)|(up&=63)<<2,max&=255,cs&=255,size&63],
		T=new Tree(max=max*8+7,++up,cs),o0=T,Tx=[],
		N=new Uint32Array(32); //stack
	init(cs);
	Tree.prototype.encode=function(s){
		var a=s+cs,i=0,n=N[0]=0;
		do{
			N[n]|=(a==this[(a=this.U[a])+cs])<<i++; //葉から根の経路をbit列化
			if(i>31)N[++n]=i=0 //32 bits以上はstackに追加
		}while(a);
		for(puts(i,N[n]);n;)puts(32,N[--n]); //まとめて書き出し
		this.update(s)
	};
	for(let n=6;h>>>=n;n=8)Out[o++]=h&255,Out[3]+=64; //元の大きさ刻印
	for(let m=(1<<order*8)-1,c;a<size;h=h<<8|c){
		c=In[a++];
		if(order)
			if(Tx[h&=m])T=Tx[h];
			else T=o0,(Tx[h]=new Tree(max,up,cs)).update(c);
		T.encode(c)
	}
	if(data)Out[o]=data;
	return Out
}
/*
伸長関数
@In: Array/Uint8Array等. 圧縮元配列
@return: Array
*/
function decompress(In){
	Tree.prototype.decode=function(){
		// 1bitずつ読み葉までの経路を辿る
		for(var c=0;(c=this[((bits?data>>--bits:(data=In[a++])>>(bits=7))&1)*cs+c])<cs;);
		this.update(c-=cs);
		return c
	};
	var a=4,c=6,h,m=In[0],size=In[3],max=In[1]*8+7,cs=In[2],o=0,up=m>>2,order=m&3,bits,data,
		O=[],T=new Tree(max,++up,cs),o0=T,Tx=[];
	init(cs);
	if(m=size>>6)for(size&=63;m--;c+=8)size+=In[a++]<<c; //元の大きさ
	for(m=(1<<order*8)-1;o<size;O[o++]=c){
		if(Tx[h&=m])T=Tx[h],c=T.decode();
		else T=o0,(Tx[h]=new Tree(max,up,cs)).update(c=T.decode());
		h=h<<8|c
	}return O
}

我ながらclass使えよと突っ込みたくなる…

実行例

var A=Array.from("That that is is that that is not is not is that it it is",a=>a.charCodeAt());
var c=compress(A,1,30,0,255), d=decompress(c);
console.log(c.length, String.fromCharCode(...d))

codepenで試し切り。関数は若干仕様変更あり(callback搭載等)

See the Pen Splay Tree Frequency Code by xezz (@xezz) on CodePen.

性能評価

圧縮率は適応型huffman符号に匹敵。超える事もざらにあります。ただし速度は褒められたものではありません。もっと高速であれば注目に値したかも。

それから、重みの増加率や重みの半減期等、いじくり回す設定値は山ほどあり、圧縮率はそれらに敏感に反応します。使いこなすには訓練と経験が欠かせないかも。

splay木は極端に偏るのが得意なので、符号長が33以上になったり、へたすると256になったりする事もあります。

参考文献

ddjcompr.zipとかいう書庫内のsixpack.cにその実装例があります。LZ法と組み合わせられている模様。本記事の薄汚い書き方よりは理解がはかどるかも?