Geek Answers Handbook

Trie building in java

How do I build a tree from a file? I want to read them from a file and then add to the appropriate level

+4
source share
3 answers

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

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

+2
source

Adding

Starting from the root, search for the first (or current) letter. If this letter is found, go to this node and search for the next letter. If the letter is not found, find the word corresponding to the current letter, if there is a similar word, add the current letter as a new node and move both words under it, otherwise add the word.

Note. . This will create a more search-optimized tree, and then the tree shown in the example. (adamant and adapt will be grouped under another "a" node)

Update: Take a look at the Trie Wikipedia article

+1
source

If you have only two levels in the tree in front of the sheets (actual words), you can just start with arrays with 28 elements and translate the letters into the index (i.e. a == 1, b == 2, etc. ) Array elements can be some set / list containing complete words. You can lazily create arrays and lists (i.e., create a root array, but have zeros for other arrays and a list of words, then you create an array / list if necessary).

Am I reading the rules that you must follow correctly?

PS I think that using arrays with the full size of each of them would not be too wasteful in space, and should also be addressed very quickly

Update: @ user1747976, and each of them will occupy about 28 * 4 or 28 * 8 bits + 12 bytes service data . We hope you use compressed operating systems, so this is 28 * 4 + 12 = 116 bytes per array. Now it depends on whether you want to use memory efficiently or work efficiently. To be efficient with memory, you can use some kind of hash file instead of arrays, but I'm not sure that the extra overhead will be less than what you use with arrays. However, the handling will be even worse. You have to use some smart loop several times depending on the tree requirement. Some ugly pseudo code to insert into a 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]; } }

A similar loop that you can use to extract words.

+1
source

More articles:


All Articles