unoh.github.com

flashlite1.1で文字圧縮してみた

Fri Jan 07 02:37:00 -0800 2011

明けましておめでとうございます＆はじめまして。12月に入社した加藤です。

FlashLite 2.0をやるつもりで入ってみたらバリバリ1.1だったので、出す機会を逸していたネタをここで出したいと思います。

FlashLite 1.1の制限にはいろいろありますが、開発する上で一番困るのは100KB制限です。
100KBと言うと、このページの右カラムに並んでいる著者一覧の写真が一つだいたい8KBくらいですので、だいたい12枚分になります。その中にグラフィックとスクリプト両方をつめ込まねばなりません。
普通のFLASHならパブリッシュ設定の「ムービーの圧縮」にチェックを入れれば圧縮が有効になるのですが、残念ながらFlashLite 1.1ではその機能はグレーアウトされて使えません。
そういうわけでFlashLite 1.1のエンジニアは日々シェイプの最適化から変数名の文字数まで、地道な作業に血道をあげています。

しかし、生成エンジンで変数差し込みをする場合、いくらswfを最適化したところで「100KB-swfのファイルサイズ」分のデータしか入れられません。Twitterクライアントを作っていたとき、これだと50件表示までしか出来なくて何とかして100件表示にしたいと思い辿り着いたのが文字圧縮です。

圧縮というとzipやらrarやらといったでお馴染みのアレですが、通常の圧縮形式は圧縮率を稼ぐために符号化やらなにやら様々な処理を行っていて、圧縮率が高い代わりに圧縮／展開処理が複雑で実行にも時間がかかります。いろんな意味で非力なFlashLite1.1では実装も難しい上、圧縮は疎か展開するにも非常に時間がかかってしまい、現実的ではありません（と言いつつ一人ハフマン符号化して圧縮を実装した人を知っていますが）。そこで目をつけたのはBPEという方法です。

BPEとはByte Pair Encodingの略で、「隣り合った二文字を使われていない一文字で置き換える」という圧縮方法です。例えば、「ABCDABCDABCDABCDABCD」という文字列をBPEで圧縮すると、ABを使われていないXに、CDをYに置き換え、「XYXYXYXYXY」となります。あとはX=AB、Y=CDという置換対応表を別で持っておけば、「XYXYXYXYXY」を「ABCDABCDABCDABCDABCD」に文字列置換だけで戻すことができます。とても単純です。ただし、その替りに圧縮率が悪く、このままではどうやっても50%以下には縮みません。しかし、その単純さ故に殆どCPUパワーを食わないため、とてもFlashLite向きと言えます（圧縮処理は重いという特徴もあるのですが、変数差し込みに使う場合それはサーバ側で行えばよく、問題になりません）。

では実際の文章で試してみましょう。まずは圧縮からです。今回は「吾輩は猫である」を使います。
英文を圧縮する場合は隣り合った2文字を1文字で置き換えますが、この場合は文章が日本語なので、2バイト文字を使われていない1バイト文字で置き換えます。頻出度合いが低くなると圧縮効果が落ちますので、今回は頻出上位60文字を抽出し置き換えました。方法は割愛。

元の文章

　吾輩は猫である。名前はまだ無い。
　どこで生れたかとんと見当がつかぬ。何でも薄暗いじめじめした所でニャ―ニャ―泣いていた事だけは記憶している。吾輩はここで始めて人間というものを見た。しかもあとで聞くとそれは書生という人間中で一番獰悪な種族であったそうだ。この書生というのは時々我々を捕えて煮て食うという話である。しかしその当時は何という考もなかったから別段恐しいとも思わなかった。ただ彼の掌に載せられてス―と持ち上げられた時何だかフワフワした感じがあったばかりである。掌の上で少し落ちついて書生の顔を見たのがいわゆる人間というものの見始であろう。この時妙なものだと思った感じが今でも残っている。第一毛をもって装飾されべきはずの顔がつるつるしてまるで薬缶だ。その後猫にもだいぶ逢ったがこんな片輪には一度も出会わした事がない。のみならず顔の真中があまりに突起している。そうしてその穴の中から時々ぷうぷうと煙を吹く。どうも咽せぽくて実に弱った。これが人間の飲む煙草というものである事はようやくこの頃知った。

BPE圧縮後

　RN-O&/*。名前-E1無"。
　_0&?4#,$]$:[.<,ぬ。H&'薄暗">I>I)#所&ZYKZYK泣"("#A1け-記憶)("*。RN-00&`I(;9$"%'!8:#。),'/$&聞@$34-B?$"%;9D&C番獰悪2種族&/+#3%1。0!B?$"%!-6F我F8捕え(煮(食%$"%話&/*。),)3![6-H$"%考'2,+#,7別段恐)"$'PG2,+#。#1彼!Q5載T74(スK$持VSげ74#6H1,X^X^)#W>./+#ば,\&/*。Q!S&少)落V<"(B?!J8:#!."Gゆ*;9$"%'!!:`&/ろ%。0!6妙2'!1$P+#W>.今&'残+("*。第C毛8'+(装飾さ4べき-U!J.<*<*)(E*&薬缶1。3!後O5'1"ぶ逢+#.0]2片輪5-C度'出会G)#A.2"。!み27UJ!真D./E\5突起)("*。3%)(3!穴!D,76FL%L%$M8吹@。_%'咽Tぽ@(実5弱+#。04.;9!飲むM草$"%'!&/*A-よ%や@0!頃知+#。

文字数は双方450文字と変わりませんが、サイズは元が896バイトに対し、圧縮後は539バイトになりました。約60%に圧縮されたということになります。この時、置換対応表は以下のようになります。

!=の
"=い
#=た
$=と
%=う
&=で
'=も
(=て
)=し
*=る
+=っ
,=か
-=は
.=が
/=あ
0=こ
1=だ
2=な
3=そ
4=れ
5=に
6=時
7=ら
8=を
9=間
:=見
;=人
<=つ
>=じ
?=生
@=く
A=事
B=書
C=一
D=中
E=ま
F=々
G=わ
H=何
I=め
J=顔
K=ー
L=ぷ
M=煙
N=輩
O=猫
P=思
Q=掌
R=吾
S=上
T=せ
U=ず
V=ち
W=感
X=フ
Y=ャ
Z=ニ
[=当
\=り
]=ん
^=ワ
_=ど
`=始

あとはこれを元に展開すればいいわけです。FlashLite1.1には置換系のメソッドがないので少々面倒ですが、僕は以下のように実装しました。

1フレーム目
stop();

//デコードキー
keys = "!\"#$%&'()*+,-./0123456789:;<>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`";
//デコード文字列
vals = "のいたとうでもてしるっかはがあこだなそれに時らを間見人つじ生く事書一中ま々わ何め顔ーぷ煙輩猫思掌吾上せずち感フャニ当りんワど始";
//圧縮後文字列
bpe_text = "　RN-O&/*。名前-E1無\"。\n　_0&?4#,$]$:[.<,ぬ。H&'薄暗\">I>I)#所&ZYKZYK泣\"(\"#A1け-記憶)(\"*。RN-00&`I(;9$\"%'!8:#。),'/$&聞@$34-B?$\"%;9D&C番獰悪2種族&/+#3%1。0!B?$\"%!-6F我F8捕え(煮(食%$\"%話&/*。),)3![6-H$\"%考'2,+#,7別段恐)\"$'PG2,+#。#1彼!Q5載T74(スK$持VSげ74#6H1,X^X^)#W>./+#ば,\&/*。Q!S&少)落V<\"(B?!J8:#!.\"Gゆ*;9$\"%'!!:`&/ろ%。0!6妙2'!1$P+#W>.今&'残+(\"*。第C毛8'+(装飾さ4べき-U!J.<*<*)(E*&薬缶1。3!後O5'1\"ぶ逢+#.0]2片輪5-C度'出会G)#A.2\"。!み27UJ!真D./E\\5突起)(\"*。3%)(3!穴!D,76FL%L%$M8吹@。_%'咽Tぽ@(実5弱+#。04.;9!飲むM草$\"%'!&/*A-よ%や@0!頃知+#。";

// キーの数を取得
key_count = length(keys);

// 繰り返し使うので連番変数にしてしまう。rkが半角文字、rcは全角文字。
for (i=1; i<=key_count; i++) {
	set("rk" add i, substring(keys, i, 1));
	set("rc" add i, mbsubstring(vals, i, 1));
}

// BPEをデコード
text_length = mblength(bpe_text);
decoded_text = "";
for (j=1; j<=text_length; j++) {
	// 一文字ずつ変数cに格納
	c = mbsubstring(bpe_text, j, 1);
	call("DECODE");
	decoded_text = decoded_text add c;
}
// 元の文章が出力される筈
trace(decoded_text);
2フレーム目
// フレームラベル「DECODE」とつける
for (m=1; m<=key_count; m++) {
    if (get("rk" add m) eq c) {
        set("c", get("rc" add m));
        break;
    }
}

一文字ずつ走査してcに文字を代入し、DECODEフレームでキーと合う文字列があったら置き換える、といった方法で圧縮された文字列を展開して元の文章に戻しています。
上ではデコードキーとデコード文字列を連結して渡し、flash内で1文字ずつ変数化していますが、もちろん変数化した後の値を渡しても構いません。
経験則では日本語の文章はだいたい70%以下にまで縮みますので、50KBの所に70KB程の文字列が入る事になります。これはTwitterの発言に換算しますと、1発言が最大140文字で全てが2バイト文字の場合は140*2で280バイトになりますので、ざっと50発言程多く入れられる計算です。

圧縮は兎も角展開については割と簡単な実装で実現できますので、文字列が多く差し込まれるswfで容量が厳しいときは検討してみてはいかがでしょうか？