LoginSignup
0
0
お題は不問！Qiita Engineer Festa 2024で記事投稿！
Qiita Engineer Festa20242024年7月17日まで開催中！
@mashuel(恵瑠 真珠)

適応型Range符号

Posted at

今回は算術符号の一種である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.

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