適応型Range符号

今回は算術符号の一種であるRange符号を紹介。圧縮効率に優れ、1文字を1 bit未満にまで圧縮できるなんてわくわくしますね。おまけにとても高速です。そこら中で使われまくっているのも納得です。

実装

頻度表を作る処理。sizeは文字の種類でFile処理するなら256とするのが定番。
その場合0～255の範囲に文字頻度、256～271に区間頻度、272に頻度合計を格納。
区間頻度は文字の種類を16分割した分。これは累積頻度を高速に求めるために使います。
単純に文字番号200までの累積頻度を求める場合、for loopを200回ぶん回す事になりますが、この実装だと200/16+200%16、つまりたったの20回ぽっちで求まります。

function initFreq(size){
	var F=new Uint16Array(size+17),i=F[size+16]=size;
	for(;i;)F[--i]=1;
	for(;i++<16;)F[size++]=16;
	return F
}

圧縮部

関数定義部と変数宣言部。Inは圧縮元配列、incは頻度増加量(0-255)、maxは頻度限界(0-255)、csは記号最大値(0-255)、orderは文脈次数(0-3)、doneは最後の処理関数、rateは進捗処理関数

async function compress(In,inc,max,cs,order,done,rate){
	var a=In.length,o=3,size=a,
		Cache,FF=0,Range=-1>>>0,Low=0,//Range符号部品
		Out=[inc&=255,max&=255,cs&=255,order&=3],
		Base=initFreq(++cs),F=Base.slice(),Models=[],//頻度表
		ms=cs+16,cm=(1<<8*order)-1,
		x=rate?65535:-1,fn=b=>setTimeout(c=>b(rate(a,size)),0);

入力元の大きさを刻印。ここでCacheの書き替えは本来不要ですが、無駄に1 byte出力される分を節約する意味があります

	for(;a-=Out[++o]=Cache=a&255;a/=256)Out[3]+=4;

頻度増加量と頻度合計の最大値を設定。大き過ぎる場合は補正

	max=max<<8|255;
	if(++inc*32>max)inc=max>>5;
	if(max+inc>65534)max=65534-inc;

符号化loop。まずorderが1以上なら文脈から頻度表を選択

	for(let b,c,e,f,i;a<size;){
		if(order)F=Models[c=c<<8&cm|b]||(Models[c]=Base.slice());
		b=In[a++]; //文字(数値)読み込み

累積頻度を求めます。最初に分割領域、次に該当文字の区間を走査

		for(i=f=0,e=b>>4;i<e;)f+=F[i+++cs];
		for(i<<=4;i<b;)f+=F[i++];

そしてRange符号で符号化。本記事で最も肝となる部分。>>>0は負数にならないようにするまじない。正規化ではRange<<=8の代わりにRange*=256とする事で負数化回避

		Range=Range/F[ms]>>>0;//頻度合計で割る
  		Low+=Range*f;//累積頻度との積を加算
		Range*=F[b];//記号頻度との積
		//正規化
		for(;Range<16777216;Low=Low<<8>>>0,Range*=256)
			if((f=Low>0xffffffff)||255>Low>>>24){
				Out[o++]=255&f--+Cache;
				for(Cache=Low>>>24;FF;FF--)Out[o++]=255&f
			}else++FF;//Lowの上位8bitが255の場合出力を保留

頻度表の更新。文字頻度と区間頻度を加算。合計値が限界突破したら全ての頻度を半減させます

		F[b]+=inc;F[cs+(b>>4)]+=inc;
		if((F[ms]+=inc)>max){
			for(i=f=0;i<cs;F[cs+(i++>>4)]-=e)f+=F[i]-=e=F[i]>>1;
			F[ms]=f
		}
		a&x||await new Promise(fn)//進捗処理。なくても良い
	}

Range符号の最終出力

	for(let i=5,f;i--;Low=Low<<8>>>0)
		if((f=Low>0xffffffff)||255>Low>>>24){
			Out[o++]=255&f--+Cache;
			for(Cache=Low>>>24;FF;FF--)Out[o++]=255&f
		}else++FF;

callback関数呼び出した後、圧縮配列を返す

	done&&done(Out,size,o);
	return Out
}

伸長部

関数定義部と変数宣言部。Inは圧縮された配列、doneは最後の処理関数、rateは進捗処理関数

async function decompress(In,done,rate){
	var a=4,o=In[3],size=0,z=In.length,Out=[],
		inc=In[0],max=In[1]<<8|255,cs=In[2],order=o&3,
		Range=-1>>>0,Low,//Range符号部品
		Base=initFreq(++cs),F=Base.slice(),Models=[];//頻度表
	const cm=(1<<8*order)-1,ms=cs+16,
		x=rate?65535:-1,
		fn=b=>setTimeout(c=>b(rate(a,z)),0);

頻度増加量と頻度合計の最大値を設定。大き過ぎる場合は補正

	if(++inc*32>max)inc=max>>5;
	if(max+inc>65534)max=65534-inc;

元の大きさ読み込みと、Range符号の初期化

	o>>=2;
	for(let s=1;size+=In[a++]*s,o--;)s*=256;
	for(o=5;--o;)Low=(Low<<8|In[a++])>>>0;

復号loop。まずorderが1以上なら文脈から頻度表を選択

	for(let b,c,e,f;o<size;){
		if(order)F=Models[c=c<<8&cm|b]||(Models[c]=Base.slice());

累積頻度の範囲特定

		Range=Range/F[ms]>>>0;//頻度合計で割る
		e=Low/Range>>>0;//上限

累積頻度から記号を特定。ここでは変数bの値

		for(b=f=0;(f+=F[b+cs])<=e;)b++;f-=F[b+cs];
		for(b<<=4;(f+=F[b])<=e;)b++;f-=F[b];

Range、Lowの更新と正規化

		Low-=Range*f;Range*=F[b];
		for(;Range<16777216;Range*=256)Low=(Low<<8|In[a++])>>>0;

頻度表更新は符号化時と同様

		F[Out[o++]=b]+=inc;F[cs+(b>>4)]+=inc;
		if((F[ms]+=inc)>max){
			for(e=f=0;e<cs;F[(e++>>4)+cs]-=e)f+=F[e]-=e=F[e]>>1;
			F[ms]=f
		}
		o&x||await new Promise(fn)//進捗処理。なくても良い
	}
	done&&done(Out,z,o);return Out
}

全貌

function initFreq(size){
	for(var F=new Uint16Array(size+17),i=F[size+16]=size;i;)F[--i]=1;
	for(;i++<16;)F[size++]=16;
	return F
}
/*
@In :input(Array/Uint8Array)
@inc :increment of symbol counter(0-255)
@max :total symbol counter limit(0-255 => mr<<8|255)
@cs :max alphabet(0-255)
@order :context order(0-3)
@done: call back of last process.
	done(A,a,z)
	@A: compressed array of input.
	@a: input size
	@z: compressed size
@rate: call back of progress
	rate(a,z)
	@a: current position
	@z: last position
@return: Promise object or compressed @A(Array) if call with await
*/
async function compress(In,inc,max,cs,order,done,rate){
	var a=In.length,o=3,size=a,
		Cache,FF=0,Range=-1>>>0,Low=0,//range coder
		Out=[inc&=255,max&=255,cs&=255,order&=3],
		Base=initFreq(++cs),F=Base.slice(),Models=[],//models
		ms=cs+16,cm=(1<<8*order)-1,
		x=rate?65535:-1,fn=b=>setTimeout(c=>b(rate(a,size)),0);
	for(;a-=Out[++o]=Cache=a&255;a/=256)Out[3]+=4;//write |A|
	max=max<<8|255;
	if(++inc*32>max)inc=max>>5;
	if(max+inc>65534)max=65534-inc;
	for(let b,c,e,f,i;a<size;){
		if(order)F=Models[c=c<<8&cm|b]||(Models[c]=Base.slice());
		b=In[a++];Range=Range/F[ms]>>>0;
		for(i=f=0,e=b>>4;i<e;)f+=F[i+++cs];//cumulate(n/16)
		for(i<<=4;i<b;)f+=F[i++];//cumulate(n/cs)
		//encode
		Low+=Range*f;Range*=F[b];
		for(;Range<16777216;Low=Low<<8>>>0,Range*=256)
			if((f=Low>0xffffffff)||255>Low>>>24)
				for(Out[o++]=255&f--+Cache,Cache=Low>>>24;FF;FF--)Out[o++]=255&f;
			else++FF;
		F[b]+=inc;F[cs+(b>>4)]+=inc;//update
		if((F[ms]+=inc)>max){//rescale
			for(i=f=0;i<cs;F[cs+(i++>>4)]-=e)f+=F[i]-=e=F[i]>>1;
			F[ms]=f
		}a&x||await new Promise(fn)
	}
	for(let i=5,f;i--;Low=Low<<8>>>0)
		if((f=Low>0xffffffff)||255>Low>>>24)
			for(Out[o++]=255&f--+Cache,Cache=Low>>>24;FF;FF--)Out[o++]=255&f;
		else++FF;
	done&&done(Out,size,o);return Out
}
/*
@In :input(Array/Uint8Array)
@done: call back of last process.
	done(A,a,z)
	@A: decompressed array of input.
	@a: input size
	@z: decompressed size
@rate: call back of progress
	rate(a,z)
	@a: current position
	@z: last position
@return: Promise object or decompressed @A(Array) if call with await
*/
async function decompress(In,done,rate){
	var a=4,o=In[3],size=0,z=In.length,
		inc=In[0],max=In[1]<<8|255,cs=In[2],order=o&3,
		Range=-1>>>0,Low,Out=[],
		Base=initFreq(++cs),F=Base.slice(),Models=[];
	const cm=(1<<8*order)-1,ms=cs+16,
		x=rate?65535:-1,
		fn=b=>setTimeout(c=>b(rate(a,z)),0);
	if(++inc*32>max)inc=max>>5;
	if(max+inc>65534)max=65534-inc;
	o>>=2;
	for(let s=1;size+=In[a++]*s,o--;)s*=256;
	for(o=5;--o;)Low=(Low<<8|In[a++])>>>0;
	for(let b,c,e,f;o<size;){
		if(order)F=Models[c=c<<8&cm|b]||(Models[c]=Base.slice());
		Range=Range/F[ms]>>>0;e=Low/Range>>>0;
		for(b=f=0;(f+=F[b+cs])<=e;)b++;f-=F[b+cs];
		for(b<<=4;(f+=F[b])<=e;)b++;f-=F[b];
		Low-=Range*f;Range*=F[b];
		for(;Range<16777216;Range*=256)Low=(Low<<8|In[a++])>>>0;
		F[Out[o++]=b]+=inc;F[cs+(b>>4)]+=inc;
		if((F[ms]+=inc)>max){//rescale
			for(e=f=0;e<cs;F[(e++>>4)+cs]-=e)f+=F[e]-=e=F[e]>>1;
			F[ms]=f
		}o&x||await new Promise(fn)
	}done&&done(Out,z,o);return Out
}

試し斬り

(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,31,66,255,1,done,rate), d=await decompress(e,done,rate);
console.log(e.length, String.fromCharCode(...d))
})()

codepen召喚

See the Pen Range Coder by xezz (@xezz) on CodePen.