2016-03-01から1ヶ月間の記事一覧

Rubyで素朴なSA-IS(suffix array induced sorting)を書いてみた

FM-indexと同様に、ほぼ最適化をしていない素朴な実装を作ってみました。元の論文の実装は空間効率まで考慮して書かれていてすごい! ……のですが、まずはそれ以外の部分の仕組みを理解したかったので、以下のコードではそこらへんも無視しています。 コード …

Rubyで素朴なFM-indexを書いてみた

BWT、検索処理の最適化・高速化は行なっていません(SA-IS、ウェーブレット行列などは使っていません)。 BWT から検索まで全体の流れが見渡せる最小限の実装にしました。 せっかくなので Ruby に馴染みのない方が見ても読みやすいと思われる書き方にしてい…