« 卒業式 | Main | スノーバードへ »

2005.03.27

自転車

の鍵を紛失したため、家までかついで歩いた・・。すごい疲れた。家でドライバーではずした。

今日はバイト。NE抽出しはじめました。終わってそしてラーメン食って学校へ。ぎりぎり泳げる時間があったので泳いだ。

そのあと、あさってからDCCでポスター発表というわけでその準備。今回は、任意の位置から低領域、高速で復元できるように圧縮するというStatic PPMと呼んでいる手法に関する発表。次の文字を予測することで圧縮を行うPPMを、その予測に使うモデルを固定することで、位置の同期さえとれればどこからでも復元できるというもの。その上予測に使うモデルを前もってDFAに変換しておくことで高速、低領域にもできる長所もある。しかし問題はどうやってそのようなモデルを作るかということ。というのもモデル自身も保存しなければならないからだ。この問題設定はMDL原理とまったく同じである。通常のPPMのように巨大な予測モデルは使えない。

Suffix Treeとまったく同様の考えでPrefixを用いるPrefix Treeを考えると、もしモデルとしてPrefix Treeがあるなら次の文字は唯一に予測できる(データ自体は何も保存しなくてよい)。しかしPrefix Treeを保存するのはコストが高い。そこで、Prefix Treeを枝刈りしたものを予測モデルとして使えばいいだろうというのがアイデア。実際にはPrefix Treeを根だけの状態からコストを計算しながら伸ばしていく。この計算はPrefix Arrays構築の部分に含めることができるので、実際にはPrefix Tree(Arrays)を完全に構築するより少ないコストで予測モデルは構築できる。予測モデルはDFAに変換され、そのあと符号化、復元はLZ並の速さで処理できる。

すでにCSAやFM-indexなど部分復元できるデータ構造があるが、これらは圧縮ファイル全体をメモリに載せておかないといけない。Static PPMならば、実験結果では、圧縮後のサイズが300MBのものは1MB程度しかメモリを必要としない

問題点として、この部分復元はindexだけしか指定できないことがあげられる(たとえば1058372byte目から100byte)。実用上は部分復元は検索結果などと組み合わせる場合がほとんど(たとえばtheが出現する場所の周辺1kBなど)。Prefix Treeを枝刈りしているという意味では、ある程度の効率で検索ができるはず。

|

« 卒業式 | Main | スノーバードへ »

Comments

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/3041/3453780

Listed below are links to weblogs that reference 自転車:

« 卒業式 | Main | スノーバードへ »