Neural network(神経回路網?)を利用した圧縮法を紹介します。かつて最強を誇ったPAQ系列の始祖にあたるp12。厳密にはp5やp6もありますが、まあ放置の方向で。
やぶからぼうに実装
const G=new Uint16Array(11265),Sigma2=new Uint16Array(1<<16);
(function(g,s,i,j){// initialize above
for(;i--;)for(j=256;j;)
s[i<<8|--j]=389.12*(i+j+1)/((.5+i)*(.5+j))|0;
for(i=11328;i;)
g[i-=64]=65536/(1+Math.exp(-i/1024))|0;
for(;i<11201;i+=j)for(j=1;j<64;)
g[i+j]=g[i]+((g[i+64]-g[i])*j++>>6)}
(G,Sigma2,256));
// setImmediateもどき
(function(a){
var F=[],hit="\0";
a.wait0=function(fn){
F[F.length]=fn;
a.postMessage(hit,"*")
};
a.onmessage=function(e){
if(e.source===a&&e.data===hit)
e.stopPropagation(),
F[0]&&F.shift()()
}
})(this);
/* compressor
@A: input(Array / Uint8Array)
@rs: short term learning rates(0-255)
@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
*/
function P12enc(A,rs,done=a=>a,rate){
var a=A.length,z=a,o=2,O=[rs&=255,a&31],q=32768,
T=new Uint32Array(6),U=new Uint16Array(1<<22),V=new Int16Array(1<<22),
s0=1,s3=0,s7=0,sw0=0,sw1=0,x1=0,x2=-1,
wait=wait0;
if(typeof rate!="function")rate=a=>a,wait=a=>a();
for(a>>>=5;a;a>>=8)O[o++]=a&255,O[1]+=32;
rs=++rs*10.24;
function fn(){
var b,c,d,i,j,p,n,g=G,S=Sigma2,st=+new Date;
for(rate(a,z);a<z&&(a&4095||Date.now()-st<200);)for(j=8,c=A[a++];j;){
p=~q&65535,n=x1,d=x2-n>>>0,
n+=d>0xfffffff?(d>>>16)*p:d>0xffffff?(d>>12)*p>>>4:d>0xfffff?(d>>8)*p>>>8:d>65535?(d>>4)*p>>>12:d*p>>>16,
(p=c>>--j&1)?x1=++n:x2=n,q=(p<<16)-q,b=p<<8|p^1;
for(i=6;i;V[n]+=q*(rs+S[U[n]=d])>>16){
d=U[n=T[--i]+s0]+b;
if((d&255)>250||d>64255)d=d>>1&32639}
if((s0=s0<<1|p)>255){
if((n=s0&255)<91&&n>64||n<123&&n>96)
sw0=sw0*997+s0>>>0;
else{if(sw0)sw1=sw0;sw0=0}
s7=s7<<8|s3>>>24,
T[0]=4128768|(s3=(s3|n)<<8>>>0)&65535,
T[s0=1]=(s3&0xffffff)%4128511,
T[2]=s3%4128493,
T[3]=(s3+s7*0x3000000>>>0)%4128451,
T[4]=(sw1+sw0*29>>>0)%4128401,
T[5]=sw0%4128409}
for(n=0;i<6;)n+=V[T[i++]+s0];
for(q=n>11264?65535:n<-11264?0:n<0?65535-g[-n]:g[n];!((x1^x2)>>24);x2=x2<<8|255)
O[o++]=x2>>>24,x1<<=8
}
if(a<z)return wait(fn);
for(;!((x1^x2)>>24);x2=x2<<8|255)
O[o++]=x2>>>24,x1<<=8;O[o]=x2>>>24;
done(O,a,o);return O
}return fn()
}
/* decompressor
@A: input(Array / Uint8Array)
@done: call back of last process.
done(A,a,z)
@A: decompressed array of input.
@a: last position
@z: decompressed size
@rate: call back of progress
rate(a,z)
@a: current position
@z: last position
*/
function P12dec(A,done=a=>a,rate){
var a=2,x=A[1],z=A.length,r=(A[0]+1)*10.24,l=x&31,o=5,O=[],q=32,
T=new Uint32Array(6),U=new Uint16Array(1<<22),V=new Int16Array(1<<22),
s0=1,s3=0,s7=0,sw0=0,sw1=0,x1=0,x2=-1,
wait=wait0;
if(typeof rate!="function")rate=a=>a,wait=a=>a();
x>>=5;
for(;x--;q*=256)l+=A[a++]*q;
for(x=0,q=32768;--o;)x=x<<8|A[a++];
function fn(){
var b,c,d,i,p,g=G,S=Sigma2,st=+new Date;
for(rate(a,z);o<l&&(o&4095||Date.now()-st<200);){
p=~q&65535,c=x1,d=x2-c>>>0,
c+=d>0xfffffff?(d>>>16)*p:d>0xffffff?(d>>12)*p>>>4:d>0xfffff?(d>>8)*p>>>8:d>65535?(d>>4)*p>>>12:d*p>>>16,
(p=x>>>0>c)?x1=++c:x2=c,q=(p<<16)-q,b=p<<8|p^1;
for(i=6;i;V[c]+=q*(r+S[U[c]=d])>>16){
d=U[c=T[--i]+s0]+b;
if((d&255)>250||d>64255)d=d>>1&32639}
if((s0=s0<<1|p)>255){
if((O[o++]=c=s0&255)<91&&c>64||c<123&&c>96)
sw0=sw0*997+s0>>>0;
else{if(sw0)sw1=sw0;sw0=0}
s7=s7<<8|s3>>>24,
T[0]=4128768|(s3=(s3|c)<<8>>>0)&65535,
T[s0=1]=(s3&0xffffff)%4128511,
T[2]=s3%4128493,
T[3]=(s3+s7*0x3000000>>>0)%4128451,
T[4]=(sw1+sw0*29>>>0)%4128401,
T[5]=sw0%4128409}
for(c=0;i<6;)c+=V[T[i++]+s0];
for(q=c>11264?65535:c<-11264?0:c<0?65535-g[-c]:g[c];!((x1^x2)>>24);x2=x2<<8|255)
x=x<<8|A[a++],x1=x1<<8>>>0
}
if(o<z)return wait(fn);
done(O,z,o);return O
}return fn()
}
P12encは引数Aを圧縮し、圧縮結果を返す。引数rsは学習率で0～255指定。
P12decは引数Aを展開して返す。両関数に備わっている引数doneとrateは終了後処理と途中処理の関数。rateが関数なら非同期っぽく振る舞い、さもなければ同期処理(再帰)。
非同期になると戻り値がごみになるので、doneで終了処理を担当。
使用例
let A=Array.from("That that is is that that is not is not is that it it is",a=>a.charCodeAt());
let c=P12enc(A,5), d=P12dec(c)
console.log(c.length, String.fromCharCode(...d))
やぶからぼうにcodepen
See the Pen P12a compressor by xezz (@xezz) on CodePen.