java - 前缀树问题

Question

我需要处理将近 1,300,000 个单词(有些单词组是相似的)。 我正在做一些小词汇，每个词都有它的描述。 需要快速搜索词汇。所以我决定使用前缀树。 首先，需要建立前缀树(这是一个缓慢的过程，我知道)，之后可能会组织快速浏览词汇。

但我的问题 - 前缀树构建速度极慢(前 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 或类似的 Set。 假设您需要搜索以“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);
}

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

结果将按添加顺序合并所有搜索，从最具体到最不具体。