他のバージョンの文書 15 | 14 | 13 | 12 | 11 | 10 | 9.6 | 9.5 | 9.4 | 9.3 | 9.2 | 9.1 | 9.0 | 8.4 | 8.3 | 8.2 | 8.1 | 8.0 | 7.4 | 7.3 | 7.2

F.31. pg_trgm

pg_trgmモジュールは、類似文字列の高速検索をサポートするインデックス演算子クラスだけではなく、トライグラム一致に基づく英数字の類似度の決定に関する関数と演算子も提供します。

F.31.1. トライグラム(またはトリグラフ)の概念

トライグラムは文字列から3つの連続する文字を取り出したグループです。 共有するトライグラムの個数を数えることで、2つの文字列の類似度を測定することができます。 この単純な考えが、多くの自然言語における単語の類似度を測定する際に非常に効率的であることが判明しています。

注記

pg_trgmは、文字列からトライグラムを抽出する時に単語以外の文字(英数字以外)を無視します。 文字列内に含まれるトライグラム集合を決める際、文字列の前に2つの空白、後に1つの空白が付いているものとみなされます。 例えば、catという文字列のトライグラム集合は、 c cacatat です。 foo|barという文字列のトライグラム集合は、 f fofoooo b babarar です。

F.31.2. 関数と演算子

pg_trgmモジュールで提供される関数を表 F.24に、演算子を表 F.25に示します。

表F.24 pg_trgm関数

関数戻り値説明
similarity(text, text)real 2つの引数がどの程度似ているかを示す数値を返します。 結果はゼロ(2つの文字列がまったく類似していないことを示す)から1(2つの文字列が同一であることを示す)までの範囲です。
show_trgm(text)text[] 与えられた文字列内のすべてのトライグラムからなる配列を返します。 (実際これはデバッグ時を除いて役に立つことはほぼありません。)
word_similarity(text, text) real 最初の引数文字列中のトライグラムの集合と、二番目の引数文字列中の順序付きトライグラム集合の中で最も類似度の高い連続した範囲の類似度を表す数字を返します。 詳細は以下の説明をご覧ください。
strict_word_similarity(text, text) real word_similarity(text, text)と同様ですが、境界の範囲を単語の境界に一致させます。 単語間にまたがるトライグラムは無いため、この関数は実際のところ最初の文字列と二番目の文字列の単語の任意の連続した範囲との間での最大類似度を返します。
show_limit()real %演算子で使用される現在の類似度閾値を返します。 これは、例えば2つの単語それぞれでミススペルがあったとしても類似しているものとみなす、その2つの単語間の最低の類似度を設定します。(廃止予定
set_limit(real)real %演算子で使用される現在の類似度閾値を設定します。 閾値は0から1までの値でなければなりません(デフォルトは0.3です)。 渡された値と同じ値が返ります。(廃止予定

以下の例を考えます。

# SELECT word_similarity('word', 'two words');
 word_similarity
-----------------
             0.8
(1 row)

最初の文字列では、トライグラムの集合は{" w"," wo","wor","ord","rd "}です。 二番目の文字列では、順序付きトライグラムの集合は{" t"," tw",two,"wo "," w"," wo","wor","ord","rds", "ds "}です。 二番目の文字列中の順序付きトライグラムの集合の中で最も類似度の高い範囲は、{" w"," wo","wor","ord"}で、類似度は0.8となります。

この関数が返す値は、最初の文字列と、二番目の文字列の部分文字列の間の最大の類似度を表す値であると、概ね解釈できます。 しかし、この関数は範囲の境界に対してパディングを行いません。 ですから、一致しない語の境界を除くと、二番目の文字列中に存在する追加文字数は考慮されません。

一方で、strict_word_similarity(text, text)は二番目の文字列の単語の範囲を選択します。 上記の例でstrict_word_similarity(text, text)は単語'words'の範囲を選択して、そのトライグラム集合は{" w"," wo","wor","ord","rds","ds "}になるでしょう。

# SELECT strict_word_similarity('word', 'two words'), similarity('word', 'words');
 strict_word_similarity | similarity
------------------------+------------
               0.571429 |   0.571429
(1 row)

このようにstrict_word_similarity(text, text)関数は単語の並び全体の類似度を求めるのに有益で、対して、word_similarity(text, text)は単語の並びの一部の類似度を求めるのにより適しています。

表F.25 pg_trgm演算子

演算子戻り値説明
text % textboolean 2つの引数がpg_trgm.similarity_thresholdで設定された類似度閾値以上の類似度を持つ場合trueを返します。
text <% textboolean 最初の引数中のトライグラムの集合と、二番目の引数中の順序付きトライグラム集合の中の範囲の類似度が、pg_trgm.word_similarity_threshold引数で設定した現在の語類似度の閾値よりも高い場合にtrueを返します。
text %> textboolean <%演算子の交代演算子です。
text <<% textboolean 二番目の引数が単語の境界と一致する順序付きトライグラム集合の連続した範囲を持っていて、かつ、最初の引数のトライグラム集合に対する類似度がpg_trgm.strict_word_similarity_thresholdで設定される現在の厳密な単語類似度の閾値より大きい場合、trueを返します。
text %>> textboolean <<%演算子の交代演算子です。
text <-> textreal 引数間の距離、この場合は1 - similarity()の値を返します。
text <<-> text real 引数間の距離、この場合は1 - word_similarity()の値を返します。
text <->> text real <<->演算子の交代演算子です。
text <<<-> text real 引数間の距離、この場合は1 - strict_word_similarity()の値を返します。
text <->>> text real <<<->演算子の交代演算子です。

F.31.3. GUCパラメータ

pg_trgm.similarity_threshold (real)

%演算子が使用する現在の類似度閾値を設定します。 閾値は0から1の間でなければなりません。(デフォルトは0.3です)

pg_trgm.word_similarity_threshold (real)

<%%>%演算子が使用する現在の語類似度閾値を設定します。 閾値は0から1の間でなければなりません。(デフォルトは0.6です)

pg_trgm.strict_word_similarity_threshold (real)

<%%>%演算子が使用する現在の厳密な語類似度閾値を設定します。 閾値は0から1の間でなければなりません。(デフォルトは0.5です)

F.31.4. インデックスサポート

pg_trgmモジュールは、テキスト列全体に非常に高速な類似度検索を行うためのインデックスを作成することができるように、GiSTおよびGINインデックス演算子クラスを提供します。 これらのインデックス種類は上記類似度演算子をサポートし、さらにLIKEILIKE~および~*問い合わせにおけるトライグラムを基にしたインデックス検索をサポートします。 (これらのインデックスは等価性や単純な比較演算子をサポートしません。ですので通常のB-treeインデックスも必要になるかもしれません。)

例:

CREATE TABLE test_trgm (t text);
CREATE INDEX trgm_idx ON test_trgm USING GIST (t gist_trgm_ops);

または

CREATE INDEX trgm_idx ON test_trgm USING GIN (t gin_trgm_ops);

この段階で、テキスト列tに類似度検索で使用可能なインデックスがあります。 典型的な問い合わせを以下に示します。

SELECT t, similarity(t, 'word') AS sml
  FROM test_trgm
  WHERE t % 'word'
  ORDER BY sml DESC, t;

これは、wordに十分似たテキスト列の値をすべて、類似度の高い順番に返します。 インデックスは非常に大規模なデータ群に対する高速操作を行うために使用されます。

以下は上の問い合わせを変形させたものです。

SELECT t, t <-> 'word' AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

これはGINインデックスではなくGiSTインデックスにより非常に効率的に実装することができます。 通常、類似度が高いものの中から少ない個数のみを必要とする場合、1番目の式よりも効率的です。

また、単語の類似度あるいは厳密な単語の類似度に対してt列のインデックスを使うことができます。 典型的な問い合わせは、

SELECT t, word_similarity('word', t) AS sml
  FROM test_trgm
  WHERE 'word' <% t
  ORDER BY sml DESC, t;

および

SELECT t, strict_word_similarity('word', t) AS sml
  FROM test_trgm
  WHERE 'word' <<% t
  ORDER BY sml DESC, t;

です。 これは、wordのトライグラム集合に十分似ている順序付きトライグラム集合に対応する連続した領域が存在するテキスト列中のすべての値を返します。 結果は、最も似ているものから、最も似ていないものへの順にソートされます。 インデックスは、非常に大きなデータ集合に対しても高速な操作ができるようにするために使われます。

いくつか例を示します。

SELECT t, 'word' <<-> t AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

SELECT t, 'word' <<<-> t AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

これはGINインデックスではなく、GiSTインデックスによって極めて効率的に実装できます。

PostgreSQL 9.1から、これらのインデックス種類はLIKEおよびILIKEにおけるインデックス検索をサポートします。 以下に例を示します。

SELECT * FROM test_trgm WHERE t LIKE '%foo%bar';

インデックス検索は、検索文字列からトライグラムを抽出し、それらをインデックスから検索することによって動作します。 検索文字列内のトライグラムが多ければ、よりインデックス検索が効率的になります。 B-treeを基にした検索とは異なり、検索文字列の左側が固定されている必要はありません。

PostgreSQL 9.3から、これらの種類のインデックスは正規表現一致(~および~*演算子)に対するインデックス検索もサポートします。 以下に例を示します。

SELECT * FROM test_trgm WHERE t ~ '(foo|bar)';

インデックス検索は、正規表現からトライグラムを抽出し、それらをインデックスから検索することで動作します。 より多くのトライグラムが正規表現から抽出される場合、インデックス検索はより効率的になります。 B-treeを基にした検索と異なり、検索文字列は先頭一致である必要はありません。

LIKEおよび正規表現検索の両方で、トライグラムが抽出されないパターンでは完全インデックススキャンより性能が落ちることに注意してください。

GiSTまたはGINインデックスの選択は、他で説明されるGiSTとGINの相対的な性能特性に依存します。 これについては、別途議論されています。

F.31.5. テキスト検索の統合

トライグラム一致は全文テキストインデックスと一緒に使用する時、非常に有用なツールです。 特に、全文検索機構では直接一致しない、ミススペルがある入力単語の認識を行うために役に立ちます。

第一段階は文書内で一意な単語からなる補助テーブルを生成することです。

CREATE TABLE words AS SELECT word FROM
        ts_stat('SELECT to_tsvector(''simple'', bodytext) FROM documents');

ここでdocumentsは、検索対象のbodytextテキストフィールドを持つテーブルです。 言語固有の設定を使用するのではなく、to_tsvector関数でsimple設定を使用する理由は、元の(語幹抽出されていない)単語のリストが欲しいためです。

次にword列にトライグラムインデックスを作成します。

CREATE INDEX words_idx ON words USING GIN (word gin_trgm_ops);

これで、上の例に似たSELECT問い合わせを使用して、ユーザの検索語内でミススペルのある単語を提示できるようになります。 有用な追加された試験は、選択された単語の長さがミススペルのある単語の長さとほぼ同じになることを要求するものです。

注記

wordsテーブルは別に生成された静的なテーブルですので、文書群の更新に合理的に追従できるよう定期的に再生成する必要があります。 正確に最新状態を維持する必要性は通常ありません。

F.31.6. 参考

GiST開発サイト http://www.sai.msu.su/~megera/postgres/gist/

Tsearch2開発サイト http://www.sai.msu.su/~megera/postgres/gist/tsearch/V2/

F.31.7. 作者

Oleg Bartunov , Moscow, Moscow University, Russia

Teodor Sigaev , Moscow, Delta-Soft Ltd.,Russia

Alexander Korotkov , Moscow, Postgres Professional, Russia

文書作成: Christopher Kings-Lynne

本モジュールはロシアモスクワのDelta-Soft Ltd.による後援です。