Spell Check / 錯字校正是如何運作的？
覺得我們的內容實用嗎？ MyApollo 電子報讀者募集中！歡迎訂閱電子報!
以前工作有同事在做 Spell Check, 那時還沒有多餘心思去了解背後真正的運作原理，不過也認為這個功能很不簡單，所以一看到 “The Algorithm Behind Spell Checkers” 這部 YT 影片時，就馬上引起我的注意。
這部影片從 Spell Check 的歷史介紹起，接著介紹它的核心概念：
- 先找出不存在於字典的字，例如 flaat
- 找出最接近它的可能字，例如 flat
第 1 步相對簡單，理論上只要存 10,000 個常用英文單字，就幾乎涵蓋多數人日常使用的單字量，藉此就可以找到「可能」的錯字（之所以用「可能」是因為它仍可能是正確的字，只是不存在於常用字的字典內而已）。 第 2 步就比較困難，需要定義所謂的「接近」是什麼意思？這個就是影片中所謂的 edit distance, 也就是 1 個單字 A, 要經過幾個步驟才能變成單字 B, 步驟的選項有：
- 新增字元
- 刪除字元
- 取代字元
譬如 fash 變成 fish 只要做 1 次取代，將 a 換成 i 就行，因此 edit distance 距離是 1 。 而找到這個距離(distance)的方法就是影片中介紹的 Levenshtein distance 與 Wagner–Fischer 演算法，有興趣的話可以花些時間看一下，可以接觸到 Dynamic Programming 這個技巧，推薦！
實務上 Spell Check 不僅是文字編輯器的常見功能，也是電商搜尋功能/網頁搜尋功能相當重要的一環，因為有很多使用者無法正確拼出商品名稱、型號，這是導致使用者直覺認為搜尋功能不準確、不實用的原因之一，因此講究的公司會加入運用 spell check 技術的校正功能，同時搜尋使用者提供的搜尋字串與 spell check 校正過的可能關鍵字，藉此提升搜尋品質。
