trie building in java

Question

How do I construct a tree from a file ? I want to be able to read them from a file and then add to appropriate level

score 2 · Accepted Answer · answered Apr 09 '13 at 16:48

2

It seems to me that you are trying to implement trie.

Look here for a nice implementation in java: http://www.cs.duke.edu/~ola/courses/cps108/fall96/joggle/trie/Trie.java

answered Apr 09 '13 at 16:48

ciastkoo

92
1
9

Thanks man, i will have a look at it – Dodi Apr 09 '13 at 16:51
Now I see why java classes are often useless.. i.e. there is always an easy way to find code to just paste and be done with it. I don't know if I would resist to reuse if it was me but experience is not really gained that way. Understanding some code != writing code. – akostadinov Apr 09 '13 at 20:47

Rylander · Answer 2 · 2013-04-09T17:24:46.760

1

Adding

Starting at the root, search for the first (or current) letter. If that letter is found then move to that node and search for the next letter. If the letter is not found, search for a word that matches the current letter, if there is a similar word then add the current letter as a new node and move both words under that, otherwise add the word.

Note: This will result in a tree that is more optimized for searches then the tree shown in the example. (adamant and adapt will be grouped under another 'a' node)

Update: Take a look at the Wikipedia article for Trie

edited Apr 09 '13 at 17:24

answered Apr 08 '13 at 18:18

Rylander

19,449
25
93
144

@user1747976 You first search for where to add it, then add it. If there is nothing in the tree add it. see updated answer. – Rylander Apr 08 '13 at 18:35
If you limit it to two levels this will give the tree shown in the question. – Rylander Apr 08 '13 at 18:48
@user1747976 if you force two levels and only use two levels it will works as in the example. you will still need to search for the correct node to added it to (creating it if needed) before adding. – Rylander Apr 08 '13 at 18:52

score 1 · Answer 3 · edited May 23 '17 at 10:34

If you have only two levels in the tree before leafs (the actual words), you can simply start with arrays with 28 elements being and translate the letters to the index (i.e. a==1, b==2, etc.). Elements of array can be some set/list that contains the full words. You can lazily create arrays and lists (i.e. create the root array but have nulls for the other arrays and list of words, then you create an array/list when/if needed).

Am I reading rules you should follow correctly?

P.S. I think that using arrays with full size each would not be too wasteful on space as well it should be very fast to address

Update: @user1747976, well each array would take around 28*4 or 28*8 bits + 12 bytes overhead. Hopefully you use compressed ops so it is 28*4+12=116bytes per array. Now it depends if you want to be memory efficient or processing efficient. To be memory efficient, you can use some kind of hashmap instead of arrays but I'm not sure the additional overhead will be less than what you use with arrays. Processing will be for sure worse though. You need to use some clever loop a number of times depending on tree dept requirement. Some ugly pseudo code for inserting into tree:

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

Similar loop you can use for retrieving words.

@user1747976, see my updated answer, make sure you understand what you're doing because I'm almost sleeping and fixed it two times already — akostadinov, Apr 08 '13 at 19:22
`letterInd()` gives you the index you gave to a letter (i.e. for "a" it would return 1). `letter(wordInd,word)` would return the letter with index `wordInd` in the word `word`. It's not creating new Object but a new Array or Node if you call it so. UPDATE: I see you have a `Node` class but it would be simpler and less overhead to not have a separate node class but use a simple Array for that. Otherwise it is possible to wrap everything in your class, depends on how you would like to do things. I just gave you an example loop to add a word. — akostadinov, Apr 08 '13 at 19:36

trie building in java

3 Answers3