用 Trigram 處理錯字 • PostgreSQL 的藝術

熱門搜尋引擎會依你的搜尋詞附上有用的資訊——自動更正（autocorrect）與「你是不是要找…？（did you mean?）」如今已是搜尋體驗的基本配備。PostgreSQL 實作了多種模糊字串比對（fuzzy string matching）方法，其中一種特別適合在已知的項目目錄中實作搜尋字串建議。

pg_trgm 擴充套件#

pg_trgm 提供基於 trigram 比對的文字相似度函式與運算子，以及支援快速相似字串搜尋的索引運算子類別。

PostgreSQL 本身就有完整的全文檢索（full text search）實作：文字搜尋解析器、支援詞幹提取（stemming）、同義詞庫的字典、全文查詢語言與結果排名工具。如果你需要的其實是全文檢索，請直接查官方文件。trigram 通常是全文檢索的互補工具——用來實作打字更正建議，或替 LIKE 與 POSIX 正規表達式搜尋加上索引。

一如往常，先在資料庫啟用擴充。若你用套件安裝 PostgreSQL，務必一併安裝 contrib 套件——總有一天你會需要它，屆時只要一句 create extension 就能開工：

create extension pg_trgm;

Trigram、相似度與搜尋#

trigram 背後的想法簡單而有效：把文字切成連續的三字母序列，就這樣。接著就能依兩段文字共有多少 trigram 來比較——這就是相似度（similarity）的概念。它效果出奇地好，而且不依賴語言。

以下查詢展示幾種 Tommy 拼法的 trigram，以及 tomy、dim 與 tom 相比的相似度值：

select show_trgm('tomy') as tomy,
       show_trgm('Tomy') as "Tomy",
       show_trgm('tom torn') as "tom torn",
       similarity('tomy', 'tom'),
       similarity('dim', 'tom');

-[ RECORD 1 ]-------------------------------------
tomy       | {" t"," to","my ",omy,tom}
Tomy       | {" t"," to","my ",omy,tom}
tom torn   | {" t"," to","om ",orn,"rn ",tom,tor}
similarity | 0.5
similarity | 0

文件對 similarity 函式的說明：回傳值介於 0（完全不相似）到 1（完全相同）。注意文字單位很小時，相似度看起來會更像猜測。預設相似度門檻是 0.3，可用 GUC 參數 pg_trgm.similarity_threshold 調整。

現在可以在音樂收藏中搜尋關於 love 的歌：

  select artist, title
    from lastfm.track
   where title % 'love'
group by artist, title
order by title <-> 'love'
   limit 10;

這裡出現兩個 pg_trgm 的新運算子：

% 讀作「相似於（similar to）」，比較左右兩個引數的 trigram。
<-> 計算兩引數間的「距離」，即 1 減去 similarity() 值。

          artist           │   title
════════════════════════════╪═══════════
 The Opals                  │ Love
 YZ                         │ Love
 Jars Of Clay               │ Love Me
 Barry Goldberg             │ Lost Love
 The Irish Tenors           │ My Love
 Spade Cooley               │ Lover
 Sugar Minott               │ Try Love
 ...
(10 rows)

trigram 相似度與正規表達式比對很不一樣。where title ~ 'peace' 一列都找不到——歌名裡從沒出現全小寫的 peace；改用不分大小寫的 ~* 才找到 11 首。而 trigram 搜尋 where title % 'peace' 找到 8 首，因為 trigram 本身就是不分大小寫計算的：

select show_trgm('peace') as "peace",
       show_trgm('Peace') as "Peace";

─[ RECORD 1 ]──────────────────────────
peace │ {" p"," pe",ace,"ce ",eac,pea}
Peace │ {" p"," pe",ace,"ce ",eac,pea}

另有一種相似度搜尋叫 word_similarity。依文件說明，它回傳的值約略可理解為「第一個字串與第二個字串任一子字串的最大相似度」，且不對範圍邊界補白——換句話說，這個函式更擅長在較長文字中找單字，很適合搜尋歌名：

select artist, title
  from lastfm.track
 where title %> 'peace';

%> 運算子使用 word_similarity，左運算元是較長的字串、右運算元是要搜尋的單字；<% 則左右對調（word <% phrase）。這次找到 12 列。

延伸比較：%> 與 ~* 結果差在哪

用 EXCEPT 讓 PostgreSQL 算出兩個結果集的差：

select artist, title
  from lastfm.track
 where title %> 'peace'

except

select artist, title
  from lastfm.track
 where title ~* 'peace';

   artist    │              title
═════════════╪═════════════════════════════════
 Dub Pistols │ Peaches - Fear of Theydon remix
(1 row)

看來 Peaches 與 peace 相似到足以入選。

補完與建議歌名#

如果搜尋字串本身打錯了呢？我們都會打錯字，使用者也一樣。試試小錯字 peas：where title ~* 'peas' 一列都沒有。使用者看到空結果不會開心，他們想要看到建議。改用相似度查詢：

select artist, title
  from lastfm.track
 where title %> 'peas';

這會列出 trigram 與搜尋字串相似的歌名，共 17 列（Peace、Peanuts、Crushed Pears、Peigin is Peadar…）——對「輸入即建議」的輸入框來說可能太多了。我們想限制為前五名，依歌名與搜尋詞的接近程度排序，再次用上 <-> 距離運算子：

   select artist, title
     from lastfm.track
   where title %> 'peas'
order by title <-> 'peas'
   limit 5;

           artist           │     title
════════════════════════════╪═══════════════
 Billy Higgins              │ Peace
 Little Joe & The Thrillers │ Peanuts
 Terry Riley                │ Peace Dance
 Dhamika                    │ Peace Prayer
 Twila Paris                │ Perfect Peace
(5 rows)

Trigram 索引#

要把這些建議直接接上使用者輸入介面，就得越快越好，而加速特定 SQL 查詢的常規答案就是索引。pg_trgm 附帶專門處理相似度搜尋的索引演算法，連正規表達式搜尋也涵蓋：

create index on lastfm.track using gist(title gist_trgm_ops);

用 explain 驗證先前的查詢已改用新索引：

explain (analyze, costs off)
select artist, title
  from lastfm.track
 where title ~* 'peace';

                                      QUERY PLAN
══════════════════════════════════════════════════════════════════════════════════════
 Index Scan using track_title_idx on track (actual time=0.552..3.832 rows=11 loops=1)
   Index Cond: (title ~* 'peace'::text)
 Planning time: 0.293 ms
 Execution time: 3.868 ms
(4 rows)

那個依距離排序的複雜查詢呢？

explain (analyze, costs off)
   select artist, title
     from lastfm.track
   where title %> 'peas'
order by title <-> 'peas'
   limit 5;

                                        QUERY PLAN
═══════════════════════════════════════════════════════════════════════════════════════
 Limit (actual time=6.730..6.773 rows=5 loops=1)
   -> Index Scan using track_title_idx on track (actual time=6.728..6.770 rows=5 loops
         Index Cond: (title %> 'peas'::text)
         Order By: (title <-> 'peas'::text)
 Planning time: 0.090 ms
 Execution time: 6.809 ms
(6 rows)

PostgreSQL 仍然只用一次索引掃描就完成整個查詢：因為索引掃描已知會依序回傳結果，上層的 limit 步驟送出前五列後就能立刻停止掃描。這樣的執行時間（毫秒級）足以讓這些查詢直接上線服務使用者。