java - 哈夫曼码解释Java

Question

我是java新手，我正在尝试通过使用在线代码来理解霍夫曼编码。我正在弄乱代码以了解它是如何工作的，因为我没有找到有关如何实现霍夫曼代码的任何内容。我需要理解为什么在这段代码中，这个人在霍夫曼树类和字符串缓冲区中使用了可比的。如果有人知道在线霍夫曼编码甚至算法的任何好的解释，请。我真的需要理解这段代码。PS:英语不是我的母语，所以很抱歉造成任何困惑。谢谢

import java.util.*;

public class HuffmanCode {
    // input is an array of frequencies, indexed by character code
    public HuffmanTree buildTree(int[] charFreqs) {
        PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>();
        // initially, we have a forest of leaves
        // one for each non-empty character
        for (int i = 0; i < charFreqs.length; i++)
            if (charFreqs[i] > 0)
                trees.offer(new HuffmanLeaf(charFreqs[i], (char)i));

        assert trees.size() > 0;
        // loop until there is only one tree left
        while (trees.size() > 1) {
            // two trees with least frequency
            HuffmanTree a = trees.poll();
            HuffmanTree b = trees.poll();

            // put into new node and re-insert into queue
            trees.offer(new HuffmanNode(a, b));
        }
        return trees.poll();
    }

    public void printCodes(HuffmanTree tree, StringBuffer prefix) {
        assert tree != null;
        if (tree instanceof HuffmanLeaf) {
            HuffmanLeaf leaf = (HuffmanLeaf)tree;

            // print out character, frequency, and code for this leaf (which is just the prefix)
            System.out.println(leaf.value + "\t" + leaf.frequency + "\t" + prefix);

        } else if (tree instanceof HuffmanNode) {
            HuffmanNode node = (HuffmanNode)tree;

            // traverse left
            prefix.append('0');
            //prefix = prefix + "0";
            printCodes(node.left, prefix);
            prefix.deleteCharAt(prefix.length()-1);

            // traverse right
            prefix.append('1');
            printCodes(node.right, prefix);
            prefix.deleteCharAt(prefix.length()-1);
        }
    }
}

哈夫曼树类:

public class HuffmanTree implements Comparable<HuffmanTree> {
    public final int frequency; // the frequency of this tree

    public HuffmanTree(int freq) {
        frequency = freq;
    }

    // compares on the frequency
    public int compareTo(HuffmanTree tree) {
        return frequency - tree.frequency;
    }
}

霍夫曼叶:

class HuffmanLeaf extends HuffmanTree {

    public final char value; // the character this leaf represents

    public HuffmanLeaf(int freq, char val) {
        super(freq);
        value = val;
    }
}

霍夫曼节点:

class HuffmanNode extends HuffmanTree {

    public final HuffmanTree left, right; // subtrees

    public HuffmanNode(HuffmanTree l, HuffmanTree r) {
        //Calling the super  constructor HuffmanTree 
        super(l.frequency + r.frequency);
        left = l;
        right = r;
    }

}

主要:

public class Main {

    public static void main(String[] args) {
        String test = "Hello World";
        HuffmanCode newCode = new HuffmanCode();

        // we will assume that all our characters will have
        // code less than 256, for simplicity
        int[] charFreqs = new int[256];
        // read each character and record the frequencies
        for (char c : test.toCharArray())
            charFreqs[c]++;

        // build tree
        ////HuffmanTree tree = buildTree(charFreqs);
        HuffmanTree tree = newCode.buildTree(charFreqs);

        // print out results
        System.out.println("SYMBOL\tWEIGHT\tHUFFMAN CODE");
        newCode.printCodes(tree, new StringBuffer());
    }

}

Answer 1

why did the guy used Stringbuffer

因为使用一个字符串构建字符串比串联字符串更受欢迎。

StringBuilder vs String concatenation in toString() in Java

When to use StringBuilder in Java

等等...

StringBuilder 与 StringBuffer 略有不同

Why use StringBuilder? StringBuffer can work with multiple thread as well as one thread?

and comparable

因为使用了优先级队列。它需要那个接口(interface)。

How do I use a PriorityQueue?

并且，阅读霍夫曼编码维基百科页面(您可以通过该页面来理解算法)，其中提到编码的最佳结构是有序的。我个人不了解该算法，但我建议不要从互联网上复制您不理解的代码。