JavaScript: 圧縮とかROLZ

圧縮解説もどきの記事なのは言うまでもありません。今回はReduced offset Lempel-Ziv、略してROLZを紹介します。LZ77系で出力される位置情報を小さい値にする事で、高い圧縮率を叩き出す事が可能。
ただし、LZ77系のように過去の文字列を好き放題選び抜ける訳ではありません。huffman符号や算術符号等のentropy符号とうまく組み合わせる事で、圧縮率を稼ぐのです

実装編

Unicode文字列を圧縮して[_0-9A-Za-z:]からなる文字列を返しやがる仕様となります(AlphamericHTMLを真似ています)。言うまでもなくJavaScriptのprogramを圧縮してeval(SROLZ64d(...))などという使い方が可能。ちなみに今回の実装ではentropy符号系は一切使っていないので、へぼい圧縮率を誇ります

/* SROLZ64e(A): compressor
@A: string
@return: string
*/
function SROLZ64e(A){
	A=A.replace(/\r\n|\r/g,"\n").split("");
	for(var a=63,b=1,B,f,g=32,h="",i=0,l,m,n,o=1,p=0,q=0,z=A.length,st,bm=0xffffff,ms,O=[],L=["_"],H=[],D=[];a;)L[a--]=String.fromCharCode(a+(a<11?48:a<37?54:60));
	do{
		B|=b,D[i&bm]=H[p=h+(h=A[a])],H[p]=i++,f=g;
		// encode Unicode
		if((p=h.charCodeAt(0))<128){
			if(f!=(g=(p>>5)+32))O[o++]=L[g];O[o++]=L[p&31]}
		else if(12287<p&&p<12544){
			if(f!=(g=(p>>5&7)+36))O[o++]=L[g];O[o++]=L[p&31]}
		else if(65279<p&&p<65440){
			if(f!=(g=(p>>5&7)+44))O[o++]=L[g];O[o++]=L[p&31]}
		else{if(f!=(g=(p-(p%=2016))/2016+49))O[o++]="m"+L[g-49];O[o++]=L[(p-(p%=63))/63]+L[p]}

		if((b<<=1)>32)O[q]=L[B],q=o++,b=1,B=0;
		for(;;){st=ms=m=0;
			for(p=a;(n=D[p&bm]|0)<p;p=n){
				for(l=0;A[++l+a]==A[l+n];);
				if(--l>m)m=l,ms=st;
				if(++st>7)break
			}
			if(!m)break;
			for(l=m;l--;H[p]=i++)D[i&bm]=H[p=h+(h=A[++a])];
			O[o++]=L[(--m<8?m:7)<<3|ms];
			if(m>6){for(m-=7;m>62;m-=63)O[o++]="z";O[o++]=L[m]}
			if((b<<=1)>32)O[q]=L[B],q=o++,b=1,B=0
		}
	}while(++a<z);
	b>1&&(O[q]=L[B]);return O.join("")
}
/* SROLZ64d(A): decompressor
@A: string
@return: string
*/
function SROLZ64d(A){
	for(var a=63,b=1,c,f,l,o=-1,p,s,z=A.length,bm=0xffffff,h="",i=0,S=String.fromCharCode,O=[],L={_:0},H=[],D=[];a;)L[S(a+(a<12?47:a<38?53:59))]=a--;
	for(A=A.split("");a<z;){
		if((f>>=1)<2)f=L[A[a++]]|64;
		if(f&1){
			// decode Unicode
			s=L[A[a++]];
			if(s>31)c=(s<(b=36)?s-32:s<44?s+348:s>48?L[b=0,A[a++]]:s+1996)<<5,s=L[A[a++]];
			O[++o]=s=S(b?c|s:(c|s)*63+L[A[a++]]),
			D[i&bm]=H[s=h+(h=s)],H[s]=i++}
		else{
			// copy
			s=L[A[a++]],l=s>>3,s&=7;
			if(++l>7)while(l+=p=L[A[a++]],p>62);
			for(p=o;p=D[p&bm]|0,s--;);
			for(;l--;H[s]=i++)D[i&bm]=H[s=h+(h=O[++o]=O[++p])]
		}
	}return O.join("")
}

使用例

let a="He told me that that that that that boy said at that time is that that"
let c=SROLZ64e(a), d=SROLZ64d(c);
console.log(a.length,"->",c.length,c,d)

出力文字94種版

出力される文字は[\t -&(-\[\]-~]の94種類(ALZ_JAを真似ています)。圧縮率が若干良くなるかもしれなません

/* SROLZ94e(A): compressor
@A: string
@return: string
*/
function SROLZ94e(A){
	A=A.replace(/\r\n|\r/g,"\n").split("");
	var a=93,b=1,B,f,g=64,h="",i=0,l,m,n,o=1,p=0,q=0,z=A.length,st,bm=0xffffff,ms,O=[],L=["	"],H=[],D=[];
	for(;a;)L[a--]=String.fromCharCode(a+(a>6)+(a>58)+32);
	do{
		B|=b,D[i&bm]=H[p=h+(h=A[a])],H[p]=i++,f=g;
		// encode unicode
		if((p=h.charCodeAt(0))<128){
			if(f!=(g=(p>>6)+64))O[o++]=L[g];O[o++]=L[p&63]}
		else if(12287<p&&p<12544){
			if(f!=(g=(p>>6&3)+66))O[o++]=L[g];O[o++]=L[p&63]}
		else if(65279<p&&p<65440){
			if(f!=(g=(p>>6&3)+70))O[o++]=L[g];O[o++]=L[p&63]}
		else{if(f!=(g=(p-(p%=6016))/6016+73))O[o++]=L[g];O[o++]=L[(p-(p%=94))/94]+L[p]}

		if((b<<=1)>32)O[q]=L[B],q=o++,b=1,B=0;
		for(;;){st=ms=m=0;
			for(p=a;(n=D[p&bm]|0)<p;p=n){
				for(l=0;A[++l+a]==A[l+n];);
				if(--l>m)m=l,ms=st;
				if(++st>8)break}
			if(!m)break;
			for(l=m--;l--;H[p]=i++)D[i&bm]=H[p=h+(h=A[++a])];
			n=7;O[o++]=L[ms?(m<8?m:7)<<3|--ms:m<(n=29)?m+64:93];
			if(m>=n){for(m-=n;m>92;m-=93)O[o++]="~";O[o++]=L[m]}
			if((b<<=1)>32)O[q]=L[B],q=o++,b=1,B=0
		}
	}while(++a<z);b>1&&(O[q]=L[B]);
	return O.join("")
}
/* SROLZ94d(A): decompressor
@A: string
@return: string
*/
function SROLZ94d(A){
	for(var a=0,b=1,c,f,l,o=93,p,s,z=A.length,bm=0xffffff,h="",i=0,S=String.fromCharCode,O=[],L={"	":0},H=[],D=[];L[S(o+(o>7)+(o>59)+31)]=o--;);
	for(A=A.split("");a<z;){
		if((f>>=1)<2)f=L[A[a++]]|64;
		if(f&1){// decode unicode
			s=L[A[a++]];
			if(s>63)c=(s<(b=66)?s-64:s<70?s+126:s>72?(b=0,s-73):s+950)<<6,s=L[A[a++]];
			O[++o]=s=S(b?c|s:(c|s)*94+L[A[a++]]),
			D[i&bm]=H[s=h+(h=s)],H[s]=i++
		}else{// copy
			l=L[A[a++]];
			if(l<64)s=(l&7)+1,l>>=3,p=7;else s=0,l-=64,p=29;
			if(++l>p)while(l+=p=L[A[a++]],p>92);
			for(p=o;p=D[p&bm]|0,s--;);
			for(;l--;H[s]=i++)D[i&bm]=H[s=h+(h=O[++o]=O[++p])]
		}
	}return O.join("")
}

使用例

let a="He told me that that that that that boy said at that time is that that"
let c=SROLZ94e(a), d=SROLZ94d(c);
console.log(a.length,"->",c.length,c,d)

しゃしゃりだすcodepen

See the Pen AROLZ_JA compressor by xezz (@xezz) on CodePen.

参考文献

rolz_article