三元组是从字符串获取的连续三个字符的组。我们可以通过计算其共享的三元组数量来衡量两个字符串的相似性。这个简单的想法被证明对衡量许多自然语言单词的相似性非常有效。

pg_trgm 模块提供的函数显示在 表格 F.25 中，运算符显示在 表格 F.26 中。

考虑以下示例

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

在第一个 string 中，三元组的集合是 {" w"," wo","wor","ord","rd "}。在第二个 string 中，有序的三元组集合是 {" t"," tw","two","wo "," w"," wo","wor","ord","rds","ds "}。第二个 string 中最相似的有序三元组范围为 {" w"," wo","wor","ord"}，而相似度为 0.8。

此函数返回一个值，该值可近似理解为第一个 string 和第二个 string 中的任何子串之间的最大相似度。但是，此函数不会在范围的边界处添加填充。因此，第二个 string 中存在的其他字符数不会被考虑，除了不匹配的单词边界外。

同时，strict_word_similarity 会在第二个 string 中选择一个单词范围。在上述示例中，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 opclass 将一组三元组近似表示为位图签名。它的可选整数参数 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 索引之间进行选择取决于 GiST 和 GIN 的相对性能特征，这些特征在其他地方进行了讨论。

三元组匹配在与全文索引结合使用时是一个非常有用的工具。特别是，它可以帮助识别拼写错误的输入词，而全文搜索机制无法直接匹配这些词。

第一步是生成一个辅助表，该表包含文档中所有唯一的单词

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

其中 documents 是一个表，它有一个文本字段 bodytext，我们希望搜索它。使用 simple 配置而不用语言特定的配置与 to_tsvector 函数的原因是，我们需要一个原始（未词干化的）单词的列表。

接下来，在单词列上创建一个三元组索引

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

Teodor Sigaev <[email protected]>，莫斯科，俄罗斯，Delta-Soft 公司

Alexander Korotkov <[email protected]>，莫斯科，俄罗斯，Postgres Professional

文档：Christopher Kings-Lynne

此模块由俄罗斯莫斯科 Delta-Soft 有限公司赞助。