java - 前缀树问题

我需要处理将近13万个单词（有些单词组是类似的）。
我在做一些类似于小词汇的事情，每个词都有自己的描述。
快速搜索词汇是必要的所以我决定用前缀树。
首先需要建立prefix树（这是一个缓慢的过程，我知道），在这个快速浏览词汇表的过程可能会被组织起来。
但我的问题是，prefix树的构建速度非常慢（前300000个单词的构建速度很快，但是尾部的构建速度非常慢，以至于我等不及树的构建了！!).
这是我的前缀树类：

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

那么，在这种情况下，有没有人对如何进行优化有什么想法或建议呢？

最佳答案

如果不需要值，我只使用navigablemap或类似的集合。
说你需要用“abc”搜索startign这个词

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

这在我的机器上使用了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
}

搜索结果将按照从最具体到最不具体的顺序组合所有搜索。
}

关于java - 前缀树问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5499064/