次数1の静的huffman符号

次数1の静的huffman符号による圧縮programを紹介します。これはつまり1文字前の文字でhuffman符号を切り替えるというものです。適応型huffman符号ではお馴染みの手法ですが、静的huffman符号で実装するのは厄介です。
と言うのも圧縮文に符号長、あるいはhuffman木自体を刻印しなければならず、最大で256文字分 x 256個となり、工夫しないと大幅な圧縮率の低下を招くからです。
今回はとっても古典的なhuffman木刻印版のようなものを実装。存分に、なんなりと期待しないで下さい。

実装編

JavaScriptで書き散らかしました。

/*圧縮関数
@In: Array/Uint8Array. 圧縮元配列
@return: Array
*/
function o1HuffEncode(In){
	//bit書き込み
	function putBits(bl,bn){
		for(;bl>=bitc;bitc=8)
			Out[op++]=Bits|(1<<bitc)-1&bn>>(bl-=bitc),Bits=0;Bits|=((1<<bl)-1&bn)<<(bitc-=bl)
	}
	//huffman木刻印
	function writeTree(c,Left,Right,Mark,Use){
		if(c<256){//記号はCBT符号化
			let a=Use[c],b=0;
			for(Mark[a]=1;a;)b+=!Mark[--a];
			for(;use>>++a;);
			c=(1<<a)-use--;b<c||(++a,b+=c);
			putBits(a,b)
		}else putBits(1,1),
			writeTree(Left[c],Left,Right,Mark,Use),
			writeTree(Right[c],Left,Right,Mark,Use)
	}
	function downheap(i,Heap,Hit,s){
		for(var j,k=Heap[i];(j=2*i)<=s&&Hit[k]>Hit[Heap[j<s&&Hit[Heap[j]]>Hit[Heap[j+1]]&&++j||j]];Heap[i]=Heap[i=j]);
		Heap[i]=k
	}
	function makeTree(Hit,Use){
		var a=-1,c,j,k,s=0,v=255,Heap=[,0],Dad=[],Left=[],Right=[];
		//heapを構築
		for(;a<v;)if(Hit[++a])Heap[++s]=a;
		for(a=s>>1;a;)downheap(a--,Heap,Hit,s);

		//huffman木を構築(最小頻度の2つのnodeを結合)
		for(k=Heap[1];s>1;Dad[Right[k]=j]=-k)
			a=Heap[1], Heap[1]=Heap[s--], downheap(1,Heap,Hit,s),
			Hit[k=++v]=Hit[a]+Hit[j=Heap[1]],
			Left[Heap[1]=Dad[a]=k]=a, downheap(1,Heap,Hit,s);

		//huffman符号を生成
		for(j=0;(s=j)<256;Hit[j]=c,Heap[j++]=v)
			for(c=v=0;s=Dad[s];v++)if(s<1)s=-s,c|=1<<v;
		use=cs;writeTree(k,Left,Right,[],Use);
		Hit.L=Heap
	}
	var a=0,bitc=8,Bits,c=0,d=0,size=In.length,op=0,use=-1,cs=0,
		o1=[],Out=[],Use=[];
	//write size
	for(;size>>++d;);
	putBits(5,d);putBits(d,size);
	//build context
	for(;a<size;o1[c][c=In[a++]]++,Use[c]=1)if(!o1[c])o1[c]=new Uint32Array(512);
	for(c in Use)if(!o1[c])(o1[c]=[])[c]=1;	// dummy
	//write exist context
	for(putBits(1,Use[a=0]);c=a<256;putBits(d*2-1,c)){
		for(d=!o1[a];d==!o1[++a]&&a<256;)c++;
		if(c<256)for(d=0;c>>++d;);
		else c=0,d=4.5
	}
	for(;++use<256;)Use[use]&&(Use[use]=cs++);
	//build huffman code
	for(a=c=d=0;c<256;c++)o1[c]&&makeTree(o1[c],Use);
	//huffman encoding
	for(;a<size;d=c)putBits(o1[d].L[c=In[a++]],o1[d][c]);
	if(Bits)Out[op]=Bits;
	return Out
}
/*展開関数
@In: Array/Uint8Array. 圧縮された配列
@return: Array
*/
function o1HuffDecode(In){
	//bit読み込み
	function getBit(){return bitc?Bits>>--bitc&1:(Bits=In[a++])>>(bitc=7)&1}
	function getBits(bl,bn){
		for(;bl>bitc;bitc=8)bn|=((1<<bitc)-1&Bits)<<(bl-=bitc),Bits=In[a++];
		return(1<<bl)-1&Bits>>(bitc-=bl)|bn
	}
	//huffman木読み込み
	function readTree(Tree,Mark,n){
		if(getBit()){
			Tree[n=c++<<1]=readTree(Tree,Mark);
			Tree[n|1]=readTree(Tree,Mark);
			return n>>1
		}//read new symbol
		let a=n=0,b;
		for(;use>>++a;);
		b=(1<<a)-use--;a=getBits(--a);
		for(a<b||(a+=a+getBit()-b);Mark[n]||a--;)n++;
		Mark[n]=1;
		return Use[n]
	}
	var a=0,bitc=0,Bits,size=getBits(getBits(5)),n,c=1,i=0,o=0,use,cs=getBits(1)-1,
		Out=[],Use=[],o1=[],Tree;
	//read exist context
	for(;i<256;c^=1){
		for(n=0;n<8&&!getBit();)n++;
		for(n=n<8?1<<n|getBits(n):256;n--;i++)if(c)o1[Use[cs++]=i]=[]
	}
	for(;++n<256;)if(o1[n])use=cs,c=256,o1[n].c=readTree(o1[n],[]);
	//huffman decoding
	for(n=0;o<size;Out[o++]=n=c)
		for(Tree=o1[n],c=Tree.c;c>255;)
			c=Tree[c<<1|(bitc?Bits>>--bitc&1:(Bits=In[a++])>>(bitc=7)&1)]
	return Out
}

中古技術の総動員という有り様。復号処理はhuffman符号を1bitずつ解読するという低速な仕様。codepenで遊ぶことも可能

See the Pen data compression by order1 static huffman by xezz (@xezz) on CodePen.