JavaScript: 圧縮とかROLZ

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

## 実装編
Unicode文字列を圧縮して`[_0-9A-Za-z:]`からなる文字列を返しやがる仕様となります([AlphamericHTML](https://qiita.com/mashuel/items/6d6d184d586c25e2b4e2)を真似ています)。言うまでもなくJavaScriptのprogramを圧縮して`eval(SROLZ64d(...))`などという使い方が可能。ちなみに今回の実装ではentropy符号系は一切使っていないので、**へぼい圧縮率**を誇ります
```js
/* 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("")
}
```
```js:使用例
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](https://qiita.com/mashuel/items/8f4ad4fbabd75cc0a15a)を真似ています)。圧縮率が若干良くなるかもしれなません
```js
/* 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("")
}
```
```js:使用例
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
<p class=codepen data-height="300" data-default-tab="result" data-slug-hash="ZEdWeeV" data-pen-title="AROLZ_JA compressor" 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/ZEdWeeV">AROLZ_JA compressor</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>

## 参考文献
[rolz_article](http://ezcodesample.com/rolz/rolz_article.html)