Shift JIS形式で文字列を盛大に圧縮するprogramを紹介します。とても日本語贔屓の設計です。htmlなりjsなり好き放題圧縮するような活用法があるとかないとか。
半角カタカナ等を使い込む事になるので、Shift JIS以外の形式で保存すると圧縮率が損なわれます。
出力文字
[\1-\t\x0B\x0C\x0E-&(-\x5B\x5D-\x7F｡-ﾟ]の186種。ShiftJISでは全て1byte。
</ や --> 等の文字列を含む可能性があるので、htmlに直接出力文字を記述する場合は注意.その場合は</のようにする。
符号化原理
LZ系、辞書幅34596、最長一致21+α。位置情報は2bytes式と3bytes式がある。二分木探索法により全ての位置で最長一致を求め、費用対効果の最適化を行う(低速)。展開は瞬時に行われる。
ShiftJISで対応している文字なら漢字以外はほぼ1byteになる可能性があるっぽい。
-
[\1-\b\t\v\f\x0E-&(-\[\]-\x7f\uff61-\uff65]文字区分に応じた文字128種
-
[ｦｧ]文字区分を
[\x00-\xFF]に切り替える -
[ｨｩ]文字区分を
[\u3000-\u30FF]に切り替える -
[ｪｫ]文字区分を
[\uFF00-\uFFFF]に切り替える -
[ｬｭｮ]文字区分を
[\u2160-\u22DF]に切り替える -
[ｯｰｱ]文字区分を
[\u2460-\u25DF]に切り替える -
[ｲ]文字区分を
[\u2600-\u267F]に切り替える -
[ｳｴ]文字区分を
[\u0380-\u047F]に切り替える -
[ｵ-ｸ]文字区分を
[\x00-\uFFFF]に切り替える -
[ｹ-ﾋ]一致長+相対位置を2文字で符号化
-
[ﾌ-ﾞ]相対位置34596未満、3-21文字の部分一致
-
ﾟ.+相対位置34596未満、22文字以上の部分一致
/* compress
LZSJencode(In,M)
@In: string
@M:
2文字符号化の場合の最長一致長. 範囲は0-57. 6程度が最適.
@Mを大きくすると[一致長+相対位置の2byte符号]における最大距離が小さくなり、@Mを小さくすると最大距離が大きくなる
@return: string
*/
function LZSJencode(In,M){
In=In.replace(/\r\n|\r/g,"\n").split("");
if(!In[0])return"";
M=(M&63)+2;if(M>59)M=59;
let W=34596,MIN=3,Max,a=0,b,c=0,d,e=1767,f,i,l,n=128,o,p=1,r,t,u,v,z=In.length,N=[],O=[0],Lz=[0],C={9:1,11:1,36:1,88:1,123:65249};
for(;c<186;)C[c]=String.fromCharCode(c+(p+=C[c++]|0));
for(v=C[M-2];M>3534/e>>0;)e--;
M=e;Max=3534/M|0;
// Unicode encoder
O.e=function(c){
var b=c&127,n=c>>7,e=f;
if(c<256){
if(e^(f=n|128))O[a++]=C[f];
O[a++]=C[b] //80-81 ASCII
}else if(c<12544&&c>12287){
if(e^(f=n+34))O[a++]=C[f];
O[a++]=C[b] //82-83 平(片)仮名
}else if(c>65279){
if(e^(f=n-378))O[a++]=C[f];
O[a++]=C[b] //84-85 全角英数字半角片
}else if(c<0x22E0&&c>0x215F){
if(e^(f=(c+32>>7)+67))O[a++]=C[f];
O[a++]=C[b-96&127] //86-88 記号
}else if(c<0x25E0&&c>0x245F){if(e^(f=(c+32>>7)+64))O[a++]=C[f];
O[a++]=C[b-96&127] //89-8B 記号
}else if(c<0x2680&&c>0x25FF){
if(e^(f=140))O[a++]=C[f];
O[a++]=C[b] //8C 記号
}else if(c>1151||c<896){
if(e^(f=(c-(c%=19968))/19968+143))O[a++]=C[f];
O[a++]=C[(c-(c%=156))/156]+C[c] //8F-92 Unicode
}else{
if(e^(f=n+134))O[a++]=C[f];
O[a++]=C[b] //8D-8E Greek,Cyrillic
}
};
//pass1: find all matches by binary tree match finder
for(let H={};a<z;++b>=O[a]||(O[a]=b,Lz[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=In[a]+In[a+1]+In[a+2]];
for(H[i]=a;p>t;){
i=e<f?e:f;
if(In[p+i]===In[a+i]){
for(;In[++i+p]===In[a+i];);
if(i>c){
d=~p+a;u=b+2;
// update cost for small distance + small matches
if(d<M)for(;i>c&&c<=Max;)u>=O[++c+a]||(O[a+c]=u,Lz[a+c]=65536*c+d);
// update cost for all matches
for(;i>c;o>=O[a+c]||(O[a+c]=o,Lz[a+c]=65536*c+d))
o=++c<22?u+1:u+2+(c-22)/185|0;
if(a+i===z)break
}
}
if(In[p+i]<In[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;
// next literal cost
c=In[a++].charCodeAt();d=c>>7;e=n;
c<256?e^(n=d|128)&&++b:
c<12544&&c>12287?e^(n=d+34)&&++b:
c>65279?e^(n=d-378)&&++b:
c<0x22E0&&c>0x215F?e^(n=(c+32>>7)+67)&&++b:
c<0x25E0&&c>0x245F?e^(n=(c+32>>7)+64)&&++b:
c<0x2680&&c>0x25FF?e^(n=140)&&++b:
c>1151||c<896?(e^(n=(c-(c%19968))/19968+143)&&++b,++b):e^(n=d+134)&&++b
}
// pass2: build LZ token
for(p=N.length=O.length=0;n=N[p++]=Lz[a],a-=n/65536|0;);
// pass3: encoding
for(f=128;Lz=N[--p];){
l=Lz/65536|0;Lz&=65535;
if(l<MIN)O.e(Lz);
else{l-=MIN;
if(Lz<M&&l<Max){
O[a++]=C[(Lz=l*M+Lz%M)/186+147|0]+C[Lz%186];continue
}
O[a++]=C[l<20?l+166:185];
if(l>18){for(l-=19;l>184;l-=185)O[a++]="ﾟ";O[a++]=C[l]}
O[a++]=C[(Lz-(Lz%=186))/186]+C[Lz]}
}return v+O.join("")
}
/* decompress
LZSJdecode(In)
@In: string
@return: string
*/
function LZSJdecode(In){
var a=0,b=0,c=0,l,o=186,p=1,N=1767,L={9:1,11:1,36:1,88:1,123:65249},Out=[],S=String.fromCharCode;
for(In=In.split("");o--;)L[S(c+(p+=L[c]|0))]=c++;
for(l=L[In[0]]+2;l>3534/N>>0;)N--;
for(;p=In[++a];)
if((l=L[p])<147){//literal
if(l>127)b=(l&=c=31)<2?l<<7:l<4?l+94<<7:l>14?(c=0,l-15)*19968:l<6?l+506<<7:l<9?(l+61<<7)-32:l<12?(l+64<<7)-32:l<13?9728:l-6<<7,l=L[In[++a]];
Out[++o]=S(c?b+l:b+l*156+L[In[++a]])
}else{//copy
if(l>165){if(l>184)while(l+=p=L[In[++a]],p>184);
p=o-L[In[++a]]*186-L[In[++a]]}
else p=(l-147)*186+L[In[++a]],l=p/N+166|0,p=o-p%N;
for(;--l>162;)Out[++o]=Out[p++]
}
return Out.join("")
}
test
let txt="じゅげむじゅげむごこうのすりきれかいじゃりすいぎょのすいぎょうまつうんらいまつふうらいまつくうねるところにすむところやぶらこうじのぶらこうじぱいぽぱいぽぱいぽのしゅーりんがんしゅーりんがんのぐーりんだいぐーりんだいのぽんぽこぴーのぽんぽこなーのちょうきゅうめいのちょうすけ";
let e=LZSJencode(txt,6), d=LZSJdecode(e);
console.log(new TextEncoder().encode(txt).length,"->",e.length,"decoded",d)
codepen的圧縮展開祭り
See the Pen text compressor for web contents by xezz (@xezz) on CodePen.
参考文献
圧縮率において以下のprogramを遥かに凌げる程度にささやかな改良を施したの本作である。