ちゃお……†

今回はPythonでお手軽にテキスト全文検索出来るライブラリ shellinford-python を紹介します。

こちらは@echizen_tmさんの shellinford をSWIGでPythonで動作させるようにしたのと、若干の機能追加したものです。Python環境さえあれば簡単にシンプルな全文検索出来るのでお手軽かと思います。

FM indexとは

バイオインフォマティクスなんかで使われる検索アルゴリズムです。わたしが説明するより良い説明を見つけたので以下に引用します。

シークエンサーのデータを解析するとき、リードをリファレンス配列にマッピングすることが第一歩である。一般にシークエンサーのリードは数百万個以上で、また、リファレンス配列の塩基数は数億にも及ぶ。これらの数百万のリードを、数億塩基からなるリファレンス配列にマッピングする際に、高速な文字列検索アルゴリズムが必要される。このようなアルゴリズムとして、FM index がある。実際に、現在のマッピングプログラムのほとんどは、FM index アルゴリズムを中心に使用してマッピングを行なっている。なお、FM index は完全一致でしか検索できない。そのため、ほとんどのプログラムでは、まずリードの一部分だけをリファレンスに対して完全一致で検索する。そして、完全一致でヒットした箇所で、リードの残った部分をリファレンスに対して Smith-Waterman アルゴリズムでアライメントを行う。
https://bi.biopapyrus.jp/rnaseq/mapping/bwt.html

shellinford-pythonの使い方

インストール

pip install shellinford

PYPIでWindows用のwheelを配布しているのでWindowsでのC++11コンパイル環境がなくても使えると思います。その他のOSではC++11コンパイル環境が必須です。

インスタンスを生成

import shellinford
fm = shellinford.FMIndex()

shellinford.FMIndex([use_wavelet_tree=True, filename=None])

filename パラメーターに str を与えた場合は、パスにある FMIndex モデルのファイルをロードします。

FM-index モデルを作る

fm.build(['Milky Holmes', 'Sherlock "Sheryl" Shellingford', 'Milky'], 'milky.fm')

FMIndex.build([docs, filename])

docs には str 型の list を与えます。 filename に str を与えるとそのパスにモデルを保存します。

上記の例では、下記のドキュメントを 'milky.fm' に保存します。

Milky Holmes
Sherlock "Sheryl" Shellingford
Milky

FM-index モデルから指定した文字列が含まれているドキュメントを検索する

search(query, [_or=False, ignores=[]])

query パラメーターは str あるいは str の list です。 _or パラメーターに True を与えるといわゆるOR検索を行います。デフォルトではいわゆるAND検索です。ignores は str の list で、検索対象から除外したい文字列を指定できます。

注意点として search メソッドは、FM-indexモデルを生成した後かロードしたのみ使えます。

1つのキーワードで検索する例

>>> for doc in fm.search('Milky'):
>>>     print('doc_id:', doc.doc_id)
>>>     print('count:', doc.count)
>>>     print('text:', doc.text)
doc_id: 0
count: [1]
text: Milky Holmes
doc_id: 2
count: [1]
text: Milky

複数のキーワードでAND検索する例

>>> for doc in fm.search(['Milky', 'Holmes']):
>>>     print('doc_id:', doc.doc_id)
>>>     print('count:', doc.count)
>>>     print('text:', doc.text)
doc_id: 1
count: [1]
text: Milky Holmes

指定した文字列を含むドキュメントの数をカウントする

>>> fm.count('Milky'):
2

>>> fm.count(['Milky', 'Holmes']):
1

count(query, [_or=False])

こちらもquery パラメーターは str あるいは str の list です。 _or パラメーターに True を与えるといわゆるOR検索を行います。デフォルトではいわゆるAND検索です。カウントしたいだけの場合は、count メソッドの方が search メソッドより少し処理が速いです。

注意点として count メソッドも、FM-indexモデルを生成した後かロードしたのみ使えます。

ドキュメントを追加する

>>> fm.push_back('Baritsu')

push_back(doc)

doc パラメーターは str です。

注意点として push_back メソッドは、 build メソッドでFM-indexモデルをビルドするまで検索に反映されません。

ファイルからFM-indexモデルをロードする

>>> fm.read('milky_holmes.fm')

read(path)

path は str でモデルのパスを指定します。

FM-indexモデルをファイルに書き込む

>>> fm.write('milky_holmes.fm')

write(path)