LoginSignup
0
0
@mashuel(恵瑠 真珠)

JavaScript: 圧縮力編8

Last updated at Posted at 2024-05-25

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

構造

まずは接尾辞木のようなものによって文脈を構築し、高速化を図ります。その弊害としてhuffman符号は毎回最初から作り直す羽目になります(本末転倒)が、前回の記事のものよりは遥かに高速です。
0次の文脈(初期接尾辞木)には最初から全ての文字を登録しておきます。sは文字(実装上は整数)、cは頻度とします。

let Tree=[];
for(let a=256;a;)Tree[--a]={s:a,c:1};

続いて指定次数まで木を伸ばす。sonは下位の文脈、dadは上位の文脈。

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の全体像は以下の通り。

/*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関数等を排除して書き替えて下さい。以下使用例。

(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による実践

See the Pen Adaptive Huffman with PPM by xezz (@xezz) on CodePen.

benchmark

引数のorderが4の場合

file名 元尺 圧縮後
angular-1.8.2.min.js 177376 59194(33.37%)
bootstrap-3.3.6.min.js 36868 10199(27.66%)
jquery-3.7.1min.js 87526 29623(33.84%)
react-0.13.3.js 600572 138588(23.07%)
vue-2.7.16.js 434871 105119(24.17%)

余談

Range符号版だと遥かに高速高圧縮率となります。ははは…さすがhuffman符号様、完全に下位互換になり下がる謙虚っぷりを見せつけてくれました

高速化

頻度と文字を一体化、整列を軽減等により高速化。ついでに頻度調整時に低頻度要素削除で圧縮率向上かも?

/*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])}
	}
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0