DivSufDict: A Linewise Dictionary Wrapper of libdivsufsort for Python / C++

DivSufDict とは

DivSufDictは行指向の辞書を前方一致で高速に検索するためのクラスです。libdivsufsortのラッパーとして書かれており、Python / C++から利用できます。

実験コードとして書いたものであり、内部的にはすべてのバイトにインデックスポイントを設定するという、かなり無駄のある作りとなっています（この用途であれば本来は行頭のみをインデックスすれば良い）。ご注意ください。

ダウンロード

DivSufDict はフリーソフトウェアです． MIT Licenseに従って本ソフトウェアを使用することができます。

DivSufDictをコンパイルするためにはBoostとlibdivsufsortがインストールされている必要があります。swigも必要です。

インストール

% tar xvzf DivSufDict-0.1.0.tar.gz
% cd DivSufDict
% sudo python setup.py install

DivSufDictはboostライブラリとlibdivsufsortを必要とします。 boostは/usr/local/include/boostに、 libdivsufsortは/usr/local/includeにあることを想定しています。もしお使いのシステムで上記の場所に必要なファイルが無い場合は、 setup.pyのswig_opts, include_dirsの項目を直接編集してください。

...
swig_opts=['-I./swig',
           '-I/usr/local/include',          # ← ここ(libdivsufsort)
           '-c++', '-python', '-shadow'],
...
include_dirs=['/usr/local/include/boost',   # ← ここ(boost)
              '/usr/local/include',         # ← ここ(libdivsufsort)
              '/usr/include',
              'swig']),
...

使い方

基本

% python
...
>>> from DivSufDict import DivSufDict, VectorString, VectorSAIdx
>>> text = """\
... abracatabra 1
... abracatab 2
... sumomomomomomo 3
... sumomo 4
... """
>>> 
>>> d = DivSufDict()
>>> d.make_sary(text)
0
>>> 
>>> res = VectorString()
>>> d.search_sary_string(text, "sum", res)
>>> for r in list(res):
...   print r
...
sumomo 4
sumomomomomomo 3
>>> 
>>> res = VectorSAIdx()
>>> d.search_sary(text, "abra", res)
>>> for r in res:
...   print r
...
14
0

textはutf-8文字列です。make_sary() でメモリ上にSuffix Arrayを作成します。search_sary_string(), search_sary()で、行頭からの前方一致検索を行います。search_sary_string()はマッチした行のコピーを、search_sary()はマッチする行の開始位置を返します。返値はそれぞれの第3引数に渡されたVectorString/VectorSAIdxオブジェクトにセットされます。
第4引数（オプション）に正数を与えることで、返される結果の数を制限することも可能です。

TODO

save_sary()作成

DivSufDict: A Linewise Dictionary Wrapper of libdivsufsort for Python / C++

DivSufDict とは

新着情報

ダウンロード

インストール

使い方

基本

TODO