周波数配列からのハフマン符号化（Java）

Question

私のハフマンコードに問題があります。メインメソッドでは、シンボルの頻度を含むInteger配列を入力します。これは、各シンボルとそのハフマンコードを印刷する必要がありますが、私は何かがメインで

間違っていると思う：

ハフマン符号で今

int[] histo = new int[]{8, 65, 124, 55, 2, 1, 0, 1}; 
System.out.println("Codage de Huffman:"); 
String[] huffman = huffman(histo); 
for (int i = 0; i < huffman.length; i++) { 
    if (histo[i] > 0) { 
     System.out.println(i + "] " + huffman[i]); 
    } 
} 

：ここ

public static String[] huffman(int[] histo) { 
    String[] codage = new String[histo.length]; 
    int valeur1; 
    int valeur2; 
    int index1 = 0; 
    int index2 = 0; 
    for (int i = 0; i < histo.length; i++) { 
     codage[i] = new String(); 
    } 

    do { 
     valeur1 = Integer.MAX_VALUE; 
     valeur2 = Integer.MAX_VALUE; 
     for (int i = 0; i < histo.length; i++) { 
      if (histo[i] > 0) { 
       if (histo[i] < valeur1) { 
        valeur2 = valeur1; 
        valeur1 = histo[index1 = i]; 
       } else if (histo[i] < valeur2) { 
        valeur2 = histo[index2 = i]; 
       } 
      } 
     } 
     histo[index1] = 0; 
     histo[index2] += valeur1; 
     codage[index1] = codage[index1] + "0"; 
     codage[index2] = codage[index2] + "1"; 
    } while (valeur2 != Integer.MAX_VALUE); 

    return codage; 

} 

が出力されます。

0] 0 
1] 0 
2] 0 
3] 111101 
4] 0 
5] 0 
7] 110 

Answer 1

問題は、コードにビットを追加すると、現在のインデックスにのみ追加されます（すべてのchiには追加されません）木の葉のように）。私がしました

public static String[] huffman(int[] histo){ 
     //build up initial list of nodes 
     List<Node> tree = new ArrayList<>(); 
     for (int i = 0; i < histo.length; i++) 
      if(histo[i] != 0) 
       tree.add(new Node(histo[i], i)); 

     //combine lowest weights untill only the root is left 
     while(tree.size() > 1){ 
      combine(tree); 
     } 

     //recursively generate code for each node in the tree 
     //if the recursion finds a leaf node, 
     //it sets the correct element in the array to the code of the node 
     Node root = tree.get(0); 
     String[] codage = new String[histo.length]; 
     root.generateCodes(codage); 

     return codage; 
    } 

    /** 
    * Sorts the list and combines the first two nodes in the list to a single node. 
    */ 
    private static void combine(List<Node> list){ 

     if(list.size() < 2) 
      return; 

     Collections.sort(list); 

     Node smallest = list.remove(0); 
     Node secondToSmallest = list.remove(0); 

     Node parent = new Node(secondToSmallest, smallest, smallest.getValue()+secondToSmallest.getValue()); 

     list.add(0, parent); 
    } 

（ノートは、私はハフマン符号の正確性について全くわからないんだけど、コードは動作するはずです）：

私はあなたがそうのように、ツリー構造で動作するように助言しますツリーの単純なノードクラスを作成しました。

public class Node implements Comparable<Node>{ 

private final Node left; 
private final Node right; 
private final int value; 
private final int index; 
private String code = ""; 

public Node(Node left, Node right, int value){ 
    this.left = left; 
    this.right = right; 
    this.value = value; 
    this.index = -1; 
} 

public Node(int value, int index){ 
    this.index = index; 
    this.value = value; 
    this.left = null; 
    this.right = null; 
} 

public void generateCodes(String[] codes){ 
    if(left != null && right != null){ 
     left.setCode("0"+getCode()); 
     left.generateCodes(codes); 
     right.setCode("1"+getCode()); 
     right.generateCodes(codes); 
    }else{ 
     codes[index] = getCode(); 
    } 
} 

private void setCode(String code){ 
    this.code = code; 
} 

public String getCode(){ 
    return code; 
} 

public Node getLeft() { 
    return left; 
} 

public Node getRight() { 
    return right; 
} 

public int getValue(){ 
    return value; 
} 

public int getIndex() { 
    return index; 
} 

@Override 
public int compareTo(Node other) { 
    if(other == null) 
     return -1; 

    return Integer.compare(getValue(), other.getValue()); 
} 

}