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

Question

Мне нужно управлять почти 1,300,000 словами (некоторые группы слов похожи). Я делаю что-то вроде небольшой лексики, где каждое слово имеет свое описание. Быстрый поиск по лексике необходим. Поэтому я решил использовать дерево префикса. Во-первых, дерево preffix необходимо для создания (это медленный процесс, я знаю это), после того как этот быстрый поиск по лексике может быть организован.

Но моя проблема - это дерево префикса строится крайне медленно (первые 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 или аналогичный набор, если вам не нужно значение. Предположим, вам нужно искать слова 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); 
} 

Это использует 1 Гб на моей машине за 10 миллионов записей и оттисков

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

EDIT: на основе обратной связи я бы предложил что-то вроде следующего подхода.

// 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, у которого есть дочерний элемент для n, у которого есть дочерний элемент для i, вы можете создать единственный узел для ing. Конечно, как хорошо это будет работать, зависит от вашего словарного запаса, и вам, вероятно, потребуется провести некоторый анализ, чтобы найти подходящие би-триграммы.

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

Answer 3

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

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