【ITニュース解説】Fuzzy String Matching in PostgreSQL with pg_trgm (Trigram Search Tutorial)

私たちが日々、ウェブサイトやアプリケーションを使う中で、名前や住所、検索キーワードなどを入力することは多い。しかし、人間は完璧な存在ではないため、時には誤字脱字をしてしまったり、人によって異なる表記を使ったり、あるいは略語を使ったりすることがある。このような状況で、データベースに完全に一致するデータだけを探そうとすると、本来見つけたい情報を見逃してしまうことがよくある。この問題を解決し、多少の違いがあっても「似ている」情報を見つけ出す技術が「あいまい検索」と呼ばれるものだ。

PostgreSQLという人気の高いデータベースには、このあいまい検索を簡単に実現するための強力な機能として「pg_trgm（ピージー・トリグラム）」という拡張機能が用意されている。これは、文字列がどれくらい似ているかを判断し、たとえわずかな違いがあっても関連するデータを見つけ出せるようにしてくれるものだ。

pg_trgmが文字列の類似度を判断するために用いるのが、「トリグラム」という概念である。トリグラムとは、非常にシンプルに言えば、文字列の中から連続する3文字を切り出したグループのことだ。例えば、「Talemul」という単語を例に考えてみよう。この単語は、次のようなトリグラムの集まりに分解される。

まず、単語の先頭と末尾には、特別なスペースが追加される。これは、単語の始まりや終わりの文字も、トリグラムとして正しく扱えるようにするための工夫だ。 「Talemul」という単語は、これらのスペースを含めて、次のようなトリグラムに分解される。 「 T」、「Tal」、「ale」、「lem」、「emu」、「mul」、「ul 」 これらのトリグラムは、それぞれ3文字ずつ切り出されているのがわかるだろう。

では、このトリグラムを使って、どのように文字列の似ている度合い、つまり類似度を測るのだろうか。例えば、「Talemul」と「Talimul」という二つの単語を比較してみよう。 「Talemul」のトリグラムは、「 T」、「Tal」、「ale」、「lem」、「emu」、「mul」、「ul 」だった。 一方、「Talimul」のトリグラムは、「 T」、「Tal」、「ali」、「lim」、「imu」、「mul」、「ul 」となる。 これらのリストを見比べると、「 T」、「Tal」、「mul」、「ul 」のように、両方の単語に共通するトリグラムがいくつかあることがわかる。pg_trgmは、二つの文字列がどれだけ多くの共通のトリグラムを持っているかを数え、その数が多いほど「似ている」と判断するのだ。この仕組みのおかげで、少しの誤字脱字やスペルミスがあったとしても、高い精度で似た文字列を見つけ出すことが可能になる。

実際にpg_trgmを使い始めるのは非常に簡単だ。まず、PostgreSQLのデータベース内でこの機能を有効にする必要がある。データベースに接続した後、以下のコマンドを実行する。

CREATE EXTENSION IF NOT EXISTS pg_trgm;

このコマンドは、もしpg_trgm拡張機能がまだデータベースにインストールされていなければ、それをインストールして利用可能にする、という意味だ。一度実行すれば、そのデータベースでpg_trgmの様々な機能を使えるようになる。正しく有効化されたかを確認したい場合は、\dxというコマンドを実行すると、現在インストールされている拡張機能の一覧が表示され、その中にpg_trgmの名前を見つけることができるだろう。

次に、具体的な例でpg_trgmを使った検索方法を見てみよう。仮に、人々の名前を保存するpeopleというテーブルがあり、そこにいくつか名前が登録されているとする。

まず、テーブルを作成し、いくつかのデータを挿入する。 CREATE TABLE people (id SERIAL PRIMARY KEY, name TEXT); INSERT INTO people (name) VALUES ('Talemul'), ('Talimul'), ('Talimul Islam'), ('Tamim'), ('Talim');

このテーブルに対して、「Talemul」という名前に似た名前を探してみよう。以下のSQLクエリを実行する。

SELECT name, similarity(name, 'Talemul') AS score FROM people WHERE name % 'Talemul' ORDER BY score DESC;

このクエリには重要なポイントがいくつかある。 similarity(name, 'Talemul')という部分は、nameカラムの値が「Talemul」という文字列とどれくらい似ているかを計算し、その類似度を「score」という名前で表示する関数だ。類似度は0から1までの数値で表され、1は完全に一致していることを意味する。 WHERE name % 'Talemul'という部分が、pg_trgmによるあいまい検索の核心となる。%記号は、pg_trgm拡張機能が提供する特別な演算子で、「左側の文字列が右側の文字列に似ているか」という条件を判断する。この条件を満たすレコードだけが、検索結果として選ばれることになる。 ORDER BY score DESCは、最も似ているものから順に結果を並べ替えるための指示だ。

このクエリを実行すると、次のような結果が得られるだろう。

name	score
Talemul	1.00000000
Talimul	0.45454547
Talimul Islam	0.29411766
Talim	0.27272728

結果を見ると、「Talemul」という完全に一致する名前はもちろん、最高のスコアである1.0を得ている。「Talimul」はスペルミスがあるにも関わらず、高いスコアで検出されているのがわかる。「Talimul Islam」や「Talim」は、共通のトリグラムが少なくなるため、スコアは低くなる。もし、特定の類似度以上のものだけを表示したい場合は、WHERE similarity(name, 'Talemul') > 0.4のように条件を追加することもできる。

このpg_trgmを使ったあいまい検索は非常に便利だが、データ量が膨大になると、検索に時間がかかることがある。特に、何十万、何百万という大量のレコードの中から似た文字列を探す場合には、その遅さがシステム全体のボトルネックになる可能性もある。このようなパフォーマンスの問題を解決するために、「インデックス」という仕組みを利用する。インデックスは、データベースがデータを高速に検索できるようにするための、いわば目次のようなものだ。

pg_trgmのあいまい検索を高速化するためには、「GINインデックス」という種類のインデックスを作成するのが非常に効果的だ。以下のコマンドでインデックスを作成できる。

CREATE INDEX idx_people_name_trgm ON people USING gin (name gin_trgm_ops);

このコマンドを実行すると、peopleテーブルのnameカラムに対して、pg_trgmの検索操作に特化したGINインデックスが作成される。一度このインデックスを作成すれば、先ほど実行した%演算子やsimilarity()関数を使った検索は、データ量が増えても非常に高速に実行されるようになる。

pg_trgmの技術は、私たちの身の回りにある様々なシステムで活用されている。 例えば、ウェブサイトの検索機能でユーザーが名前を検索するとき、誤字があっても関連する候補を表示してくれる「もしかして？」のような機能や、ユーザーが文字を入力している途中で関連性の高い単語を提案する「オートコンプリート」機能にも応用できる。 また、データベースに保存されている顧客データの中に、スペル違いの重複した名前がないかを検出し、データを整理する「重複排除」の目的にも利用できるだろう。さらに、大規模な検索エンジンでは、ユーザーの検索意図をより正確に捉えるために、このあいまい検索の考え方が広く取り入れられている。

このように、トリグラムという単純なアイデア、つまり単語を3文字の塊に分解し、それらの共通部分を比較することで類似度を計算するという方法は、非常に強力な機能をもたらす。PostgreSQLのpg_trgm拡張機能は、この強力な技術をSQLデータベース内で直接利用できるようにしてくれる。これにより、わざわざ別の専門的な検索エンジンを用意しなくても、誤字脱字に強く、ユーザーにとって使いやすい検索機能を、データベースの内部だけで簡単に構築できるのだ。これは、システムを構築する上で非常に大きなメリットとなる。