JavaScript: 圧縮力編8

皆様お待ちかねの圧縮力の記事となってしまいました。今回はhuffman符号と部分一致予測(通称PPM)の組み合わせを紹介します。

## 構造
まずは接尾辞木**のようなもの**によって文脈を構築し、高速化を図ります。その弊害としてhuffman符号は毎回最初から作り直す羽目になります(本末転倒)が、[前回の記事](https://qiita.com/mashuel/items/02b4794e6a65d3ac9d6b)のものよりは遥かに高速です。
0次の文脈(初期接尾辞木)には最初から全ての文字を登録しておきます。`s`は文字(実装上は整数)、`c`は頻度とします。
```js
let Tree=[];
for(let a=256;a;)Tree[--a]={s:a,c:1};
```
続いて指定次数まで木を伸ばす。`son`は下位の文脈、dadは上位の文脈。
```js
for(let d=Tree[0],i=-1;d=d.son=[],d.dad=Tree,Tree=d,i++<order;)
	d=Tree[0]={s:0,c:1};
```
以上を踏まえてprogramの全体像は以下の通り。
```js
/*insert sort
@A: 整列元配列
@a: 始点
@b: 終点
*/
function isort(A,a,b){
	for(var c,i=a,j,k;a<b;A[j]=c)
		if((c=A[j=k=++a])<A[i])for(;j>i;)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の頻度表を返す(decode用). 偽ならhuffman符号bit列作成
@N: 記号のbit長
*/
function HuffGen(C,L,c,d,N=9){
	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++]&~M,
		C[n]=C[n]&M|e<<N,
		f+=C[m=i<c&&(l==e||C[i]>>N<=C[l]>>N)?i++:l++]&~M,
		C[m]=C[m]&M|e<<N,C[e]=C[e++]&M|f;
	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: 圧縮元配列
@order: 最大次数(0-15)
@done: 後処理の関数. 省略可
	done(a,b,c)
	@a: 圧縮済み配列
	@b: |In|
	@c: |a|
@rate: 進捗用関数. 省略可
	rate(a,b)
	@a: 現在の処理位置
	@b: |In|
*/
async function compress(In,order,done,rate=a=>a){
	function puts(l,c){//bit列書き込み
		for(;l>=bn;bn=8)Out[o++]=bits|=(1<<bn)-1&c>>(l-=bn),bits=0;
		bits|=((1<<l)-1&c)<<(bn-=l)
	}
	const CN=256,Join=[],Out=[order&=15],fn=b=>setTimeout(c=>b(rate(a,z)),0);
	var a=CN,o=1,z=In.length,Tree=Array(CN),Context=Tree,bits,bn=8,st=+new Date;
	//build order0
	for(;a;)Tree[--a]={s:a,c:1}; //s=文字 c=頻度
	//接尾辞木に最高次数まで文脈追加
	for(let d=Tree[0],i=-1;d=d.son=[],d.dad=Tree,Tree=d,i++<order;)
		d=Tree[0]={s:0,c:1};

	for(let b=In[a++];;){
		let Hit=[],L,c,d,i=-1,l=0,s;
		//scan model
		for(;c=Context[++i];)
			if(!Join[s=c.s])Hit[l++]=s|c.c<<9,s===b&&(d=c);

		if(l>1){//候補が2文字以上あればhuffnman符号利用
			Hit[l++]=(i+1<<8)-i*i>>8<<9|CN; //add escape code
			l<9?isort(Hit,0,l):qsort(Hit,0,l-1);
			HuffGen(Hit,L=[],l)
		}
		if(c=d){//現行文脈で符号化
			L?puts(L[b],Hit[b]):puts(1,1);
			//頻度更新
			if(255<(c.c+=2))for(c of Context)c.c-=c.c>>1;

			if(Context===Tree)Context=Tree=d.son;//最高次数だった
			else{//最高次数まで新たな文字追加
				for(i=0;Context!==Tree;Tree=Tree.dad)
					Tree.push(Join[i++]={s:b,c:1});

				//接尾辞木拡張
				if(c=d.son)Context=Tree=c;
				else d=d.son=[],d.dad=Tree,Tree=d;
				for(;--i;Tree=d)d=Join[i],d=d.son=[],d.dad=Tree;
				Join[i].son=Tree;Join.length=0
			}b=In[a++];
			a&8191||Date.now()-st<200||await new Promise(fn,st=+new Date)
		}else{
			L?puts(L[CN],Hit[CN]):puts(1,0);
			for(c of Context)Join[c.s]=1;//除外文字登録
			//低次へ移行
			do if(!(Context=Context.dad)){
				for(Out[o]=bits;!Out[o--];)Out.length--;
				done&&done(Out,z,o);return Out
			}while(!Context[i])
		}
	}
}
/*伸長処理
@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){
	const CN=256,Join=[],Out=[],fn=b=>setTimeout(c=>b(rate(a,z)),0),
		//huffman符号用配列
		Mx=new Uint32Array(25), Ps=new Uint32Array(25), Sm=new Uint16Array(CN+1);
	var a=CN,o=0,z=In.length,Tree=Array(CN),Context=Tree,bits,bn=5,st=+new Date;

	for(;a;)Tree[--a]={s:a,c:1};
	for(let d=Tree[0],i=In[0];d=d.son=[],d.dad=Tree,Tree=d,~i--;)
		d=Tree[0]={s:0,c:1};

	for(;--bn;)bits=bits<<8|In[++a];
	for(;;){
		let Hit=[],c,i=-1,l=0,s;
		//scan model
		for(;c=Context[++i];)
			if(!Join[s=c.s])Hit[l++]=c.c<<9|s,Join[s]=c;

		if(l<2){//候補が1文字だけ. escape文字含め1bitで判別
			s=(bits>>8-bn&0xffffff)>>23?Hit[0]&511:CN;
			if(++bn>7)bn=0,bits=bits<<8|In[++a]
		}else{// huffman符号復号
			Hit[l++]=(i+1<<8)-i*i>>8<<9|CN; //add escape code
			l<9?isort(Hit,0,l):qsort(Hit,0,l-1);
			c=Hit[l-1]&511;
			let L=[],d=buildCode(L,Mx,Ps,Sm,HuffGen(Hit,L,l,1));
			for(l=L[c],c=(bits>>8-bn&0xffffff)>>24-d;c>=Mx[l];)l++;
			for(bn+=l;bn>7;bn-=8)bits=bits<<8|In[++a];
			s=Sm[Ps[l]+(c-Mx[l-1]>>d-l)]
		}
		if(s<CN){//正当な文字
			d=Join[Out[o++]=s];
			//頻度更新
			if(255<(d.c+=2))for(c of Context)c.c-=c.c>>1;

			if(Context===Tree)Context=Tree=d.son;
			else{//最高次数まで新たな文字追加
				for(i=0;Context!==Tree;Tree=Tree.dad)
					Tree.push(Join[i++]={s:s,c:1});

				//接尾辞木拡張
				if(c=d.son)Context=Tree=c;
				else d=d.son=[],d.dad=Tree,Tree=d;
				for(;--i;Tree=d)d=Join[i],d=d.son=[],d.dad=Tree;
				Join[i].son=Tree
			}Join.length=0;
			o&8191||Date.now()-st<200||await new Promise(fn,st=+new Date)
		}else //低次へ移行
			do if(!(Context=Context.dad)){
				done&&done(Out,z,o);return Out
			}while(!Context[i])
	}
}
```
冒頭から`isort`やら`qsort`やら整列関数をわざわざ定義しております。組み込みの`Array.prototype.sort`使えばいいだろうという話ですが、自前の関数の方が高速だったので見送りました(browserによっては組み込み関数の方が高速かも)。

`compress`と`decompress`が圧縮/伸長関数です。圧縮側では引数`order`で速度や圧縮率を調整。範囲は0～15。基本的に大きくするほど低速化し、圧縮率は向上、記憶空間は好き放題使いまくります。処理する配列が小さい場合は`order`を上げても逆効果になりやすいです。

非同期関数にしているのは進捗表示のためです。どうでもいいと思う人はasync、Promise、引数のcallback関数等を排除して書き替えて下さい。以下使用例。
```js
(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,3,done,rate), d=await decompress(e,done,rate);
console.log(String.fromCharCode(...d))
})()
```
毎度恒例のcodepenによる実践

<p class=codepen data-height="300" data-default-tab="result" data-slug-hash="MWdjgpr" data-pen-title="Adaptive Huffman with PPM" data-user="xezz" style="height:300px;box-sizing:border-box;display:flex;align-items:center;justify-content:center;border:2px solid;margin:1em 0;padding:1em"> <span>See the Pen <a href="https://codepen.io/xezz/pen/MWdjgpr">Adaptive Huffman with PPM</a> by xezz (<a href="https://codepen.io/xezz">@xezz</a>) on <a href="https://codepen.io">CodePen</a>.</span></p><script async src="https://cpwebassets.codepen.io/assets/embed/ei.js"></script>

## benchmark
引数の`order`が4の場合
<table>
<tr><th>file名<th>元尺<th>圧縮後
<tr><td>angular-1.8.2.min.js<td>177376<td>59194(33.37%)
<tr><td>bootstrap-3.3.6.min.js<td>36868<td>10199(27.66%)
<tr><td>jquery-3.7.1min.js<td>87526<td>29623(33.84%)
<tr><td>react-0.13.3.js<td>600572<td>138588(23.07%)
<tr><td>vue-2.7.16.js<td>434871<td>105119(24.17%)
</table>

## 余談
[Range符号版](https://qiita.com/mashuel/items/9b76e0c9585dd46a834e)だと遥かに高速高圧縮率となります。ははは…さすがhuffman符号様、完全に下位互換になり下がる謙虚っぷりを見せつけてくれました

## 高速化
頻度と文字を一体化、整列を軽減等により高速化。ついでに頻度調整時に低頻度要素削除で圧縮率向上かも?
```js
/*huffman符号召喚
@C: Array. 各要素は,下位 @N bitsに記号, 上位bitsに記号頻度.
	予め昇順に整列しておかねばならない.
	@dが偽なら最終的に各要素にhuffman符号のbit列が格納される
@L: Array. 各要素にhuffman符号のbit長が格納される
@c: @Cの要素数
@d: 真なら@Cの頻度表を返す(decode用). 偽ならhuffman符号bit列作成
@N: 記号のbit長
*/
function HuffGen(C,L,c,d,N=9){
	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++]&~M,
		C[n]=C[n]&M|e<<N,
		f+=C[m=i<c&&(l==e||C[i]>>N<=C[l]>>N)?i++:l++]&~M,
		C[m]=C[m]&M|e<<N,C[e]=C[e++]&M|f;
	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: 圧縮元配列
@order: 最大次数(0-15)
@done: 後処理の関数. 省略可
	done(a,b,c)
	@a: 圧縮済み配列
	@b: |In|
	@c: |a|
@rate: 進捗用関数. 省略可
	rate(a,b)
	@a: 現在の処理位置
	@b: |In|
*/
async function compress(In,order,done,rate=a=>a){
	function puts(l,c){
		for(;l>=bits;bits=8)Out[o++]=data|=(1<<bits)-1&c>>(l-=bits),data=0;
		data|=((1<<l)-1&c)<<(bits-=l)
	}
	const CN=256,z=In.length,Hit=new Uint32Array(CN+1),Join=[],Out=[order&=15],
		cmp=(a,b)=>a.c-b.c, fn=b=>wait0(c=>b(rate(a,z)));
	var a=CN,o=1,Tree=[],Context=Tree,data,bits=8,st=+new Date;
	for(;a;)Tree[--a]={c:512+a};//reset order0
	for(let d=Tree[0];d=d.son=[],d.dad=Tree,Tree=d,~order--;)d=Tree[0]={c:512};
	for(let b=In[a++];;){
		let L,c,d,e,f,i=-1,l=0,s;
		for(;c=Context[++i];)
			if(!Join[(s=c.c)&255])Hit[l++]=s,(s&255)===b&&(d=c,e=i);

		if(l>1){//候補が2文字以上あればhuffnman符号利用
			f=(i+1<<8)-i*i>>8<<9|CN;
			for(c=0;f>Hit[c]&&++c<l;);
			for(s=l++;c<s;)Hit[s--]=Hit[s];Hit[c]=f;//insert escape code
			HuffGen(Hit,L=[],l)
		}
		if(c=d){//現行文脈で符号化
			L?puts(L[b],Hit[b]):puts(1,1);
			//頻度更新
			s=c.c+=1024;
			if(e<--i&&s>Context[e+1].c){//insertion sort
				for(;Context[e++]=Context[e],e<i&&s>Context[e+1].c;);Context[e]=c
			};
			if(s>>17){//限界なので半減させる
				if(Context.dad){
					i=0;// for order1+
					for(c of Context)e=c.c,e=c.c=e>>10<<9|e&255,e>>9&&(Context[i++]=c);
					Context.length=i
				}else for(c of Context)c.c-=c.c>>10<<9;// for order0
				Context.sort(cmp)
			}
			if(Context===Tree)Context=Tree=d.son;//最高次数だった
			else{//最高次数まで新たな文字追加
				for(i=0,b+=512;Context!==Tree;Tree=Tree.dad){
					Join[i++]=f={c:b};
					if(l=Tree.length){
						for(c=0;b>Tree[c].c&&++c<l;);
						Tree.splice(c,0,f)//insert
					}else Tree[0]=f
				}
				//接尾辞木拡張
				if(c=d.son)Context=Tree=c;
				else d=d.son=[],d.dad=Tree,Tree=d;
				for(;--i;d=d.son=[],d.dad=Tree,Tree=d)d=Join[i];
				Join[i].son=Tree;Join.length=0
			}b=In[a++];
			a&8191||Date.now()-st<200||await new Promise(fn,st=+new Date)
		}else{//fail
			L?puts(L[CN],Hit[CN]):puts(1,0);
			for(c of Context)Join[c.c&255]=1;//除外文字登録
			//低次へ移行
			do if(!(Context=Context.dad)){//done
				for(Out[o]=data;!Out[o--];)Out.length--;
				done&&done(Out,z,Out.length);return Out
			}while(!Context[i])
		}
	}
}
/*伸長処理
@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){
	const CN=256,z=In.length,Hit=new Uint32Array(CN+1),Join=[],Out=[],
		Mx=new Uint32Array(25),Ps=new Uint32Array(25),Sm=new Uint16Array(CN+1),
		cmp=(a,b)=>a.c-b.c, fn=b=>wait0(c=>b(rate(a,z)));
	var a=CN,o=0,Tree=[],Context=Tree,bits=5,data,st=+new Date;
	for(;a;)Tree[--a]={c:512+a};
	for(let d=Tree[0],i=In[0];d=d.son=[],d.dad=Tree,Tree=d,~i--;)d=Tree[0]={c:512};
	for(;--bits;)data=data<<8|In[++a];
	for(;;){
		let c,d,e,f,i=-1,l=0,s;
		for(;c=Context[++i];)if(!Join[(s=c.c)&255])Hit[l++]=s;

		if(l<2){
			s=(data>>8-bits&0xffffff)>>23?Hit[0]&511:CN;
			if(++bits>7)bits=0,data=data<<8|In[++a]
		}else{
			f=(i+1<<8)-i*i>>8<<9|CN;
			for(c=0;f>Hit[c]&&++c<l;);
			for(s=l;c<s;)Hit[s--]=Hit[s];Hit[c]=f;
			//decode huffman
			c=Hit[l++]&511;
			d=buildCode(s=[],Mx,Ps,Sm,HuffGen(Hit,s,l,1));
			for(l=s[c],c=(data>>8-bits&0xffffff)>>24-d;c>=Mx[l];)l++;
			for(bits+=l;bits>7;bits-=8)data=data<<8|In[++a];
			s=Sm[Ps[l]+(c-Mx[l-1]>>d-l)]
		}
		if(s<CN){
			Out[o++]=s;
			for(e=i;d=Context[--e],s^255&d.c;);
			l=d.c+=1024;
			if(e<--i&&l>Context[e+1].c){
				for(;Context[e++]=Context[e],e<i&&l>Context[e+1].c;);Context[e]=d
			}
			if(l>>17){
				if(Context.dad){i=0;
					for(c of Context)e=c.c,e=c.c=e>>10<<9|e&255,e>>9&&(Context[i++]=c);
					Context.length=i
				}else for(c of Context)c.c-=c.c>>10<<9;
				Context.sort(cmp)
			}
			if(Context===Tree)Context=Tree=d.son;
			else{
				for(i=0,s+=512;Context!==Tree;Tree=Tree.dad){
					Join[i++]=f={c:s};
					if(l=Tree.length){
						for(c=0;s>Tree[c].c&&++c<l;);
						Tree.splice(c,0,f)
					}else Tree[0]=f
				}
				if(c=d.son)Context=Tree=c;
				else d=d.son=[],d.dad=Tree,Tree=d;
				for(;--i;d=d.son=[],d.dad=Tree,Tree=d)d=Join[i];
				Join[i].son=Tree;Join.length=0
			}o&8191||Date.now()-st<200||await new Promise(fn,st=+new Date)
		}else{
			for(c of Context)Join[c.c&255]=1;
			do if(!(Context=Context.dad)){
				done&&done(Out,z,o);return Out
			}while(!Context[i])}
	}
}
```