Huffman代码实现

Question

我正在寻找代码评审、优化、最佳实践。

/**
 * Huffman encoding obeys the huffman algorithm.
 * It compresses the input sentence and serializes the "huffman code"
 * and the "tree" used to generate  the huffman code
 * Both the serialized files are intended to be sent to client.
 * 
 */
public final class Huffman {

    private Huffman() {};

    private static class HuffmanNode {
        char ch;
        int frequency;
        HuffmanNode left;
        HuffmanNode right;

        HuffmanNode(char ch, int frequency,  HuffmanNode left,  HuffmanNode right) {
            this.ch = ch;
            this.frequency = frequency;
            this.left = left;
            this.right = right;
        }
    }

    private static class HuffManComparator implements Comparator<HuffmanNode> {
        @Override
        public int compare(HuffmanNode node1, HuffmanNode node2) {
            return node1.frequency - node2.frequency;
        }
    }

    /**
     * Compresses the string using huffman algorithm.
     * The huffman tree and the huffman code are serialized to disk
     * 
     * @param sentence                  The sentence to be serialized
     * @throws FileNotFoundException    If file is not found
     * @throws IOException              If IO exception occurs.
     */ 
    public static void compress(String sentence) throws FileNotFoundException, IOException {
        if (sentence == null) {
            throw new NullPointerException("Input sentence cannot be null.");
        }
        if (sentence.length() == 0) {
            throw new IllegalArgumentException("The string should atleast have 1 character.");
        }

        final Map<Character, Integer> charFreq = getCharFrequency(sentence); 
        final HuffmanNode root = buildTree(charFreq);
        final Map<Character, String> charCode = generateCodes(charFreq.keySet(), root);
        final String encodedMessage = encodeMessage(charCode, sentence);
        serializeTree(root);
        serializeMessage(encodedMessage);
    }

    private static Map<Character, Integer> getCharFrequency(String sentence) {
        final Map<Character, Integer> map = new HashMap<Character, Integer>();

        for (int i = 0; i < sentence.length(); i++) {
            char ch = sentence.charAt(i);
            if (!map.containsKey(ch)) {
                map.put(ch, 1);
            } else {
                int val = map.get(ch);
                map.put(ch, ++val);
            }
        }

        return map;
    }


    /** 
     * Map<Character, Integer> map
     * Some implementation of that treeSet is passed as parameter.
     * @param map
     */
    private static HuffmanNode buildTree(Map<Character, Integer> map) {
        final Queue<HuffmanNode> nodeQueue = createNodeQueue(map);

        while (nodeQueue.size() > 1) {
            final HuffmanNode node1 = nodeQueue.remove();
            final HuffmanNode node2 = nodeQueue.remove();
            HuffmanNode node = new HuffmanNode('\0', node1.frequency + node2.frequency, node1, node2);
            nodeQueue.add(node);
        }

        // remove it to prevent object leak.
        return nodeQueue.remove();
    }

    private static Queue<HuffmanNode> createNodeQueue(Map<Character, Integer> map) {
        final Queue<HuffmanNode> pq = new PriorityQueue<HuffmanNode>(11, new HuffManComparator());
        for (Entry<Character, Integer> entry : map.entrySet()) {
            pq.add(new HuffmanNode(entry.getKey(), entry.getValue(), null, null));
        }
        return pq;
    }

    private static Map<Character, String> generateCodes(Set<Character> chars, HuffmanNode node) {
       final Map<Character, String> map = new HashMap<Character, String>();
       doGenerateCode(node, map, "");
       return map;
    }


    private static void doGenerateCode(HuffmanNode node, Map<Character, String> map, String s) {
        if (node.left == null && node.right == null) {
            map.put(node.ch, s);
            return;
        }    
        doGenerateCode(node.left, map, s + '0');
        doGenerateCode(node.right, map, s + '1' );
    }


    private static String encodeMessage(Map<Character, String> charCode, String sentence) {
        final StringBuilder stringBuilder = new StringBuilder();

        for (int i = 0; i < sentence.length(); i++) {
            stringBuilder.append(charCode.get(sentence.charAt(i)));
        }
        return stringBuilder.toString();
    }

    private static void serializeTree(HuffmanNode node) throws FileNotFoundException, IOException {
        final BitSet bitSet = new BitSet();
        try (ObjectOutputStream oosTree = new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/tree"))) {
            try (ObjectOutputStream oosChar = new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/char"))) {
                IntObject o = new IntObject();
                preOrder(node, oosChar, bitSet, o);
                bitSet.set(o.bitPosition, true); // padded to mark end of bit set relevant for deserialization.
                oosTree.writeObject(bitSet);
            }
        }
    }

    private static class IntObject {
        int bitPosition;
    }

    /*
     * Algo:
     * 1. Access the node
     * 2. Register the value in bit set.
     * 
     * 
     * here true and false dont correspond to left branch and right branch.
     * there,
     * - true means "a branch originates from leaf"
     * - false mens "a branch originates from non-left".
     * 
     * Also since branches originate from some node, the root node must be provided as source 
     * or starting point of initial branches.
     *     
     * Diagram and how an bit set would look as a result.
     *              (source node)
     *             /             \
     *          true             true
     *           /                  \
     *       (leaf node)        (leaf node)
     *          |                     |
     *        false                  false 
     *          |                     |
     *          
     * So now a bit set looks like [false, true, false, true]          
     * 
     */
    private static void preOrder(HuffmanNode node, ObjectOutputStream oosChar, BitSet bitSet, IntObject intObject) throws IOException {
        if (node.left == null && node.right == null) {
            bitSet.set(intObject.bitPosition++, false);  // register branch in bitset
            oosChar.writeChar(node.ch);
            return;                                  // DONT take the branch.
        }
        bitSet.set(intObject.bitPosition++, true);           // register branch in bitset
        preOrder(node.left, oosChar, bitSet, intObject); // take the branch.

        bitSet.set(intObject.bitPosition++, true);               // register branch in bitset
        preOrder(node.right, oosChar, bitSet, intObject);    // take the branch.
    }

    private static void serializeMessage(String message) throws IOException {
        final BitSet bitSet = getBitSet(message);

        try (ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/encodedMessage"))){

            oos.writeObject(bitSet);
        } 
    }

    private static BitSet getBitSet(String message) {
        final BitSet bitSet = new BitSet();
        int i = 0;
        for (i = 0; i < message.length(); i++) {
            if (message.charAt(i) == '0') {
                bitSet.set(i, false);
            } else {
                bitSet.set(i, true);
            }
        }
        bitSet.set(i, true); // dummy bit set to know the length 
        return bitSet;
    }

    /**
     * Retrieves back the original string.
     * 
     * 
     * @return                          The original uncompressed string
     * @throws FileNotFoundException    If the file is not found
     * @throws ClassNotFoundException   If class is not found
     * @throws IOException              If IOException occurs
     */
    public static String expand() throws FileNotFoundException, ClassNotFoundException, IOException {
        final HuffmanNode root = deserializeTree();
        return decodeMessage(root);
    }

    private static HuffmanNode deserializeTree() throws FileNotFoundException, IOException, ClassNotFoundException {
        try (ObjectInputStream oisBranch = new ObjectInputStream(new FileInputStream("/Users/ap/Desktop/tree"))) {
            try (ObjectInputStream oisChar = new ObjectInputStream(new FileInputStream("/Users/ap/Desktop/char"))) {
                final BitSet bitSet = (BitSet) oisBranch.readObject();
                return preOrder(bitSet, oisChar, new IntObject());
            }
        }
    }

    /*
     * Construct a tree from: 
     * input [false, true, false, true, (dummy true to mark the end of bit set)]
     * The input is constructed from preorder traversal
     * 
     * Algo:
     * 1  Create the node.
     * 2. Read what is registered in bitset, and decide if created node is supposed to be a leaf or non-leaf 
     * 
     */
    private static HuffmanNode preOrder(BitSet bitSet, ObjectInputStream oisChar, IntObject o) throws IOException {   
        // created the node before reading whats registered.
        final HuffmanNode node = new HuffmanNode('\0', 0, null, null);

        // reading whats registered and determining if created node is the leaf or non-leaf.
        if (!bitSet.get(o.bitPosition)) {
            o.bitPosition++;              // feed the next position to the next stack frame by doing computation before preOrder is called.
            node.ch = oisChar.readChar();
            return node;
        } 

        o.bitPosition = o.bitPosition + 1;  // feed the next position to the next stack frame by doing computation before preOrder is called.
        node.left = preOrder(bitSet, oisChar, o); 

        o.bitPosition = o.bitPosition + 1; // feed the next position to the next stack frame by doing computation before preOrder is called.
        node.right = preOrder(bitSet, oisChar, o);

        return node;
    }

    private static String decodeMessage(HuffmanNode node) throws FileNotFoundException, IOException, ClassNotFoundException {
        try (ObjectInputStream ois = new ObjectInputStream(new FileInputStream("/Users/ameya.patil/Desktop/encodedMessage"))) {
            final BitSet bitSet = (BitSet) ois.readObject();
            final StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < (bitSet.length() - 1);) {
                HuffmanNode temp = node;
                // since huffman code generates full binary tree, temp.right is certainly null if temp.left is null.
                while (temp.left != null) {
                    if (!bitSet.get(i)) {
                        temp = temp.left;
                    } else {
                        temp = temp.right;
                    }
                    i = i + 1;
               }
                stringBuilder.append(temp.ch);
            }
            return stringBuilder.toString();
        }
    }

    public static void main(String[] args) throws FileNotFoundException, IOException, ClassNotFoundException {
        // even number of characters
        Huffman.compress("some");
        Assert.assertEquals("some", Huffman.expand());

        // odd number of characters
        Huffman.compress("someday");
        Assert.assertEquals("someday", Huffman.expand());

        // repeating even number of characters + space + non-ascii
        Huffman.compress("some some#");
        Assert.assertEquals("some some#", Huffman.expand());

        // odd number of characters + space + non-ascii
        Huffman.compress("someday someday&");
        Assert.assertEquals("someday someday&", Huffman.expand());
    }
}

Answer 1

大起点

• 明确码
• 短方法
• JavaDoc
• 测试(尽管需要像palacsint指出的那样进行重组)

封装

将一些逻辑分离并封装到自定义类中，而不是直接传递集合。这样做可以提高可测试性和可重用性。一个主要的例子是字符频率映射，它可以很容易地在许多其他程序中重用。

这里有一个简单的实现，它只提供了这个程序所必需的东西，但它肯定可以从诸如size()、getCount(Character c)等方法中受益。我也没有费心地将公开的映射/集包装在不可修改的集合中，这是可取的(尽管另一个选项见下文)。

/**
 * Keeps a running count of how many times each unique character is seen.
 */
public class CharacterCounter
{
    private final HashMap<Character, Integer> counts = new HashMap<>();

    /**
     * Increments the count of the given character,
     * setting it to one on first appearance.
     *
     * @param c the character to count
     */
    public void increment(Character c) {
        Integer freq = counts.get(c);
        if (freq == null) {
            counts.put(c, 1);
        } else {
            counts.put(c, freq + 1);
        }
    }

    /**
     * Increments the count of each character in the given text.
     *
     * @param text contains the characters to count
     */
    public void increment(String text) {
        for (char c : text) {
            increment(c);
        }
    }

    /**
     * Returns the set of characters seen.
     *
     * @return set containing each character seen while counting
     */
    public Set<Character> getCharacters() {
        return counts.keySet();
    }

    /**
     * Returns the set of characters seen along with their counts.
     *
     * @return set containing each character seen while counting and its count
     */
    public Set<Map.Entry<Character, Integer>> getCharacterCounts() {
        return counts.entrySet();
    }
}

为了避免公开底层映射，您可以使用闭包(Java 8)或匿名访问者类来更进一步：

public class CharacterCounter
{
    ...
    public interface Visitor {
        void visit(Character c, Integer count);
    }

    /**
     * Passes each character and its count to the given visitor.
     *
     * @param visitor receives characters and counts in an undefined order
     */
    public void apply(Visitor visitor) {
        for (Map.Entry<Character, Integer> entry : counts.entrySet()) {
            visitor.visit(entry.getKey(), entry.getValue());
        }
    }
}

private static Queue<HuffmanNode> createNodeQueue(CharacterCounter counter) {
    final Queue<HuffmanNode> pq = new PriorityQueue<>(11, new HuffManComparator());
    counter.apply(new CharacterCounter.Visitor() {
        public void visit(Character c, Integer count) {
            pq.add(new HuffmanNode(c, count, null, null));
        }
    });
    return pq;
}

我将在构建和管理来自HuffmanTree的CharacterCounter节点时执行相同的封装。

Miscellaneous

• 为HuffmanNode提供一个双参数构造函数，该构造函数将其他参数默认为null。
• 直接为自然排序实现Comparable<HuffmanNode>，而不是向优先级队列提供单独的Comparator。
• 注意不要在注释中包含太多的代码细节。随着代码的更改，注释将变得不正确。例如: /** * Map map *该treeSet的某些实现作为参数传递。* @param map */私有静态HuffmanNode buildTree(Map map) {第一行没有必要，因为它在方法签名中，第二行提到的参数应该是不正确的TreeSet。
• 由于垃圾收集器，这是完全不必要的: //删除它，以防止对象泄漏。返回nodeQueue.remove()；由于nodeQueue是本地的，并且从不对外公开，因此将收集它及其对根节点的引用。

Answer 2

阅读您假定的代码：

1. 数据总是序列化到磁盘上的同一位置。
2. 数据总是从磁盘上的同一位置解码。
3. 您的源字母表只能由UTF-16码点组成.

在我看来，第一条和第二条是不好的。您可能希望在某个时候对压缩数据执行其他操作，比如在base64中对其进行编码并以文本模式传输到网页。数字3是如此-所以取决于你如何使用赫夫曼编码器。

我不同意公认的答案，即代码是清楚的.

当小函数变得太多的时候是有限度的，我相信你已经越过了这条线。为了验证正确的实现，很难遵循该算法(我理解Huffman，它只是很难跳过所有函数)。

测试您的压缩数据是否小于源数据

正如palacsint在回答中所说的那样，您的测试应该是单元测试。另外，您应该做的最重要的测试是确保压缩的数据比原始数据小。

具体来说，任何正确实现的Huffman编码器都应该非常接近于Shannon源编码定理。对于足够多的样本，您应该在该链接中限制的1%以内。

其他评论

您正在以字符串的形式生成前缀代码，并执行字符串加法。我发现这样的代码很难理解，因为你掩盖了你在做比特算术的事实。

我将使用节点的自然排序，而不是实现比较器类。

我没有看到任何提到停止符号，以防止意外解码垃圾时，您的输出比特流不是一个偶数的8位。

这是：

    try (ObjectOutputStream oosTree = new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/tree"))) {
        try (ObjectOutputStream oosChar = new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/char"))) {

为了避免筑巢，我会这样做：

    try (ObjectOutputStream oosTree = 
             new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/tree"));
         ObjectOutputStream oosChar = 
             new ObjectOutputStream(new FileOutputStream("/Users/ap/Desktop/char"))) {

IntObject类似乎解决了将整数作为参数传递的问题，因此我会构造代码，这样就不需要这样做了。