拼寫檢查算法如何優化對建議詞的搜索？

Question

根據我的理解，拼寫檢查算法通過檢查轉換次數（交換字母，添加字母，刪除字母等）來查找建議，給定單詞需要成爲字典中的一個或多個真實單詞。我明白他們也在看上下文，但現在讓我們將其排除在外。

假設我想查看單詞overflw在字典中是否看起來像單詞，如果它在適當的位置添加了1個字母。我能看到被做的唯一方法是蠻力：檢查每個

aoverflw 
boverflw 
coverflw 
. 
. 
. 
overflnw 
overflow 
overflpw 
. 
. 
overflwy 
overflwz 

是詞典中的單詞。

有沒有更好的方法來做到這一點？

Answer 1

你正在從假設拼寫檢查器有一個字典，只能告訴你字典中是否存在一個單詞。但在大多數拼寫檢查器中，字典實現爲某種類型的trie，通常是directed acyclic word graph（DAWG）。這是一個更具多功能的數據結構，而不是具有查找功能的簡單字典。

實現方式各不相同，但從概念上講，您可以在字典中查看單詞的搜索，從單詞的第一個字符開始，並從DAWG的根目錄中獲取該節點。該節點包含所有以下字母的條目等。如果重複執行該操作，最終會出現以下其中一種可能性：

1. 您在樹中遇到葉節點，而您處於這個詞的結尾。如果這是真的，你知道這個詞在字典中存在。
2. 您會遇到一個葉節點，但在單詞中還剩下字母。想象一下，如果文檔中的單詞是「fatx」。您已到達樹中的葉節點「t」，但您的單詞中仍留有「x」。
3. 你到了詞的結尾，但你不在葉節點。例如，文檔中的單詞是「overfl」。
4. 您位於非葉節點上，遇到無法識別的字母。例如，這個詞是「overfdow」。你在樹中的'f'節點，並且字符'd'不在'f'後面的字母列表中。

在過去三年的情況下，你知道你在樹是什麼節點，你知道字母（和，對於這個問題，什麼話）可以產生。例如，你有「overflw」。樹中'l'節點表示'l'後面的可能字符是'e'（溢出），'o'（溢出，溢出等）和'y'（溢出）。如果您想對可能性進行詳盡搜索以提出建議，則不必嘗試字母表中的每個字母。所有你必須嘗試的是字典知道的字母「overfl」。在這種情況下不需要檢查'q'，因爲我們已經知道它不可能匹配。

其基本思想是字典數據結構（trie）包含搜索行爲。或者，另一方面，依賴於數據結構的代碼深入瞭解如何實現該特里結構。這使得更快地尋找建議，但我不會說這很容易。

您可以通過另一種方法來加速搜索，創建另一個具有相反順序的單詞。如果您想查找缺少前幾個字符的單詞的建議，這很有幫助。例如，如果有人輸入「elpful」，你會想要「有幫助」的建議。你可以搜索每個第一級節點，尋找「有用的」，「漂亮的」等等。但是反向DAWG將以'l'開始併產生「lufple」...然後看到'h'可以跟隨，並且建議「有用」。當一個單詞的第二個或第三個字母丟失時，這種類型的東西可能非常有用。

基本上，使用DAWG尋找後綴很容易。尋找前綴的計算成本很高。但是，如果您使用相同的單詞創建DAWG，只能向後搜索，則前綴搜索與後綴搜索一樣有效。