JavaScript: ALZ_JAの圧縮力を上げまくる企画

ALZ_JAとはかつてweb業界で暗躍しまくったかどうか定かではないもしれないとされる程の名作programです。AlphamericHTML同様、web素材(html,js,css等)を圧縮して下さるのですが、動作速度はほぼ変わらないのに圧縮率はそれ以上という代物です。その驚異的な性能により、web開発者を度肝を抜きまくり震撼させ恐怖のどん底に叩き落としたわけがないのは言うまでもありません。
たださすがに約20年前の中古programですので、現代の超巨大過ぎるweb素材の圧縮には不向きとなりつつあります。そんな名作を蘇らせるべく改良を施すのが今回の企画です。

本家の仕様

• 7bit ASCII文字、shift-jis、euc-jp、iso-2022-jpで扱える大部分の文字を半角英数字記号93種に変換
• LZ77系の圧縮法を採用。一般的なHTMLに対する圧縮率は50～60%程度
• 辞書(滑走窓)1209文字
• 一致長3～94文字
• 半角空白1286文字のpreset辞書搭載

圧縮関数

EncodeALZ_JA=new Function("s",'for(var a="",c,i=32,j=0,K,k,L,l=-1,p,t="     ",A=new Array();i<127;i++)if(34!=i&&92!=i)A[j++]=String.fromCharCode(i);for(i=1272;i<1280;i++)t+=t;t+=s;while(p=t.substr(i,94)){for(j=2;j<=p.length;j++){if(-1==(k=t.substring(i-1209,i+j-1).lastIndexOf(p.substring(0,j))))break;K=k}if(2==j||3==j&&L==l){L=l;if((c=t.charCodeAt(i++))<128){if(L!=(l=(c-(c%=64))/64+70))a+=A[l];a+=A[c]}else if(12288<=c&&c<12544){if(L!=(l=((c-=12288)-(c%=64))/64+72))a+=A[l];a+=A[c]}else if(65280<=c&&c<65440){if(L!=(l=((c-=65280)-(c%=64))/64+76))a+=A[l];a+=A[c]}else{c=(c<9840)?c:(c<40870)?c-10128:c-33043;if(L!=(l=(c-(c%=5952))/5952+64))a+=A[l];a+=A[(c-(c%=93))/93]+A[c]}}else{a+=A[(K-(K%=93))/93+79]+A[K]+A[j-3];i+=j-1}}return a')

伸長関数

DecodeALZ_JA=new Function("a",'for(var C=new Object,c,i=32,j=0,k,l,m,p,s="     ",u=String.fromCharCode,w;i<127;i++)if(34!=i&&92!=i)C[u(i)]=j++;for(i=8;i;i--)s+=s;while((c=C[a.charAt(i++)])<93)if(c<64)s+=u(m?l*64+c:((c=(l*64+c)*93+C[a.charAt(i++)])<9840)?c:(c<30742)?c+10128:c+33043);else if(c<70){l=c-64;m=0}else if(c<79){l=(c<72)?c-70:(c<76)?c+120:c+944;m=1}else{if(p=(w=s.slice(-1209)).substring(k=(c-79)*93+C[a.charAt(i++)],j=k+C[a.charAt(i++)]+2))while(w.length<j)w+=p;s+=w.substring(k,j)}return s.slice(1280)')

といった感じのprogramで見直すべき点がちらほら見受けられます。

文字の制約解放運動

AlphamericHTMLとは違い、Unicodeの大部分の文字が未対応となっています(完全に日本語贔屓の設計)。今時絵文字すら扱えないようでは話にならないので、全ての文字に対応させます。

欲張りな辞書拡張

本家は一致flagとして13種類の文字を採用していて、その後に93種類の文字を出力。それによって 13*93=1209 を表現しています。その次に一致長を表す93種類の文字を出力。
まず符号化に使える文字を1個(tab)追加します。更に出力順を逆にすると大幅に辞書を拡張できます。一致長を一致flagとし、続けて辞書の位置を2文字で出力。すると 94*94=8836 となり、約7倍にもなります。その代償として一致長はわずか3～15となります。しかし15の場合に特別な処理にすれば、一致長の制限は実質無くなります。

選りすぐりの最長一致系列

本家の処理では最長一致した部分を即採用しています(業界用語でGreedy parsingと呼ぶ)。しかしその位置から1つずらした方が最長一致が長くなる事があります(Lazy parsing)。

どえらい高速化

上記改良を施すにはもはやsubstrとlastIndexOfごときに頼っていられません。hash表を使って最長一致系列を求めまくっていきます。

function compress(A){
	A=A.replace(/\r\n|\r/g,"\n").split("");
	for(var MO=8836,MIN=3,a=93,c,f,g=64,i,l,m,n,o=0,p,r,s,t,x=A[0]+A[1]+A[2],z=A.length,now=MO+1,pl=MIN-1,po=0,mch=MO>>2,O=[],N={},H={},L=["	"];a;)L[a--]=String.fromCharCode(a+(a>6)+(a>58)+32);
	// Unicodeの符号化
	O.e=function(c){f=g;
		if((c=c.charCodeAt(0))<128){
			if(f!=(g=(c>>6)+64))this[o++]=L[g];this[o++]=L[c&63]}
		else if(12287<c&&c<12544){
			if(f!=(g=(c>>6&3)+66))this[o++]=L[g];this[o++]=L[c&63]}
		else if(65279<c&&c<65440){
			if(f!=(g=(c>>6&3)+70))this[o++]=L[g];this[o++]=L[c&63]}
		else{
			if(f!=(g=(c-(c%=6016))/6016+73))this[o++]=L[g];this[o++]=L[(c-(c%=94))/94]+L[c]
		}
	};
	for(;a<z;){r=pl;
		if(a+r<z){
			for(i=mch,l=m=0,n=H[x]|0;;n=N[n%MO]|0){
				p=now-n;
				if(p<=l||p>MO)break;
				s=a+r,t=s-p;
				loop:{for(;s>=a;s--){if(A[s]!=A[t])break loop;t--}
					t+=r+=2;
					for(s+=r;A[s]==A[t];s++)t++;
					r=s-a,m=p-1;
					if(r>i||s==z)break
				}l=p
			}
		}
		if(pl>=r&&pl!=MIN-1){ //old match at least as good;use that one
			l=pl-MIN,O[o++]=L[l<10?l+84:93];
			if(l>8){for(l-=9;l>92;l-=93)O[o++]="~";O[o++]=L[l]}
			c=po,O[o++]=L[(c-(c%=94))/94]+L[c];
			r=pl-1,pl=MIN-1
		}
		else if(r==MIN-1)r=1,O.e(A[a]); //no match;just put out the literal
		else{
			if(pl!=MIN-1)O.e(A[a-1]); //longer match now.output previous literal
			po=m,pl=r,r=1
		}
		for(;r--;now++)
			if((c=a+++MIN)<=z){
				N[now%MO]=H[x],H[x]=now;
				if(c<z)x=A[c-2]+A[c-1]+A[c]
			}
	}return O.join("")
}
// 解凍
function decompress(A){
	for(var a=93,b,c=1,l,o=-1,p,L={"	":0},O=[],S=String.fromCharCode;a;)L[S(a+(a>7)+(a>59)+31)]=a--;
	for(A=A.split("");(l=L[A[a++]])>-1;)
		if(l>83){
			if(l>92)for(;l+=p=L[A[a++]],p>92;);
			for(p=o-L[A[a++]]*94-L[A[a++]];81<l--;)O[++o]=O[p++]}
		else{
			if(l>63)b=(l<(c=66)?l-64:l<70?l+126:l>72?(c=0,l-73):l+950)<<6,l=L[A[a++]];
			O[++o]=S(c?b|l:(b|l)*94+L[A[a++]])
	}return O.join("")
}

試し切り

a=compress("クッパがよっぱらってナッパイッパかっぱらった")
b=decompress(a)

お気軽お手軽足軽簡易動作検証

See the Pen ALZ_JA2 by xezz (@xezz) on CodePen.

更なる大した事のない改良

などといった内容のお遊びはこの辺にして、そろそろALZ_JAの本気を出して頂きましょう。控え目に言って辞書幅を35344に設定します。
LZ系列の最適化による圧縮率の控え目な向上も可能です。圧縮速度の大幅な低下を招きますが、知った事ではないかもしれません。使い方は改良案1と同じです。

// 圧縮
function compress(A){
	A=A.replace(/\r\n|\r/g,"\n").split("");
	for(var W=35344,MIN=3,a=93,b,c,d,e,f,i,l,n=64,o,p,r,s,t,u,z=A.length,H={},N=[],L=[0],O=[0],M=["	"];a;)M[a--]=String.fromCharCode(a+(a>6)+(a>58)+32);

	O.e=function(c,e){e=f;
		if(c<128){
			if(e^(f=(c>>6)+64))this[a++]=M[f];this[a++]=M[c&63]}
		else if(12287<c&&c<12544){
			if(e^(f=(c>>6&3)+66))this[a++]=M[f];this[a++]=M[c&63]}
		else if(65279<c&&c<65440){
			if(e^(f=(c>>6&3)+70))this[a++]=M[f];this[a++]=M[c&63]}
		else{
			if(e^(f=(c-(c%=6016))/6016+73))this[a++]=M[f];this[a++]=M[(c-(c%=94))/94]+M[c]
		}
	};
	// LZ factorization
	for(;a<z;++b>=O[a]||(O[a]=b,L[a]=65536+c)){
		b=O[a],r=a%W,l=r+W,c=2,e=f=0,t=a<W?-1:a-W,p=H[i=A[a]+A[a+1]+A[a+2]];
		for(H[i]=a;p>t;){
			i=e<f?e:f;
			if(A[p+i]===A[a+i]){
				for(;A[++i+p]===A[a+i];);
				if(i>c){d=~p+a;s=d<8836?12:14;
					for(u=d<8836?b+2:b+3;i>c;o>=O[a+c]||(O[a+c]=o,L[a+c]=65536*c+d))
						o=++c<s?u+1:u+2+(c-s)/93|0;
					if(a+i===z)break}
			}
			if(A[p+i]<A[a+i])N[r]=p,p=N[r=p%W+W],f=i;
			else N[l]=p,p=N[l=p%W],e=i}
		N[l]=N[r]=-1;
		c=A[a++].charCodeAt();s=n;
		if(c<128)s^(n=(c>>6)+64)&&++b;
		else if(12287<c&&c<12544)s^(n=(c>>6&3)+66)&&++b;
		else if(65279<c&&c<65440)s^(n=(c>>6&3)+70)&&++b;
		else s^(n=(c-(c%6016))/6016+73)&&++b,++b
	}
	for(p=N.length=O.length=0;n=N[p++]=L[a],a-=n/65536|0;);
	for(f=64;d=N[--p];){
		l=d/65536|0;d&=65535;
		if(l<MIN)O.e(d);
		else{l-=MIN;
			if(d<8836)O[a++]=M[l<10?l+84:93];
			else{
				if(d<17672)d-=8836,O[a++]="t"+M[l<12?l+58:69];
				else if(d<26508)d-=17672,O[a++]="t"+M[l<12?l+70:81];
				else d-=26508,O[a++]="t"+M[l<12?l+82:93];l-=2
			}
			if(l>8){for(l-=9;l>92;l-=93)O[a++]="~";O[a++]=M[l]}
			O[a++]=M[(d-(d%=94))/94]+M[d]
		}
	}return O.join("")
}
// 解凍
function decompress(A){
	for(var a=93,b,c=1,i,l,o=-1,p,L={"	":0},O=[],S=String.fromCharCode;a;)L[S(a+(a>7)+(a>59)+31)]=a--;
	for(A=A.split("");(l=L[A[a++]])>-1;)
		if(l>83){if(l>92)for(;l+=p=L[A[a++]],p>92;);
			for(p=o-L[A[a++]]*94-L[A[a++]];81<l--;)O[++o]=O[p++]}
		else{
			if(l>63){p=L[A[a++]];
				if(l>72){
					if(l>82&&p>57){i=8836;
						if(p>81)p-=24,i*=3;
						else if(p>69)p-=12,i+=i;
						if(p>68)for(;p+=l=L[A[a++]],l>92;);
						for(i=o-L[A[a++]]*94-L[A[a++]]-i;55<p--;)O[++o]=O[i++];continue}
					b=l-73<<6;c=0}
				else b=(l<66?l-64:l<70?l+126:l+950)<<6,c=1;l=p}
			O[++o]=S(c?b|l:(b|l)*94+L[A[a++]])}
	return O.join("")
}

気ままに試運転

See the Pen ALZ_JA3 by xezz (@xezz) on CodePen.

前回記事:AlphamericHTMLを破改する