白話文解說 Levenshtein Distance(萊文斯坦距離)
不知道你是否曾好奇,像 Google 或 Bing 這類搜尋引擎,是如何辨識你輸入的錯別字?例如,當你輸入 “seperate”(錯誤拼字)時,搜尋引擎能夠自動修正為正確的 “separate”,並以正確拼字進行搜尋和呈現結果。
本文將介紹一種演算法 — Levenshtein Distance(或稱萊文斯坦距離)!透過這個演算法,我們可以了解搜尋引擎如何尋找相似的單字,而且這個演算法也被知名的 Elasticsearch 所使用,相當值得認識!
接下來,本文將從編輯距離(edit distance)的概念出發,逐步帶你深入了解 Levenshtein Distance。