Obtenir une liste de mots d'un Trie

Question

Je cherche à utiliser le code suivant pour ne pas vérifier s'il y a un mot correspondant dans le Trie mais pour retourner une liste de tous les mots commençant par le préfixe entré par l'utilisateur. Quelqu'un peut me diriger dans la bonne direction? Je ne peux pas le faire fonctionner du tout .....

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

Vous devez utiliser une liste
List<String> myList = new ArrayList<String>();
if(matchingStringFound)
myList.add(stringToAdd);

Answer 2

Le est d'utiliser une depth-first search solution la plus simple.

Vous descendez le trie, correspondant lettre par lettre de l'entrée. Ensuite, une fois que vous n'avez plus de lettre à faire correspondre, tout sous ce nœud sont des chaînes que vous voulez. Explorons récursivement toute cette sous-chaîne, en construisant la chaîne à mesure que vous descendez dans ses nœuds.

Answer 3

Ceci est plus facile à résoudre récursivement à mon avis. Il serait quelque chose comme ceci:

1. Ecrire une fonction récursive Print qui imprime tous les nœuds du Trie enraciné dans le nœud que vous donnez comme paramètre. Wiki vous explique comment procéder (regardez le tri).
2. Trouvez le dernier caractère de votre préfixe, et le nœud qui est étiqueté avec le caractère, descendant de la racine dans votre trie. Appelez la fonction Print avec ce noeud en tant que paramètre. Ensuite, assurez-vous que vous avez également sorti le préfixe avant chaque mot, car cela vous donnera tous les mots sans leur préfixe.

Si vous n'êtes pas vraiment à l'efficacité, vous pouvez simplement exécuter Print avec le principal nœud racine et seulement imprimer ces mots qui commencent par le préfixe qui vous intéresse. Cela est plus facile à mettre en œuvre, mais plus lentement.

Answer 4

Vous devez traverser le sous-arbre en commençant par le noeud que vous avez trouvé pour le préfixe. Commencez de la même manière, c'est-à-dire trouvez le bon noeud. Ensuite, au lieu de vérifier son marqueur, traversez cet arbre (c'est-à-dire parcourez tous ses descendants, un DFS est un bon moyen de le faire), en sauvegardant la sous-chaîne utilisée pour atteindre le nœud "courant" du premier nœud.

Si le nœud actuel est marqué comme un mot, entrez * le préfixe + sous-chaîne atteint.

* ou l'ajouter à une liste ou à quelque chose.

Answer 5

Après votre boucle for, ajoutez un appel à 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

J'ai construit une structure arborescente une fois pour l'un des ITA les puzzles

public class 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

Voici une implémentation en C++

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

Dans votre fonction de recherche, vous pouvez lui demander de renvoyer le noeud où se termine le préfixe.Si vous vous assurez que votre nœud dispose d'un champ pour enregistrer chaque enfant (vecteur?), Vous pouvez lister tous les enfants de ce nœud où se termine votre préfixe.

Answer 8

J'ai fait face à ce problème en essayant de créer un module de remplissage automatique de texte. J'ai résolu le problème en créant un Trie dans lequel chaque nœud contient son nœud parent ainsi que les enfants. J'ai d'abord cherché le nœud à partir du préfixe d'entrée. Puis j'ai appliqué un Traversal sur le Trie qui explore tous les nœuds du sous-arbre avec sa racine comme nœud de préfixe. chaque fois qu'un nœud feuille est rencontré, cela signifie que la fin d'un mot à partir du préfixe d'entrée a été trouvée. En partant de ce nœud feuille, je parcours les nœuds parents obtenant le parent du parent, et atteins la racine du sous-arbre. Ce faisant, j'ai continué à ajouter les clés des noeuds dans une pile. À la fin j'ai pris le préfixe et j'ai commencé à l'ajouter en faisant sauter la pile. J'ai continué à enregistrer les mots dans une ArrayList. À la fin de la traversée, j'obtiens tous les mots à partir du préfixe d'entrée. Voici le code avec un exemple d'utilisation:

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("________________"); 

} 



}// 

Exemple

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

Après la construction de Trie, vous pouvez le faire DFS à partir du nœud, où vous avez trouvé le préfixe:

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

Le bel Le code récursif peut être utilisé lorsque votre TrieNode est comme ceci: Ce code fonctionne bien.

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); 

      } 
     }