在 Java 中使用 Trie 自动完成

Question

我正在完成这项实现自动完成和字典的作业。我已经成功地实现了拼写检查以及 addWord() 和 isWord() 函数。但是我就是无法实现为自动完成预测单词的功能。

package spelling;

import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;

/** 
 * An trie data structure that implements the Dictionary and the AutoComplete ADT
 * @author You
 *
 */
public class AutoCompleteDictionaryTrie implements  Dictionary, AutoComplete {
private TrieNode root;
private int size;


public AutoCompleteDictionaryTrie()
{
    root = new TrieNode();
    size=0;
}


/** Insert a word into the trie.
 * For the basic part of the assignment (part 2), you should ignore the word's case.
 * That is, you should convert the string to all lower case as you insert it. */
public boolean addWord(String word)
{
    //TODO: Implement this method.
    String Word=word.toLowerCase();
    if(isWord(Word))
        return false;
    HashMap<Character, TrieNode> children=root.children;
    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));
            children.put(c, t);
        }

        children = t.children;
        if(i==Word.length()-1)
        {
            t.isWord = true; 
            size++;
        }
    }
    return true;
}

/** 
 * Return the number of words in the dictionary.  This is NOT necessarily the same
 * as the number of TrieNodes in the trie.
 */
public int size()
{
    //TODO: Implement this method
    return size;
}


/** Returns whether the string is a word in the trie */
@Override
public boolean isWord(String s) 
{
    // TODO: Implement this method
    TrieNode t = searchNode(s.toLowerCase());

    if(t != null && t.isWord) 
        return true;
    else
        return false;
}
public TrieNode searchNode(String str){
    HashMap<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;
        }
    }

    return t;
}

/** 
 *  * Returns up to the n "best" predictions, including the word itself,
 * in terms of length
 * If this string is not in the trie, it returns null.
 * @param text The text to use at the word stem
 * @param n The maximum number of predictions desired.
 * @return A list containing the up to n best predictions
 */@Override
 public List<String> predictCompletions(String prefix, int numCompletions) 
 {
     // TODO: Implement this method
     // This method should implement the following algorithm:
     // 1. Find the stem in the trie.  If the stem does not appear in the trie, return an
     //    empty list
     // 2. Once the stem is found, perform a breadth first search to generate completions
     //    using the following algorithm:
     //    Create a queue (LinkedList) and add the node that completes the stem to the back
     //       of the list.
     //    Create a list of completions to return (initially empty)
     //    While the queue is not empty and you don't have enough completions:
     //       remove the first Node from the queue
     //       If it is a word, add it to the completions list
     //       Add all of its child nodes to the back of the queue
     // Return the list of completions
     List<String> completions=null;
     int counter=0;
     if (prefix==null){
         return Collections.emptyList();
     }

     prefix=prefix.toLowerCase();
     if(isWord(prefix))
         completions.add(prefix);
     LinkedList nodes = new LinkedList();

     TrieNode curr=searchNode(prefix);
     nodes.addLast(curr);
     while(!nodes.isEmpty() && counter!=numCompletions)
     {
         if((nodes.removeFirst()).isWord)
         completions.add(curr.getText());
         TrieNode next = null;
         for (Character c : curr.getValidNextCharacters()) {
                next = curr.getChild(c);
         }
     }


     return Collections.emptyList();

 }
 public void checkNull(String word){
    if (word==null)
        throw new NullPointerException("Null word passed");
 }
// For debugging
public void printTree()
{
    printNode(root);
}

/** Do a pre-order traversal from this node down */
public void printNode(TrieNode curr)
{
    if (curr == null) 
        return;

    System.out.println(curr.getText());

    TrieNode next = null;
    for (Character c : curr.getValidNextCharacters()) {
        next = curr.getChild(c);
        printNode(next);
    }
}



}

这是 TrieNode 的代码 class:

package spelling;

import java.util.HashMap;
import java.util.Set;

/** 
* Represents a node in a Trie
* @author UC San Diego Intermediate Programming MOOC Team
*
 */
class TrieNode {
HashMap<Character, TrieNode> children; 
private String text;  // Maybe omit for space
boolean isWord;

/** Create a new TrieNode */
public TrieNode()
{
    children = new HashMap<Character, TrieNode>();
    text = "";
    isWord = false;
}

/** Create a new TrieNode given a text String to store in it */
public TrieNode(String text)
{
    this();
    this.text = text;
}

/** Return the TrieNode that is the child when you follow the 
 * link from the given Character 
 * @param c The next character in the key
 * @return The TrieNode that character links to, or null if that link
 *   is not in the trie.
 */
public TrieNode getChild(Character c)
{
    return children.get(c);
}

/** Inserts this character at this node.
 * Returns the newly created node, if c wasn't already
 * in the trie.  If it was, it does not modify the trie
 * and returns null.
 * @param c The character that will link to the new node
 * @return The newly created TrieNode, or null if the node is already 
 *     in the trie.
 */
public TrieNode insert(Character c)
{
    if (children.containsKey(c)) {
        return null;
    }

    TrieNode next = new TrieNode(text + c.toString());
    children.put(c, next);
    return next;
}

/** Return the text string at this node */
public String getText()
{
    return text;
}

/** Set whether or not this node ends a word in the trie. */
public void setEndsWord(boolean b)
{
    isWord = b;
}

/** Return whether or not this node ends a word in the trie. */
public boolean endsWord()
{
    return isWord;
}

/** Return the set of characters that have links from this node */
public Set<Character> getValidNextCharacters()
{
    return children.keySet();
}

}

即使有算法，我也无法实现它。任何形式的帮助将不胜感激。

Answer 1

您是否正在尝试将此问题作为 Coursera 圣地亚哥大学课程的一部分来解决？如果是这样，那么您所要做的就是遵循 class 中作为注释编写的算法。不管怎样，我在这里添加了我对这个方法的实现的副本。请不要将其复制并粘贴为您的解决方案的一部分。用它作为指导。我在代码中添加了注释以帮助您理解我的算法：

     //Trying to find the stem in Trie
     String prefixToCheckLowerCase = prefix.toLowerCase();
     int completionsCount = 0;
     List<String> completions = new LinkedList<String>();
     TrieNode traversal = root;
     for (int i = 0; i < prefixToCheckLowerCase.length(); i++)
     {
         if (traversal.getValidNextCharacters().contains(prefixToCheckLowerCase.charAt(i)))
        {
            traversal = traversal.getChild(prefixToCheckLowerCase.charAt(i));
        } 
         //Means  stem not found, returns an empty list
         else
            return completions;
     }
     //If current word is an end word, increment the counter and add it to compeltions list
     if (traversal.endsWord()) 
     {
         completionsCount=1;
         completions.add(traversal.getText());
     }

     List<TrieNode> nodesToBeSearched = new LinkedList<TrieNode>();
     List<Character> ChildCharaterList = new LinkedList<Character>(traversal.getValidNextCharacters());
     //Filling the list with children of the current node, first level of of the breadth first search 
     for (int i=0; i<ChildCharaterList.size(); i++) 
     {
         nodesToBeSearched.add(traversal.getChild(ChildCharaterList.get(i)));
     }
     //while loop for the linked list elements and see if any compeltions exists , inside it we will also check each node children and add them to the list!!!
     while (nodesToBeSearched!=null  && nodesToBeSearched.size()>0 && completionsCount < numCompletions)
     {
         TrieNode trieNode = nodesToBeSearched.remove(0);
         if (trieNode.endsWord()) 
         {
             completionsCount++;
             completions.add(trieNode.getText());
         }

         List<Character> subTrieNodeCholdren = new LinkedList<Character>(trieNode.getValidNextCharacters());
         //Adding all next level tries to the linked list , kinda recursive!!!
         for (int i=0; i<subTrieNodeCholdren.size();i++) 
         {
             nodesToBeSearched.add(trieNode.getChild(subTrieNodeCholdren.get(i)));
         }
     }
     return completions;

Answer 2

import java.util.ArrayList;
class TrieNode{
    char data;
    boolean isTerminating;
    TrieNode children[];
    int childCount;

    public TrieNode(char data) {
        this.data = data;
        isTerminating = false;
        children = new TrieNode[26];
        childCount = 0;
    }
}

public class Trie {
    private TrieNode root;
    //ArrayList<String> ans=new ArrayList<>();

    public Trie() {
        root = new TrieNode('[=10=]');
    }

    private void add(TrieNode root, String word){
        if(word.length() == 0){
            root.isTerminating = true;
            return;
        }       
        int childIndex = word.charAt(0) - 'a';
        TrieNode child = root.children[childIndex];
        if(child == null){
            child = new TrieNode(word.charAt(0));
            root.children[childIndex] = child;
            root.childCount++;
        }
        add(child, word.substring(1));
    }

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

    private void searchHelper(TrieNode root,String word,String ans)
    {
      try
      {
      if(word.length()==0)
      {
        if(root.isTerminating == true)
        {
          System.out.println(ans);
        }
        for(int i=0;i<26;i++)
        {
          TrieNode temp=root.children[i];
          if(temp !=null)
          {
            //ans=ans+temp.data;
            //System.out.println("test check "+ans );
            searchHelper(temp,word,ans+temp.data);
          }
        }
      }
      int childIndex=word.charAt(0)-'a';
      TrieNode child=root.children[childIndex];
      if(child == null)
      {
        //System.out.print();
        return ;
      }
      ans=ans+word.charAt(0);
      searchHelper(child,word.substring(1),ans);

    }
      catch(Exception e)
      {
        //System.out.println("error");
      }
    }

    public void  search(String word)
    {
      String s="";
      searchHelper(root,word,s);
    }

    public void autoComplete(ArrayList<String> input, String word) {
        // Complete this function
        // Print the output as specified in question
        Trie ansTrie = new Trie();
        for(int i=0;i<input.size();i++)
        {
            ansTrie.add(input.get(i)); 
        }
        ansTrie.search(word);
    }
}

希望对您的疑惑有所帮助。对于任何缩进错误，我已经很抱歉了。

Answer 3

        import java.util.HashMap;
        import java.util.HashSet;
        import java.util.LinkedList;
        import java.util.List;
        import java.util.Map;
        import java.util.Queue;
        import java.util.Set;
        import java.util.stream.Collectors;
        
            public class TrieImpl {
        
            static class Element {
                private Trie trie;
                private String word;
        
                Element(Trie trie, String word) {
                    this.trie = trie;
                    this.word = word;
                }
            }
        
            static class Trie {
                private boolean isLeaf;
                private Map<Character, Trie> children;
                private Map<Character, Integer> character;
        
                Trie() {
                    isLeaf = false;
                    children = new HashMap<>();
                    character = new HashMap<>();
                }
        
                public void insert(String word) {
                    Trie curr = this;
                    for (Character ch : word.toCharArray()) {
                        curr.children.putIfAbsent(ch, new Trie());
                        int count = (curr.character.get(ch) == null) ? 1 : curr.character.get(ch) + 1;
                        curr.character.put(ch, count);
                        curr = curr.children.get(ch);
                    }
                    curr.isLeaf = true;
                }
        
                public boolean search(String word) {
                    Trie curr = this;
                    for (Character ch : word.toCharArray()) {
                        if (curr.children.get(ch) == null)
                            return false;
                        curr = curr.children.get(ch);
                    }
                    return curr.isLeaf;
                }
        
                public void delete(String word) {
                    if (search(word)) {
                        Trie lastSecond = this;
                        Character charToRemove = word.charAt(0);
                        Trie curr = this;
                        int i = -1;
                        while (i < word.length() && curr != null) {
                            if (curr.isLeaf && i != word.length() - 1) {
                                charToRemove = word.charAt(i + 1);
                                lastSecond = curr;
                            }
                            i = i + 1;
                            if (i < word.length())
                                curr = curr.children.get(word.charAt(i));
                        }
                        lastSecond.children.remove(charToRemove);
                    }
                }
        
                public int findPrefixCount(String word) {
                    Trie curr = this;
                    Character lastChar = null;
                    int count = 0;
                    for (Character ch : word.toCharArray()) {
                        if (curr.children.get(ch) == null)
                            return 0;
                        if (count < word.length() - 1) {
                            curr = curr.children.get(ch);
                            count++;
                        }
                        lastChar = ch;
                    }
                    if (lastChar != null && curr.character.get(lastChar) != null)
                        return curr.character.get(lastChar);
                    else
                        return 0;
                }
        
                public Set<String> autoComplete(String word) {
                    Trie curr = this;
                    int count = 0;
                    String wo = "";
                    Queue<Element> queue = new LinkedList<>();
                    Set<String> set = new HashSet<>();
                    for (Character ch : word.toCharArray()) {
                        if (count < word.length()) {
                            curr = curr.children.get(ch);
                            count++;
                            wo += ch;
                        }
                    }
                    if (curr != null)
                        queue.add(new Element(curr, wo));
        
                    while (!queue.isEmpty()) {
                        Element elem = queue.poll();
                        Trie current = elem.trie;
                        String temp = elem.word;
                        if (current != null && current.isLeaf)
                            set.add(temp);
                        List<Character> keys = current.character.keySet().stream().collect(Collectors.toList());
                        for (int i = 0; i < current.children.size(); i++) {
                            queue.add(new Element(current.children.get(keys.get(i)), temp + keys.get(i)));
                        }
        
                    }
                    return set;
        
                }
                    }
        
                public static void main(String[] args) {
                Trie head = new Trie();
                head.insert("techie");
                head.insert("techi");
                head.insert("tech");
                head.insert("tecabc");
                head.insert("tecabk");
                head.insert("tecabd");
                head.insert("tecalmz");
                Set<String> words = head.autoComplete("t");
                words.stream().forEach(x -> System.out.println(x));
        
            }
        
        }

在 Java 中使用 Trie 自动完成

AutoComplete using a Trie in Java

java

autocomplete

trie

breadth-first-search