適応型Range符号

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

## 実装
頻度表を作る処理。`size`は文字の種類でFile処理するなら256とするのが定番。
その場合0～255の範囲に文字頻度、256～271に区間頻度、272に頻度合計を格納。
区間頻度は文字の種類を16分割した分。これは累積頻度を高速に求めるために使います。
単純に文字番号200までの累積頻度を求める場合、for loopを200回ぶん回す事になりますが、この実装だと`200/16+200%16`、つまりたったの20回ぽっちで求まります。
```js
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`は進捗処理関数
```js
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出力される分を節約する意味があります
```js
	for(;a-=Out[++o]=Cache=a&255;a/=256)Out[3]+=4;
```
頻度増加量と頻度合計の最大値を設定。大き過ぎる場合は補正
```js
	max=max<<8|255;
	if(++inc*32>max)inc=max>>5;
	if(max+inc>65534)max=65534-inc;
```
符号化loop。まず`order`が1以上なら文脈から頻度表を選択
```js
	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++]; //文字(数値)読み込み
```
累積頻度を求めます。最初に分割領域、次に該当文字の区間を走査
```js
		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`とする事で負数化回避
```js
		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の場合出力を保留
```
頻度表の更新。文字頻度と区間頻度を加算。合計値が限界突破したら全ての頻度を半減させます
```js
		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符号の最終出力
```js
	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関数呼び出した後、圧縮配列を返す
```js
	done&&done(Out,size,o);
	return Out
}
```
### 伸長部
関数定義部と変数宣言部。`In`は圧縮された配列、`done`は最後の処理関数、`rate`は進捗処理関数
```js
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);
```
頻度増加量と頻度合計の最大値を設定。大き過ぎる場合は補正
```js
	if(++inc*32>max)inc=max>>5;
	if(max+inc>65534)max=65534-inc;
```
元の大きさ読み込みと、Range符号の初期化
```js
	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以上なら文脈から頻度表を選択
```js
	for(let b,c,e,f;o<size;){
		if(order)F=Models[c=c<<8&cm|b]||(Models[c]=Base.slice());
```
累積頻度の範囲特定
```js
		Range=Range/F[ms]>>>0;//頻度合計で割る
		e=Low/Range>>>0;//上限
```
累積頻度から記号を特定。ここでは変数`b`の値
```js
		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の更新と正規化
```js
		Low-=Range*f;Range*=F[b];
		for(;Range<16777216;Range*=256)Low=(Low<<8|In[a++])>>>0;
```
頻度表更新は符号化時と同様
```js
		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
}
```
## 全貌
```js
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
}
```
試し斬り
```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,31,66,255,1,done,rate), d=await decompress(e,done,rate);
console.log(e.length, String.fromCharCode(...d))
})()
```
codepen召喚
<p class="codepen" data-height="300" data-default-tab="result" data-slug-hash="RwmxVbm" data-pen-title="Range Coder" 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/RwmxVbm">Range Coder</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>