java - 从频率数组进行霍夫曼编码(Java 中)

Question

我的霍夫曼代码有问题。在主要方法中，我输入一个包含符号频率的整数数组。它应该打印出每个符号及其霍夫曼代码，但我认为有些问题

主要内容:

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

您的问题是，当您向代码添加一点时，您仅将其添加到当前索引(而不是树的所有子级)。

我建议您使用树结构，如下所示:(注意，我不完全确定霍夫曼代码的正确性，但代码应该可以工作)

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

}