takuti.me ABOUT

2017-08-09

あのときのビールをもう一度(PostgreSQLでFuzzy Searchを試す)

Seven Databases in Seven Weeks を読んでいたら、PostgreSQLでテキスト検索をする話が出てきた。先日 Levenshtein Distance(編集距離)について書いたばかりでホットな話題なので、少し遊んでみよう。

$ postgres --version
postgres (PostgreSQL) 9.6.3

※インデックスと英語以外の言語の場合については割愛。

データ

お気に入りのアメリカのクラフトビールデータセットを使う。適当に create table してCSVからデータを読み込む:

create table beers (
    key int,
    abv real,
    ibu real,
    id int,
    name varchar(128),
    style varchar(64),
    brewery_id int,
    ounces real
);
\copy beers from 'beers.csv' with csv;
sample=# select * from beers limit 5;
 key |  abv  | ibu |  id  |        name         |             style              | brewery_id | ounces
-----+-------+-----+------+---------------------+--------------------------------+------------+--------
   0 |  0.05 |     | 1436 | Pub Beer            | American Pale Lager            |        408 |     12
   1 | 0.066 |     | 2265 | Devil's Cup         | American Pale Ale (APA)        |        177 |     12
   2 | 0.071 |     | 2264 | Rise of the Phoenix | American IPA                   |        177 |     12
   3 |  0.09 |     | 2263 | Sinister            | American Double / Imperial IPA |        177 |     12
   4 | 0.075 |     | 2262 | Sex and Candy       | American IPA                   |        177 |     12

やったぜ。

今回はRecSys2016に参加したときにいい感じのパブで飲んだ、Notch Brewing(マサチューセッツ州)のビール "Left of the Dial" (ABV 4.3%) を当該データセットから探す。1年前の思い出をもう一度!(そんなに好みのビールじゃなかったけど)

woo~🍺

A post shared by @takuti on

完全一致

まずは愚直に where 句で完全一致検索をしてみよう:

sample=# select * from beers where name = 'Left of the Dial';
 key | abv | ibu | id | name | style | brewery_id | ounces
-----+-----+-----+----+------+-------+------------+--------
(0 rows)

無い…。

LIKE と ILIKE

そんなはずはない!というわけで、Fuzzy Search を試みる。

LIKE でビール名の前後に何らかの文字列があることを許容すれば:

sample=# select * from beers where name LIKE '%Left of the Dial%';
 key  |  abv  | ibu |  id  |         name         |    style     | brewery_id | ounces
------+-------+-----+------+----------------------+--------------+------------+--------
 1504 | 0.043 |     | 1917 | Left of the Dial IPA | American IPA |        271 |     12
(1 row)

あったー!ABVも記録と一致している。まさにこれだ。

ILIKELIKE の大文字・小文字を無視する版で、全部小文字で検索してもお目当てのビールがヒットするようになる:

sample=# select * from beers where name LIKE '%left of the dial%';
 key | abv | ibu | id | name | style | brewery_id | ounces
-----+-----+-----+----+------+-------+------------+--------
(0 rows)

sample=# select * from beers where name ILIKE '%left of the dial%';
 key  |  abv  | ibu |  id  |         name         |    style     | brewery_id | ounces
------+-------+-----+------+----------------------+--------------+------------+--------
 1504 | 0.043 |     | 1917 | Left of the Dial IPA | American IPA |        271 |     12
(1 row)

正規表現

もう少し柔軟に、正規表現を使った検索も可能。

先の LIKE 相当の正規表現マッチは ~ で探して次の通り:

sample=# select * from beers where name ~ '.*Left of the Dial.*';
 key  |  abv  | ibu |  id  |         name         |    style     | brewery_id | ounces
------+-------+-----+------+----------------------+--------------+------------+--------
 1504 | 0.043 |     | 1917 | Left of the Dial IPA | American IPA |        271 |     12
(1 row)

~* で探せば、大文字・小文字を無視してくれて ILIKE 相当の結果も得られる:

sample=# select * from beers where name ~ '.*left of the dial.*';
 key | abv | ibu | id | name | style | brewery_id | ounces
-----+-----+-----+----+------+-------+------------+--------
(0 rows)

sample=# select * from beers where name ~* '.*left of the dial.*';
 key  |  abv  | ibu |  id  |         name         |    style     | brewery_id | ounces
------+-------+-----+------+----------------------+--------------+------------+--------
 1504 | 0.043 |     | 1917 | Left of the Dial IPA | American IPA |        271 |     12
(1 row)

編集距離

とはいえ、検索クエリは LIKE と正規表現だけでカバーできるほど単純なものではない。特にtypo、これが厄介。

そこで編集距離 (Levenshtein Distance) を使って、もう少しtypoにロバストなクエリにする。

PostgreSQLでは fuzzystrmatch モジュールに関数 levenshtein などが含まれている:

sample=# create extension fuzzystrmatch;
CREATE EXTENSION
sample=# select levenshtein('kitten', 'sitting');
 levenshtein
-------------
           3
(1 row)

"Left of the Dial" からの編集距離が10以下のビールは結構ある:

sample=# select * from beers where levenshtein(lower(name), lower('Left of the Dial')) <= 10;
 key  |  abv  | ibu |  id  |         name         |          style           | brewery_id | ounces
------+-------+-----+------+----------------------+--------------------------+------------+--------
  274 | 0.054 |     | 1411 | Sawtooth Ale         | American Blonde Ale      |        407 |     12
  383 | 0.072 |  60 | 1801 | Last Stop IPA        | American IPA             |        308 |     12
  428 | 0.073 |     | 1785 | Le Flaneur Ale       | American Wild Ale        |         10 |     16
  690 | 0.072 |     | 1623 | Lift Off IPA         | American IPA             |        358 |     16
  695 |  0.06 |     | 2371 | Neato Bandito        | Euro Pale Lager          |        127 |     12
 1101 | 0.068 |  90 | 1903 | Let It Ride IPA      | American IPA             |        277 |     12
 1385 | 0.075 |  85 | 2159 | City of the Sun      | American IPA             |        209 |     16
 1493 | 0.045 |  50 | 2692 | Get Together         | American IPA             |          0 |     16
 1504 | 0.043 |     | 1917 | Left of the Dial IPA | American IPA             |        271 |     12
 1650 |  0.06 |  20 | 1791 | Hot Date Ale         | Chile Beer               |        314 |     16
 1658 | 0.065 |     | 2559 | Blood of the Unicorn | American Amber / Red Ale |         52 |     16
 1702 |  0.08 |     | 1375 | Nectar of the Hops   | Mead                     |        421 |     16
 2171 | 0.041 |     | 1780 | Rise to the Top      | Cream Ale                |        142 |     12
 2337 |       |     |  652 | West Sixth IPA       | American IPA             |        100 |     12
(14 rows)

また、levenshtein_less_equal(string 1, string 2, max distance)max distance より小さい編集距離の文字列に対してはその正確な編集距離を、それ以外については max distance より大きな適当な値(ここでは max distance + 1)を返す関数:

select
    name,
    levenshtein(lower(name), lower('Left of the Dial')), /* 正確な編集距離 */
    levenshtein_less_equal(lower(name), lower('Left of the Dial'), 11) /* 編集距離11以下だけ真面目に計算する */
from
    beers
limit
    5;
        name         | levenshtein | levenshtein_less_equal
---------------------+-------------+------------------------
 Pub Beer            |          14 |                     12
 Devil's Cup         |          14 |                     12
 Rise of the Phoenix |          11 |                     11
 Sinister            |          14 |                     12
 Sex and Candy       |          13 |                     12
(5 rows)

これいいですね。『いまさら編集距離 (Levenshtein Distance) を実装するぜ』でも書いたとおり Levenshtein Distance は動的計画法によって計算されるので、明らかに max distance より距離が大きくなるケースをさっさと切り捨てるのは小粒でぴりりと辛い工夫。

編集距離6以下を探せば、"Left of the Dial IPA" のみがヒットするようになる:

sample=# select * from beers where levenshtein_less_equal(lower(name), lower('Left of the Dial'), 6) <= 6;
 key  |  abv  | ibu |  id  |         name         |    style     | brewery_id | ounces
------+-------+-----+------+----------------------+--------------+------------+--------
 1504 | 0.043 |     | 1917 | Left of the Dial IPA | American IPA |        271 |     12
(1 row)

そして問題のtypoだが、この通り DialDaniel にtypoしても問題ない:

sample=# select * from beers where levenshtein_less_equal(lower(name), lower('Left of the Dniel'), 6) <= 6;
 key  |  abv  | ibu |  id  |         name         |    style     | brewery_id | ounces
------+-------+-----+------+----------------------+--------------+------------+--------
 1504 | 0.043 |     | 1917 | Left of the Dial IPA | American IPA |        271 |     12
(1 row)

『どの程度typoを許容するか』と『ヒットする件数』はトレードオフの関係にあるので、閾値を定めるのは結構大変。

文字のtri-gram

編集距離以上にtypoにロバストなのが、文字のtri-gramによる検索。

文字のtri-gramは単語のマルコフ連鎖の文字版、のようなイメージ。PostgreSQLでは pg_trgm モジュールをいれることでtri-gramのマッチ(文字列の部分的な一致)による柔軟な検索ができる。

たとえば Avatar という文字列からは avata のようなtri-gramが得られて、我々はそのtri-gramの意味で一致する文字列を探すことができる:

sample=# create extension pg_trgm;
CREATE EXTENSION
sample=# select show_trgm('Avatar');
              show_trgm
-------------------------------------
 {"  a"," av","ar ",ata,ava,tar,vat}
(1 row)

実際には、where 句の =~% に置き換えるだけでtri-gramベースの検索が走る。

末尾の IPA が抜け落ちたくらいは問題ない:

sample=# select * from beers where name % 'Left of the Dial';
 key  |  abv  | ibu |  id  |         name         |    style     | brewery_id | ounces
------+-------+-----+------+----------------------+--------------+------------+--------
 1504 | 0.043 |     | 1917 | Left of the Dial IPA | American IPA |        271 |     12
(1 row)

DialDia になっちゃっててもOK:

sample=# select * from beers where name % 'Left of the Dia';
 key  |  abv  | ibu |  id  |         name         |    style     | brewery_id | ounces
------+-------+-----+------+----------------------+--------------+------------+--------
 1504 | 0.043 |     | 1917 | Left of the Dial IPA | American IPA |        271 |     12
(1 row)

Dial が完全に抜け落ちていると、tri-gramに ofthe を含む他のビールまでヒットするようになる:

sample=# select * from beers where name % 'Left of the';
 key  |  abv  | ibu |  id  |         name         |          style          | brewery_id | ounces
------+-------+-----+------+----------------------+-------------------------+------------+--------
 1047 |  0.07 |  68 | 2294 | The Power of Zeus    | American Pale Ale (APA) |        168 |     12
 1385 | 0.075 |  85 | 2159 | City of the Sun      | American IPA            |        209 |     16
 1504 | 0.043 |     | 1917 | Left of the Dial IPA | American IPA            |        271 |     12
(3 rows)

大文字・小文字や Dial のtypoくらいじゃへこたれない:

sample=# select * from beers where name % 'left of the daniel';
 key  |  abv  | ibu |  id  |         name         |    style     | brewery_id | ounces
------+-------+-----+------+----------------------+--------------+------------+--------
 1504 | 0.043 |     | 1917 | Left of the Dial IPA | American IPA |        271 |     12
(1 row)

TSVector

自然言語として、もっと直感に即した“それっぽさ”を見たければ TSVector という表現が使える。

"Left of the Dial" のTSVector表現はこんな感じ:

sample=# select to_tsvector('Left of the Dial');
    to_tsvector
-------------------
 'dial':4 'left':1
(1 row)

これによって語順に依存しない、字句(トークン)の存在有無に基づく検索が可能。ofthe のような stop word の除外、大文字・小文字の統一といった基本的な前処理は勝手にやってくれる。

ビール名のTSVector to_tsvector(name) について、leftipa を含むものを列挙すれば期待通り "Left of the Dial" が得られる:

sample=# select * from beers where to_tsvector(name) @@ to_tsquery('english', 'left & ipa');
 key  |  abv  | ibu |  id  |         name         |    style     | brewery_id | ounces
------+-------+-----+------+----------------------+--------------+------------+--------
 1504 | 0.043 |     | 1917 | Left of the Dial IPA | American IPA |        271 |     12
(1 row)

なお、to_tsvector() @@ to_tsquery() は次の構文と等価:

sample=# select * from beers where name @@ 'left & ipa';
 key  |  abv  | ibu |  id  |         name         |    style     | brewery_id | ounces
------+-------+-----+------+----------------------+--------------+------------+--------
 1504 | 0.043 |     | 1917 | Left of the Dial IPA | American IPA |        271 |     12
(1 row)

残念ながらtypoはカバーできない:

sample=# select * from beers where name @@ 'left & daniel';
 key | abv | ibu | id | name | style | brewery_id | ounces
-----+-----+-----+----+------+-------+------------+--------
(0 rows)

サウンド距離

「なんとなく覚えているけど、正確には書けない!」というときのために、システムはtypoにロバストであってほしい。ここまで見てきたのは、そのためのスペルに基づく様々なFuzzy Search手法。

一方、スペルではなく“発音の近さ”(サウンド距離)で検索する方法もある。

この機能は levenshtein のときにいれた fuzzystrmatch モジュールに含まれている。

IPA(あいぴーえー)を ipear(あいぺあー)と読んでみよう。 ipear の発音は次のように記号化される:

sample=# select dmetaphone('ipear'), dmetaphone_alt('ipear'), metaphone('ipear', 8), soundex('ipear');
 dmetaphone | dmetaphone_alt | metaphone | soundex
------------+----------------+-----------+---------
 APR        | APR            | IPR       | I160
(1 row)

明らかにtypoの域を越えているので、素のtri-gramでは何もヒットしない:

sample=# select * from beers where name % 'ipear';
 key | abv | ibu | id | name | style | brewery_id | ounces
-----+-----+-----+----+------+-------+------------+--------
(0 rows)

しかし(記号化された)発音のtri-gramを比較すれば:

sample=# select * from beers where metaphone(name, 8) % metaphone('ipear', 8);
 key  |  abv  | ibu |  id  |   name   |    style     | brewery_id | ounces
------+-------+-----+------+----------+--------------+------------+--------
   97 | 0.065 |     | 2578 | IPA      | American IPA |         35 |     12
  591 | 0.057 |  58 | 2380 | IPA #11  | American IPA |        121 |     16
  892 | 0.074 |  74 | 1777 | 2020 IPA | American IPA |        240 |     16
 1114 | 0.068 |  55 |  558 | I-10 IPA | American IPA |        527 |     12
 1192 | 0.068 |     | 2493 | I.P. Eh! | American IPA |         59 |     12
 1906 |  0.07 | 113 |   24 | 113 IPA  | American IPA |        371 |     12
(6 rows)

おぉーIPAめっちゃ出てくるー。

まとめ

以上、柔軟な検索を実現するためのFuzzy Search手法たちでした。

実際のところ、RDB上でのFuzzy Searchって世の中ではどれだけ実用されているんだろうか。アルゴリズムの計算量、インデックスがどれだけ効果的に使えるか、期待する出力、etc..に応じて適切な検索手法を選択する必要があるので、なかなか難しい話題だと思う。

そして複数の手法を組み合わせたハイブリッドFuzzy Searchも可能なので、さらに悩む。"Seven Databases in Seven Weeks" では次のようなクエリが紹介されている:

select * from actors
where metaphone(name,8) % metaphone('Robin Williams',8) 
order by levenshtein(lower('Robin Williams'), lower(name));

(Levenshtein Distance で order by とか絶対やりたくないけど…。)

まぁ細かいことは気にせず、みんなも思い出のビールを検索してみよう!(?)