(JAVA) out of memory error
OK I'm implementing a data structure called "trie" to store a dictionary of words. The text file I'm reading in has over 172K words....this, with a good implementation of a trie should not take more than 20-22MBs of memory. For some reason my implementation gives me an OutOfMemoryError.
If I use a small dictionary....say 50K words everything is fine...any ideas?
BTW...I'm passing a hashedMap set to add.
Code:
class TrieNode {
TrieNode[] myLinks;
boolean myIsWord;
String myWord;
/**
* create a new TrieNode (characters a-z and ' ')
*/
public TrieNode() {
myLinks = new TrieNode[Trie.ALPH];
myIsWord = false;
myWord = null;
}
}
public class Trie {
TrieNode root;
public static final int ALPH = 27;
public Trie() {
root = new TrieNode();
}
/**
* Add a string to the trie
*
* @param s The string added to Trie
*/
public void add(String s) {
TrieNode t = root;
int limit = s.length();
for(int k=0; k < limit; k++) {
int index = index(s.charAt(k));
if (t.myLinks[index] == null) {
t.myLinks[index] = new TrieNode();
}
t = t.myLinks[index];
}
t.myIsWord = true;
t.myWord = s;
}
/**
* print every word in the trie, one per line
*
*/
public void printTrie() {
printTrie(root);
}
private void printTrie(TrieNode t) {
if (t != null) {
if (t.myIsWord) {
System.out.println(t.myWord);
}
for(int k=0; k < ALPH; k++) {
if (t.myLinks[k] != null) {
// System.out.println("Descend to child " + letter(k));
printTrie(t.myLinks[k]);
}
}
}
}
/**
* determine if a word is in the trie (starting at root)
*
* @param s The string searched for
* @return true iff s is in trie (starting at root)
*/
public boolean contains(String s) {
TrieNode t = root;
int limit = s.length();
for(int k=0; k < limit; k++) {
int index = index(s.charAt(k));
if (t.myLinks[index] == null) return false;
t = t.myLinks[index];
}
return t.myIsWord;
}
// convert all unknown symbols to spaces
public static int index(char ch) {
int i = (int) (ch - 'a');
if ((i < ALPH-1) && (i >= 0))
return i;
else
return ALPH-1;
}
public static char letter(int i) {
if (i == ALPH-1)
return ' ';
else
return (char) (i + 'a');
}
}
