整数列を小さくしたい時に役立たずで便利な方法を紹介します。例によって圧縮と関連する記事となります。programはJavaScript様で記述しますが、他言語への移植も容易でしょう。
実装編
Range Coder
entropy符号で有名なRange Coder様を活用します(ちなみに桁上がり有りの面倒臭い版)
class RangeCoder{
constructor(In, isDec){
this.B=this.N=this.L=0;
this.R=-1>>>0;
if(isDec)
this.A=In,
this.L=(In[0]<<24|In[1]<<16|In[2]<<8|In[this.a=3])>>>0;
else this.A=[], this.a=-1
}
//符号化の仕上げ
flush(){
for(var{A,B,N,L,a}=this, b=5, c;b--;L=L<<8>>>0)
if((c=0xffffffff<L)||255>L>>>24)
for(A[a++]=255&c--+B, B=L>>>24;N;N--)
A[a++]=255&c;
else++N;
return A
}
//累積頻度c, 頻度f, 合計頻度tを元に符号化
encode(c, f, t){
var r=this.R/t>>>0, l=this.L+r*c;
for(r*=f;r<16777216;r*=256, l=l<<8>>>0)
if((c=0xffffffff<l)||255>l>>>24)
for(this.A[this.a++]=255&c--+this.B, this.B=l>>>24;this.N;this.N--)
this.A[this.a++]=255&c;
else++this.N;
this.R=r, this.L=l
}
// 確率 p/(1<<P) でbit b(0 or 1)を符号化
encodeBit(b, p, P=12){
p*=this.R>>>P, P=this.L+=-b&p;
p=p+(-b&this.R-p-p)>>>0;
for(;p<16777216;p*=256, P=P<<8>>>0)
if((b=0xffffffff<P)||255>P>>>24)
for(this.A[this.a++]=255&b--+this.B, this.B=P>>>24;this.N;this.N--)
this.A[this.a++]=255&b;
else++this.N;
this.R=p, this.L=P
}
// min以上max以下の数値vを符号化
encodeValue(min, max, v){
for(let u;max-min>65535;v>u?min=u+1:max=u)
u=min+(max-min>>>1), this.encodeBit(v>u,1,1);
min^max&&this.encode(v-min, 1, max-min+1)
}
//復号用(頻度合計tから累積頻度返す)
getCumFreq(t){
for(var R=this.R;R<16777216;R*=256) this.L=(this.L<<8|this.A[++this.a])>>>0;
return this.L/(this.R=R/t>>>0)>>>0
}
decode(c, f){this.L-=this.R*c, this.R*=f}
// 確率 p/(1<<P) で1 bit復号
decodeBit(p, P=12){
for(var{L,R}=this;R<16777216;R*=256) L=(L<<8|this.A[++this.a])>>>0;
p*=R>>>P;
if(P=L>=p)R-=p, L-=p;
else R=p;
this.R=R, this.L=L;
return P
}
// min以上max以下の数値を復号
decodeValue(min, max){
for(let u;max-min>65535;this.decodeBit(1,1)?min=u+1:max=u)
u=min+(max-min>>>1);
if(min^max) this.decode(max=this.getCumFreq(max-min+1),1), min+=max;
return min
}}
符号化処理ではRangeCoderのinstance生成時に引数不要です
符号化
RC=new RangeCoder;
復号処理では第一引数に符号化された配列、第二引数にtrueとみなせる値を放り込む
復号
RC=new RangeCoder(array,1);
使用例
function enc(){
let rc=new RangeCoder;
for(let a=256;a--;)rc.encodeValue(0,256,a);
return rc.flush()
}
function dec(In){
let rc=new RangeCoder(In,1);
for(let a=256;a--;)console.log(rc.decodeValue(0,256))
}
let e=enc(), d=dec(e)
整数列の符号化/復号
ここからが本番。この実装では数列の長さは1<<32未満、整数全体の合計値は1<<53未満、整数範囲は0以上1<<31未満。
function log2b(a,b,c){
c=(65535<a)<<4,c|=b=(255<(a>>>=c))<<3,c|=b=(15<(a>>=b))<<2;return(c|=b=(3<(a>>=b))<<1)|a>>b>>1
}
//符号化の核
function hits(coder, Int, size, sum){
let Hit=new Float64Array(33), Sum=new Float64Array(33);
let p=size, min=sum, max=sum;
for(;p;)Hit[log2b(Int[--p]+1)]++;
for(let i=0, a=1, b=2;i<33&&size>0;){
let f=Hit[i++], l=max/(b-1)>>>0;
coder.encodeValue(l<size?size-l:0, size-(size*(b-2)<min)>>>0, f>>>0);
min-=f*(b-2), max-=f*(a-1);
a*=2, b*=2, size-=f
}
for(let i=33, a=(1<<30)*4, b=a*2, s=min=max=0, f;i--;b/=2)
Sum[i]=s, s+=f=Hit[i], min+=f*(a-1), max+=f*(b-2), a/=2;
for(;sum;){
let i=0, a=1, b=2, s=Int[p++], f;
for(size=log2b(s+1);i<size;Sum[i++]--, a*=2, b*=2)
if(f=Hit[i]) coder.encode(f>>>0, Sum[i]>>>0, f+Sum[i]>>>0);
Sum[i]>0&&coder.encode(0, Hit[i]>>>0, Hit[i]+Sum[i]>>>0);
Hit[i]--, min-=--a, max-=b-=2;
coder.encodeValue(Math.max(sum-max,a)>>>0, Math.min(sum-min,b)>>>0, s>>>0);
sum-=s
}
}
//復号の核
function gets(coder, Int, size, sum){
let Hit=new Float64Array(33), Sum=new Float64Array(33);
let p=0, min=sum, max=sum;
for(let i=0, a=1, b=2, s=size;i<33&&s>0;){
let l=max/(b-1)>>>0, f=coder.decodeValue(l<s?s-l:0,s-(s*(b-2)<min)>>>0);
min-=f*(b-2), max-=f*(a-1);
a*=2, b*=2, s-=Hit[i++]=f
}
for(let i=33, a=(1<<30)*4, b=a*2, f, s=min=max=0;i--;b/=2)
Sum[i]=s, s+=f=Hit[i],
min+=f*(a-1), max+=f*(b-2), a/=2;
for(;p<size;){
let i=0, a=1, b=2, f;
for(;Sum[i]>0;Sum[i++]--, a*=2, b*=2)
if(f=Hit[i]){
if(coder.getCumFreq(f+Sum[i]>>>0)<f){
coder.decode(0,f>>>0);break
}
coder.decode(f>>>0,Sum[i]>>>0)
}
Hit[i]--, min-=--a, max-=b-=2;
sum-=Int[p++]=coder.decodeValue(Math.max(sum-max,a)>>>0, Math.min(sum-min,b)>>>0)
}
}
//圧縮main関数
function uintEncode(In){
let RC=new RangeCoder;
let sum=0, size=In.length, b=0;
for(let a=size;a;)sum+=In[--a];
for(let a=sum;a-=a&1;a/=2)++b;
RC.encodeValue(0,52,b); //sumのbit数 刻印
RC.encodeValue(b&&2**b,2**++b-1,sum); //sum 刻印
b=Math.log2(size)|0;
RC.encodeValue(0,31,b); //sizeのbit数 刻印
RC.encodeValue(b&&1<<b,2**++b-1,size); //size 刻印
sum&&hits(RC, In, size, sum); //整数列符号化
return RC.flush()
}
//伸張main関数
function uintDecode(In){
let RC=new RangeCoder(In,1);
let b=RC.decodeValue(0,52), sum=RC.decodeValue(b&&2**b,2**++b-1);
b=RC.decodeValue(0,31);
let size=RC.decodeValue(b&&2**b,2**++b-1);
let Int=new Uint32Array(size);
sum&&gets(RC, Int, size, sum);
return Int
}
では256個の8～31 bitsのまばらな整数列の圧縮実験
test
for(let i=24;i;){
let A=[], a=0, b=8+i--;
for(let c=256, d;c--;A[a++]=2**d+Math.random()*~d|0) d=Math.random()*b|0;
a=uintEncode(A);
document.write(b-1," bits x 256 to ",a.length," bytes, decoding ",uintDecode(a).every((a,b)=>a===A[b])&&"ok","<br>",A,"<hr>")
}
しょぼい? いまいち? ぽんこつ? いえいえ、それ程でもありませんよ。
活用術
静的Range Coder等のように頻度表を効率良く圧縮する場合に利用できるかもしれません。静的huffman符号でも使えない事はないですが、その場合頻度表より符号長を圧縮するのが一般的。