超huffman符号

適応型huffman符号もどきを利用した高圧縮programを紹介します。純粋な統計型手法であり、速度は全く褒められたものではありません。圧縮性能はgzipに匹敵しまくるとかしないとか…。

手口

1文字符号化/復号化するごとに最初からhuffman符号を作り直すという非常に効率の悪い事をしています。統計の取り方の都合上、そうせざるを得なくなりました。
その都合とは、過去の文脈を洗いざらい調べ尽くして文字の頻度を混合するというもの(PPMとは似て非なるもの)。この二段攻撃により想像を絶する程の低速ぶりを発揮しちゃっています。ついでに記憶空間も大量消費しやがります。
まあ実際には文脈の長さは指定した値に固定され、調べるにも限度があります。

実装

それではJavaScript様による実装を晒しておきます。低速なので非同期関数にしました。compress()とdecompress()が本体です。

//加重倍率調整配列
const coef=new Uint32Array([34304,33348,240,0,29273,128512,24,1,64128,125986,8,0,13316,40448,1,5,8768,36872,0,14,7364,65306,0,20,8716,73216,0,21,6848,88138,0,31,8145,86156,0,28,12297,84480,0,22,4864,81952,0,54,2,106496,0,232,15826,127776,0,31,20,130560,0,252,5464,130816,0,160,10368,130816,0,124,102720,130944,0,253]);

/*insert sort
@A: 整列元配列
@i: 始点
@l: 終点
*/
function isort(A,i,l){
	for(var a=i,c,j,k;i<l;A[j]=c)
		if((c=A[j=k=++i])<A[a])for(;j>a;)A[j]=A[--j];
		else for(;c<A[--k];)A[j]=A[j=k]
}
/*quick sort
@A: 整列元配列
@a: 始点
@b: 終点
*/
function qsort(A,a,b){
	if(b-a<9)return isort(A,a,b);
	var c=A[a],d,i=A[b],j=a,k=b,p=A[a+b>>1];
	c>i?c>p?p>i||(p=i):p=c:i>p?c>p&&(p=c):p=i;
	for(i=a;j<=k;)
		if((c=A[j])>p)A[j]=A[k],A[k--]=c;
		else{if(c<p)d=A[i],A[i++]=c,A[j]=d;j++}
	a<--i&&qsort(A,a,i);++k<b&&qsort(A,k,b)}

/*huffman符号召喚
@C: Array. 各要素は,下位 @N bitsに記号, 上位bitsに記号頻度.
	予め昇順に整列しておかねばならない.
	@dが偽なら最終的に各要素にhuffman符号のbit列が格納される
@L: Array. 各要素にhuffman符号のbit長が格納される
@c: @Cの要素数
@d: 真なら@Cの頻度表を返す. 偽ならhuffman符号bit列作成
@N: 記号のbit長
*/
function HuffGen(C,L,c,d,N=8){
	var M=(1<<N)-1,e=0,f,i=0,l=0,m,n,LC=[,2];
	do f=C[n=i<c&&(l==e||C[i]>>>N<=C[l]>>>N)?i++:l++],
		f-=f&M,C[n]=C[n]&M|e<<N,
		n=C[m=i<c&&(l==e||C[i]>>>N<=C[l]>>>N)?i++:l++],
		n-=n&M,C[m]=C[m]&M|e<<N,C[e]=C[e++]&M|f+n;
	while(~e+c);
	for(f=0,C[--e]&=M;e;f<l?LC[f=l]=2:LC[l]+=2)
		c=C[--e],l=C[c>>N]>>N,C[e]=c&M|++l<<N,LC[l++]--;
	for(n=l;l;l--)for(c=LC[l];c--;)L[C[e++]&M]=l;
	if(d)return LC;
	for(c=0;l<n;)LC[l]=c=c+LC[l++]<<1;
	for(e in L)C[e]=LC[L[e]-1]++
}
/*for decode
@Len: Array. 各要素はhuffman符号のbit長
@Max: Array. 復号に利用
@Pos: Array. 復号に利用
@Sym: Array. 復号される文字の表
@C: Array. @Lenの頻度表
*/
function buildCode(Len,Max,Pos,Sym,C){
	var T=[],mb=C.length-1,i=0,p=C[0]=Pos[0]=Max[0]=0,s=0,v=1<<mb;
	for(;i<mb;T[i]=Pos[i]=Pos[i-1]+C[i-1])
		p+=C[++i]<<mb-i,Max[i]=i<mb?p:v;
	for(s in Len)Sym[T[Len[s]]++]=+s;return mb
}
/*圧縮処理
@In: 圧縮元配列
@mo: 最大次数(0-15)
@lv: 探索深度(0-15). 大きくすると低速化し圧縮率が向上するかも
@mv: 真なら次数0～2の頻度最大値が小さく, 偽なら大きくなる
@done: 後処理の関数. 省略可
	done(a,b,c)
	@a: 圧縮済み配列
	@b: |In|
	@c: |a|
@rate: 進捗用関数. 省略可
	rate(a,b)
	@a: 現在の処理位置
	@b: |In|
*/
async function compress(In,mo,lv,mv,done,rate=a=>a){
    //bit書き込み
	function puts(l,n){
		for(;l>=b;b=8)O[o++]=B|=(1<<b)-1&n>>(l-=b),B=0;
		B|=((1<<l)-1&n)<<(b-=l)
	}
	let O=[(mo&=15)<<4|(lv&=15),0],
		l=In.length,a=0|Math.log2(l),c=256,o=1,use=0,t=+new Date,
		b=7,B=!mv<<7,// bit coder
		c2=In[0],c1=In[1],c0=In[2];// context bytes
	const MO=mo+1,DEPTH=c<<lv,m0=mv?65534:255,
		Use=new Uint8Array(c), Hit=new Float64Array(c),
		o0=new Uint32Array(c), o1=[], o2=[], P=[o0],// order0,1,2 model and its pointer
		Link=new Uint32Array(l), p2=[],// positions
		fn=b=>setTimeout(c=>b(rate(a,l)),0);

	for(let i=MO;i>2;)P[i--]=new Uint32Array(c);
	if(!l)return O;
	for(let i=l;i;)Use[In[--i]]=1;
	puts(5,a+1);puts(a,l^1<<a); //元の大きさ刻印
	for(a=0;a<l&&a<3;)puts(8,In[a++]);
	for(mv=mv?65534:127;c;)(o1[--c]=new Uint16Array(257))[256]=mv;

	if(l>3){ // write symbol table by RLE+gamma code
		for(puts(1,Use[0]);c<256;){
			let n=1,s=Use[c];
			for(;s&&(Use[c]=Hit[use]=use++),s==Use[++c]&&c<256;)n++;
			if(n<256)for(s=0;n>>++s;);else s=4.5,n=0;
			puts(s*2-1,n)
		}
		if(use<3){//文字3種類未満. 1種類なら何もしない
			if(use>1)for(;a<l;)puts(1,Use[In[a++]]);//2種類なら全て1 bitで符号化
			puts(7,0);return done&&done(O,l,o),O
		}
	}
	if(use<256)for(let i=l;i;)In[--i]=Use[In[i]];//元配列を必要最低限の数値に置換

	for(;a<l;a&4095||Date.now()-t<200||await new Promise(fn,t=+new Date)){
		let i=c1<<8|c0, n=c2<<8|c1, x=p2[n]||(p2[n]=new Uint32Array(256)), L=[];

		if(!o2[i])(o2[i]=new Uint16Array(257))[256]=mv;
		P[1]=o1[c0];P[2]=o2[i];

		if(MO>2)//次数3以上の文脈の統計をとる
			for(n=DEPTH,i=x[c0];i&&n--;i=Link[i])
				for(let j=2,c=In[i];j++<MO&&In[i-j]===In[a-j];)P[j][c]++;

		//文字頻度を混合
		for(i=0;i<=MO;){
			let j=use,h=0,s=0,c;
			for(n=P[i];j;)if(c=n[--j])s+=c,Use[h++]=j;
			if(!s)break;
			c=coef[4*i|h<2]/(1+coef[4*i+2]-s/~coef[4*i+++3])<<8; //混合倍率
			if(c)for(;h;n[s]*=i<4)Hit[s=Use[--h]]+=c*n[s];
			else if(i>3)for(;h;)n[Use[--h]]=0
		}
		// huffman code
		qsort(Hit,i=0,use-1);
		HuffGen(Hit,L,use);
		puts(n=L[c=In[a]],Hit[c]);
		if(n>24)throw 0; // bad code

		for(c2=c1;i<use;)Hit[i]=i++;//初期化
		Link[a]=x[c1=c0];x[c0]=a++;

		//update order0
		if(++o0[c]>m0)for(i=use;i;)o0[--i]-=o0[i]>>2; //各頻度削減
		//update order1
		x=P[1];
		if(++x[c0=c]>x[256]){
			if(x[256]<64000)x[256]+=x[256]>>6; //上限値拡大
			for(i=use;i;)x[--i]-=x[i]>>2 //各頻度削減
		}
		//update order2
		x=P[2];
		if(++x[c]>x[256]){
			if(x[256]<64000)x[256]+=x[256]>>5; //上限値拡大
			for(i=use;i;)x[--i]-=x[i]>>2 //各頻度削減
		}
	}
	if(B)O[o++]=B;return done&&done(O,l,o),O
}
/*伸長処理
@In: 伸長元配列
@done: 後処理の関数. 省略可
	done(a,b,c)
	@a: 圧縮済み配列
	@b: |In|
	@c: |a|
@rate: 進捗用関数. 省略可
	rate(a,b)
	@a: 現在の処理位置
	@b: |In|
*/
async function decompress(In,done,rate=a=>a){
	//bit読み込み
	function gets(l,n){
		n=(B>>8-b&0xffffff)>>24-l;
		for(b+=l;b>7;b-=8)B=B<<8|In[a++];
		return n
	}
	let a=1,b=0,B,c=256,d=In[0],o=d>>4,use=0,z=In.length,t=+new Date;
	const MO=++o,DEPTH=c<<(d&15),O=[],
		I=new Uint8Array(c), Hit=new Float64Array(c), Use=new Uint8Array(c),
		o0=new Uint32Array(c), o1=[], o2=[], p2=[], P=[o0],
		fn=b=>setTimeout(c=>b(rate(a,z)),0),
		// for huffman code
		Mx=new Uint32Array(25),Ps=new Uint32Array(25),Sm=new Uint8Array(c);

	for(let i=4;i--;)B=B<<8|In[a++];

	let mv=gets(1),l=gets(5),m0=mv?255:65534;

	for(;o;)P[o--]=new Uint32Array(c);
	if(!l)return done&&done(O,z,o),O;
	for(l=1<<--l|gets(l);o<l&&o<3;)O[o++]=gets(8);

	let c2=O[0],c1=O[1],c0=O[2],Link=new Uint32Array(l);

	for(mv=mv?127:65534;c;)(o1[--c]=new Uint16Array(257))[256]=mv;
	if(l>3){// read symbol table
		for(let d=gets(1),n;c<256;d^=1){
			for(n=0;n<8&&!gets(1);)n++;
			n=n<8?1<<n|gets(n):256;
			if(d)for(;n--;)Use[I[Hit[use]=use]=c++]=use++;else c+=n
		}
		if(use<3){
			if(use<2)for(c=Use[0];o<l;)O[o++]=c;
			else for(;o<l;)O[o++]=Use[gets(1)];
			return done&&done(O,z,o),O
		}
	}
	for(let i=3;i;)O[--i]=Use[O[i]];
	for(;o<l;o&4095||Date.now()-t<200||await new Promise(fn,t=+new Date)){
		let i=c1<<8|c0, n=c2<<8|c1, x=p2[n]||(p2[n]=new Uint32Array(256)), L=[];

		if(!o2[i])(o2[i]=new Uint16Array(257))[256]=mv;
		P[1]=o1[c0];P[2]=o2[i];

		if(MO>2)
			for(i=x[c0],n=DEPTH;i&&n--;i=Link[i])
				for(let j=2,c=O[i];j++<MO&&O[i-j]===O[o-j];)P[j][c]++;

		for(i=0;i<=MO;){
			let j=use,h=0,s=0,c;
			for(n=P[i];j;)if(c=n[--j])s+=c,Use[h++]=j;
			if(!s)break;
			c=coef[4*i|h<2]/(1+coef[4*i+2]-s/~coef[4*i+++3])<<8;
			if(c)for(;h;n[s]*=i<4)Hit[s=Use[--h]]+=c*n[s];
			else if(i>3)for(;h;)n[Use[--h]]=0
		}
		// decode huffman code
		qsort(Hit,i=0,use-1);n=255&Hit[use-1];
		d=buildCode(L,Mx,Ps,Sm,HuffGen(Hit,L,use,1));
		c=(B>>8-b&0xffffff)>>24-d;
		for(n=L[n];c>=Mx[n];)++n;
		for(b+=n;b>7;b-=8)B=B<<8|In[a++];
		c=Sm[Ps[n]+(c-Mx[n-1]>>d-n)];

		for(c2=c1;i<use;)Hit[i]=i++;
		Link[o]=x[c1=c0];O[x[c0]=o++]=c;
		//update order0
		if(++o0[c]>m0)for(i=use;i;)o0[--i]-=o0[i]>>2;
		//update order1
		x=P[1];
		if(++x[c0=c]>x[256]){
			if(x[256]<64000)x[256]+=x[256]>>6;
			for(i=use;i;)x[--i]-=x[i]>>2
		}
		//update order2
		x=P[2];
		if(++x[c]>x[256]){
			if(x[256]<64000)x[256]+=x[256]>>5;
			for(i=use;i;)x[--i]-=x[i]>>2
		}
	}
	if(use<256)for(use=o;use;)O[--use]=I[O[use]]; //置換表で復元
	return done&&done(O,z,o),O
}

続いて使用例

(async()=>{
let A=Array.from("That that is is that that is not is not is that it it is",a=>a.charCodeAt());
let rate=(a,b)=>{console.log((a/b*1e4|0)/100,"%")}, done=(a,b,c)=>{console.log(b,"->",c,a)};
let e=await compress(A,7,6,0,done,rate), d=await decompress(e,done,rate);
console.log(String.fromCharCode(...d))
})()

fileの圧縮と伸長を実践したい人はcodepenでどうぞ。100KB以上のfileになると、もはや使い物にならない程度には役に立たない不便利な奴です。

See the Pen Adaptive Huffman code with context mixing by xezz (@xezz) on CodePen.