Проблема с префиксом дерева

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

На моем аппарате используется 1 ГБ для 10 миллионов записей и отпечатков

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

Вы создаете по крайней мере одну HashMap для каждого слова (часто больше) - поэтому, если у вас действительно много разных слов, вам не хватает памяти.Не вызывайте явно System.gc, вместо этого наблюдайте за вашей программой с помощью jconsole или аналогичного инструмента для профилирования.

Я полагаю, что после ваших первых 300000 слов просто память почти заполнена, и ваша программа тратит большую частьпришло время пытаться получить больше места.Если это так, попробуйте дать вашей программе больше памяти (с опцией -Xmx).

Answer 3

Предполагая, что проблема в том, что после нескольких сотен тысяч слов ваше дерево становится слишком высоким, вы можете попытаться использовать некоторые часто встречающиеся биграммы или триграммы вместо отдельных букв для пары узлов, чтобы сделать егонемного короче.Например, если у вас много слов, оканчивающихся на «ing», вместо одного узла для g, у которого есть дочерний элемент для n, у которого есть дочерний элемент для i, вы можете создать один узел для ing.Конечно, насколько хорошо это будет работать, зависит от вашего словарного запаса, и вам, вероятно, потребуется провести некоторый анализ, чтобы найти подходящие би-, триграммы для использования.

В общем, поскольку вы говорите, что проверили сборку мусораЯ думаю, было бы полезно, если бы вы могли выяснить, существует ли определенный размер дерева, после которого ваше приложение начинает замедляться или проблема в чем-то совершенно ином.Лучшее представление о том, в чем именно проблема, может дать вам новые идеи о том, как ее решить.