6

私はハフマン エンコーディング プログラムに取り組んでおり、ほぼ完成していますが、無限再帰ループに陥っています。これがどこで間違っているのか誰にも分かりますか?

これは私が得ているエラーです:

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)

出力は継続的に 5:1、5:4、5:2 の繰り返しです

私のデータファイルは次のようになります。

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

そして私のコードは

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

2 に答える 2

3

あなたのツリービルディングは間違っています。

while(huffmanList.size() > 1){
    HuffmanNode x = huffmanList.poll();
    HuffmanNode y = huffmanList.poll();

キューから最も軽い木を 2 つ取り出し、

    HuffmanNode result = new HuffmanNode("-", x.getCount() + y.getCount(), null, x, y);

そしてそれらをマージし、重みの合計を重みとしてツリーを形成します - これまでのところ、とても良いです。

    if(root == null){     // never happens, but doesn't matter
        root = result;
    }
    else{
        root.buildTree(result);

次に、新しく形成されたツリーを に挿入しますroot

    }
    huffmanList.add(result);                    
}

キューに追加します。

さて、で始まるキューを考えてみましょう

(a,1), (b,2), (c,3), (d,3), (e,3), ...

root = new HuffmanNode();に設定root(null, 0)ます。

まず、abノードがマージされ、 が得られ<(a,1) | (-,3) | (b,2)>ます。root農産物への挿入

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

以来3 > 0。行列は

<(a,1) | (-,3) | (b,2)>, (c,3), (d,3), (e,3) ...

マージされたツリーを挿入した後 [マージされたツリーは、いくつかの重み 3 ノードの後に​​挿入することもできますが、それには少し時間がかかります]。

これで、最も軽い 2 つのツリーがポップされてマージされ、次のようになります。

<AB | (-,6) | (c,3)>

(略語付きAB = <(a,1) | (-,3) | (b,2)>)。次に、そのツリーがツリーに挿入されrootます。6 > 0の右の子に挿入されるため、 の右の子にroot挿入6 > 3され、ノードの右の子(-,3)6 > 2なり(b,2)ます。ただし、新しくマージされたツリーの左の子と右の子はroot同じオブジェクトを参照するため、この挿入の後、

                   __________
                  |          |
                  v          |
    (null,0)   (-,6)         |
    /      \   /   \         |
  null     (-,3)   (c,3)     |
           /   \             |
       (a,1)   (b,2)         |
                   \_________|

ツリーであるはずのサイクル。次に、2 つのノードがポップ(d,3)および(e,3)マージされ、重み 6 のツリーが作成されます。このツリーがrootグラフに挿入されると、ループします。

異なる挿入動作および/または文字の異なる重みは詳細を変更しますが、最初に十分なノードがある場合は常にサイクルにつながるグラフへの参照が afterroot.buildTree(result);huffmanList.add(result);queue に含まれているという事実があります。rootそして、十分なサイクルが得られると、buildTree()呼び出しが無限ループに陥らない可能性は低くなります。

を呼び出すべきではありませんroot.buildTree(result)。ツリーは、キューに含まれるツリーが 1 つだけになるまで、キューから最も軽い 2 つをマージし、結果を再挿入するだけで構築されます。

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();
于 2012-12-07T20:14:19.733 に答える
0

変更してみる

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

if(root == null){

また

ifこのような多数のコードを短縮してみてください

 char c = letter.charAt(0);
 int index = c - 97;
 freq[index]++;
于 2012-12-07T07:51:54.620 に答える