如何计算霍夫曼码上的位数？

Question

我正在尝试计算txt文件的字节数。为了做到这一点，我必须计算哈夫曼编码的压缩效率。我有三节关于霍夫曼的课。

在主类中：

Scanner s = new Scanner(System.in);
    // creating a priority queue q.
    // makes a min-priority queue(min-heap).
    PriorityQueue<HuffmanNode> q
            = new PriorityQueue<HuffmanNode>(count.length, new MyComparator());

    for (int i = 0; i < count.length; i++) {

        // creating a Huffman node object
        // and add it to the priority queue.
        HuffmanNode hn = new HuffmanNode();

        hn.c = alphabet[i];
        hn.data = count[i];

        hn.left = null;
        hn.right = null;

        // add functions adds
        // the huffman node to the queue.
        q.add(hn);
    }

    // create a root node
    HuffmanNode root = null;

    // Here we will extract the two minimum value
    // from the heap each time until
    // its size reduces to 1, extract until
    // all the nodes are extracted.
    while (q.size() > 1) {

        // first min extract.
        HuffmanNode x = q.peek();
        q.poll();

        // second min extarct.
        HuffmanNode y = q.peek();
        q.poll();

        // new node f which is equal
        HuffmanNode f = new HuffmanNode();

        // to the sum of the frequency of the two nodes
        // assigning values to the f node.
        f.data = x.data + y.data;
        f.c = '-';

        // first extracted node as left child.
        f.left = x;

        // second extracted node as the right child.
        f.right = y;

        // marking the f node as the root node.
        root = f;

        // add this node to the priority-queue.
        q.add(f);
    }

    // print the codes by traversing the tree
    Huffman.printCode(root, "");

Huffman类：

public class Huffman {
// recursive function to print the
// huffman-code through the tree traversal.
// Here s is the huffman - code generated.
public static void printCode(HuffmanNode root, String s)
{
    // base case; if the left and right are null
    // then its a leaf node and we print
    // the code s generated by traversing the tree.
    if (root.left
            == null
            && root.right
            == null
            && Character.isLetter(root.c)) {

        // c is the character in the node
        System.out.println(root.c + ":" + s);

        return;
    }

    // if we go to left then add "0" to the code.
    // if we go to the right add"1" to the code.

    // recursive calls for left and
    // right sub-tree of the generated tree.
    printCode(root.left, s + "0");
    printCode(root.right, s + "1");
}

还有两个关于设置对象的类和一个用于节点比较的类。Huffman工作得很好，我得到了以下结果：

t:000
c:00100
g:00101
d:0011
w:01000
u:01001
r:0101
e:011
s:1000
n:1001
h:1010
i:1011
o:1100
b:110100... //for the rest aphabet letters. 

我需要的是计算每个字母显示的位数，并将它们保存到一个整数数组中，例如t:3 o:4(...)

有什么想法吗？

Answer 1

您希望创建一个< Character，int[] >类型的映射作为Huffman类的私有属性。然后，在if语句的主体中，您希望在map中放入一个新的对，该对是您拥有的字符和字符串。在您的例子中，应该是root.c和s。

因为它是一个字符串，你当然需要将它转换成一个整数数组。你可以在这里找到简单的方法：Converting String Array to an Integer Array。

然后，您可以创建一个方法，该方法从Huffman类调用属性(即map)，然后从map调用您想要的任何数组。

因此，您的Huffman类必须成为一个带有构造函数的对象，因此您将创建一个Huffman对象，然后运行您的print代码方法，然后从Huffman对象中获取地图。