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

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

pg_trgmモジュールは、テキスト列全体に非常に高速な類似度検索を行うためのインデックスを作成することができるように、GiSTおよびGINインデックス演算子クラスを提供します。 これらのインデックス種類は上記類似度演算子をサポートし、さらにLIKE、ILIKE、~および~*問い合わせにおけるトライグラムを基にしたインデックス検索をサポートします。 （これらのインデックスは等価性や単純な比較演算子をサポートしません。ですので通常の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番目の式よりも効率的です。

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の相対的な性能特性に依存します。 まとめとしては、GINインデックスはGiSTインデックスより検索が高速ですが、構築または更新は低速です。 このためGINは静的なデータに、GiSTはよく更新されるデータに適しています。

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

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

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

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

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

Oleg Bartunov <oleg@sai.msu.su>, Moscow, Moscow University, Russia

Teodor Sigaev <teodor@sigaev.ru>, Moscow, Delta-Soft Ltd.,Russia

文書作成: Christopher Kings-Lynne

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