pg_trgm
モジュールは、類似文字列の高速検索をサポートするインデックス演算子クラスだけではなく、トライグラム一致に基づく英数字の類似度の決定に関する関数と演算子も提供します。
このモジュールは「trusted」と見なされます。つまり、現在のデータベースに対してCREATE
権限を持つ非スーパーユーザがインストールできます。
トライグラムは文字列から3つの連続する文字を取り出したグループです。 共有するトライグラムの個数を数えることで、2つの文字列の類似度を測定することができます。 この単純な考えが、多くの自然言語における単語の類似度を測定する際に非常に効率的であることが判明しています。
pg_trgm
は、文字列からトライグラムを抽出する時に単語以外の文字(英数字以外)を無視します。
文字列内に含まれるトライグラム集合を決める際、文字列の前に2つの空白、後に1つの空白が付いているものとみなされます。
例えば、「cat
」という文字列のトライグラム集合は、「 c
」、「 ca
」、「cat
」、「at
」です。
「foo|bar
」という文字列のトライグラム集合は、「 f
」、「 fo
」、「foo
」、「oo
」、「 b
」、「 ba
」、「bar
」、「ar
」です。
pg_trgm
モジュールで提供される関数を表 F.26に、演算子を表 F.27に示します。
表F.26 pg_trgm
Functions
以下の例を考えます。
# 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
は二番目の文字列の単語の範囲を選択します。
上記の例でstrict_word_similarity
は単語'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
関数は単語の並び全体の類似度を求めるのに有益で、対して、word_similarity
は単語の並びの一部の類似度を求めるのにより適しています。
表F.27 pg_trgm
Operators
演算子 説明 |
---|
2つの引数が |
最初の引数中のトライグラムの集合と、二番目の引数中の順序付きトライグラム集合の中の範囲の類似度が、 |
|
二番目の引数が単語の境界と一致する順序付きトライグラム集合の連続した範囲を持っていて、かつ、最初の引数のトライグラム集合に対する類似度が |
|
引数間の「距離」、この場合は1 - |
引数間の「距離」、この場合は1 - |
|
引数間の「距離」、この場合は1 - |
|
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です)
pg_trgm
モジュールは、テキスト列全体に非常に高速な類似度検索を行うためのインデックスを作成できるように、GiSTおよびGINインデックス演算子クラスを提供します。
これらのインデックス種類は上記類似度演算子をサポートし、さらにLIKE
、ILIKE
、~
、~*
および=
問い合わせにおけるトライグラムを基にしたインデックス検索をサポートします。
pg_trgm
のデフォルトのビルドでは、類似度比較は大文字と小文字を区別しません。
非等価演算子はサポートされていません。
これらのインデックスは、等価演算子に対する通常の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);
gist_trgm_ops
GiST演算子クラスはトライグラムの集合をビットマップ署名として近似します。
オプションの整数パラメータsiglen
は、署名の長さをバイト単位で決定します。
デフォルトの署名の長さは12バイトです。
署名の長さの有効な値は1から2024バイトまでです。
長い署名では、インデックスはより大きくなってしまいますが、(インデックスのより小さな部分とより少ないヒープページを走査することで)検索がより正確になります。
署名の長さが32バイトのインデックスを作成する例
CREATE INDEX trgm_idx ON test_trgm USING GIST (t gist_trgm_ops(siglen=32));
この段階で、テキスト列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の相対的な性能特性に依存します。 これについては、別途説明されています。
トライグラム一致は全文テキストインデックスと一緒に使用する時、非常に有用なツールです。 特に、全文検索機構では直接一致しない、ミススペルがある入力単語の認識を行うために役に立ちます。
第一段階は文書内で一意な単語からなる補助テーブルを生成することです。
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
テーブルは別に生成された静的なテーブルですので、文書群の更新に合理的に追従できるよう定期的に再生成する必要があります。
正確に最新状態を維持する必要性は通常ありません。
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
Alexander Korotkov <a.korotkov@postgrespro.ru>
, Moscow, Postgres Professional, Russia
文書作成: Christopher Kings-Lynne
本モジュールはロシアモスクワのDelta-Soft Ltd.による後援です。