Infinite Recursion, StackOverError in huffman tree
encoding, huffman-code, java, recursion
Solution
Your tree-building is at fault.
while(huffmanList.size() > 1){
HuffmanNode x = huffmanList.poll();
HuffmanNode y = huffmanList.poll();
You take the two lightest trees from the queue,
HuffmanNode result = new HuffmanNode("-", x.getCount() + y.getCount(), null, x, y);
and merge them, forming a tree with the sum of weights as weight - so far, so good.
if(root == null){ // never happens, but doesn't matter
root = result;
}
else{
root.buildTree(result);
Then you insert the new-formed tree into the `root`,
}
huffmanList.add(result);
}
and add it back into the queue.
Now, let us consider a queue starting with
(a,1), (b,2), (c,3), (d,3), (e,3), ...
`root = new HuffmanNode();` set `root` to `(null, 0)`.
First, the `a` and `b` nodes are merged, giving `<(a,1) | (-,3) | (b,2)>`. Inserting into `root` produces
(null,0)
/ \
null (-,3)
/ \
(a,1) (b,2)
since `3 > 0`. The queue is
<(a,1) | (-,3) | (b,2)>, (c,3), (d,3), (e,3) ...
after inserting the merged tree [the merged tree could also be inserted after a couple of weight-3 nodes, then it would take a bit longer].
Now the two lightest trees are popped and merged, giving
<AB | (-,6) | (c,3)>
(with the abbreviation `AB = <(a,1) | (-,3) | (b,2)>`). That tree is then inserted into the `root` tree. `6 > 0`, so it's inserted into the right child of `root`, `6 > 3`, so it's inserted into the right child of `(-,3)`, `6 > 2`, so it becomes the right child of the `(b,2)` node. But, the left child of the newly merged tree and the right child of `root` refer to the same object, so after this insertion, you have
__________
| |
v |
(null,0) (-,6) |
/ \ / \ |
null (-,3) (c,3) |
/ \ |
(a,1) (b,2) |
\_________|
a cycle in what's supposed to be a tree. Next, the two nodes `(d,3)` and `(e,3)` are popped and merged, giving a tree of weight 6, and when that tree shall be inserted into the `root` graph, it would loop.
Different insertion behaviour and/or different weights of the letters would change the details, but the fact that after `root.buildTree(result);` and `huffmanList.add(result);` the queue contains a reference into the graph topped by `root` leads to cycles whenever you have enough nodes initially. And once you have enough cycles, the probability that a `buildTree()` call will not land in an infinite loop is small.
You simply should not call `root.buildTree(result)`. The tree is constructed by simply merging the two lightest from the queue and reinserting the result, until the queue contains only one tree.
while(huffmanList.size() > 1){
HuffmanNode x = huffmanList.poll();
HuffmanNode y = huffmanList.poll();
HuffmanNode result = new HuffmanNode("-", x.getCount() + y.getCount(), null, x, y);
huffmanList.add(result);
}
root = huffmanList.poll();
Problem
I am working on a Huffman Encoding program and I am almost finished but I am stuck in an infinite recursion loop. Does anyone have an idea where this is going wrong? This is the error I am getting: ``` Exception in thread "main" java.lang.StackOverflowError at sun.nio.cs.SingleByteEncoder.encodeLoop(SingleByteEncoder.java:130) at java.nio.charset.CharsetEncoder.encode(CharsetEncoder.java:544) at sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:252) at sun.nio.cs.StreamEncoder.write(StreamEncoder.java:106) at java.io.OutputStreamWriter.write(OutputStreamWriter.java:190) at java.io.BufferedWriter.flushBuffer(BufferedWriter.java:111) at java.io.PrintStream.write(PrintStream.java:476) at java.io.PrintStream.print(PrintStream.java:619) at java.io.PrintStream.println(PrintStream.java:756) at HuffmanNode.buildTree(hw4.java:63) at HuffmanNode.buildTree(hw4.java:64) at HuffmanNode.buildTree(hw4.java:64) at HuffmanNode.buildTree(hw4.java:64) at HuffmanNode.buildTree(hw4.java:64) at HuffmanNode.buildTree(hw4.java:64) at HuffmanNode.buildTree(hw4.java:64) at HuffmanNode.buildTree(hw4.java:64) ``` and the output is continually 5:1, 5:4, 5:2, repeating my datafile looks like this: ``` a a a a d d d d d d d d k k k k k k f f f f f f h h h h h h b b b b b b b b n n n n n n n e e e e e i i i i i i i i l k j a n s g l k j a s v o i j a s d l k g k n m a s d k l o v h a s d g z ``` and my code is ``` import java.util.*; import java.io.*; class HuffmanNode implements Comparable<HuffmanNode>{ HuffmanNode right; HuffmanNode left; HuffmanNode parent; int count; String letter; public HuffmanNode(){} public HuffmanNode (String letter, int count){ this.letter = letter; this.count = count; } public HuffmanNode (String letter, int count, HuffmanNode parent, HuffmanNode left, HuffmanNode right){ this.letter = letter; this.count = count; this.left = left; this.right = right; this.parent = parent; } public void setCount(int count){ this.count = count; } public int getCount(){ return count; } public void setRight(HuffmanNode right){ this.right = right; } public HuffmanNode getRight(HuffmanNode right){ return right; } public void setLeft(HuffmanNode left){ this.left = left; } public HuffmanNode getLeft(HuffmanNode left){ return left; } public void setParent(HuffmanNode right){ this.left = left; } public HuffmanNode getParent(HuffmanNode parent){ return parent; } public void buildTree(HuffmanNode node){ if (node.compareTo(this) <= 0 && left != null){ System.out.println(node.getCount() + ":" + this.count); left.buildTree(node); } else if (node.compareTo(this) <= 0 && left == null){ this.left = node; node.parent = this; } else if (node.compareTo(this) > 0 && right != null){ System.out.println(node.getCount() + ":" +this.count); right.buildTree(node); } else if (node.compareTo(this) > 0 && right == null){ this.right = node; node.parent = this; } } public int compareTo(HuffmanNode x){ return this.count - x.count; } public void genCode(String s){ if(left != null){ left.genCode(s + "0"); } if(right != null){ right.genCode(s + "1"); } if (left == null && right == null){ System.out.println(s); } } } public class hw4{ public static void main (String []args)throws IOException{ //ask user to enter file name System.out.printf("Enter a file location and name to encode [press Enter]: "); Scanner input = new Scanner(System.in); String filename = input.next(); //Gets file name from Scanner and checks to see if valid File file = new File(filename); //if (!file.isFile()){ //System.out.printf("Enter a file location and name to encode [press Enter]: "); //} Scanner text = new Scanner(file); String[] letters = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"}; int[] freq = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; String letter; String tempStr; int tempInt; while(text.hasNext()){ letter = text.next(); //System.out.printf("%s\n", letter); char c = letter.charAt(0); int index = c - 97; freq[index]++; } for(int i=0; i <25; i++){ System.out.printf("%s:%d\n", letters[i], freq[i]); } System.out.printf("\n"); for (int n=0; n <25; n++) { for (int i=0; i <25; i++) { if (freq[i] > freq[i+1]) { // exchange elements tempInt = freq[i]; tempStr = letters[i]; freq[i] = freq[i+1]; letters[i] = letters[i+1]; freq[i+1] = tempInt; letters[i+1] = tempStr; } } } PriorityQueue<HuffmanNode> huffmanList = new PriorityQueue<HuffmanNode>(); for(int i=0; i <26; i++){ System.out.printf("%s:%d\n", letters[i], freq[i]); if(freq[i] > 0){ huffmanList.add(new HuffmanNode(letters[i],freq[i])); } } HuffmanNode root = new HuffmanNode(); while(huffmanList.size() > 1){ HuffmanNode x = huffmanList.poll(); HuffmanNode y = huffmanList.poll(); HuffmanNode result = new HuffmanNode("-", x.getCount() + y.getCount(), null, x, y); if(root == null){ root = result; } else{ root.buildTree(result); } huffmanList.add(result); } root.genCode(" "); } } ```