similarityをつかったゆるいbi-gram検索

セリヌンティウスは激怒した。俺は「センヌリティウス」じゃねー!

similarity関数を使ったゆるいbi-gram検索をしてみる

pg_bigmのsimilarityサポート版が動くようになったので、そろそろ本当にやりたかった「ゆるいbi-gram検索」をやってみようと思う。
といっても、文書とbi-gramインデクスだけでは出来ないので、いくつかの他のソフトウェアの手助けと準備が必要になる。

必要なもの

とりあえずMecabがあれば何とかなりそう。
APIとかを叩くのは面倒なので検索対象の文書のロード元ファイルに対してmecabのコマンドを実行し、そこから名詞のみを抽出したテキストファイルを作っておく。ロード元文書のファイルは例によって、青空文庫の「走れメロス」を使わせてもらおう。

今回の例の場合、hashire_merosu.txtをmecabにかけ、そこからmeros-token.txtというファイルを生成する。

$ mecab hashire_merosu.txt | grep 名詞 | gawk '{print $1}' | sort | uniq > merosu-token.txt

生成したファイルの中はこんな感じ。

(前略)
わが身
わけ
わし
ん
アレキス
シラクス
シルレル
セリヌンティウス
ゼウス
ディオニス
フィロストラトス
マント
メロス
哀れ
(後略)

ゆるい検索

pg_bigm+similarityを使ったゆるい検索は、以下のような方法になる。

  • トークン用テーブルに対して、誤りを含むキーワード渡し、類似度を算出。
  • 類似度が閾値を超え、かつ最も類似度が高い結果を1件返却する。
    • ここで揺らいだキーワードをトークン用テーブル内にあるトークンに正規化(という言い方が正しいかは微妙だが)する。
  • 正規化されたキーワードを使って、検索対象の文書に対してbigm検索を行う。

トークン用テーブルの生成

以下のように、トークン用のテーブル(token)を作り、そこにさっき生成した名詞のみを抜き出したテキストをロードし、そのトークン用テーブルに対してpg_bigmのインデクスを設定する。

CREATE TABLE token (data text);
COPY token (data) FROM '/tmp/merosu-token.txt';
CREATE INDEX token_bigm_idx ON token USING gin (data gin_bigm_ops);

今回は、検索対象となる青空文庫から抜き出したものを使うが、実際に使う場合にはMecabで使っているようなIPA辞書+検索対象となるテキストにあった辞書みたいなものを作って、それをテーブルに格納することになると思う。

トークン用テーブルへの検索

で、このトークン用テーブルに対して、誤りを含むようなテキストを与えて、最も類似度が高いキーワードを抜き出す。
例えばこんな感じ。

bigm=# SELECT data FROM token WHERE data % 'センヌリティウス' ORDER BY similarity(data, 'センヌリティウス') DESC LIMIT 1;
       data
------------------
 セリヌンティウス

「センヌリティウス」に最も近い「セリヌンティウス」が返却された。
ちなみに「センヌリティウス」と「セリヌンティウス」の類似度は

bigm=# SELECT similarity('セリヌンティウス','センヌリティウス');
 similarity
------------
   0.384615

という値なので意外と低いw
仕組み上、文字の入れ替えなどがあるとヒットしないbi-gramが増えるからだろうけど。

取得したトークンによる全文検索

で、あとは上記のトークン取得のクエリをサブクエリとしてlikequery関数に与えればOKだ。

bigm=# SELECT id, data FROM test WHERE data LIKE likequery(
 (SELECT data FROM token WHERE data % 'センヌリティウス' ORDER BY similarity(data, 'センヌリティウス') DESC) 
) ;
(中略)
 64 |  セリヌンティウスは、すべてを察した様子で首肯《うなず》き、刑場一ぱいに鳴り響くほど音高くメロスの右頬を殴った。殴ってから優しく微笑《ほほえ》み、
 66 |  メロスは腕に唸《うな》りをつけてセリヌンティウスの頬を殴った。

「センヌリティウス」で
セリヌンティウス」を含む
テキストの全文検索が出来た。(ドヤァ!

きちんとトークン取り出しのところ(token_bigm_idx)も、全文検索のところ(test_bigm_idx )もインデクスが使われてますね。善哉。

bigm=# EXPLAIN SELECT id, data FROM test WHERE data LIKE likequery(
 (SELECT data FROM token WHERE data % 'センヌリティウス' ORDER BY similarity(data, 'センヌリティウス') DESC) 
);
                                         QUERY PLAN
--------------------------------------------------------------------------------------------
 Bitmap Heap Scan on test  (cost=56.04..60.06 rows=1 width=323)
   Recheck Cond: (data ~~ likequery($0))
   InitPlan 1 (returns $0)
     ->  Sort  (cost=44.03..44.04 rows=1 width=6)
           Sort Key: (similarity(token.data, 'センヌリティウス'::text))
           ->  Bitmap Heap Scan on token  (cost=40.01..44.02 rows=1 width=6)
                 Recheck Cond: (data % 'センヌリティウス'::text)
                 ->  Bitmap Index Scan on token_bigm_idx  (cost=0.00..40.01 rows=1 width=0)
                       Index Cond: (data % 'センヌリティウス'::text)
   ->  Bitmap Index Scan on test_bigm_idx  (cost=0.00..12.01 rows=1 width=0)
         Index Cond: (data ~~ likequery($0))
(11 rows)

おわりに

ということで、とりあえず一人はbi-gramのsimilarity関数サポートがあると嬉しいユーザがいるので、正式版に取り込んでもらえることを期待しています。>藤井さん&澤田さん