高階圧縮

文字列圧縮の分野で近年盛んに研究されている文法圧縮という手法がある．(例:SLP)

この手法は与えられた文字列を生成する文脈自由文法を構成し，それを保存することによって元のデータサイズより小さいサイズでの保存を達成する.

ここで高階圧縮とは与えられた文字列を生成する高階プログラムを構成し，それを保存する圧縮法である．（ここでは高階プログラムとしてラムダ式を用いる）

ラムダ式は文脈自由文法より表現力が強いため，高階圧縮は文法圧縮より小さいサイズでの圧縮が期待されている．

高階圧縮の例としてaが65536回続いた後に$がくるテキストを考える．

この時　（λf.f f f f a $）(λx.λy.x (x y))　という短いラムダ式で上記のテキストを表現可能である．

上記のように超指数的な表現が可能であり，また高階モデル検査によってデータを展開することなく操作可能などの利点がある．

現在の研究では，XMLデータに対して効果的な圧縮であることがわかっている．

ここからさらに，どのようなデータに効果的なのかや，DNAなどの遺伝情報から既存の技術では発見できないような高階なパターン （たとえばその個人特有の関数や家族間で共通したパターンがあるかなど）が見つかるかどうかの実験を続けていく．

また，高階圧縮の高速化や圧縮手法の改善なども並行しておこなっている．

発表文献

“高階圧縮の高速化と効率の良い符号化”，矢口和也, 小林直樹, 篠原歩,　コンピュテーション研究会，vol.~113, no.~252, COMP2013-34, pp.~13-20, 2013年10月

参考文献

Naoki Kobayashi, Kazutaka Matsuda, Ayumi Shinohara: Functional programs as compressed data. PEPM 2012: 121-130