三元组是从字符串中取出的三个连续字符组成的组。我们可以通过统计两个字符串共享的三元组数量来衡量它们的相似度。这个简单的想法在许多自然语言中衡量单词相似度方面非常有效。

pg_trgm 模块提供的函数见 Table F.26，操作符见 Table F.27。

考虑下面的示例：

# 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 更适合查找与单词片段的相似度。

pg_trgm 模块提供 GiST 与 GIN 索引操作符类，允许在文本列上创建索引以实现非常快速的相似度搜索。这些索引类型支持上述相似度操作符，此外还支持针对 LIKE、ILIKE、~、~* 与 = 查询的基于三元组的索引搜索。在默认构建的 pg_trgm 中，相似度比较不区分大小写。不支持不等值操作符。请注意，对于等值操作符，这些索引的效率可能不如常规 B 树索引。

示例：

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;

这可以被 GiST 索引高效实现，但 GIN 索引做不到。当只需要少量最接近的匹配时，这种写法通常优于第一种。

也可以在 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;

这可以被 GiST 索引高效实现，但 GIN 索引做不到。

从 PostgreSQL 9.1 开始，这些索引类型还支持 LIKE 与 ILIKE 的索引搜索，例如

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

索引搜索通过从搜索字符串中提取三元组，然后在索引中查找它们来实现。搜索字符串中的三元组越多，索引搜索越有效。与基于 B 树的搜索不同，搜索字符串无需左锚定。

从 PostgreSQL 9.3 开始，这些索引类型还支持正则表达式匹配（~ 与 ~* 操作符）的索引搜索，例如

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

索引搜索通过从正则表达式中提取三元组，然后在索引中查找它们来实现。能从正则表达式中提取的三元组越多，索引搜索越有效。与基于 B 树的搜索不同，搜索字符串无需左锚定。

对于 LIKE 与正则表达式搜索，请记住：无法提取出任何三元组的模式会退化为全索引扫描。

在 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 查询来为用户搜索词中的拼写错误单词建议正确拼写。一个有用的附加测试是要求选中的单词与拼错的单词长度也相近。

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>，俄罗斯莫斯科，莫斯科大学

Teodor Sigaev <teodor@sigaev.ru>，俄罗斯莫斯科，Delta-Soft Ltd.

Alexander Korotkov <a.korotkov@postgrespro.ru>，俄罗斯莫斯科，Postgres Professional

文档：Christopher Kings-Lynne

本模块由俄罗斯莫斯科的 Delta-Soft Ltd. 赞助。