該文章同步發佈於：我的部落格

也歡迎關注我的 Facebook 以及 Instagram 接收軟體相關的資訊！

在看過 Term level, Full text 以及 Phrase Query 三種不同搜尋之後，想必對於搜尋已經有了一些概念。

但根據目前學習到的搜尋方式，會發現如果打錯字時，沒辦法搜尋到想要的資料，儘管相關性看起來很高，像是 aple 以及 apple。

而 Elasticsearch ( 以下簡稱 ES )，就提供了一個很棒的功能，叫做『 模糊搜尋 』，一起來看看是如何實現的。

Fuzzy Search

舉例，我們搜尋 Wedding 時，不小心少打一個字，變成 Weding，這時候就會沒有任何搜尋結果，這是在預期內的，根據 inverted index 是找不到這個 key 的。

// GET /movies/_search

{
  "query": {
    "match": {
      "title": {
        "query": "Weding"
      }
    }
  }
}

結果如下：

該如何做可以達到模糊搜尋的效果呢？只需要加上 fuzziness 這個選項，並設置成 auto 即可。

// GET /movies/_search

{
  "query": {
    "match": {
      "title": {
        "query": "Weding",
        "fuzziness": "auto"
      }
    }
  }
}

就能找到 5 筆相關的結果：

首先，ES 是採用 Levenshtein Distance 這套算法來處理這項功能。

這個算法實現的細節太難了，不重要，我們專注於在 ES 的層面上是如何實現，以及要如何設定 fuzziness 的值就好。

這個 fuzziness 可以設定成數字或是 auto，那設定成數字代表什麼呢？維基百科寫得非常好。

看至少需要多少次的處理才能將一個字串變成另一個字串

舉例來說，zo 變成 zoo 只需要 1 次的處理，但 ale 變成 apple 卻需要 2 次的處理。

而這個 fuzziness 的值，就是讓你去設定最高你可以接受幾次的處理。

當設定成 auto 時，ES 有自己的規則存在，如下圖：

當單字的長度在 1~2 之間，代表的像是 ok 或是 hi 這樣的單字，當使用者打錯時，可以接受的處理次數是 0，也就是不會去進行模糊搜尋。

最多的處理次數是 2 的可能原因

1. 根據研究指出，人類很少在同一個單字中出現 2 次以上的拼寫錯誤，所以這樣的設定可以達成大概 80% ~ 90% 正確的模糊搜尋效果。
2. 如果可以接受處理次數在 auto 的情況下會達到 3，這樣的搜尋結果是非常不可預測，以及非常不準確的，試著想看看，搜尋 woooh 會出現 watch 的內容，這應該是蠻糟糕的。
3. 效能考量，當數字超過 2 時，需要做的配對會更多，耗費的資源也會更多。

而關於 spelling checker 這樣的大題材，可以試著看看下面這兩篇很有趣的論文：

1. Using the Web for Language Independent Spellchecking and Auto-correction

2. How Difficult is it to Develop a Perfect Spell-checker? A Cross-linguistic Analysis through Complex Network Approach

Fuzzy Transpositions

這個段落會介紹另外一個有趣的功能，叫做 transposition，轉換位置。

舉例來說，Wedding 以及 Wedidng 在剛剛提到 fuzziness 內需要做 2 次的處理，才可以配對成功。

但在 ES 之中，如果設定 fuzziness 後，會有一個預設的值叫做 fuzziness_transposition 並且設定成 true，這個值是做什麼的？賣個關子，等等就會知道。

而 transposition 這件事說白了就是交換相鄰的兩個單字，但搭配上 fuzzy 這件事後，就會試著把相鄰的單字交換後嘗試去配對，若是配對成功只算 1 次的處理。

在下面的範例中，我們設定最高的處理次數是 1，也代表了 Wedidng 是不可能配對到 Wedding 的，因為要做 2 次處理。

// GET /movies/_search

{
  "query": {
    "match": {
      "title": {
        "query": "Wedidng",
        "fuzziness": 1
      }
    }
  }
}

但神奇的事情出現了，它可以搜尋的到。

就是因為這個 fuzziness_transposition 的預設值搞的鬼，它使用 transposition 的方式，讓這個單字只經過 1 次處理就達到目的。

所以我們把這個選項關掉試試看：

// GET /movies/_search

{
  "query": {
    "match": {
      "title": {
        "query": "Wedidng",
        "fuzziness": 1,
        "fuzzy_transpositions": "false"
      }
    }
  }
}

當沒有 transposition 後，最高只接受 1 次處理的查詢是對不上的，如下圖：

結語

模糊搜尋是一個雙面刃的功能，設定的值需要經過不斷地驗證和測試才可以找到最適合的數字，但對於大多數的情況來說，開啟 auto 就非常夠用了。

至於為什麼說是雙面刃呢？因為打開模糊搜尋意味著會有一些不符合預期的搜尋結果出現，像是 migrate 和 immigrate 就不一樣，但還是會被同時顯示出來。