JavaScript: AlphamericHTMLを破改する!

AlphamericHTMLとはかつてweb素材の圧縮で一世を風靡しまくったかどうか定かではないかもしれないとされる程の伝説のprogramです。browser上で動作し、圧縮率、動作速度、使い勝手どれをとっても文句のつけどころがないもの でした。
たださすがに約20年前の化石ですので、もはや現代の巨大過ぎるweb素材の圧縮には実用的ではなくなりました。まあそんな歴史的裏話はどうでもいいかもしれないので、そろそろ本題にすり替えていきましょう。

仕様

• 文字列(Unicode)を[0-9A-Za-z_]の63種からなる文字列に変換
• LZ77系の圧縮法を採用(圧縮率60～70%)。無圧縮も可。
• 辞書(滑走窓)819文字
• 一致長3～64文字
• 半角空白1024個のpreset辞書搭載

圧縮関数

EncodeAlphamericString=new Function("s",'for(var a="",c,i=1014,j,K,k,L,l=-1,p,t=" ",A="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_".split(a);i<1024;i++)t+=t;t+=s;while(p=t.substr(i,64)){for(j=2;j<=p.length;j++){if(-1==(k=t.substring(i-819,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%=32))/32+64))a+=A[l-32];a+=A[c]}else if(12288<=c&&c<12544){if(L!=(l=((c-=12288)-(c%=32))/32+68))a+=A[l-32];a+=A[c]}else if(65280<=c&&c<65440){if(L!=(l=((c-=65280)-(c%=32))/32+76))a+=A[l-32];a+=A[c]}else{if(L!=(l=(c-(c%=1984))/1984))a+="n"+A[l];a+=A[(c-(c%=62))/62]+A[c]}}else{a+=A[(K-(K%=63))/63+50]+A[K]+A[j-3];i+=j-1}}return a')

伸長関数

DecodeAlphamericString=new Function("a",'for(var C=new Object,c,i=0,j,k,l,m,p,s="    ",w;i<63;i++)C["0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_".charAt(i)]=i;while(i-=7)s+=s;while((c=C[a.charAt(i++)])<63)if(c<32)s+=String.fromCharCode(m?l*32+c:(l*32+c)*62+C[a.charAt(i++)]);else if(c<49){l=(c<36)?c-32:(c<44)?c+348:c+1996;m=1}else if(c<50){l=C[a.charAt(i++)];m=0}else{if(p=(w=s.slice(-819)).substring(k=(c-50)*63+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(1024)')

当時としてはかなり巧妙なprogramです。縮める余地はてんこ盛りですが、それはともかく改良していきましょう。まず辞書幅819文字は少な過ぎるので大幅に増やす事を考えます。

辞書拡張

本家は一致flagとして13種類の文字を採用していて、その後に63種類の文字を出力。それによって 13*63=819 を表現しています。その次に一致長を表す63種類の文字を出力。
単純に出力順を逆にすると大幅に辞書を拡張できます。一致長を一致flagとし、続けて辞書の位置を2文字で出力。すると 63*63=3969 となり、約5倍にもなります。その代償として一致長はわずか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=3969,MIN=3,a=62,c,f,g=32,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=z/64+256|0,O=[],N={},H={},L=["_"];a;)
		L[a--]=String.fromCharCode(a+(a<10?48:a<36?55:61));

	O.e=function(c){f=g;
			if((c=c.charCodeAt(0))<128){
				if(f!=(g=(c>>5)+32))this[o++]=L[g];this[o++]=L[c&31]}
			else if(12287<c&&c<12544){
				if(f!=(g=(c>>5&7)+36))this[o++]=L[g];this[o++]=L[c&31]}
			else if(65279<c&&c<65440){
				if(f!=(g=(c>>5&7)+44))this[o++]=L[g];this[o++]=L[c&31]}
			else{if(f!=(g=(c-(c%=1984))/1984+49))this[o++]="m"+L[g-49];this[o++]=L[(c-(c%=62))/62]+L[c]}};

	for(;a<z;){r=pl;
		if(a+r<z){
			for(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>mch||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<13?l+50:62];
			if(l>11){for(l-=12;l>61;l-=62)O[o++]="z";O[o++]=L[l]}
			c=po,O[o++]=L[(c-(c%=63))/63]+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=62,b,c=1,l,o=-1,p,L={_:0},O=[],S=String.fromCharCode;a;)L[S(a+(a<11?47:a<37?54:60))]=a--;
	for(A=A.split("");(l=L[A[a++]])>-1;)
		if(l>49){
			if(l>61)for(;l+=p=L[A[a++]],p>61;);
			for(p=o-L[A[a++]]*63-L[A[a++]];47<l--;)O[++o]=O[p++]
		}
		else{
			if(l>31)b=(l<(c=36)?l-32:l<44?l+348:l>48?L[c=0,A[a++]]:l+1996)<<5,l=L[A[a++]];
			O[++o]=S(c?b|l:(b|l)*62+L[A[a++]])
		}
	return O.join("")
}

試し切り

a=compress("bananaばななそんなバナナ")
b=decompress(a)

お気軽お手軽簡単動作検証

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

実は10年以上前に作った骨董品だったりします…

更なる改良

この程度はまだ序の口で、辞書の大きさにしてもまだまだ増やす余地があります。符号化にはまだ使い切ってない出力法があるので、そこを埋めていきます。今回は例として辞書幅11907に設定します。
他にもLZ系列の最適化による圧縮率の改善が可能です(業界用語でOptimal parsing)。ただしそれには圧縮速度の大幅な低下を伴います。実装例を示します。使い方は改良案1と同じです。

function compress(A){
	A=A.replace(/\r\n|\r/g,"\n").split("");
	for(var W=11907,MIN=3,a=62,b,c,d,e,f,i,l,n=32,o,p,r,s,t,u,z=A.length,H={},L=[],N=[],O=[0],M=["_"];a;)M[a--]=String.fromCharCode(a+(a<10?48:a<36?55:61));

	// Unicodeの符号化
	O.e=function(c,e){e=f;
		if(c<128){
			if(e^(f=(c>>5)+32))this[a++]=M[f];this[a++]=M[c&31]}
		else if(12287<c&&c<12544){
			if(e^(f=(c>>5&7)+36))this[a++]=M[f];this[a++]=M[c&31]}
		else if(65279<c&&c<65440){
			if(e^(f=(c>>5&7)+44))this[a++]=M[f];this[a++]=M[c&31]}
		else{if(e^(f=(c-(c%=1984))/1984+49))this[a++]="m"+M[f-49];this[a++]=M[(c-(c%=62))/62]+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<3969?15:16;
					for(u=d<3969?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+(c-s<60?2:(o=c-s-60)<63?3:o<3969?4:5);
					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();e=n;
		if(c<128)e^(n=(c>>5)+32)&&++b;
		else if(12287<c&&c<12544)e^(n=(c>>5&7)+36)&&++b;
		else if(65279<c&&c<65440)e^(n=(c>>5&7)+44)&&++b;
		else e^(n=(c-(c%1984))/1984+49)&&(b+=2),++b
	}
	for(p=N.length=O.length=0;n=N[p++]=L[a],a-=n/65536|0;);
	for(f=32;d=N[--p];){
			l=d/65536|0;d&=65535;
		if(l<MIN)O.e(d);
		else{l-=MIN;
			if(d<3969)O[a++]=M[l<13?l+50:62];
			else{if(d<7938)d-=3969,O[a++]="m"+M[l<13?l+34:47];
			else d-=7938,O[a++]="m"+M[l<13?l+48:61];--l}
			if(l>11)if((l-=12)<60)O[a++]=M[l];
			else for(O[a++]=M[(l-=60)<63?60:l<3969?61:62];O[a++]=M[l%63],l=l/63|0;);
			O[a++]=M[(d-(d%=63))/63]+M[d]}}
	return O.join("")
}
function decompress(A){
	for(var a=62,b,c=1,l,n,o=-1,p,r,L={_:0},O=[],S=String.fromCharCode;a;)L[S(a+(a<11?47:a<37?54:60))]=a--;
	for(A=A.split("");(l=L[A[a++]])>-1;)
		if(l>49){
			if(l>61)if((p=L[A[a++]])<60)l+=p;
			else for(l+=60,n=1;l+=L[A[a++]]*n,--p>59;)n*=63;
			for(p=o-L[A[a++]]*63-L[A[a++]];47<l--;)O[++o]=O[p++]}
		else{
			if(l>31){n=l<(p=36)?l-32:l<44?l+348:l>48?L[p=0,A[a++]]:l+1996;
				if(n>33&&!p){p=3969;
					if(n>47)n-=14,p+=p;
					if(n>46)if((l=L[A[a++]])<60)n+=l;
					else for(n+=60,r=1;n+=L[A[a++]]*r,--l>59;)r*=63;
					for(p=o-L[A[a++]]*63-L[A[a++]]-p;31<n--;)O[++o]=O[p++];continue}
					l=L[A[a++]];b=n<<5;c=p}
			O[++o]=S(c?b|l:(b|l)*62+L[A[a++]])}
	return O.join("")
}

試運転

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