エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
2013年度の文法圧縮の進展 - Yasuo Tabeiの日記
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
2013年度の文法圧縮の進展 - Yasuo Tabeiの日記
年が明けて2014年の1月ももう半分まで来てしまいましたが、調度良い時期ですので, 2013年の振り返り記... 年が明けて2014年の1月ももう半分まで来てしまいましたが、調度良い時期ですので, 2013年の振り返り記事の代わりに2013年の文法圧縮の進展を振り返ってみたいと思います。 はじめに文法圧縮を簡単におさらいすると, 文法圧縮とは入力となるテキストのみを表現する小さいCFGを構築する圧縮方式です. ゲノム配列, バージョン管理されたテキスト, リポジトリー上でのソースコードなど反復する部分列を多く含むテキストに対して高い圧縮率を達成することができます. これらのテキストは反復テキストと呼ばれ, 次世代シーケンサー技術やバージョン管理ソフトの発展により文法圧縮は今後ますます重要な技術と言えます. 文法圧縮には2つの問題があります。一つ目は入力テキストを表現する小さいCFGをどのように構築するかという問題です。最小化問題はNP-hardとして知られていて, 現在までにさまざまな近似アルゴリズム