wat-arrayでラクラク実装☆FM-Indexの作り方 - EchizenBlog-Zwei
というわけで大変便利なライブラリwat-arrayを使ってFM-Indexを簡単に実装してみるよ。本格的なライブラリは既にFM-Index++という良いものがあるので、本記事では仕組みの解説を目的とする。 参考資料: FM-index++を公開しました - tb_yasuの日記 An alphabet-friendly FM-index (P. Ferragina, G. Manzini, V. Makinen, G. Navarro, 2004) なお、本記事では前回の記事で実装した(ってほどでもないけど)text2bwt()とLF()を使っている。 話題のwat-arrayを使ってBurrows-Wheeler変換(BWT)してみた - EchizenBlog-Zwei 今回もテキストとしてmississippi#を使う。まずテキストから任意のキーの出現回数を得る関数get_rows(
話題のwat-arrayを使ってBurrows-Wheeler変換(BWT)してみた - EchizenBlog-Zwei
先日PFIの岡野原氏によってwat-arrayというライブラリが公開された。 wat-array : wavelet木を利用した高速配列処理ライブラリ : Preferred Research Blog このライブラリは内部でウェーブレット木(wavelet tree)という簡潔データ構造(succinct data structure)を使っている。このため文字列に対するrank()やselect()などの操作が効率的にできるようになっている。 ・・・といっても馴染みのない人にとっては何が嬉しいのかピンと来ないかもしれない。そこでBurrows-Wheeler変換(BWT, Burrows-Wheeler Transform)を例にとってwat-arrayの使いみちを説明してみる。 Burrows-Wheeler変換というのはテキストを同じ文字が並びやすいように変換したもので、通常ランレ
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や２０文字種のタンパク質など、文字種類数が少ない対象にはハミング距離
Compressed Permuterm Index - 射撃しつつ前転 改
hillbigさんに紹介してもらったCompressed Permuterm Indexをちょっと前に読んだ。Compressed Permuterm Index以前にそもそもbackward search自体が理解できなくて、refferされてる別の論文読んだりしてたらだいぶ時間がかかってしまった。 この論文に書かれているアイデアを文章で説明するなら、単語集合を*辞書順にソートしておけば*、Suffix Arrayを作ったときに、単語の先頭から末尾へジャンプするのは簡単だ、という事だ。この事実を利用して、Prefix Suffix Searchが実現できるよーと言うのがこの論文の主張。アイデア自体はすごい単純だし、実装もすごく簡単なんだけど、どんなものを食べればこんなすごいアイデアが出てくるようになるのかはさっぱりわからない。脱帽。 backward searchに関しては、というか、圧
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
