PostgreSQL pg_trgm

一個(gè) trigram 是從一個(gè)字符串中取出的由三個(gè)連續(xù)字符組成的組。我們可以通過對(duì)兩個(gè)字符串之間共享的 trigram 計(jì)數(shù)來度量它們的相似度。這種簡(jiǎn)單的思想已經(jīng)成為在很多自然語言中度量詞相似度的有效方法。

pg_trgm模塊所提供的函數(shù)如表 F.24中所示，操作符則顯示在表 F.25中。

考慮下面的例子：

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

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

這個(gè)函數(shù)返回的值可以大概地理解為第一個(gè)字符串和第二個(gè)字符串任意子串的最大相似度。不過，這個(gè)函數(shù)不會(huì)對(duì)該部分的邊界加入填充。因此，除了失配的詞邊界之外，第二個(gè)字符串中存在的額外字符的數(shù)目沒有被考慮。

同時(shí)，strict_word_similarity在第二個(gè)字符串中選擇一個(gè)由詞構(gòu)成的部分。 在上面的例子中，strict_word_similarity會(huì)選擇單個(gè)詞'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函數(shù)對(duì)于計(jì)算整個(gè)詞的相似度有用，而word_similarity更適合于計(jì)算詞的部分相似度。

pg_trgm模塊提供了 GiST 和 GIN 索引操作符類，這允許你在一個(gè)文本列上創(chuàng)建索引用于快速相似度搜索的目的。這些索引類型支持上述的相似度操作符，并且額外支持基于 trigram 的索引搜索用于LIKE、ILIKE、~和~*查詢（這些索引不支持等值或簡(jiǎn)單比較操作符，因此你可能還需要一個(gè)常規(guī)的 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 將一組三元組近似為位圖簽名。 它的可選整數(shù)參數(shù)siglen 確定簽名長(zhǎng)度（以字節(jié)為單位）。 默認(rèn)長(zhǎng)度為 12 個(gè)字節(jié)。簽名長(zhǎng)度的有效值介于 1 到 2024 字節(jié)之間。 更長(zhǎng)的簽名導(dǎo)致更精確的搜索（掃描索引的一小部分和更少的堆頁(yè)面），但代價(jià)是更大的索引。

創(chuàng)建簽名長(zhǎng)度為 32 字節(jié)的此類索引的示例：

CREATE INDEX trgm_idx ON test_trgm USING GIST (t gist_trgm_ops(siglen=32));

此時(shí)，你將有一個(gè)t列上的索引，你可以用它進(jìn)行相似度搜索。一個(gè)典型的查詢是

SELECT t, similarity(t, 'word') AS sml
  FROM test_trgm
  WHERE t % 'word'
  ORDER BY sml DESC, t;

這將返回在文本列中與word足夠相似的所有值，按最佳匹配到最差匹配的方式排序。索引將被用來讓這種搜索變快，即使在一個(gè)非常大的數(shù)據(jù)集上。

上述查詢的一種變體是

SELECT t, t <-> 'word' AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;

這能夠用 GiST 索引有效地實(shí)現(xiàn)，但是用 GIN 索引無法做到。當(dāng)只想要少數(shù)最接近的匹配時(shí)，這通常會(huì)比第一種形式更好。

也可以把一個(gè)t列上的索引用于詞相似度或者嚴(yán)格詞相似度。典型的查詢是：

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;

這將返回文本列中符合條件的所有值：這些值在其對(duì)應(yīng)的有序trigram集中有一個(gè)連續(xù)部分與word的trigram集合足夠相似，這些值會(huì)按照最好匹配到最差匹配的順序排列。即便在非常大的數(shù)據(jù)集上，索引也將使得這一操作的速度夠快。

上述查詢可能的變體有：

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 索引很高效地實(shí)現(xiàn)，但是用 GIN 索引不行。

從PostgreSQL 9.1 中開始，這些索引類型也支持用于LIKE和ILIKE的索引搜索，例如

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

該索引搜索通過從搜索字符串中抽取 trigram 并且在索引中查找它們來工作。搜索字符串中有更多 trigram，索引搜索的效率更高。不像基于 B-樹的搜索，搜索字符串不需要是左錨定的。

從PostgreSQL 9.3 中開始，這些索引類型也支持用于正則表達(dá)式匹配（~和~*操作符）的索引搜索，例如

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

該索引搜索通過從正則表達(dá)式中抽取 trigram 并且在索引中查找它們來工作。正則表達(dá)式中能抽取出更多 trigram，索引搜索的效率更高。不像基于 B-樹的搜索，搜索字符串不需要是左錨定的。

對(duì)于LIKE和正則表達(dá)式搜索，記住沒有可抽取 trigram 的模式將退化成一個(gè)全索引掃描。

GiST 和 GIN 索引之間的選擇依賴于 GiST 和 GIN 的相對(duì)性能特性，這在其他地方討論。

在與一個(gè)全文索引聯(lián)合使用時(shí)，trigram 匹配是一種非常有用的工具。特別是它能有助于識(shí)別拼寫錯(cuò)誤的輸入詞，這些詞直接用全文搜索機(jī)制是不會(huì)被匹配的。

第一步是生成一個(gè)包含文檔中所有唯一詞的輔助表：

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

其中documents是一個(gè)具有我們希望搜索的文本域bodytext的表。對(duì)to_tsvector函數(shù)使用simple配置而不是使用語言相關(guān)的配置的原因是，我們想要一個(gè)原始（沒有去掉詞根的）詞的列表。

接下來，在詞列上創(chuàng)建一個(gè) trigram 索引：

CREATE INDEX words_idx ON words USING GIN(word gin_trgm_ops);

現(xiàn)在，類似于前面例子的一個(gè)SELECT查詢可以被用來為用戶搜索術(shù)語中的拼寫不當(dāng)?shù)脑~建議拼寫。要求被選擇的詞也與拼寫不當(dāng)?shù)脑~具有相似的長(zhǎng)度是一種有用的額外測(cè)試。

GiST 開發(fā)站點(diǎn) http://www.sai.msu.su/~megera/postgres/gist/

Tsearch2 開發(fā)站點(diǎn) http://www.sai.msu.su/~megera/postgres/gist/tsearch/V2/