拼寫檢查器：三元搜索樹

Question

我已經使用三元搜索樹進行了拼寫檢查代碼。任何人都可以告訴我如何在TST中找到下一個可能的單詞。 例如，如果我想搜索如果我在拼寫檢查器中搜索單詞「Manly」並且該單詞不存在於TST中，則其輸出如 您的意思是： 「Man」 「Mango」 。 .means可能接近單詞

Answer 1

搜索TST中的單詞將終止在樹中的特定位置。從這一點上，你可以簡單地上升到樹中的一個層次，直到你達到不僅僅是你來自的孩子的水平。

在該級別上，您可以簡單地選擇其他可能的路徑並返回這些單詞。

Answer 2

我已經實現了自己的拼寫檢查程序，但是我使用的是三元dag，而不是簡單的三元樹，因爲Peter Kankowski建議here。你可以看看我的blog的一些細節，以及我是如何做到的。它在希臘文，但你可以得到一個想法。

編輯：

好吧，你是對的。 基本的想法是使用給定編輯距離的預先創建的候選列表（對於我來說值爲2是可以的）。爲了減少列表的大小，可以使用通配符。 這樣的列表當然可以用不同的方式構建。我更喜歡/ while循環是這樣的（例如，用於兩個換人的人選）

void Substitute2(vector<wchar_t*>& v, const wstring& w) 
{ 
    size_t len = w.size(); 
    if (len < 2) 
     return; 
    size_t p1 = 0, p2 = 1; 
    while (p1 < len) { 
     p2 = p1 + 1; 
     while (p2 < len) { 
      wchar_t* chars = new wchar_t[ len + 1 ]; 
      for (size_t i = 0; i < len; ++i) { 
       if (i != p1 && i != p2) { 
        chars[ i ] = w[ i ]; 
       } 
      } 
      chars[ p1 ] = '?'; 
      chars[ p2 ] = '?'; 
      chars[ len ] = '\0'; 
      v.push_back(chars); 
      p2++; 
     } 
     p1++; 
    } 
} 

已經準備的候選人名單，在三元DAG簡單的搜索列表中的每個項目將給予我們的建議後拼寫錯誤的單詞。

void Search(FileNode* pDict, FileNode* pNode, const wchar_t* Word, wstring Sug, set<wstring>& List) 
{ 
    if (IsNullLink(pNode, pDict)) 
     return; 
    if (*Word == '?') { 
     Search(pDict, GetLo(pNode, pDict), Word, Sug, List); 
     Search(pDict, GetEq(pNode, pDict), Word + 1, Sug + pNode->Char, List); 
     Search(pDict, GetHi(pNode, pDict), Word, Sug, List); 
    } else { 
     if (*Word < pNode->Char) { 
      Search(pDict, GetLo(pNode, pDict), Word, Sug, List); 
     } else if (*Word > pNode->Char) { 
      Search(pDict, GetHi(pNode, pDict), Word, Sug, List); 
     } else { 
      if (pNode->Char == '\0') 
      { 
       List.insert(Sug); 
      } 
      if (*Word != '\0') { 
       Search(pDict, GetEq(pNode, pDict), Word + 1, Sug + pNode->Char, List); 
      } 
     } 
    } 
} 

注：字典是一個編譯（基於文件）三元DAG