Unendliche Rekursion, StackOverError im Huffman-Baum

Question

Ich arbeite an einem Huffman-Encoding-Programm, und ich bin fast fertig, aber ich bin in einer unendlichen Rekursionsschleife stecken. Hat jemand eine Idee, wo das schief geht?

Dies ist der Fehler Ich erhalte:

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) 

und der Ausgang ist kontinuierlich 5: 1, 5: 4, 5: 2, Wiederholung

meine Daten-Datei wie folgt aussieht:

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 

und mein Code

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

Answer 1

Ihr Baum-Gebäude ist zu verkürzen.

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

Sie nehmen die beide leichtesten Bäume aus der Warteschlange,

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

und kombinieren sie, einen Baum mit der Summe der Gewicht als Gewicht bilden - so weit, so gut.

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

Dann legen Sie die neugebildete Baum in die root,

} 
    huffmanList.add(result);      
} 

und fügen Sie ihn in die Warteschlange zurück.

Nun, lassen Sie uns eine Warteschlange betrachten mit

Start

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

root = new HuffmanNode(); gesetzt root zu (null, 0).

Zuerst werden die Knoten a und b zusammengeführt, was <(a,1) | (-,3) | (b,2)> ergibt. Einfügen in root produziert

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

seit 3 > 0. Die Warteschlange ist

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

nach dem fusionierten Baum Einfügen [das fusionierte Baum auch nach ein paar Gewicht-3 Knoten eingeführt werden könnte, dann wäre es ein bisschen länger dauern].

Nun werden die beiden leichtesten Bäume geknallt und fusionierte,

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

(mit der Abkürzung AB = <(a,1) | (-,3) | (b,2)>) geben. Dieser Baum wird dann in den Baum root eingefügt. 6 > 0, so ist es in das rechte Kind von root, 6 > 3 eingefügt, so ist es in das rechte Kind von (-,3), 6 > 2 eingefügt, so wird es das richtige Kind der (b,2) Knoten. Aber das linke Kind des neu fusionierten Baumes und das rechte Kind root beziehen sich auf das gleiche Objekt, so dass nach dieser Einführung haben Sie

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

ein Zyklus in dem, was angenommen hat, ein Baum zu sein. Als nächstes werden die zwei Knoten (d,3) und (e,3) geknallt und zusammengeführt, was einen Baum mit der Gewichtung 6 ergibt, und wenn dieser Baum in den root Graph eingefügt werden soll, würde er eine Schleife bilden.

Verschiedene Einfügeverhalten und/oder unterschiedliche Gewichte der Buchstaben würden die Details ändern, aber die Tatsache, dass nach root.buildTree(result); und huffmanList.add(result); die Warteschlange einen Verweis auf die von root gekrönt Graph enthält führt zu Zyklen, wenn Sie zunächst genug Knoten haben. Und sobald Sie genügend Zyklen haben, ist die Wahrscheinlichkeit, dass ein buildTree() Anruf nicht in einer Endlosschleife landen wird, gering.

Sie sollten einfach nicht root.buildTree(result) anrufen. Der Baum wird konstruiert, indem einfach die beiden hellsten aus der Warteschlange zusammengeführt werden und das Ergebnis erneut eingefügt wird, bis die Warteschlange nur einen Baum enthält.

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

Answer 2

Try

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

zu

if(root == null){ 

Auch

try Änderung Ihrer numerious if Codes wie diese Schuld

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