주파수 배열에서 허프만 코딩 (자바로)

Question

허프만 코드에 문제가 있습니다. main 메서드에서 나는 Symbols 빈도를 포함하는 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

문제는 코드에 비트를 추가 할 때 코드를 현재 색인에만 추가한다는 것입니다 (모든 코드에 적용되지는 않습니다). 나무의 ldren). 나는했습니다

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

}