trie building in java

Question

Как построить дерево из файла? Я хочу, чтобы иметь возможность читать их из файла, а затем добавить к соответствующему уровню

Answer 1

Мне кажется, что вы пытаетесь реализовать trie.

Посмотрите здесь для хорошей реализации в Java: http://www.cs.duke.edu/~ola/courses/cps108/fall96/joggle/trie/Trie.java

Answer 2

Добавление

Начиная с корня, поиска первого (или текущего) письма. Если эта буква найдена, перейдите на этот узел и выполните поиск следующей буквы. Если письмо не найдено, найдите слово, соответствующее текущей букве, если есть аналогичное слово, добавьте текущую букву в качестве нового узла и переместите оба слова под этим, иначе добавьте слово.

Примечание: Это приведет к тому, что дерево будет более оптимизировано для поиска, а затем дерево, показанное в примере. (Непреклонен и адаптируют будут сгруппированы под другим «а» узел)

Update: Посмотрите на статью Википедии для Trie

Answer 3

Если у вас есть только два уровня в дереве до лаврового листа (фактическое слова), вы можете просто начать с массивов с 28 элементами, являющимися и перевести буквы в индекс (т.е. a == 1, b == 2 и т. д.). Элементами массива могут быть некоторые set/list, содержащие полные слова. Вы можете лениво создавать массивы и списки (т. Е. Создавать корневой массив, но иметь нули для других массивов и список слов, тогда вы создаете массив/список при необходимости, если это необходимо).

Я читаю правила, которым вы должны следовать правильно?

P.S. Я думаю, что использование массивов с полным размером каждого из них не было бы слишком расточительным на пространстве, а также должно быть очень быстро, чтобы обратиться к

Обновление: @ user1747976, и каждый массив будет занимать около 28 * 4 или 28 * 8 бит + 12 байты overhead. Надеемся, вы используете сжатые операционные системы, поэтому это 28 * 4 + 12 = 116 байтов на массив. Теперь это зависит от того, хотите ли вы эффективно использовать память или эффективно работать. Чтобы быть эффективной с памятью, вы можете использовать какой-то хэш-файл вместо массивов, но я не уверен, что дополнительные накладные расходы будут меньше, чем то, что вы используете с массивами. Тем не менее, обработка будет еще хуже. Вам нужно использовать несколько умных циклов несколько раз в зависимости от требования к дереву. Некоторые некрасиво псевдо-код для вставки в дерево:

root=new Object[28]; 
word="something"; 
pos = root; 
wordInd=1; 
for (int i=1; i<=TREE_DEPTH ; i++) { 
    targetpos = letterInd(letter(wordInd,word)); 
    if (i==TREE_DEPTH) { 
     if (pos[targetpos] == null) pos[targetpos] = new HashSet<String>(); 
     (Set) pos[targetpos].add(word); 
     break; 
    } else { 
     if (pos[targetpos] == null) pos[targetpos] = new Object[28]; 
     wordInd++; 
     pos = pos[targetpos]; 
    } 
} 

Похожие петли можно использовать для извлечения слов.