模糊搜索&自動糾錯——Fuzzy Query by Levenshtein Automata

05-19

在我們每天使用的搜索引擎中，有這麼一個簡單的小功能經常被忽略——模糊搜索以及自動糾錯。當我們輸入一個錯誤的單詞時，與其相似的結果將會被返回。這個小功能需要很高的效率以提供良好的用戶體驗。

舉個栗子：

「relevent」自動糾錯為「relevant」

不知道你有沒有思考過這是如何實現的呢？

如果你對它感興趣的話，請耐心讀完本文，你將會有所收穫。

本文的目的在於以簡單易懂的方式闡述一種實現Fuzzy Query的方法——Levenshtein Automata。這種方法目前被用於Apache Lucene里。

在我們開始聊看起來很複雜的Levenshtein Automata前，首先需要知道以下這些事情。

Levenshtein Distance

首先，模糊匹配返回的單詞集合是與搜索的單詞相似的結果。那麼，我們首先需要的就是定義這種相似。

給定兩個字元串（單詞），稱兩個字元串之間的「距離」為Levenshtein Distance，即編輯距離。簡單來說，就是由字元串A變成字元串B所需要的最少變化（插入，刪除，替換）次數。

示例：abcd 和 acdf 的編輯距離為2。
abcd ------> 刪除 b ------> acd
acd ------> 插入 f ------> acdf

編輯距離的定義非常簡單，距離越小的兩個單詞就越相似。接下來，對於給定的兩個字元串，我們需要用一種方法來計算編輯距離。直觀的方法是遞歸，更優的方法是動態規劃。在這裡不詳細介紹了，這個問題是個經典演算法問題，有太多的資料可以去看。

Lucene內的Levenshtein Distance實現?

github.com

這裡貼一下Lucene內的實現。對於利用動態規劃編輯距離的計算，演算法時間複雜度為 $O(MN)$ ，空間複雜度可以優化到 $O(N)$ 。

說到這裡，我們已經知道如何定義相似。回到文章開始的使用場景，我們可以把這個問題簡單提煉一下。

問題的輸入：

已知的詞典集合D，D中包含著大量的正確單詞。
用戶輸入查詢的字元串query。
距離n，衡量某一字元串與查詢query的相似程度（即編輯距離大小）

問題的輸出：

一個集合results，是與query距離小於n的，詞典D的子集。

Naive Method

說到這裡，想必你已經想出來一個最簡單的方法了——把集合D中每一個單詞和query的距離都計算一下，返回結果小於n的就可以了。

然而，這種方法每作一次查詢都需要遍歷一次詞典D，並計算每個單詞與query的編輯距離，在上述需要立即給用戶返回結果的場景中，顯然不具有現實意義。我們需要更高效的方法。

下面就要提到本文的主角了——Levenshtein Automata。

Levenshtein Automata

簡單來說，這個演算法是對給定的query和距離n建立一個有限狀態自動機FSA（Finite State Automaton），這樣就可以在 $O(N)$ 時間內判斷兩個字元串是否相似（編輯距離小於n）。

演算法的感性理解，把自動機看成一個黑盒即可

利用Levenshtein Automata，對比之前的動態規劃，我們把 $O(MN)$ 演算法提升到了 $O(N)$ ，對於D中大量的字元串來說，至少這是一個優化。當然這個演算法並不是只有這個優點。

等一下，什麼是有限狀態自動機？讓我們一步一步來。

Finite State Automaton (FSA)

如果你嘗試搜索有限狀態自動機，複雜的數學模型和難懂的術語可能讓你暈頭轉向。

但對於這個演算法來說，我們只需要簡單理解FSA即可。

可以把FSA成一個有向圖，圖裡的節點是狀態。這個有向圖有一個入口，我們從入口進入，然後輸入給FSA的字元串的每一個字元，就是一個指導我們沿著圖中的相應的邊轉移到下一個狀態的命令。

圖中是一個很簡單的例子，從左邊入口進入狀態1。假設輸入的query字元串為FOOD，則字元F讓我們轉移到狀態2，接下來兩個字元O都會使我們沿著邊回到狀態2，最後D讓我們到達狀態3。這裡的狀態3有黑色的圈，表示FSA中的接受狀態。如果query字元串是FOO，那麼最終我們會停留在狀態2，就表示FSA不接受這個字元串。

圖中的示例對於每個狀態，同樣符號的邊只有一個，這樣的FSA稱為確定有限狀態自動機(deterministic finite automaton, DFA)。還有一種非確定有限狀態自動機NFA（參考下圖）。它可以由同一狀態發出多條相同符號的邊，而且允許空邊的存在，用 $epsilon$ 來表示，即不需要輸入也可以通過這條邊轉移到下一個狀態。

我們簡單了解了FSA，那麼下一步就是如何根據query構建它呢？

構建NFA

樣例及下文示例代碼來自Nick Johnsons Blog

NFA(query=food, n=2)

這裡給出了一個樣例的NFA。

這個狀態機的入口是左下角，由於包含了 $epsilon$ 空邊，所以這是個NFA。首先理解每個狀態中的數字是什麼意思。每個狀態的形式是 $n^e$ ，其中 $n$ 是走到當前狀態消耗的字元數， $e$ 表示錯誤數，也就是編輯距離。由於我們的query是food，有四個字元，n是2，最多距離為2，所以右上角的狀態是 $4^2$ 。

再看圖中的邊，有三種類型的邊，分別是 $*$ ， $epsilon$ 以及字元。其中水平向右的邊都是字元邊，表示輸入當前邊上符號的字元時候轉移，意思是不做編輯。向上的 $*$ 邊表示插入操作，這個操作不消耗輸入字元（相當於一種空邊）但是需要一次編輯，所以由 $0^0$ 轉移到的下一個狀態是 $0^1$ 。向右上方的邊表示一次替換操作，這個既需要消耗一個輸入字元，又需要一次編輯。向右上方的 $epsilon$ 邊表示刪除操作。

圖中最右側的三個狀態是黑色的圈，也就是接受狀態。如果輸入一個字元串，最終狀態停在 $4^0,4^1,4^2$ 這三個狀態的話，表示這個字元串和food在距離2內相似。

如果這樣還是很抽象的話，讓我們舉個例子。

假設輸入了前兩個字母f和x，我們可能會暫時停在以下幾個灰色狀態。

比如我們消耗第一個f向右移動，然後消耗x字元做替換操作（原始的第二個字元應該是o）向右上移動，到達狀態 $2^1$ 。如果接下來是od，那麼我們可以接受fxod。事實上恰好是第二個字元o做一次替換操作得到fxod。

又比如我們消耗f向右移動，又進行刪除操作向右上移動，再消耗一個x做替換操作，到達狀態 $3^2$ 。如果接下來的輸入是d，那麼我們可以接受fxd。事實上food恰好刪除第二個字元且替換第三個字元可以得到fxd。

所以灰色的六個狀態是所有可能的當前狀態，隨著輸入更多的字元，這些狀態會不斷進行狀態轉移。最終輸入所有的字元，停在某幾個可能的狀態。如果這些狀態中存在接受狀態，則可以說明我們經過某些操作可以把輸入的字元串轉化成food，也就是說可以接受這個輸入的單詞。

相信我，當你看懂這個圖之後，會有一種很奇妙的感覺。

其實構造這樣的NFA並不複雜，下面是python的實現。

def levenshtein_automata(term, k): nfa = NFA((0, 0)) for i, c in enumerate(term): for e in range(k + 1): # Correct character nfa.add_transition((i, e), c, (i + 1, e)) if e < k: # Deletion nfa.add_transition((i, e), NFA.ANY, (i, e + 1)) # Insertion nfa.add_transition((i, e), NFA.EPSILON, (i + 1, e + 1)) # Substitution nfa.add_transition((i, e), NFA.ANY, (i + 1, e + 1)) for e in range(k + 1): if e < k: nfa.add_transition((len(term), e), NFA.ANY, (len(term), e + 1)) nfa.add_final_state((len(term), e)) return nfa

可以看出構造這樣的一個NFA的複雜度是 $O(kN)$ ，這裡的k很小，通常為2或3（Lucene內的n=2）所以可以近似看成N的線性時間。

咦？好像不對啊，雖然構造起來很快，可是在NFA中進行狀態轉移，每一步都有多種情況，事實上計算量反而更多了呀。

於是我們需要把NFA轉換成DFA。在計算理論中，NFA和DFA是等價的。但DFA中對於每一個轉移，下一個活躍狀態是確定的，所以計算是非常高效的。

構建DFA

這裡是個由query=food建立的DFA，輸入任意單詞，如果最終落在粗的圓圈上，即接受狀態，則表示這個單詞的編輯距離與food小於等於1。

DFA(query=food, n=1)

這個圖要比之前NFA好理解的多，不信我們再來個例子試試。假如我們有單詞feod。那麼狀態轉移的過程應該是

$0^01^1 ightarrow0^11^01^12^1 ightarrow1^12^1 ightarrow2^13^1 ightarrow4^1$

最後的狀態是接受狀態，所以輸入的單詞我們認為是與food相似的。怎麼樣，是不是很簡單？

可以發現，在DFA中的計算是非常的高效。但是如何從NFA構造一個DFA呢？

標準的方法是冪集構造（Powerset Construction）。然而這種方法的最壞時間是 $O(2^n)$ 。指數複雜度的演算法我們是不能接受的。可是並不要太擔心，首先對於Levenshtein Automata來說是不會接近最壞時間的，其次，我們甚至有 $O(n)$ 的演算法來構造DFA $^{[1]}$ ，甚至有一些跳過構造DFA的步驟而是基於表格的演算法。（Lucene內的實現就非常神奇，有興趣可以去研究一下）

更高效的搜索

到這裡我們已經了解了如何高效的構造Levenshtein Automata了，當然還有一個問題就是如何更高效的搜索D中的單詞。

一種方法是將D本身看做DFA。字典集D常用數據結構如Trie，是一種特殊的DFA。將D和Levenshtein Automata進行交運算。也就是同時遍歷兩個DFA，並且只沿著相同的邊前進。當兩個DFA都到達了接受狀態，則當前的單詞可以作為結果集中的一個輸出。

def intersect(dfa1, dfa2): stack = [("", dfa1.start_state, dfa2.start_state)] while stack: s, state1, state2 = stack.pop() for edge in set(dfa1.edges(state1)).intersect(dfa2.edges(state2)): state1 = dfa1.next(state1, edge) state2 = dfa2.next(state2, edge) if state1 and state2: s = s + edge stack.append((s, state1, state2)) if dfa1.is_final(state1) and dfa2.is_final(state2): yield s

這種方法適用於以DFA的形式進行存儲的字典集。

然而還有很多字典是以某種sorted list的形式存儲在內存里，又或者以BTree的方式在硬碟中，這該怎麼辦呢？

Naive的方法是從最小的字元串依次放到自動機中遍歷，然而我們可以做一些改進。由於Levenshtein Automata像一個有向圖。如果某個錯誤的字元串最後落在了某個拒絕狀態，可以從這個狀態開始回溯搜索，找到自動機里按字典序的停在下一個接受狀態的單詞。我們只需要把自動機做一點預處理，讓搜索的時候從每一個狀態的最小字典序的邊開始，就可以簡單快速的找到下一個可接受的單詞。這就意味著在有序的字典D中可以直接跳過這個單詞之前的所有錯誤情況，極大提高了遍歷的效率。

從第一個單詞開始遍歷，放入自動機中若拒絕，則搜索下一個可接受單詞，跳到這個單詞處繼續遍歷。

到這裡，這篇文章就結束啦！如果你認真地讀到了這裡，相信你應該弄懂了基本的原理。

接下來會繼續分享更多有趣的內容的。

默默匿去讀書啦。ε=ε=ε=ε=ε=┌(;￣◇￣)┘

參考

$[1]$ Fast string correction with Levenshtein automata

$[2]$ http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata