自动建议的前缀树

Question

我编写了一个快速前缀树实现。我知道这可能并不完美，但我需要确保我的基本知识是正确的。

我的主要关切是：

1. 我找到正确的数据结构了吗？
2. 这是一个可伸缩的解决方案吗？如果这是一棵大树，我会遇到什么样的问题？

public class PrefixTree {
//isLeaf would point out the end of a word in the tree
boolean isLeaf;
HashMap<Character, PrefixTree> map;

public PrefixTree() {
    map=new HashMap<Character, PrefixTree>();
    isLeaf=false;
}

//insert a new word into the tree
public void put(String s) {
    if(s.length()==0) {
        //if the word ends here, we need to point it out using the isLeaf
        //boolean field, and the insertion job is done, so return
        isLeaf=true;
        return;
    }
    //if the first character of the string doesn't exits
    //we create a new node for the and insert it into the map
    if(!map.containsKey(s.charAt(0))) {
        map.put(s.charAt(0), new PrefixTree());
    }
    //now this newly create node or if it already existed
    //would contain the rest of the substring
    map.get(s.charAt(0)).put(s.substring(1));
}

//tree travelsal to examine the contents of the tree
public void travelTree(String perm) {
    if(isLeaf) {
        System.out.println(perm);
    }
    if(map.size()==0) return;
    for(Character c:map.keySet()) {
        map.get(c).travelTree(perm+c);
    }
}

//this overloaded function is used as a helper function with the getSuggestions
//functions
//doesn't need to be called on from the root
public void travelTree(String perm, List<String> sl) {
    if(isLeaf) {
        sl.add(perm);
    }
    if(map.size()==0) return;
    for(Character c:map.keySet()) {
        map.get(c).travelTree(perm+c, sl);
    }
}    

public List<String> getSuggestions(String q) {
    //I am passing along this List object into the nested recursive calls 
    //from here onwards, is this a better approach than having every 
    //recursive function call create an arraylist object and append the 
    //return items and finally return the final list
    List<String> suggestions=new ArrayList<String>();
    getSuggestions(q, "", suggestions);
    return suggestions;
}

public void getSuggestions(String q, String perm, List<String> sl) {
    if(q.length()==0) {            
        travelTree(perm, sl);
        //we don't return as we need to go into further depth for more
        //suggestions
    }
    if(map.size()==0) return;
    if(q.length()>0 && map.containsKey(q.charAt(0))) {
        //make sure we call getSuggestions on specific node instead of
        //current instance's getSuggestions
        map.get(q.charAt(0)).getSuggestions(q.substring(1), perm+q.charAt(0), sl);
    }
}
}

Answer 1

总的来说，看起来您已经在那里创建了一段干净而简单的代码。我还有一些建议要给你：

Nitpicks:

• 你的压痕需要重新考虑一下。按照惯例，大括号中的所有内容都由一个级别(4空格/1选项卡)缩进。您的类主体没有缩进“正确”
• 您的前缀树可以使用一些急切的初始化。如果只声明字段(应该是私有的，顺便说一句)，那么构造函数是完全多余的。类似于以下内容:公共类PrefixTree { // isLeaf ...专用布尔值isLeaf = false；私有Map map =新HashMap<>()；此外，我还将映射类型更改为map (它是一个接口)，而不是HashMap。这样做的好处是:您可以随时更改地图实现。

评论：

你的评论是全面明确和简单的。他们解释了为什么和什么，虽然，这是不可取的评论海事组织。代码中的注释应该解释做出某些决定的原因。代码应该足够清晰，原因是显而易见的。

此外，注释中还有大量拼写错误。这意味着额外的心理压力，因为读者必须从句子上下文中破译实际的单词。

此外，我看到您的许多方法都是对它们所做的进行注释的。为此，您绝对应该使用javadoc。它允许您以程序员都可读并易于被IDE使用的方式记录方法(及其用途)：

/**
 * Insert a new word into the tree
 * 
 * @param s The word to be inserted
 */
public void put(String s) {

范围界定：

正如在前面的吹毛求疵中所提到的:您的字段应该是私有的。我甚至要说地图也应该是最终的。

此外，您还向公众公开了一个助手函数(travelTree)。海事组织这种方法绝对应该是保密的。

您的关注点：

1. 你接受正确的数据结构了吗？，在我看来，这个看起来是肯定的。很好地选择一张地图来表示每个树节点的字符选择。但是，我有一个很大的问题，就是你假设要与树一起使用的类型，即String。虽然字符串是“通用的”，但我更希望看到您使用CharSequence，它是字符串的超类。它还公开了.length()和.charAt()方法。只有您对.substring()的调用才需要更改为.subsequence(1, len - 1)
2. 这是一个可伸缩的解决方案吗？如果这是一棵大树，我会遇到什么样的问题？，嗯，这相当简单。这个解决方案是相当可伸缩的，主要是因为您对正在使用的内存非常有效，而且遍历树主要是遵循HashMap中的指针。但是，对于大型树来说，您必须期望的是非常大的内存消耗(并不奇怪)和增加遍历时间。目前，您无法通过带有“长”字(如“木琴”)的单独分支进行短途遍历。这意味着您可能在遍历过程中“浪费”了一些时间。

Summa Summarum:

代码是干净的和相对简单的。各地都有轻微的违反java惯例的情况，注释有太多的拼写错误，但是您对数据结构的选择是一个很好的选择。

总的来说:做得不错，但你可以做得更好;)