Nieskończona rekursja, StackOverError w drzewie Huffmana

Question

Pracuję nad programem do kodowania Huffmana i już prawie skończyłem, ale utknąłem w nieskończonej pętli rekursji. Czy ktoś ma pojęcie, gdzie to idzie źle?

Jest to błąd otrzymuję:

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) 

i wyjście jest stale 5: 1, 5: 4, 5: 2, powtarzając

mój datafile wygląda następująco:

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 

i mój kod jest

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

Twój drzewa budynek ponosi winy.

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

Bierzesz dwa najjaśniejsze drzew z kolejki,

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

i połączyć je, tworząc drzewo z sumy wag jak waga - tak daleko, tak dobrze.

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

Następnie włóż nową formowane drzewa w root,

} 
    huffmanList.add(result);      
} 

i dodać go do kolejki.

Teraz rozważmy kolejkę zaczynając

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

root = new HuffmanNode(); ustawić root do (null, 0).

Najpierw połączone są węzły a i b, co daje <(a,1) | (-,3) | (b,2)>. Wstawianie do root produkuje

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

ponieważ 3 > 0. Kolejka ta jest

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

po włożeniu połączonego drzewa [połączony drzewo może być wkładany po kilku wagi 3 węzłów, a to trochę dłużej].

Teraz dwa najlżejsze drzewa trzasnął i połączone, dając

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

(ze skrótem AB = <(a,1) | (-,3) | (b,2)>). To drzewo jest następnie wstawiane do drzewa root. 6 > 0, więc jest wstawiany do prawego dziecka root, 6 > 3, więc jest wstawiany do prawego dziecka (-,3), 6 > 2, więc staje się właściwym dzieckiem węzła (b,2). Ale lewa dziecko nowo połączyła drzewa i prawo dzieckiem root odnoszą się do tego samego obiektu, więc po tym wprowadzeniu, masz

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

cyklu, w jakim ma być drzewem. Następnie dwa węzły: (d,3) i (e,3) są poppingowane i łączone, co daje drzewo o wadze 6, a kiedy to drzewo zostanie wstawione do wykresu root, zapętli się.

Different zachowanie wstawiania i/lub różne ciężary liter zmieni dane, ale fakt, że po root.buildTree(result); i huffmanList.add(result); kolejka zawiera odniesienie do wykresu czele root prowadzi do cykli, gdy masz wystarczająco dużo węzłów początkowo. A jeśli masz wystarczająco dużo cykli, prawdopodobieństwo, że wywołanie buildTree() nie znajdzie się w nieskończonej pętli, jest małe.

Po prostu nie należy dzwonić pod numer root.buildTree(result). Drzewo jest konstruowane przez proste połączenie dwóch najlżejszych z kolejki i ponowne wstawienie wyniku, aż kolejka zawiera tylko jedno drzewo.

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

Spróbuj zmienić

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

do

if(root == null){ 

także

spróbować skrócić numerious kod if jak ten

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