適応型Huffman符号

今回紹介するのは適応型Huffman符号(FGK法)となります。かつて一世を風靡しまくらなかった有名な手法なので、御存じない方も多いことでしょう。
この手法はhuffman木が成り立つための必要十分条件として「全ての節は必ず2つの子を持ち、それぞれに重みの小さい順に番号を付けたとき、2つの子の番号は連続しており、且つ親の節の番号は子の節の番号よりも大きくなる」が成り立つことを利用しています。この条件は、兄弟条件と呼ばれています。

実装

huffman木はTypedArrayで構築。そうする事でとても高速になります。sonはhuffman木の左右の子、dadはその親節、hitは各節の重みを指します。huffman木に無い記号を符号化する時は、escape記号を符号化してからCBT符号で記号を符号化。そしてhuffman木に記号を登録。などとアレコレやるとうまい具合に圧縮できます。

const ESC=256,ROOT=ESC|512;
// huffman tree
function Tree(max){
	if(max&=-1)this.max=max;
	var a=this.son=new Uint16Array(ESC*7+10);
	a[0]=ROOT;
	this.dad=a.subarray(max=ESC*2+3);
	this.leaf=a.subarray(max*=2);
	(this.hit=a.subarray(max+ESC+1))[0]=1
}
Tree.prototype={next:1,max:4096,
// It is called to increment the count for a given symbol. After incrementing the symbol, this code has to work its way up through the dad nodes, incrementing each one of them. That is the easy part. The hard part is that after incrementing each dad node, we have to check to see if it is now out of the proper order. If it is, it has to be moved up the Tree into its proper place
update:function(c){
	c=this.leaf[c];
	var P=this.dad,C=this.son,F=this.hit,n,t,u;
	do{
		for(t=++F[n=c];n&&F[n-1]<t;--n);
		if(c>n)t=C[c],u=C[n],C[c]=u,C[n]=t,
			t>511?this.leaf[t&511]=n:P[t]=P[t+1]=n,
			u>511?this.leaf[u&511]=c:P[u]=P[u+1]=c,
			t=F[c],F[c]=F[n],F[c=n]=t
	}while(c=P[c]);
	++F[c]<this.max||this.scale()
},
// Adding a new node to the Tree is pretty simple. It is just a matter of splitting the lightest-weight node in the Tree, which is the highest valued node. We split it off into two new nodes, one of which is the one being added to the Tree. We assign the new node a weight of 0, so the Tree doesn't have to be adjusted. It will be updated later when the normal update process occurs. Note that this code assumes that the lightest node has a leaf as a son. If this is not the case, the Tree would be broken
add:function(c){
	var z=this.next+=2,n=this.leaf[c]=--z,l=--n,s=this.son;
	this.dad[n]=this.dad[z]=--l;
	s[n]=s[l];
	this.hit[n]=this.hit[l];this.hit[z]=0;
	s[z]=c|512;
	this.leaf[s[n]&511]=s[l]=n
},
// Rebuilding the Tree takes place when the counts have gone too high. From a simple point of view, rebuilding the Tree just means that we divide every count by two. Unfortunately, due to truncation effects, this means that the Tree's shape might change. Some nodes might move up due to cumulative increases, while others may move down
scale:function(){
	var i=this.next,j=i,k=i,l,n=i,w,P=this.dad,C=this.son,F=this.hit,L=this.leaf;
	for(;k;)if(C[--k]>511)C[--j]=C[k],F[j]=F[k]+1>>1;
	for(;j;F[k]=w){
		w=F[--j]=F[--i]+F[--i];
		for(C[k=l=j]&=511;w<F[++k];);
		for(k--;l<k;F[l]=F[++l])C[l]=C[l+1];
		C[k]=i}
	for(i=n;i;k>511?L[k&511]=i:P[k]=P[++k]=i)k=C[--i]
}};
/*
FGKenc(In,order,max,done,rate): 圧縮処理
@In: 要素が0～255の数値配列
@order: 文脈数(0-2)
@max: 度数最大値=(m:0-2047)*8+256
@done: 処理終了後に実行する関数. 省略すると圧縮された配列を返す関数になる
	done(O,a,z)
	@O: 圧縮された配列
	@a: @Inの要素数
	@z: @Oの要素数
	処理結果を出力するなら console.log(a,z,a/z) という具合
@rate:処理途中に実行する関数. 関数でない場合はFGKeを同期処理する
	rate(a,z)
	@a: 処理途中の位置
	@z: @Inの要素数
@return: @doneの実行結果
*/
function FGKenc(In,order,max,done,rate){
	function puts(n,c){
		for(;n>=bits;bits=8)Out[o++]=data|=(1<<bits)-1&c>>(n-=bits),data=0;
		data|=((1<<n)-1&c)<<(bits-=n)
	}
	order&=3;max&=2047;
	var sync="function"!=typeof rate,a=0,bits=3,m=(1<<order*8)-1,data=max<<5&255|order<<3,x,z=In.length,o=1,Out=[max>>3],H=[];
	done=done||function(O){return O};
	rate=rate||function(){};
	max=max*8+256;if(max<1024&&!order)max+=1024;
	function F(){
		var c,d,e,g=sync?-1:4095,l,n,t,u=sync?1/0:+new Date,E;
		for(rate(a,z);a&g||new Date-u<200;x=x<<8|c){
			t=H[x&=m]||(H[x]=new Tree(max));
			l=e=0,E=t.leaf,d=E[c=In[a++]]||E[e=ESC];
			for(n=-1;d;d=t.dad[d])n^=(d&1)<<l++;
			puts(l,n);
			if(e){ // send escape + symbol(CBT coded)
				for(n=0,l=c<256?c:c=256;l;)n+=!E[--l];
				for(e=257-(t.next>>1);e>>++l;);
				e=(1<<l)-e;n<e?--l:n+=e;puts(l,n);
				if(a>z)return puts(7,0),done(Out,z,o);
				t.add(c)
			}t.update(c)
		}setTimeout(F,0)
	}return F()
}
/*
FGKdec(In,done,rate): 伸張処理
@In: 要素が0～255の数値配列
@done: 処理終了後に実行する関数. 省略すると伸張された配列を返す関数になる
	done(O,a,z)
	@O: 伸張された配列
	@a: @Inの要素数
	@z: @Oの要素数
	処理結果を出力するなら console.log(a,z,a/z) という具合
@rate:処理途中に実行する関数.
	rate(a,z)
	@a: 処理途中の位置
	@z: @Inの要素数
return: @doneの実行結果
*/
function FGKdec(In,done,rate){
	function gets(n,c){for(;n>bits;bits=8)c|=((1<<bits)-1&data)<<(n-=bits),data=In[a++];return(1<<n)-1&data>>(bits-=n)|c}
	var sync="function"!=typeof rate,a=0,bits=0,data,mc=gets(11)*8+256,m=(1<<gets(2)*8)-1,o=0,x,z=In.length,Out=[],H=[];
	done=done||function(O){return O};
	rate=rate||function(){};
	if(mc<1024&&!m)mc+=1024;
	function F(){
		var c,e,g=sync?-1:4095,n,t,u=sync?1/0:+new Date,C;
		for(rate(a,z);a&g||new Date-u<200;x=x<<8|c){
			t=H[x&=m]||(H[x]=new Tree(mc));C=t.son;
			for(c=0;(c=C[c])<512;)c+=bits?data>>--bits&1:(data=In[a++])>>(bits=7)&1;
			c&=511;
			if(c>255){ // escaped
				for(c=e=0,n=257-(t.next>>1);n>>++e;);
				n=(1<<e)-n;e=gets(--e);
				for(e<n||(e+=e+gets(1)-n);t.leaf[c]||e--;)c++;
				if(c>255)return done(Out,z,o);
				t.add(c)
			}t.update(Out[o++]=c)
		}setTimeout(F,0)
	}return F()
}

使用例

let A=Array.from("That that is is that that is not is not is that it it is",a=>a.charCodeAt());
let e=FGKenc(A,240,1), d=FGKdec(e);
console.log(A.length,"->",e.length, String.fromCharCode(...d))

codepen召喚

See the Pen Adaptive huffman Code(FGK algo) by xezz (@xezz) on CodePen.