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年前の思い出をもう一度！（そんなに好みのビールじゃなかったけど）
完全一致
まずは愚直に 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も記録と一致している。まさにこれだ。
ILIKE は LIKE の大文字・小文字を無視する版で、全部小文字で検索してもお目当てのビールがヒットするようになる：
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だが、この通り Dial を Daniel に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 という文字列からは av や ata のような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)
Dial が Dia になっちゃってても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に of や the を含む他のビールまでヒットするようになる：
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)
これによって語順に依存しない、字句（トークン）の存在有無に基づく検索が可能。of や the のような stop word の除外、大文字・小文字の統一といった基本的な前処理は勝手にやってくれる。
ビール名のTSVector to_tsvector(name) について、left と ipa を含むものを列挙すれば期待通り "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 とか絶対やりたくないけど…。）
まぁ細かいことは気にせず、みんなも思い出のビールを検索してみよう！（？）
シェアする
カテゴリ
あわせて読みたい
- 2017-08-20
- HiveでテキストのFuzzy Search
- 2017-07-28
- いまさら編集距離 (Levenshtein Distance) を実装するぜ
- 2017-03-18
- 情報検索・インタラクション系の国際会議 CHIIR2017 に参加した #chiir2017
最終更新日: 2022-01-18
書いた人: たくち
Takuya Kitazawa（たくち）です。長野県出身、カナダ・バンクーバー在住のソフトウェアエンジニア。これまでB2B/B2Cの各領域で、Web技術・データサイエンス・機械学習のプロダクト化および顧客への導入支援・コンサルティング、そして関連分野の啓蒙活動に携わってきました。現在は主に北米（カナダ）、アジア（日本）、アフリカ（マラウイ）の個人および企業を対象にフリーランスとして活動中。詳しい経歴はレジュメ を参照ください。いろいろなまちを走って、時に自然と戯れながら、その時間その場所の「日常」を生きています。ご意見・ご感想およびお仕事のご相談は [email protected] まで。
近況 一杯のコーヒーを贈る免責事項
- Amazonのアソシエイトとして、当サイトは amazon.co.jp 上の適格販売により収入を得ています。
- 当サイトおよび関連するメディア上での発言はすべて私個人の見解であり、所属する（あるいは過去に所属した）組織のいかなる見解を代表するものでもありません。
- 当サイトのコンテンツ・情報につきまして、可能な限り正確な情報を掲載するよう努めておりますが、個人ブログという性質上、誤情報や客観性を欠いた意見が入り込んでいることもございます。いかなる場合でも、当サイトおよびリンク先に掲載された内容によって生じた損害等の一切の責任を負いかねますのでご了承ください。
- その他、記事の内容や掲載画像などに問題がございましたら、直接メールでご連絡ください。確認の後、対応させていただきます。