從Trie獲取單詞列表

Question

我正在尋找使用以下代碼來檢查Trie中是否存在匹配的單詞，但要返回列表中以用戶輸入的前綴開頭的所有單詞。有人能指引我朝着正確的方向嗎？我不能讓它在所有的工作.....

public boolean search(String s) 
{ 
    Node current = root; 
    System.out.println("\nSearching for string: "+s); 

    while(current != null) 
    { 
     for(int i=0;i<s.length();i++) 
     {    
      if(current.child[(int)(s.charAt(i)-'a')] == null) 
      { 
       System.out.println("Cannot find string: "+s); 
       return false; 
      } 
      else 
      { 
       current = current.child[(int)(s.charAt(i)-'a')]; 
       System.out.println("Found character: "+ current.content); 
      } 
     } 
     // If we are here, the string exists. 
     // But to ensure unwanted substrings are not found: 

     if (current.marker == true) 
     { 
      System.out.println("Found string: "+s); 
      return true; 
     } 
     else 
     { 
      System.out.println("Cannot find string: "+s +"(only present as a substring)"); 
      return false; 
     } 
    } 

    return false; 
} 

} 

Answer 1

你需要使用一個列表
List<String> myList = new ArrayList<String>();
if(matchingStringFound)
myList.add(stringToAdd);

Answer 2

最簡單的解決方法是使用一個depth-first search。

你走下來，從輸入匹配字母。然後，一旦你沒有更多的字母匹配，該節點下的所有字符都是你想要的字符串。遞歸地探索整個子節點，並在下降到節點時構建字符串。

Answer 3

在我看來，這更容易遞歸解決。它會去是這樣的：

1. 寫遞歸函數Print，打印所有節點植根於你給作爲參數的節點線索。 Wiki告訴你如何做到這一點（看看排序）。
2. 找到您的前綴的最後一個字符，以及用字符標記的節點，從您的trie的根節點開始。使用此節點作爲參數調用Print函數。然後，只要確保在每個單詞前都輸出前綴，因爲這會爲您提供所有沒有前綴的單詞。

如果你真的不關心效率，你可以只運行Print與主根節點，只打印那些你感興趣的前綴開頭的話。這是比較容易實現，但速度較慢。

Answer 4

您需要遍歷從您找到的前綴節點開始的子樹。

以相同的方式開始，即找到正確的節點。然後，不是檢查它的標記，而是遍歷該樹（即遍歷其所有後代;一個DFS是一個好辦法），保存用於從第一個節點到達「當前」節點的子字符串。

如果當前節點被標記爲單詞，則輸出*前綴+子串達到。

*或將其添加到列表或其他東西。

Answer 5

在for循環之後，添加對printAllStringsInTrie（current，s）的調用;

void printAllStringsInTrie(Node t, String prefix) { 
    if (t.current_marker) System.out.println(prefix); 
    for (int i = 0; i < t.child.length; i++) { 
    if (t.child[i] != null) { 
     printAllStringsInTrie(t.child[i], prefix + ('a' + i)); // does + work on (String, char)? 
    } 
    } 
} 

Answer 6

我建立了一個特里曾經爲ITA一個拼圖

公共類WordTree {

class Node { 

    private final char ch; 

    /** 
    * Flag indicates that this node is the end of the string. 
    */ 
    private boolean end; 

    private LinkedList<Node> children; 

    public Node(char ch) { 
     this.ch = ch; 
    } 

    public void addChild(Node node) { 
     if (children == null) { 
      children = new LinkedList<Node>(); 
     } 
     children.add(node); 
    } 

    public Node getNode(char ch) { 
     if (children == null) { 
      return null; 
     } 
     for (Node child : children) { 
      if (child.getChar() == ch) { 
       return child; 
      } 
     } 
     return null; 
    } 

    public char getChar() { 
     return ch; 
    } 

    public List<Node> getChildren() { 
     if (this.children == null) { 
      return Collections.emptyList(); 
     } 
     return children; 
    } 

    public boolean isEnd() { 
     return end; 
    } 

    public void setEnd(boolean end) { 
     this.end = end; 
    } 
} 


Node root = new Node(' '); 

public WordTree() { 
} 

/** 
* Searches for a strings that match the prefix. 
* 
* @param prefix - prefix 
* @return - list of strings that match the prefix, or empty list of no matches are found. 
*/ 
public List<String> getWordsForPrefix(String prefix) { 
    if (prefix.length() == 0) { 
     return Collections.emptyList(); 
    } 
    Node node = getNodeForPrefix(root, prefix); 
    if (node == null) { 
     return Collections.emptyList(); 
    } 
    List<LinkedList<Character>> chars = collectChars(node); 
    List<String> words = new ArrayList<String>(chars.size()); 
    for (LinkedList<Character> charList : chars) { 
     words.add(combine(prefix.substring(0, prefix.length() - 1), charList)); 
    } 
    return words; 
} 


private String combine(String prefix, List<Character> charList) { 
    StringBuilder sb = new StringBuilder(prefix); 
    for (Character character : charList) { 
     sb.append(character); 
    } 
    return sb.toString(); 
} 


private Node getNodeForPrefix(Node node, String prefix) { 
    if (prefix.length() == 0) { 
     return node; 
    } 
    Node next = node.getNode(prefix.charAt(0)); 
    if (next == null) { 
     return null; 
    } 
    return getNodeForPrefix(next, prefix.substring(1, prefix.length())); 
} 


private List<LinkedList<Character>> collectChars(Node node) { 
    List<LinkedList<Character>> chars = new ArrayList<LinkedList<Character>>(); 

    if (node.getChildren().size() == 0) { 
     chars.add(new LinkedList<Character>(Collections.singletonList(node.getChar()))); 
    } else { 
     if (node.isEnd()) { 
      chars.add(new LinkedList<Character>(Collections.singletonList(node.getChar()))); 
     } 
     List<Node> children = node.getChildren(); 
     for (Node child : children) { 
      List<LinkedList<Character>> childList = collectChars(child); 
      for (LinkedList<Character> characters : childList) { 
       characters.push(node.getChar()); 
       chars.add(characters); 
      } 
     } 
    } 
    return chars; 
} 


public void addWord(String word) { 
    addWord(root, word); 
} 

private void addWord(Node parent, String word) { 
    if (word.trim().length() == 0) { 
     return; 
    } 
    Node child = parent.getNode(word.charAt(0)); 
    if (child == null) { 
     child = new Node(word.charAt(0)); 
     parent.addChild(child); 
    } 
    if (word.length() == 1) { 
     child.setEnd(true); 
    } else { 
     addWord(child, word.substring(1, word.length())); 
    } 
} 


public static void main(String[] args) { 
    WordTree tree = new WordTree(); 
    tree.addWord("world"); 
    tree.addWord("work"); 
    tree.addWord("wolf"); 
    tree.addWord("life"); 
    tree.addWord("love"); 
    System.out.println(tree.getWordsForPrefix("wo")); 
} 

}

Answer 7

這裏是C++

https://github.com/dchavezlive/Basic-Trie

實現

在您的搜索功能中，您可以讓它返回前綴結束位置的節點。如果你確定你的節點有一個字段來保存每個孩子（向量？），那麼你可以列出你的前綴結束的那個節點的所有孩子。

Answer 8

我在嘗試製作文本自動完成模塊時遇到此問題。我通過創建一個Trie來解決這個問題，其中每個節點都包含它的父節點以及子節點。首先，我搜索從輸入前綴開始的節點。然後我在Trie上應用遍歷，探索子樹的所有節點，並將其根作爲前綴節點。每遇到葉節點，就意味着已經找到從輸入前綴開始的單詞的結尾。從該葉節點開始，迭代父節點的父節點，併到達子樹的根。在這樣做的時候，我一直在堆棧中添加節點的密鑰。最後我拿到了前綴，並通過彈出堆棧開始附加它。我一直保存在一個ArrayList中的單詞。在遍歷結束時，我得到從輸入前綴開始的所有單詞。下面是使用示例代碼：

class TrieNode 
{ 
    char c; 
    TrieNode parent; 
    HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>(); 
    boolean isLeaf; 

    public TrieNode() {} 
    public TrieNode(char c){this.c = c;} 
} 

-

public class Trie 
{ 
    private TrieNode root; 
    ArrayList<String> words; 
    TrieNode prefixRoot; 
    String curPrefix; 

    public Trie() 
    { 
     root = new TrieNode(); 
     words = new ArrayList<String>(); 
    } 

    // Inserts a word into the trie. 
    public void insert(String word) 
    { 
     HashMap<Character, TrieNode> children = root.children; 

     TrieNode crntparent; 

     crntparent = root; 

     //cur children parent = root 

     for(int i=0; i<word.length(); i++) 
     { 
      char c = word.charAt(i); 

      TrieNode t; 
      if(children.containsKey(c)){ t = children.get(c);} 
      else 
      { 
      t = new TrieNode(c); 
      t.parent = crntparent; 
      children.put(c, t); 
      } 

      children = t.children; 
      crntparent = t; 

      //set leaf node 
      if(i==word.length()-1) 
       t.isLeaf = true;  
     } 
    } 

    // Returns if the word is in the trie. 
    public boolean search(String word) 
    { 
     TrieNode t = searchNode(word); 
     if(t != null && t.isLeaf){return true;} 
     else{return false;} 
    } 

    // Returns if there is any word in the trie 
    // that starts with the given prefix. 
    public boolean startsWith(String prefix) 
    { 
     if(searchNode(prefix) == null) {return false;} 
     else{return true;} 
    } 

    public TrieNode searchNode(String str) 
    { 
     Map<Character, TrieNode> children = root.children; 
     TrieNode t = null; 
     for(int i=0; i<str.length(); i++) 
     { 
      char c = str.charAt(i); 
      if(children.containsKey(c)) 
      { 
       t = children.get(c); 
       children = t.children; 
      } 
      else{return null;} 
     } 

     prefixRoot = t; 
     curPrefix = str; 
     words.clear(); 
     return t; 
    } 


    /////////////////////////// 


    void wordsFinderTraversal(TrieNode node, int offset) 
    { 
     // print(node, offset); 

     if(node.isLeaf==true) 
     { 
      //println("leaf node found"); 

      TrieNode altair; 
      altair = node; 

      Stack<String> hstack = new Stack<String>(); 

      while(altair != prefixRoot) 
      { 
      //println(altair.c); 
      hstack.push(Character.toString(altair.c)); 
      altair = altair.parent; 
      } 

      String wrd = curPrefix; 

      while(hstack.empty()==false) 
      { 
      wrd = wrd + hstack.pop(); 
      } 

      //println(wrd); 
      words.add(wrd); 

     } 

     Set<Character> kset = node.children.keySet(); 
     //println(node.c); println(node.isLeaf);println(kset); 
     Iterator itr = kset.iterator(); 
     ArrayList<Character> aloc = new ArrayList<Character>(); 

     while(itr.hasNext()) 
     { 
     Character ch = (Character)itr.next(); 
     aloc.add(ch); 
     //println(ch); 
     } 

    // here you can play with the order of the children 

     for(int i=0;i<aloc.size();i++) 
     { 
     wordsFinderTraversal(node.children.get(aloc.get(i)), offset + 2); 
     } 

    } 


void displayFoundWords() 
{ 
    println("_______________"); 
    for(int i=0;i<words.size();i++) 
    { 
    println(words.get(i)); 
    } 
    println("________________"); 

} 



}// 

例

Trie prefixTree; 

prefixTree = new Trie(); 

    prefixTree.insert("GOING"); 
    prefixTree.insert("GONG"); 
    prefixTree.insert("PAKISTAN"); 
    prefixTree.insert("SHANGHAI"); 
    prefixTree.insert("GONDAL"); 
    prefixTree.insert("GODAY"); 
    prefixTree.insert("GODZILLA"); 

    if(prefixTree.startsWith("GO")==true) 
    { 
    TrieNode tn = prefixTree.searchNode("GO"); 
    prefixTree.wordsFinderTraversal(tn,0); 
    prefixTree.displayFoundWords(); 

    } 

    if(prefixTree.startsWith("GOD")==true) 
    { 
    TrieNode tn = prefixTree.searchNode("GOD"); 
    prefixTree.wordsFinderTraversal(tn,0); 
    prefixTree.displayFoundWords(); 

    } 

Answer 9

建設特里之後，你可以做DFS從節點，您在哪裏找到的前綴開始：

Here Node is Trie node, word=till now found word, res = list of words 

def dfs(self, node, word, res): 
    # Base condition: when at leaf node, add current word into our list 
    if EndofWord at node: 
     res.append(word) 
     return 
    # For each level, go deep down, but DFS fashion 
    # add current char into our current word. 
    for w in node: 
     self.dfs(node[w], word + w, res) 

Answer 10

The bel ow遞歸代碼可用於你的TrieNode是這樣的： 這段代碼工作正常。

TrieNode(char c) 
{ 

     this.con=c; 
     this.isEnd=false; 
     list=new ArrayList<TrieNode>(); 
     count=0; 

} 

//-------------------------------------------------- 

public void Print(TrieNode root1, ArrayList<Character> path) 
{ 

     if(root1==null) 
      return; 

     if(root1.isEnd==true) 
     { 
      //print the entire path 
      ListIterator<Character> itr1=path.listIterator(); 
      while(itr1.hasNext()) 
      { 
       System.out.print(itr1.next()); 
      } 
      System.out.println(); 
      return; 
     } 
     else{ 
      ListIterator<TrieNode> itr=root1.list.listIterator(); 
      while(itr.hasNext()) 
      { 
       TrieNode child=itr.next(); 
       path.add(child.con); 
       Print(child,path); 
       path.remove(path.size()-1); 

      } 
     }