FM-Indexライブラリに文書検索機能を実装しました

計算機科学

ウェーブレット木ライブラリShellinfordのFM-Indexクラスに文書検索機能を追加実装したので公開しておく。


テストデータとして(http://jusyo.jp/)の住所データを用いる。

$$ mkdir var
$$ cd var
$$ wget http://jusyo.jp/downloads/new/csv/csv_zenkoku.zip
$$ unzip csv_zenkoku.zip

$$ nkf -w zenkoku.txt > zenkoku.txt.utf8
$$ perl -ne '@a=split(/\t/);$s="$a[7]$a[9]$a[11]";
     $s=~s/"//g;print "$s\n"' zenkoku.txt.utf8 > zenkoku.key
$$ sort -u zenkoku.key -o zenkoku.key
$$ cd ..

インストは以下のとおり。

$$ cd src
$$ make
$$ sudo make install
$$ cd ..

あとはshellinford/sample/以下のサンプルを使って文書検索ができる。

$$ cd sample
$$ make
$$ ./make_fm_index ../var/zenkoku.index < ../var/zenkoku.key

これでzenkoku.indexという検索用の辞書ができた。あとは

$$ ./search_fm_index ../var/zenkoku.index
麻布
10 hits.
[20812]: 北海道目梨郡羅臼町麻布町(1)
[70320]: 新潟県三条市麻布(1)
[76668]: 東京都港区元麻布(1)
[76672]: 東京都港区南麻布(1)
[76677]: 東京都港区東麻布(1)
[76689]: 東京都港区西麻布(1)
[76692]: 東京都港区麻布十番(1)
[76693]: 東京都港区麻布台(1)
[76694]: 東京都港区麻布永坂町(1)
[76695]: 東京都港区麻布狸穴町(1)

というように麻布を含む文書(住所)が検索できる。
というわけでそれなりに使えるものができた気がする。とりあえずの利用者は自分なので積極的に活用していく予定。