JavaScript: ALZW_JAとかいう圧縮program

以前に紹介したALZ_JAを元にした圧縮programを紹介します。ALZ_JAの圧縮原理はLZ77ですが、LZW風に書き換えたものとなります。Unicodeの変換原理は同等、出力文字も同様に半角英数字記号等94種類のみ。
LZWもどき実装の詳細はC言語による標準アルゴリズム事典のsqueeze.cを参照して下さい。この記事では説明文を端折りまくっています。しかもinline展開しまくりでわけワカメ。

const InitCT=Array.from(Array(1<<16),(a,b)=>b);
//圧縮関数
function ALZW_JAenc(A){
	A=A.replace(/\r\n|\r/g,"\n");
	var N=65536,MM=100,MD=N+8836,DS=N,a=1,b=1,c=A.charCodeAt(0),e=93,f,g=64,m,n,o=1,p,q,r,cp,cl=0,pp,pl,qi,qo,u,B,O=[],U=["	"],
		Np=[],Op=[],M=[],C=InitCT.slice(),//新旧待ち行列, 一致文字列, 文字集合
		P=[],LC=[],LS=[],RS=[];//親, 左の子, 左右兄弟
	for(;e;)U[e--]=String.fromCharCode(e+(e>6)+(e>58)+32);
	while(c>-1){
		pp=cp,pl=cl,cl=0,q=qi,p=c;
		do{
			if(p>=N)
				if(p==q)q=Op[p];
				else{
					p==qo?Op[qo=Np[p]]=u:Op[Np[n=Op[p]]=Np[p]]=n;
					if(qi==u)Op[qi=qo=p]=Np[p]=u;
					else if(q==u)Op[p]=u,qo=Op[Np[p]=qo]=p;
					else if(q==qi)Op[p]=qi,Np[p]=u,qi=Np[qi]=p;
					else Np[p]=Np[Op[p]=q],Np[q]=Op[Np[p]]=p}
			M[cl++]=c,c=A.charCodeAt(a++);
			for(p=LC[cp=p];p!=u&&c!=C[p];)p=RS[p]//node p の文字 c に当たる子を返す
		}while(p!=u);
		if((p=cp)<N){f=g;//Unicodeの符号化
			if(p<128){//ASCII
				if(f!=(g=(p>>6)+64))O[o++]=U[g];
				O[o++]=U[p&63]
			}else if(12287<p&&p<12544){//平仮名or片仮名
				if(f!=(g=(p>>6&3)+66))O[o++]=U[g];
				O[o++]=U[p&63]
			}else if(65279<p&&p<65440){//全角英数字記号
				if(f!=(g=(p>>6&3)+70))O[o++]=U[g];
				O[o++]=U[p&63]
			}else{//その他文字
				if(f!=(g=(p-(p%=6016))/6016+73))O[o++]=U[g];
				O[o++]=U[(p-(p%=94))/94]+U[p]
			}
		}else O[o++]=U[(p-=N)/94|0]+U[p%94],B|=b;//辞書番号出力
		//木の更新
		if(pp!=u)for(n=0;cl--;pp=p){
			if(++pl>MM)break;m=M[n++];
			for(p=LC[pp];p!=u&&m!=C[p];)p=RS[p];
			if(p==u){
				if(DS<MD)p=DS++;
				else{
					if(pp==qo)break;
					Op[qo=Np[p=qo]]=u,
					r=RS[p],l=LS[p],l!=u?RS[l]=r:LC[P[p]]=r;
					if(r!=u)LS[r]=l
				}
				C[p]=m,LC[p]=LS[p]=u,m=RS[p]=LC[pp];
				if(m!=u)LS[m]=p;
				LC[P[p]=pp]=p;
				if(qi==u)Op[qi=qo=p]=Np[p]=u;
				else if((r=pp<N?qi:Op[pp])==u)Op[p]=u,qo=Op[Np[p]=qo]=p;
				else if(r==qi)Op[p]=qi,Np[p]=u,qi=Np[qi]=p;
				else Np[p]=Np[Op[p]=r],Np[r]=Op[Np[p]]=p
			}
		}
		if(!(b<<=1)){//output flag by base85 encoding
			for(B>>>=0,p=5,n="";p--;B=B/85|0)n=U[B%85]+n;
			O[e]=n,b=1,e=o++,B=0
		}
	}
	//flush bits buffer
	if(b>1){for(B>>>=0,p=5,n="";p--;B=B/85|0)n=U[B%85]+n;O[e]=n}
	return O.join("")
}
//展開関数
function ALZW_JAdec(A){
	for(var N=65536,MM=100,MD=N+8836,DS=N,F,a=0,b=0,c=1,f=32,cp,cl=0,pp,pl,m,n=1,o=93,p,q,qi,qo,r,u,z=A.length,O=[],Np=[],Op=[],M=[],C=InitCT.slice(),P=[],LC=[],RS=[],LS=[],U={"	":0},S=String.fromCharCode;o;)U[S(o+(o>7)+(o>59)+31)]=o--;
	for(A=A.split("");a<z;){pp=cp,pl=cl,cl=0;
		if(f>31)for(f=6,F=0;--f;)F=F*85+U[A[a++]];
		p=U[A[a++]];
		if(F&1<<f++)p=U[A[a++]]+p*94+N;
		else{
			if(p>63)b=(p<(c=66)?p-64:p<70?p+126:p>72?(c=0,p-73):p+950)<<6,p=U[A[a++]];
			p=c?b|p:(b|p)*94+U[A[a++]]
		}
		for(cp=p;p!=u;p=P[p]){
			if(p>=N&&p!=qi){
				p==qo?Op[qo=Np[p]]=u:Op[Np[n=Op[p]]=Np[p]]=n;
				if(qi==u)Op[qi=qo=p]=Np[p]=u;
				else Np[p]=u,qi=Np[Op[p]=qi]=p}
			M[MM-++cl]=C[p]}n=MM-cl;
		for(m=0;m<cl;)O[o++]=S(M[n+m++]);
		if(pp!=u)for(;cl--;pp=p){
			if(++pl>MM)break;m=M[n++];
			for(p=LC[pp];p!=u&&m!=C[p];)p=RS[p];
			if(p==u){
				if(DS<MD)p=DS++;
				else{
					if(pp==qo)break;
					Op[qo=Np[p=qo]]=u,
					r=RS[p],l=LS[p],l!=u?RS[l]=r:LC[P[p]]=r;
					if(r!=u)LS[r]=l
				}
				C[p]=m,LC[p]=LS[p]=u,m=RS[p]=LC[pp];
				if(m!=u)LS[m]=p;
				LC[P[p]=pp]=p;
				if(qi==u)Op[qi=qo=p]=Np[p]=u;
				else if((r=pp<N?qi:Op[pp])==u)Op[p]=u,qo=Op[Np[p]=qo]=p;
				else if(r==qi)Op[p]=qi,Np[p]=u,qi=Np[qi]=p;
				else Np[p]=Np[Op[p]=r],Np[r]=Op[Np[p]]=p
			}
		}
	}return O.join("")
}

使用例

let e=ALZW_JAenc("こつそしょうしょうそしょうしょうそ"),
	d=ALZW_JAdec(e);
console.log(e,d)

codepen

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

特徴

圧縮率は概ねALZ_JA3を下回ります。でも御乱心下さい。展開速度もちゃっかり負けています。そして圧縮速度は…勝てない!? これでは使い所さんが無いジャマイカ…