Unicode で処理しなきゃいけないので Posql_Unicode を使用しています。
前のPOST でも書きましたが、
結局、JavaScript の String オブジェクト関数のほとんどを 完全互換で実装しました。
SpiderMonkey のソースを参考にさせていただきました。
lastIndexOf とか、アルゴリズムがすごいです。
各メソッドは Posql_ECMA クラスに集約しています。
以下がそのメソッドたち。
- charAt
- charCodeAt
- fromCharCode
- indexOf
- lastIndexOf
- length *1
- slice
- split
- substr
- substring
- toLowerCase
- toUpperCase
- toString
これらは Posql 2.15 で実装できてるものです。
今後、増えるかもしれないです。
Posql_ECMA クラスの使い方は 前のPOST を参考にしてみてください。
今回は Posql_Archive で実装された、
- encodeAlphamericString
- decodeAlphamericString
<?php require_once 'posql.php'; $posql = new Posql; // 適当な日本語の文字列 $string = 'こんにちは。こんにちは。どなたかいませんか。おーい'; var_dump($string); // エンコード (圧縮) $encode = $posql->archive->encodeAlphamericString($string); var_dump($encode); // デコード (解凍) $decode = $posql->archive->decodeAlphamericString($encode); // 元の文字列と比較 var_dump($decode === $string); ?>
Posql_Archive オブジェクトは archive からアクセスできます。
AlphamericHTML は、LZ77圧縮アルゴリズムを採用しているので
連続した文字列が多ければ多いほど圧縮率は高くなります。
string 'こんにちは。こんにちは。どなたかいませんか。おーい'(length=75)
string 'cJeJdB1Fa2_v4d9AcVB4dUcReJcBa2cAhSc4'(length=36)
boolean true
出力はこんな感じになりました。
文字コードは UTF-8 です。
length を見るとわかるように、半分以下のバイト数に圧縮されています。
そしてさらに、
文字列を英数字 [0-9A-Za-z_] のみからなる文字列 (AlphamericString) に変換しています。
無事、解凍された文字列は元通りなんですが
実はこれ、ものすごいどころじゃくなく遅いです。
一応、実装できたからいいかー。

8 コメント:
AlphamericHTMLで検索してたどり着きました。まさかPHPで実装してるなんて…。使わせていただきます。ありがとうございます。
本家AlphamericHTMLを改良してみました。辞書の大きさは約5倍、最長一致長は無制限なので圧縮率向上していると思います。ついでに高速化。
圧縮文に含まれる文字列や文字の符号化原理は同じですが、互換性は無し。
String Objectは必要最小限に抑えたのでPHPでの実装も楽かも。
function encode(A){A=A.replace(/\r\n|\r/g,"\n").split("");
for(var a=0,c=0,f,g=32,l,n,o=0,p=47,v,z=A.length,limit,size=3969,ml,mp,H={},N={},F={},L=["_"],O=[],MIN=3;c<62;)
L[++c]=String.fromCharCode(c+(p+={11:7,37:6}[c]|0));
while(a-1&&n-p>=limit;n=N[n%size])
if(c++,A[a+ml]==A[n+ml-p]){
for(l=0;A[a+l]==A[n+l-p];l++);
if(ml256)F[v]=1;
if(ml>=p+MIN||!p)break;
p=0}
if(ml>z-a)ml=z-a;
if(ml>5)+32))O[o++]=L[g];O[o++]=L[c&31]}
else if(12287>5&7)+36))O[o++]=L[g];O[o++]=L[c&31]}
else if(65279>5&7)+44))O[o++]=L[g];O[o++]=L[c&31]}
else{if(f!=(g=(c-(c%=1984))/1984))O[o++]="m"+L[g];O[o++]=L[(c-(c%=62))/62]+L[c]}}
else{l=ml,l-=MIN,c=~mp+a,
O[o++]=L[(l<13?l:12)+50];
if(l>11){for(l-=12;l>61;l-=62)O[o++]="z";O[o++]=L[l]}
O[o++]=L[(c-(c%=63))/63]+L[c]}
for(;ml--;H[v]=a++)N[a%size]=H[v=A[a]+A[a+1]+A[a+2]]}
return O.join("")}
// 解凍
function decode(A){
for(var a=0,b,c=0,f=1,o=-1,p=47,C={"_":0},O=[],S=String.fromCharCode;c<62;)
C[S(++c+(p+={11:7,37:6}[c]|0))]=c;
for(A=A.split("");(c=C[A[a++]])>-1;)
if(c>49){
if(c>61)while(c+=p=C[A[a++]],p>61);
for(p=o-C[A[a++]]*63-C[A[a++]];4731)b=(c<(f=36)?c-32:c<44?c+348:c>48?C[f=0,A[a++]]:c+1996)<<5,c=C[A[a++]];
O[++o]=S(f?b|c:(b|c)*62+C[A[a++]])}
return O.join("")}
げっ、文字化けしてる…。
4731)
↓
47< c-- ;
というか復号処理の関数が途中から破綻している!
function decode(A){
for(var a=0,b,c=0,l,o=-1,p=47,L={"_":0},O=[],S=String.fromCharCode;c<62;)
L[S(++c+(p+={11:7,37:6}[c]|0))]=c;
for(A=A.split("");(l=L[A[a++]])>-1;)
if(l>49){if(l>61)while(l+=p=L[A[a++]],p>61);
for(p=o-L[A[a++]]*63-L[A[a++]];l-->47;)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("")}
SyntaxError で実行できないです。
> while(a-1&&n-p>=limit;n=N[n%size])
↑の ; だと思いますが。
あと、関数名が encode / decode とありますが、
どういった手法 (アルゴリズム) のエンコードなのか
明記していただけるとわかりやすいです。
Webサイト等ありましたら URL もお願いします。
AlphamericHTML は、[a-zA-Z0-9_] のみで構成される
結果となるのが魅力的なのですが、
それがなく 0x00 ~ 0xFF までとなると、
zlib を使ったほうが効率的になってしまいます。
うわっ! 圧縮処理も文字化けしてますね。最長一致検索の手法はLHAを元にしていました。
で、あれから少し改良。
符号化原理
[V-Y] :文字区分を [\x00-\x7F]に切り替える
[Za-g] :文字区分を [\u3000-\u30FF]に切り替える
[h-l] :文字区分を [\xFF00-\xFF9F]に切り替える
m :文字区分を [\x00-\uFFFF]に切り替える
[n-y] :3~14文字の部分一致
z\w+ :15文字以上の部分一致
\w\w :一致位置.上記2つに続けて出力.0~3968の相対位置となる
// 圧縮
function encode(A){A=A.replace(/\r\n|\r/g,"\n").split("");
for(var MO=3969,MIN=3,a=0,c=0,f,g=32,i,l,m,n=MIN,o=0,p=47,r,s,t,x=A[0]+A[1]+A[2],z=A.length,now=MO+1,pl=MIN-1,po=0,mch=256,mdef=64,O=[],N={},H={},L=["_"];c<62;)
L[++c]=String.fromCharCode(c+(p+={11:7,37:6}[c]|0));
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>5&7)+36))this[o++]=L[g];this[o++]=L[c&31]}
else if(65279>5&7)+44))this[o++]=L[g];this[o++]=L[c&31]}
else{if(f!=(g=(c-(c%=1984))/1984))this[o++]="m"+L[g];this[o++]=L[(c-(c%=62))/62]+L[c]}};
while(a7)c>>=2;
for(i=c;c;n=N[n%MO]|0){ //最長一致検索
p=now-n;
if(p<=l||p>MO)break;
s=a+r,t=a-p+r;
loop:{for(;s>=a;s--){if(A[s]!=A[t])break loop;t--}
t+=r+2;
for(s+=r+2;A[s]==A[t]&&si)break}
l=p}}
if(pl>=r&&pl!=MIN-1){ //この部分一致を採用
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]); //最低一致未満
else{if(pl!=MIN-1)O.e(A[a-1]); //まだ長い部分一致があるっぽい
po=m;
if(r11){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];
pl=MIN-1}}
for(n=a+r;a!=n;a++){
if(a+MIN<=z){
N[now%MO]=H[x],H[x]=now;
if(a+MIN<z)x=x.slice(-2)+A[a+MIN]}
now++}}
return O.join("")}
余談ですが…確かにzlibを使った方が高圧縮率ですね。
[a-zA-Z0-9_]にこだわらずALZ_JAのようにもっと文字を増やせば更に圧縮率は良くなります。
ところでこちらの書き込みでは半角の<>を含めるのは駄目なのですか?
うわっ! 圧縮処理も文字化けしてますね。最長一致検索の手法はLHAを元にしていました。で、あれから少し改良。
// 圧縮
function encode(A){A=A.replace(/\r\n|\r/g,"\n").split("");
for(var MO=3969,MIN=3,a=0,c=0,f,g=32,i,l,m,n=MIN,o=0,p=47,r,s,t,x=A[0]+A[1]+A[2],z=A.length,now=MO+1,pl=MIN-1,po=0,mch=256,mdef=64,O=[],N={},H={},L=["_"];c<62;)
L[++c]=String.fromCharCode(c+(p+={11:7,37:6}[c]|0));
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>5&7)+36))this[o++]=L[g];this[o++]=L[c&31]}
else if(65279>5&7)+44))this[o++]=L[g];this[o++]=L[c&31]}
else{if(f!=(g=(c-(c%=1984))/1984))this[o++]="m"+L[g];this[o++]=L[(c-(c%=62))/62]+L[c]}};
while(a7)c>>=2;
for(i=c;c;n=N[n%MO]|0){ //最長一致検索
p=now-n;
if(p<=l||p>MO)break;
s=a+r,t=a-p+r;
loop:{for(;s>=a;s--){if(A[s]!=A[t])break loop;t--}
t+=r+2;
for(s+=r+2;A[s]==A[t]&&si)break}
l=p}}
if(pl>=r&&pl!=MIN-1){ //この部分一致を採用
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]); //最低一致未満
else{if(pl!=MIN-1)O.e(A[a-1]); //まだ長い部分一致があるっぽい
po=m;
if(r11){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];
pl=MIN-1}}
for(n=a+r;a!=n;a++){
if(a+MIN<=z){
N[now%MO]=H[x],H[x]=now;
if(a+MIN<z)x=x.slice(-2)+A[a+MIN]}
now++}}
return O.join("")}
余談ですが…確かにzlibを使った方が高圧縮率ですね。
[a-zA-Z0-9_]にこだわらずALZ_JAのようにもっと文字を増やせば更に圧縮率は良くなります。
ところでこちらの書き込みでは半角の<>を含めるのは駄目なのですか?
また変になってる…。ちなみにdecode関数はそのまま使えます。
function encode(A){A=A.replace(/\r\n|\r/g,"\n").split("");
for(var MO=3969,MIN=3,a=0,c=0,f,g=32,i,l,m,n=MIN,o=0,p=47,r,s,t,x=A[0]+A[1]+A[2],z=A.length,now=MO+1,pl=MIN-1,po=0,mch=256,mdef=64,O=[],N={},H={},L=["_"];c<62;)
L[++c]=String.fromCharCode(c+(p+={11:7,37:6}[c]|0));
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))this[o++]="m"+L[g];this[o++]=L[(c-(c%=62))/62]+L[c]}};
while(a<z){r=pl;
if(a+r<z){c=mch,l=m=0,n=H[x]|0;
if(r>7)c>>=2;
for(i=c;c;n=N[n%MO]|0){ //最長一致検索
p=now-n;
if(p<=l||p>MO)break;
s=a+r,t=a-p+r;
loop:{for(;s>=a;s--){if(A[s]!=A[t])break loop;t--}
t+=r+2;
for(s+=r+2;A[s]==A[t]&&s<z;s++)t++;
r=s-a,m=p-1;
if(s==z||r>i)break}
l=p}}
if(pl>=r&&pl!=MIN-1){ //この部分一致を採用
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]); //最低一致未満
else{if(pl!=MIN-1)O.e(A[a-1]); //まだ長い部分一致があるっぽい
po=m;
if(r<mdef)pl=r,r=1;
else{ l=r-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];
pl=MIN-1}}
for(n=a+r;a!=n;a++){
if(a+MIN<=z){
N[now%MO]=H[x],H[x]=now;
if(a+MIN<z)x=x.slice(-2)+A[a+MIN]}
now++}}
return O.join("")}
コメントを投稿