我的霍夫曼代码有问题。在main方法中,我输入一个包含Symbols频率的Integer数组。它应该打印出每个Symbol及其Huffman代码,但我认为出了点问题
在主要方面:
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
最佳答案
您的问题是,当您向代码中添加一些代码时,只会将其添加到当前索引(而不是树的所有子代)中。
我建议您使用树结构,如下所示:(请注意,我不确定霍夫曼代码的正确性,但是该代码应该可以工作)
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());
}
}
关于java - 频率阵列的霍夫曼编码(Java),我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/43913784/