数値関数による長文圧縮

フィールド全体を通して規則性に乏しく, どういう経路を選んでもかなりのバイト数を要する問題は, しばしば長文と呼ばれます.
今回は, 数値関数の助けを借りて長文を攻略する手法を紹介しましょう.

基本的な考え方

不規則な長文であるほど, 多くの種類のパーツを作りたいわけですが,
それら全てについて, 良い圧縮率を誇る関数を考えるのは, 困難といえるでしょう.
例えば1変数関数f(X)を用いて, f(-)の形で多くの種類のパーツを作る場合,
当然その引数もたくさんの種類が必要になってくるはずで,
でも引数の部分が巨大になると良い圧縮率は得られません.

そこで, 数値に注目します. 数値は, 1から255までの255種類ありながら, どれもが1Bとして扱われます.
したがって, 上手い数値関数f(T)を作ると,

255種類のパーツが, 全て2バイトf(-)として記述できる!

ことになります. もちろん「255種類のパーツ」とは言っても,
あまりに無秩序に各数値に割り当てるのは困難です.
そこで, 「ある程度統一性のある255種類」であり, なおかつ「長文圧縮に有効」と考えられるものとして,
次のようなものを数値に対応させることが考えられます:

  1. [s] or [rs] or [rrs] or [rrrs] を合計4個並べたものは全部で256種ある. そのうち1種以外で255個.
  2. [s] or [rs] or [ls] を合計5個並べたものは全部で243種ある.
  3. [s] or [r] を合計8個並べたものは全部で256種ある. そのうち1種以外で255個.
  4. [s] or [rs] を合計8個並べたものは全部で256種ある. そのうち1種以外で255個.

これらの使い分けについてですが, 第1, 第2の方法は, 左にも右にも曲がりやすいですね.
第2の方法は, 後ろを振り返れなくなっているので問題によっては使えないですが,
使える問題だと, 第1の方法に比べて1つの数値で多く配置できるので有効になるかもしれません.

第3, 第4の方法についてですが, これもやはり第4の方法では, 後ろを振り返れない代わりに圧縮率を追求しています.
第1の方法と第3の方法, 第2の方法と第4の方法を比べた場合, どういう形が作れるかという点では完全に一致しますが,
圧縮率は経路によって異なってきそうです. 例えば

ssssssss

だと第1の方法では2つ, 第3の方法では1つの数値に対応しますし,

lsrslsrslsrslsrs

だと第1の方法では2つ, 第3の方法では (lをrrrと見なして) 3つの数値に対応します.
基本的には, 直進が多いか否かで選び分けると良さそうですね.

実装例

すべて, f(1)からf(255)にそれっぽいのが現れるようになっています.

数値の並べ方

さて, f(T)という関数で, 色んなパーツを255種類すべて作れるようになりました!
例えばs,rs,rrs,rrrsを4つ並べた場合には, 「4歩が2Bになる!」というわけです.
しかし実際にはもうひと工夫することで, よりよい圧縮率が実現できます.
例えば次の定義をしましょう:

g(A,B,C,D,E,F):f(A)f(B)f(C)f(D)f(E)f(F)

この定義により, 6つの数値を7Bで呼び出せるようになります.
「4歩が1つの数値になる!」だったので, 「24歩が7Bになる!」となり, 約3.5歩を1Bにできました!
引数を増やしていくと, 当然どんどん圧縮率は上がります.
仮想的に, 26個を超えて無限に多く引数を持たせると, 圧縮率は実質「4歩が1B」となりますね.

しかし, 高い圧縮率を実現しようとすると, 関数定義の負担も増えていくので, ある程度のところで妥協しないといけません.

例えば, 90個の数値を並べることを考えましょう. この場合, gの引数を変化させると,

(gの定義) + (実行部分)

は次のように変化します:

gの定義は簡単ですね. 1つ引数を追加するたびに3B増えます.
実行部分は, 90の約数のところは簡単ですね. (90/N) * (N+1)というような式です.
引数7個の場合は約数になってはいないのですが, 91個の数値を並べてしまうことにしてしまうと, 104Bになります.
引数4個の場合はこの考え方だと92個の数値を並べて115Bになりそうですが,

(88個の数値を並べる) + f(A) + f(B)

とした方が,

(88個の数値を並べる) + g(A,B,C,D)

よりも短くなっています. このような計算を経て, 今回は引数が5個 or 6個として圧縮するのが最善だと分かります.


結局この方法で長文を解くには,

というステップが必要です. 問題によっては, s, rs, rrs, rrrsが500個以上も並ぶ場合もあり,
数値の並びに変換するステップは特に大変なので, 何らかのプログラムを用意しておくといいでしょう.

もちろん, 有用な「並べ方」はここに挙げたものばかりとは限りませんし,
同じ並べ方についても, より良い関数定義がありうるかもしれません.
是非色んな手法を模索してみてください!


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-01-27 (日) 22:41:04 (2089d)