从Trie获取单词列表

本文介绍了从Trie获取单词列表的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在寻找使用以下代码来检查Trie中是否不存在单词匹配，而是返回一个列表，列出所有以用户输入的前缀开头的单词.有人可以指出我正确的方向吗?我根本无法正常工作.....

I'm looking to use the following code to not check whether there is a word matching in the Trie but to return a list all words beginning with the prefix inputted by the user. Can someone point me in the right direction? I can't get it working at all.....

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

推荐答案

我在尝试制作文本自动完成模块时遇到了此问题.我通过制作一个Trie(每个节点包含其父节点和子节点)解决了这个问题.首先，我搜索了从输入前缀开始的节点.然后，我在Trie上应用了遍历，以其根作为前缀节点来探索子树的所有节点.每当遇到叶节点时，都意味着已找到从输入前缀开始的单词结尾.从该叶节点开始，我遍历父节点成为父节点的父节点，并到达子树的根.在这样做的同时，我一直在堆栈中添加节点的键.最后，我拿了前缀并开始通过弹出堆栈来附加它.我一直将单词保存在ArrayList中.在遍历结束时，我得到了所有从输入前缀开始的单词.这是带有用法示例的代码:

I faced this problem while trying to make a text auto-complete module. I solved the problem by making a Trie in which each node contains it's parent node as well as children. First I searched for the node starting at the input prefix. Then I applied a Traversal on the Trie that explores all the nodes of the sub-tree with it's root as the prefix node. whenever a leaf node is encountered, it means that the end of a word starting from input prefix has been found. Starting from that leaf node I iterate through the parent nodes getting parent of parent, and reach the root of the subtree. While doing so I kept adding the keys of nodes in a stack. In the end I took the prefix and started appended it by popping the stack. I kept on saving the words in an ArrayList. At the end of the traversal I get all the words starting from the input prefix. Here is the code with usage example:

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