PostgreSQL pg_trgm

一个 trigram 是从一个字符串中取出的由三个连续字符组成的组。我们可以通过对两个字符串之间共享的 trigram 计数来度量它们的相似度。这种简单的思想已经成为在很多自然语言中度量词相似度的有效方法。

pg_trgm模块所提供的函数如表 F.24中所示，操作符则显示在表 F.25中。

考虑下面的例子：

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

在第一个字符串中，trigram集合是{" w"," wo","wor","ord","rd "}。在第二个字符串中，trigram的有序集是{" t"," tw","two","wo "," w"," wo","wor","ord","rds","ds "}。在第二个字符串中最相似的trigram有序集的部分是{" w"," wo","wor","ord"}，并且相似度是 0.8。

这个函数返回的值可以大概地理解为第一个字符串和第二个字符串任意子串的最大相似度。不过，这个函数不会对该部分的边界加入填充。因此，除了失配的词边界之外，第二个字符串中存在的额外字符的数目没有被考虑。

同时，strict_word_similarity在第二个字符串中选择一个由词构成的部分。 在上面的例子中，strict_word_similarity会选择单个词'words'形成的部分， 其trigram集合为{" 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 索引操作符类，这允许你在一个文本列上创建索引用于快速相似度搜索的目的。这些索引类型支持上述的相似度操作符，并且额外支持基于 trigram 的索引搜索用于LIKE、ILIKE、~和~*查询（这些索引不支持等值或简单比较操作符，因此你可能还需要一个常规的 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;

这将返回文本列中符合条件的所有值：这些值在其对应的有序trigram集中有一个连续部分与word的trigram集合足够相似，这些值会按照最好匹配到最差匹配的顺序排列。即便在非常大的数据集上，索引也将使得这一操作的速度够快。

上述查询可能的变体有：

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';

该索引搜索通过从搜索字符串中抽取 trigram 并且在索引中查找它们来工作。搜索字符串中有更多 trigram，索引搜索的效率更高。不像基于 B-树的搜索，搜索字符串不需要是左锚定的。

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

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

该索引搜索通过从正则表达式中抽取 trigram 并且在索引中查找它们来工作。正则表达式中能抽取出更多 trigram，索引搜索的效率更高。不像基于 B-树的搜索，搜索字符串不需要是左锚定的。

对于LIKE和正则表达式搜索，记住没有可抽取 trigram 的模式将退化成一个全索引扫描。

GiST 和 GIN 索引之间的选择依赖于 GiST 和 GIN 的相对性能特性，这在其他地方讨论。

在与一个全文索引联合使用时，trigram 匹配是一种非常有用的工具。特别是它能有助于识别拼写错误的输入词，这些词直接用全文搜索机制是不会被匹配的。

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

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

其中documents是一个具有我们希望搜索的文本域bodytext的表。对to_tsvector函数使用simple配置而不是使用语言相关的配置的原因是，我们想要一个原始（没有去掉词根的）词的列表。

接下来，在词列上创建一个 trigram 索引：

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/