通配符值的Trie實現

我正在實現一個算法來執行目錄匹配。所以我給了一組有效的路徑，可以包含通配符（用「X」表示）。然後，當我傳入一個輸入時，我需要知道該輸入是否與我有效集合中的某個路徑匹配。當傳入的通配符值與另一個有效值匹配時，我遇到了通配符問題。下面是一個例子：通配符值的Trie實現

集的有效路徑：

/guest 
/guest/X 
/X/guest 
/member 
/member/friends 
/member/X 
/member/X/friends

示例輸入：

/member/garbage/friends  
/member/friends/friends

這些都應該返回true，但是隻有第一個一樣。在第一種情況下，因爲「垃圾」與其他可能的路徑不匹配，但此時有一個通配符選項，它將跳過它並繼續前進，然後它看到「朋友」，並知道它是匹配的。然而，我的第二種情況是行不通的，因爲它會看到朋友，在我的行爲中走向另一條路，而不是通配符路徑。因爲在這個位置有一個有「朋友」的有效路徑，它認爲它就是這樣。然後再次看到「朋友」，但從這一點來看，沒有「朋友」的有效路徑，所以它返回false。

我的問題是，我怎麼才能讓它識別其他有效的路徑，即使它在樹中錯誤的分支。我的搜索代碼和示例trie圖如下。

我的字典樹的搜索算法如下：

private TrieNode searchNode(String input) { 
    Map<String, TrieNode> children = root.children; 
    TrieNode t = null; 

    // break up input into individual tokens 
    String[] tokenizedLine = input.split("/"); 
    for(int i = 0; i < tokenizedLine.length; i++){ 
     String current = tokenizedLine[i]; 

     if(children.containsKey(current)) { 
      t = children.get(current); 
      children = t.children; 
     }else if(children.containsKey("X")){ 
      t = children.get("X"); 
      children = t.children; 
     }else{ 
      return null; 
     } 
    } 

    return t; 
}

，將與我的樣本路徑設置建立特里樹的形象：當我輸入/成員/朋友/朋友我的算法會沿着突出顯示的路徑前進，並停下來，因爲它之後沒有看到其他「朋友」，但我怎麼才能讓它將第一個「朋友」識別爲通配符值，然後繼續看到第二個「朋友」通配符之後？

感謝您的幫助！

來源

2017-07-24 zulusam

想通了。我實施了一些回溯跟蹤最後一個節點，看到兩條可能的路徑。如果它在一條路徑上發現死路，它將返回到最後一次看到兩條可能的路徑並嘗試另一條路徑。新算法如下所示：

private TrieNode searchNode(String input) { 
     Map<String, TrieNode> children = root.children; 
     TrieNode t = null; 

     // Variables for backtrack function 
     TrieNode alternativeWildcardNode = null; 
     int wildcardIndex = 0; 
     Map<String, TrieNode> wildcardChildren = root.children; 

     // break up input into individual tokens 
     String[] tokenizedLine = input.split("/"); 
     for(int i = 0; i < tokenizedLine.length; i++){ 
      String current = tokenizedLine[i]; 

      //System.out.println(current); 
      //System.out.println(Integer.toString(i)); 

      if(children.containsKey(current) && children.containsKey("X")) { 
       // store current variable state in case we need to back track here 
       alternativeWildcardNode = children.get("X"); 
       wildcardIndex = i; 
       wildcardChildren = alternativeWildcardNode.children; 

       t = children.get(current); 
       children = t.children; 
      }else if(children.containsKey(current)) { 
       t = children.get(current); 
       children = t.children; 
      }else if(children.containsKey("X")){ 
       t = children.get("X"); 
       children = t.children; 
      }else if(alternativeWildcardNode != null){ 
       // if we've reached a branch with no match, but had a possible wildcard previously 
       // call reset state to the wildcard option instead of static 
       t = alternativeWildcardNode; 
       alternativeWildcardNode = null; 
       i = wildcardIndex; 
       children = wildcardChildren; 
      }else{ 
       return null; 
      } 
     } 

     return t; 
    }

來源

2017-07-24 03:00:19 zulusam

通配符值的Trie實現

回答

相關問題