【PostgreSQL】pg_trgmによる文字列の類似度検索を試す

はじめに

データベースに、類似したデータが既に登録されているかどうかを確認したいケースがあります。

LIKE検索を使えば、指定したパターンについて部分一致検索が可能です。また、全角と半角、大文字と小文字の違いはプログラムで正規化することで、ある程度は同一のデータとして扱うことができます。しかし、正規化が難しい表記ゆれや、スペルミスなどで異なる文字列となった場合には、完全一致・正規化だけでは類似しているかどうかを判別できません。

今回は、PostgreSQLのpg_trgmモジュールを使用して、データベースに類似データがあるかどうかを検索してみました。

pg_trgmモジュールとは

pg_trgmは、文字列を連続した3文字ずつに分割（トライグラム）し、共通のトライグラムの個数によって文字列同士の類似度を判定する、PostgreSQLの拡張機能です。

例えば、「醤油を大さじ2杯加えます。」という文章は、 " 醤"、" 醤油"、"醤油を"、"油を大"、"を大さ"、…のように分割されます。

類似度を判定するための関数には以下のものがあり、それぞれ0から1までの小数で類似度が表現されます。1に近づくほど一致しているということになります。

similarity(クエリ文字列, 対象文字列)

クエリ文字列と対象文字列の、全体的なトライグラム集合の類似度を調べます。

word_similarity(クエリ文字列, 対象文字列)

対象文字列に存在する任意の連続した部分文字列の中で、クエリ文字列と最も類似する部分の類似度を調べます。クエリ文字列が対象文字列の一部である場合に高くなる傾向があります。

例えば、クエリ文字列がappleで対象文字列がapplesの場合、類似度が高くなります。

strict_word_similarity(クエリ文字列, 対象文字列)

word_similarityと同様ですが、単語の境界を考慮します。

クエリ文字列がapple、対象文字列がapplesの場合、単語の境界を考慮するとapplesで一つの単語となります。クエリ文字列を対象文字列の一部とみなすためにはsが不要と判定されるため、word_similarityより類似度は低くなります。

また、基本的に単語の境界を半角スペースで判断するため、日本語の文章そのままの場合、期待通りに動かない場合があります。

参考：F.35. pg_trgm — トライグラム一致を使ったテキストの類似度をサポートする

前提

本記事は以下の条件で検証しています。

• PostgreSQL 18.4

試してみる

検証用に以下のテーブルを作成します。

CREATE TABLE recipes (
    id SERIAL NOT NULL,
    instruction VARCHAR(255) NOT NULL,
    created_at TIMESTAMP,
    updated_at TIMESTAMP,
    PRIMARY KEY (id)
);

データを投入します。

INSERT INTO recipes (instruction) VALUES
('醤油を大さじ2杯加えます。'),
('醤油を大さじ２杯加えます。'),
('しょうゆを大さじ2杯加えます。'),
('醤油を大さじ2杯加え、炒めます。'),
('醤油を大匙2杯加えます。'),
('砂糖を大さじ2杯加えます。'),
('大さじ2杯加え'),
('砂糖を大さじ1、醤油を大さじ2杯加えます。'),
('砂糖を大さじ1、醤油を大さじ2杯加えます。ざっくりと混ぜます。'),
('醤油を大さじ2杯、みりんを大さじ1杯、砂糖を小さじ1杯加えます。'),
('ごま油を大さじ2杯加え、ボウルであえます。'),
('醤油を入れたら、ひと煮立ちするまで待ちます。'),
('大さじ2杯の醤油を加えます。'),
('大さじ加えます2杯醤油を。'),
('レンジで3分間あたためます。'),
('豚薄切り肉100g、ピーマン2個、なす2本'),
('焼き色がついたら裏返します。')
;

まだpg_trgmが有効になっていない場合は、最初の1回のみ以下のクエリを実行して拡張機能を有効にします。

-- 初回のみ
CREATE EXTENSION IF NOT EXISTS pg_trgm;

以下のクエリを実行して、similarity、word_similarity、strict_word_similarityをそれぞれ取得します。

SELECT
    id,
    instruction,
    similarity('醤油を大さじ2杯加えます。', instruction) as sim,
    word_similarity('醤油を大さじ2杯加えます。', instruction) AS word_sim,
    strict_word_similarity('醤油を大さじ2杯加えます。', instruction) as strict_word_sim
FROM recipes
ORDER BY sim DESC;

結果は以下のようになりました。

概ね、似たデータはどの関数でも0.4～1の数値を示し、似ていないデータは0～0.1を示していることがわかります。

「砂糖を大さじ1、醤油を大さじ2杯加えます。」のような、部分的に一致しているが余計な文字列が追加されている場合、全体的なトライグラムの類似度を測るsimilarityでは0.68だったものの、2つの文字列の部分文字列の類似度を表すword_similarityやstrict_word_similarityでは1となりました。

逆に、「大さじ2杯加え」のような、対象文字列がクエリ文字列の一部である場合は、word_similarityでは低い類似度となります。

select
word_similarity('醤油を大さじ2杯加えます。', '砂糖を大さじ1、醤油を大さじ2杯加えます。ざっくりと混ぜます。'), -- 1.0
word_similarity('砂糖を大さじ1、醤油を大さじ2杯加えます。ざっくりと混ぜます。', '醤油を大さじ2杯加えます。'); -- 0.4642857

また、1文字だけ全角・半角が異なる「醤油を大さじ２杯加えます。」が全関数で0.625、漢字・ひらがな違いの「醤油を大匙2杯加えます。」や「しょうゆを大さじ2杯加えます。」もsimilarityでは0.5程度となり、表記ゆれがトライグラムベースの類似度の低下につながることが見てとれます。一方で、意味的に異なる「砂糖を大さじ2杯加えます。」も、表記ゆれと同程度の類似度となっています。

word_similarityとstrict_word_similarityの数値の違いがなぜこうなるかについては、文章を見ただけではわかりません。上述のとおり日本語の文章を形態素解析なしでそのまま扱う場合、判定が正しくない場合があります。基本的にはsimilarityかword_similarityを用途に応じて使うのが良さそうです。

pg_trgmの演算子

類似度についていくつかの演算子が用意されています。

%演算子を使うと、pg_trgm.similarity_thresholdで設定された値（デフォルトは0.3）以上の類似度を検索することができます。

SELECT
    id,
    instruction,
    similarity('醤油を大さじ2杯加えます。', instruction) as sim,
    word_similarity('醤油を大さじ2杯加えます。', instruction) AS word_sim
FROM recipes
where '醤油を大さじ2杯加えます。' % instruction
ORDER BY sim DESC;

以下の結果の通り、0.3以上のデータが取得できます。

<%演算子は%演算子と似ていますが、similarityの代わりにword_similarityを基準とします。word_similarity_thresholdのデフォルトは0.6です。

SELECT
    id,
    instruction,
    similarity('醤油を大さじ2杯加えます。', instruction) as sim,
    word_similarity('醤油を大さじ2杯加えます。', instruction) AS word_sim
FROM recipes
where '醤油を大さじ2杯加えます。' <% instruction
ORDER BY word_sim DESC;

他にも演算子がありますので、気になった方は公式ドキュメントをご参照ください。

参考：F.35. pg_trgm — トライグラム一致を使ったテキストの類似度をサポートする

補足

インデックスについて

pg_trgmモジュールはGiSTインデックスとGINインデックスをサポートしています。

本記事では検証していませんが、大量データを扱う場合はいずれかのインデックスの追加を検討してください。

以下の公式ドキュメントではGINインデックスを推奨していますが、用途に応じて適切な方を選択してください。

参考：12.9. テキスト検索に好ましいインデックス種類

その他の文字列比較手法

今回はトライグラムによる表記レベルの類似度検索を扱いましたが、目的に応じて他の手法もあります。

pg_bigm

pg_trgmは3文字ずつの区切りで、英語などのアルファベット圏での使用を想定しています。日本語の文章では、strict_word_similarityの単語境界の判定が期待と異なる場合があります。一方、pg_bigmは2文字ずつの区切りで、日本語処理に対応した設計がされています。

レーベンシュタイン距離

pg_trgmと同じように、文字の並びが似ているかを測る手法ですが、pg_trgmが0～1で類似度で表すのに対し、レーベンシュタイン距離はある文字列を別の文字列に変換するために必要な操作回数を距離として表します。

数文字のスペルミスのような操作には強い一方、単語の位置が大きく入れ替わるようなケースでは距離が大きくなる傾向があります。

ベクトル化（埋め込み）

表記ではなく意味的な近さを測ります。「しょうゆ」と「醤油」のような表記ゆれも類似語と判定できますが、その分実装が複雑になります。「意味的に似た文章を探したい」という要件であればベクトル検索の検討が必要です。

おわりに

類似したデータの検索にトライグラムを利用したPostgreSQLの拡張機能、pg_trgmを試してみました。

今回用意したデータの中では概ね期待した結果が得られましたが、表記ゆれで類似度が低下したり、意味が違っていても違いが数文字であれば類似寄りとして判定されるなどがありました。

similarityやword_similarityのしきい値をどのくらいに設定すれば良いかは、実際のデータや用途によって異なるため、ご自身のデータセットで実際に検証してみることをおすすめします。

この記事がどなたかの参考になれば幸いです。