Trie最長的前綴匹配

Question

我沒有得到trie這個詞概念的結尾。我認爲我對自己的理解並不完整。有人可以請解釋在代碼HERE

// If this is end of a word, then update prevMatch 
       if(crawl.isEnd()) 
        prevMatch = level + 1; 

Answer 1

當代碼節節攀升線索尋找一個gifen字最長前綴，就會出現此以下的一段。

假設你有一個已經包含單詞的線索：

「的」 「一」 「曾經」

和您要搜索的「繁重」的最長前綴，你會期望在3（即「一」出來的是最長前綴已經存在

正在執行的代碼讀取：

// See if there is a Trie edge for the current character 
    if (child.containsKey(ch)) { 
     result += ch;   //Update result 
     crawl = child.get(ch); //Update crawl to move down in Trie 

     // If this is end of a word, then update prevMatch 
     if (crawl.isEnd()) { 
      prevMatch = level + 1; 
     } 
    } else { 
     break; 
    } 

所以想象你正在看「n」的「繁重」。你會發現「on」是作爲片段而不是end（因爲你沒有把單詞「on」放在句子中，但是在那裏單詞「one」是）。此代碼將繼續爬下樹，並顯示下一個字符「e」，但不會更改prevMatch。然而，在查看「e」時，樹和中存在匹配，因爲單詞「one」在樹中，所以該代碼存儲3在prevMatch中，因此它是end。

Answer 2

當單詞結束時，IsEnd killswitch被設置，但它不是句號或搜索的結尾。單詞被存儲在一個樹或散列表中。它可能發生搜索詞不是第一個或第二個殺戮開關。