similarityをつかったゆるいbi-gram検索 応用編
俺自身は「インタフェース」派なんだけどさ・・・
前回の方式の問題
さて、前回のエントリ(similarityをつかったゆるいbi-gram検索 - 日々の記録 別館)で、N-gramのゆるい検索の一番基本的なパターンを示したのだけど、この方式にはまだまだ問題がある。
前回はトークン辞書内に「センヌリティウス」に類似する語が一つ(「セリヌンティウス」)だけだったので、問題はなかったのだが、類似する語が複数存在すると、サブクエリで返却されるレコードがN件になるためエラーになってしまう。
で、エラーを抑止するためにサブクエリ内でLIMIT 1で1件しか返却しないようにすれば、とりあえずの問題は回避できるのだが、そのやり方では、以下の様なケースに対応しきれない・・・
表記ゆれが多数存在するケース
日本語外来語には、この表記ゆれが多数存在するケースがしばしば見受けられる。
例えば、代表的なものとしては「インタフェース」(私はこの表記派)が挙げられる。
- インタフェース
- インターフェース
- インタフェイス
- インターフェイス
どうでもいいけど
Googleでそれぞれの表記が何件ヒットするか見てみると・・・
| インタフェース | 約 13,700,000 件 |
| インターフェース | 約 5,380,000 件 |
| インタフェイス | 約 14,000,000 件 |
| インターフェイス | 約 16,800,000 件 |
ということで、結構どの表記も有力っぽい・・・困ったものだ。
表記ゆれの例
例えば、以下のようなテキストがテーブルに格納されているとする。
bigm=# SELECT * FROM test; id | data ----+---------------------------------------------------------------------------------- 1 | 抗がん剤として用いられているインターフェロンを学ぶことにした。 2 | 今月号のインターフェースはコンパイラ特集だ。 3 | 実装はユーザインタフェースだけでなく、ユーザエクスペリエンスを考えねばならない。 4 | 発注元との意識ずれでインタフェイスの再設計をすることになった。 5 | 僕の考えた最強のユーザー・インターフェイスは却下された。 6 | C型肝炎の治療法としてインターフェノン治療という方法がある。 7 | 歌声喫茶でインターナショナルを熱唱した。 8 | 横浜へ遊びに行ってインターコンチネンタルホテルに泊まった。 9 | インターフェレンスとは「干渉」という意味である。 (9 rows)
で、これらからMecabを使って抽出＋若干の編集(「インタフェイス」は手動で追加)すると、こんなトークンテーブルが生成される。
bigm=# SELECT * FROM token ORDER by token;
token
------------------------------
（中略）
インター
インターコンチネンタルホテル
インターナショナル
インターフェース
インターフェイス
インターフェノン
インターフェレンス
インターフェロン
インタフェース
インタフェイス
コンパイラ
（後略）で、これらに対して前回のエントリで示した方法で検索するとサブクエリ内で複数レコードがヒットしてしまうので、当然ながらエラーになる。
bigm=# SELECT id, data FROM test WHERE data LIKE likequery( (SELECT token FROM token WHERE token % 'インタフェース' ORDER BY similarity(token, 'インタフェース') DESC) ) ; ERROR: more than one row returned by a subquery used as an expression
これを解決する一番安直な解決方法は、サブクエリから返却されるレコードをLIMITを使って1件に絞り込むことだ。
bigm=# SELECT id, data FROM test WHERE data LIKE likequery( (SELECT token FROM token WHERE token % 'インタフェース' ORDER BY similarity(token, 'インタフェース') DESC LIMIT 1) ) ; id | data ----+---------------------------------------------------------------------------------- 3 | 実装はユーザインタフェースだけでなく、ユーザエクスペリエンスを考えねばならない。 (1 row)
まあ、このケースの場合は完全一致するキーワード「インタフェース」を含むからあまり違和感はない。
しかし、「ゆるい検索」をしたい私にはちょっと不満が残る。
そう、表記ゆれのリストに上がっている「インターフェース」「インターフェイス」「インタフェイス」を含むテキストが検索されていないのが悲しい・・・。
N件のトークン候補を持つテキストの全文検索
最初、これを解決するためにはpg_bigmに追加の機能(LIKEでIN述語)の実装が必要なのかと思っていたのだが、PostgreSQL文書をいろいろ探しているうちに、PostgreSQLの機能の組み合わせだけで、なんとかなりそうだということがわかってきた。
以下にその方法を示す。
方式の概要
方式は至って簡単。
- PostgreSQLはスカラと配列間の評価を行うために、ALL/ANY構文が用意されている。
- 今回の場合、条件値と配列の間をLIKE評価して一つでもLIKE評価が真の配列要素が存在すれば真とする評価(ANY評価)を行えば良い。
- 配列にはtokenテーブルから検索されたN行の結果を配列に変換したものを与えれば良い。
- N行の結果を配列にするために、array_agg関数を使えば良い。
実例
ということで、「インタフェース」を条件として与えて、「インターフェース」「インターフェイス」「インタフェイス」などの表記揺れをもつテキストを1つのクエリで検索する例を示す。
わかりやすくするため、各ステップ別にクエリを発行してみる。
まず、「インターフェース」を条件と与えてtokenテーブルから最もsimilarity関数の結果として類似している上位5件のトークンを求めるクエリの例を示す。
bigm=# SELECT token AS token FROM token WHERE token % 'インタフェース' ORDER BY similarity(token, 'インタフェース') DESC LIMIT 5;
token
--------------------
インタフェース
インターフェース
インタフェイス
インターフェイス
インターフェレンス
(5 rows)「インターフェレンス」が取得されちゃうのは、まあご愛嬌ってことでｗ
最終的にこの結果はLIKE文にかけるので、中間一致検索をさせるために前後に'%'を付与しなければならない。幸い、pg_bigmにはその手のちょっと面倒な操作をサポートするlikequeryという関数があるので、それを使わせてもらう。
bigm=# SELECT likequery(token) AS token FROM token WHERE token % 'インタフェース' ORDER BY similarity(token, 'インタフェース') DESC LIMIT 5;
token
----------------------
%インタフェース%
%インターフェース%
%インタフェイス%
%インターフェイス%
%インターフェレンス%
(5 rows)次にこの結果を1つの配列に集約する。このためにarray_agg関数を用いる。
bigm=# SELECT array_agg(sml.token) FROM (SELECT likequery(token) AS token FROM token WHERE token % 'インタフェース' ORDER BY similarity(token, 'インタフェース') DESC LIMIT 5) as sml;
array_agg
------------------------------------------------------------------------------------------------
{%インタフェース%,%インターフェース%,%インタフェイス%,%インターフェイス%,%インターフェレンス%}
(1 row)これで1行の配列に結果を集約できた。
あとは、この配列に対してLIKE＋ANY演算をかければOK。
一つ注意が必要なのはLIKE条件値となる配列をTEXT型の配列だと明示的に示しておかないとエラーになるということくらいか。
bigm=# SELECT data FROM test WHERE data LIKE ANY ((SELECT array_agg(sml.token) FROM (SELECT likequery(token) AS token FROM token WHERE token % 'インタフェース' ORDER BY similarity(token, 'インタフェース') DESC LIMIT 5) as sml)::text[]);
data
----------------------------------------------------------------------------------
今月号のインターフェースはコンパイラ特集だ。
実装はユーザインタフェースだけでなく、ユーザエクスペリエンスを考えねばならない。
発注元との意識ずれでインタフェイスの再設計をすることになった。
僕の考えた最強のユーザー・インターフェイスは却下された。
インターフェレンスとは「干渉」という意味である。
(5 rows)「インタフェース」を条件として
「インタフェース」
「インターフェース」
「インタフェイス」
「インターフェイス」
を含むテキストを検索することが出来た。(ﾄﾞﾔｧ
＃「インターフェレンス」が検索されているのがちょっと微妙だが、ご愛嬌ってことでｗ
一応プランを確認
じゃあ、一応、プランも確認してみるか・・・と。
bigm=# EXPLAIN SELECT data FROM test WHERE data LIKE ANY ((SELECT array_agg(sml.token) FROM (SELECT likequery(token) AS token FROM token WHERE token % 'インタフェース' ORDER BY similarity(token, 'インタフェース') DESC LIMIT 5) as sml)::text[]);
QUERY PLAN
---------------------------------------------------------------------------------------------------
Seq Scan on test (cost=10000000040.06..10000000041.26 rows=1 width=32)
Filter: (data ~~ ANY ($0))
InitPlan 1 (returns $0)
-> Aggregate (cost=40.05..40.06 rows=1 width=32)
-> Limit (cost=40.03..40.03 rows=1 width=32)
-> Sort (cost=40.03..40.03 rows=1 width=32)
Sort Key: (similarity(token.token, 'インタフェース'::text))
-> Bitmap Heap Scan on token (cost=36.00..40.02 rows=1 width=32)
Recheck Cond: (token % 'インタフェース'::text)
-> Bitmap Index Scan on token_idx (cost=0.00..36.00 rows=1 width=0)
Index Cond: (token % 'インタフェース'::text)
(11 rows)ぎゃあああ・・・
肝心のテキスト検索側でインデクス使われてないじゃないですか、やだー！
この問題をなんとか解決しなくては。
やっぱり定数と配列間の比較演算とインデクス演算子を実装しないと駄目なのかな・・・orz
ということで、ゆるいbi-gram検索の実装はもう少し頑張らないといけないようだ。しくしく。
