无限递归，哈夫曼树中的StackOverError。

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?

我正在编写一个Huffman编码程序，我差不多完成了，但是我陷入了一个无限递归循环。有没有人知道哪里出了问题?

This is the error I am getting:

这是我的错误:

Exception in thread "main" java.lang.*Error
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

输出是5:1,5:4,5:2，重复。

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(" ");
}
}

2 个解决方案

#1

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).

根= new HuffmanNode();将根设置为(null, 0)。

First, the a and b nodes are merged, giving <(a,1) | (-,3) | (b,2)>. Inserting into root produces

首先，a和b节点合并，给予<(a,1) | (-，3) | (b,2)>。插入根产生

         (null,0)
          /    \
        null  (-,3)
              /   \
            (a,1) (b,2)

since 3 > 0. The queue is

因为3 > 0。队列是

<(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

(简称AB = <(a,1)|(- 3)|(b,2)>)。然后将该树插入到根树中。> 0，所以它插入到根的右子结点，6 > 3，所以它插入到(-，3)，6 > 2的右子结点，所以它就变成了(b,2)节点的右子结点。但是，新合并的树的左子和根的右子引用相同的对象，所以在插入之后，就有了。

                   __________
                  |          |
                  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.

一个周期，它应该是一棵树。接下来，两个节点(d,3)和(e,3)被弹出并合并，给出了一个6的树，当树被插入到根图中时，它会循环。

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.

不同的插入行为和/或不同权重的字母会改变细节，但事实是，在root.buildTree(结果)之后;和huffmanList.add(结果);队列中包含一个引用，当您开始有足够的节点时，根引导到循环。一旦有了足够的周期，构建树()调用将不会在无限循环中降落的概率很小。

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.

您不应该调用root.buildTree(结果)。该树是通过简单地从队列中合并两个lightest并重新插入结果来构造的，直到队列只包含一棵树。

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();

#2

Try changing

试着改变

if(root.equals("null")){

to

来

if(root == null){

Also

也

try to shorten your numerious if code like this

如果代码像这样，尽量缩短您的numerious。

 char c = letter.charAt(0);
 int index = c - 97;
 freq[index]++;