2013年度の文法圧縮の進展 - Yasuo Tabeiの日記
年が明けて2014年の１月ももう半分まで来てしまいましたが、調度良い時期ですので, 2013年の振り返り記事の代わりに2013年の文法圧縮の進展を振り返ってみたいと思います。 はじめに文法圧縮を簡単におさらいすると, 文法圧縮とは入力となるテキストのみを表現する小さいCFGを構築する圧縮方式です. ゲノム配列, バージョン管理されたテキスト, リポジトリー上でのソースコードなど反復する部分列を多く含むテキストに対して高い圧縮率を達成することができます. これらのテキストは反復テキストと呼ばれ, 次世代シーケンサー技術やバージョン管理ソフトの発展により文法圧縮は今後ますます重要な技術と言えます. 文法圧縮には２つの問題があります。一つ目は入力テキストを表現する小さいCFGをどのように構築するかという問題です。最小化問題はNP-hardとして知られていて, 現在までにさまざまな近似アルゴリズム
文法圧縮 (Edit Sensitive Parsing (ESP))を実装してみた - Yasuo Tabeiの日記
ALSIPの時に聴いて気になっていた文法圧縮法Edit Sensitive Parsing (ESP)を実装しました。 文法圧縮とは、与えられた文章から曖昧でない文脈自由文法*1をもとめることにより圧縮する手法です。文脈自由文法のサイズは、導出規則の右辺の終端記号と非終端記号の個数の総和として求められますが、サイズ最小の文脈自由文法を求める問題はNP-Hardとして知られています。これまで近似解を求める手法が提案されてきましたが、文書長 n に線形なメモリが必要で実用的ではありませんでした。例えば、有名な文法圧縮法の一つであるRePairはおおよそ5nのメモリが必要です[1]。2002年にCormodeら[2]が、文書長に依存しないメモリーで文脈自由文法を求める手法(Edit Sensitive Parsing (ESP))を提案しました。必要なメモリーは、文脈自由文法のサイズをgとしたと
ESPによる文法圧縮の実装を公開しました。 - Yasuo Tabeiの日記
2012-02-04の記事 http://d.hatena.ne.jp/tb_yasu/20120204 のESPによる文法圧縮の実装に関して問い合わせが数件ありましたのでソースコードを公開しました。 今後のアップデートのしやすさを考慮してgithubにアップロードしました。 https://github.com/tb-yasu/GrammarCompression 現在のところ、文章から文法を構築する機能と、文法から文章を復元する機能をサポートしています。 esp-0.0.1.tar.bz2をダウンロードしましたら、tarで解凍してください。 tar -xzvf esp-0.0.1.tar.bz2 解凍出来ましたらmakeでコンパイルできます。 cd esp-0.0.1/src make 文章から文法を構築する際は、esp-compressコマンドを使用します。 ./esp-compre
2013年前半振り返り - Yasuo Tabeiの日記
暑い日々が続きますが、いかがお過ごしでしょうか？ 早いもので2013年もう８月ということでだいぶ遅いですが2013年の前半の成果を振り返ってみたいと思います。幸いにも2013年の前半に4本論文を出す事ができました。内分けは、データマイニング・機械学習1本、バイオインフォマティクス1本、 文字列処理２本となります。以下では１つ１つ論文の内容を簡単に紹介していきたいと思います。 Yasuo Tabei, Akihiro Kishimoto, Masaaki Kotera, Yoshihiro Yamanishi: Succinct Interval Splitting Tree for Scalable Similarity Search of Compound-Protein Pairs with Property Constraints, 19th ACM SIGKDD Conferenc
FM-index++を公開しました - Yasuo Tabeiの日記
FM-indexのC++による実装 FM-index++を公開しました。 http://code.google.com/p/fmindex-plus-plus/ FM-index[1〜4]とは、圧縮全文索引の一種でO(n)時間とO(nlgσ)メモリー(n:テキスト長、σ:文字種類数)で構築することができます。最近では、テキスト処理ばかりでなくゲノム検索[5]など、いろいろなところで応用されています。今回は、クエリーに対する検索操作の内、exact検索、ハミング距離による検索、編集距離による検索の３つを実装しました。それぞれの計算時間は、qがクエリーの長さとすると、exact検索がO(q)時間、 ハミング距離による検索がO(q^σ)時間、編集距離による検索がO((q \times q)^σ)時間です。よって、４文字種のDNAや２０文字種のタンパク質など、文字種類数が少ない対象にはハミング距離
MinHashを用いたSketchSort - Yasuo Tabeiの日記
MinHashを用いたSketchSortの論文がMolecular Informaticsに採択されました。 論文は下のサイトからダウンロードすることができます。 Yasuo Tabei and Koji Tsuda: SketchSort: Fast All Pairs Similarity Search for Large Databases of Molecular Fingerprints, Molecular Informatics, 2011. Link ソフトウェアをgoogle codeにて公開しています。 本論文では、以前紹介したCosine距離に基づく高速な全点間類似度検索法(SketchSort)をJaccard-Tanimoto距離に基づく手法に拡張しました。このため、以前は与えられた任意の２点間のCosine距離をハミング距離で保存したままバイナリ文字列へとハッ
大規模フィンガープリント類似検索のための簡潔マルチビット木の実装を公開しました - Yasuo Tabeiの日記
以前のブログで紹介した簡潔マルチビット木のc++による実装 (Succinct Multibit Tree (SMBT)) を公開致しました。ソフトウェアーはgoogle codeからダウンロードすることができます。 http://code.google.com/p/smbt/ SMBTは去年のWABIで発表した内容にもとづいています。 簡潔マルチビット木に関するブログ記事 : http://d.hatena.ne.jp/tb_yasu/20120808/1344415559 論文 : Yasuo Tabei: Succinct Multibit Tree: Compact Representation of Multibit Trees by Using Succinct Data Structures in Chemical Fingerprint Searches, Workshop
人工知能学会誌 私のブックマークに簡潔データ構造という題で記事を書きました - Yasuo Tabeiの日記
人工知能学会誌の私のブックマークに簡潔データ構造という題で記事を書きました。私のブックマークは研究者が自らの研究をする中で普段使っているWeb上のリソースを公開するための記事です。今までいろいろな研究者が記事を書かれています。 http://www.ai-gakkai.or.jp/jsai/journal/mybookmark/ 幸いにも今回は、私が執筆の機会を頂くことができたので情報検索などでよく使われている簡潔データ構造のリソースについてまとめてみました。 http://www.ai-gakkai.or.jp/jsai/journal/mybookmark/26-6.html 記事を書いてみて思ったことは、ライブラリの充実により実際の場面で使いやすくなっていることと、多くのエンジニアや研究者がブログなどをつうじて記事を公開してくださっているおかげでこの分野が日本語で勉強しやすくなってい
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
