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や２０文字種のタンパク質など、文字種類数が少ない対象にはハミング距離及び編集距離による検索は応用できますが、テキストなどの文字種類数が多い対象に応用するのは困難です(exactな検索は可能)。FM-indexは、接尾辞配列とウェーブレット木をもとにして構築することができるのですが、接尾辞配列はmoriさんによるinduced sortingの実装 SAIS(http://sites.google.com/site/yuta256/sais)を、ウェーブレット木は岡野原さんによるwat-array(http://code.google.com/p/wat-array/)を使わさせていただいております。

2011年1月6日
仕組みについてechizen_tmさんが詳しく解説しています。こちらもご参照ください。
http://d.hatena.ne.jp/echizen_tm/20110102/1293996904

参考文献
[1]Paolo Ferragina and Giovanni Manzini. Opportunistic data structures with applications. In Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS), Redondo Beach, CA, (USA), 2000.
[2]Paolo Ferragina and Giovanni Manzini. An experimental study of an opportunistic index.In Proc. 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), Washington DC, (USA), 2001.
[3]Paolo Ferragina and Giovanni Manzini. Indexing compressed text. Journal of the ACM (JACM), 52, 4 (Jul. 2005), 552-581
[4]Paolo Ferragina and Giovanni Manzini. An experimental study of a compressed index. Information Sciences. Vol 135, (2001), 13-28.
[5]Li H. and Durbin R. (2009) Fast and accurate short read alignment with Burrows-Wheeler Transform. Bioinformatics, 25:1754-60.