前缀树问题

Question

我需要处理近130万个单词(有些单词组是相似的)。我正在做一些类似于小词汇表的事情，其中每个单词都有自己的描述。需要通过词汇表进行快速搜索。所以我决定使用前缀树。首先需要建立偏好树(这是一个很慢的过程，我知道)，在快速浏览词汇表之后，可能会组织起来。

但我的问题是-偏好树的构建速度非常慢(前300,000个单词构建得很快，但尾部的构建非常非常慢，以至于我都等不及构建树了！！)。

下面是我的前缀树类：

public class InverseVocabularyTree implements Serializable 
{
    private HashMap<Character, InverseVocabularyTree> childs;
    private String description; 

    public InverseVocabularyTree() {        
        childs=new HashMap<Character, InverseVocabularyTree>();     
    }

    public void addWord(String word, String description){       
        InverseVocabularyTree tr=this;      
        InverseVocabularyTree chld=this;
        char[] letters=word.toCharArray();
        for (int i=word.length()-1; i>=0; i--) {        
            if (!tr.childs.containsKey(letters[i]))
            {               
                for(int j=i; j>=0; j--) //a small optimisation..
                {
                    chld=new InverseVocabularyTree();
                    tr.childs.put(letters[j], chld);
                    tr=chld;
                }
                break;
            }
            else
            tr=tr.childs.get(letters[i]);
        }
        tr.description=description;         
        return;
    }

    public HashMap<Character, InverseVocabularyTree> getChilds() {
        return childs;
    }

    public String[] getRemovableBasicParts() {
        return removableBasicParts;
    }

    public LinkedList<String[]> getAllRemovableBasicParts() {
        LinkedList<String[]> ret=new LinkedList<String[]>();
        if (removableBasicParts!=null)
            ret.add(removableBasicParts);
        if (childs.keySet().isEmpty())
            return ret;
        for(char c : childs.keySet())
            ret.addAll(childs.get(c).getAllRemovableBasicParts());
        return ret;
    }   
}

那么，有没有人有一些想法或建议在这种情况下如何优化？

Answer 1

如果不需要值，我会使用NavigableMap或类似的集合。假设您需要搜索以"abc“开头的单词，您只需执行以下操作

NavigableMap<String, Boolean> wordmap = new TreeMap<String, Boolean>();
Random random = new Random(1);
for(int i=0;i<10*1000*1000;i++)
    wordmap.put(Long.toString(Math.abs(random.nextLong()), 36).substring(1), true);
String prefix = "abcd";
for (String word : wordmap.subMap(prefix, prefix+"\uffff").keySet()) {
    System.out.println(word + " starts with " + prefix);
}

//或者

for (String word : wordmap.tailMap(prefix).keySet()) {
    if (!word.startsWith(prefix)) break;
    System.out.println(word + " starts with " + prefix);
}

这在我的机器上使用了1 1GB，用于1000万个条目和打印

abcd0krpbk1 starts with abcd
abcd7xi05pe starts with abcd
abcdlw4pwfl starts with abcd

编辑:根据反馈，我建议使用以下方法。

// keys stored in reverse order of the original string.
NavigableMap<String, Boolean> wordmap
String search = "dcba";
// retains hte order keys were added.
Map<String, Boolean> results = new LinkedHashMap<String, Boolean>();
for(int i=search.size();i>=1;i--) {
    String s = search.substring(0, i);
    results.putAll(wordmap.subMap(s, s+'\uFFFF')); // ignores duplicates
}

结果将所有搜索的组合按它们添加的顺序排列，从最具体到最不具体。}

Answer 2

假设问题是在数十万个单词之后，您的树变得太高，您可以尝试使用某些常见的二元或三元语法，而不是几个节点的单个字母，以使其更短。例如，如果你有很多以" ing“结尾的单词，而不是有一个g的节点，g有一个孩子，n有一个孩子，i有一个孩子，你可以为ing创建一个节点。当然，这会有多好取决于你的词汇表，你可能需要做一些分析来找到合适的二元，三元语法来使用。

一般来说，既然你说你已经检查了垃圾收集，我认为如果你能找出是否有一个特定的树大小，之后你的应用程序开始变慢，或者问题是完全不同的东西，这将是很有用的。更好地了解问题究竟是什么，可以给你如何解决它的新想法。

Answer 3

您为每个单词(通常更多)创建了至少一个HashMap -因此，如果您有许多不同的单词，则会耗尽内存。不要显式地调用System.gc，而是使用jconsole或类似的分析器工具来观察您的程序。

我想，在你写完前300000个单词之后，内存几乎已经满了，而你的程序大部分时间都在试图获得更多的空间。如果是这种情况，请尝试为您的程序提供更多内存(使用-Xmx选项)。