Huffman code implementation

Question

I'm looking for code review, optimizations, best practices.

/**
 * 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

Great Start

• Clear code
• Short methods
• JavaDoc
• Tests (though they need reorganizing as palacsint noted)

Encapsulate

Separate and encapsulate some of the logic into custom classes rather than passing around collections directly. Doing so improves testability and reusability. One prime example is the character frequency map which could easily be reused in many other programs.

Here's a simple implementation that provides only what's necessary for this program, but it could certainly benefit from methods such as size(), getCount(Character c), etc. I also haven't bothered wrapping the exposed map/set in unmodifiable collections which would be advisable (though see below for another option).

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

To avoid exposing the underlying map you could go further by using a closure (Java 8) or anonymous visitor class:

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

I would perform the same encapsulation with HuffmanTree building and managing the nodes from the CharacterCounter.

Miscellaneous

• Provide a two-argument constructor for HuffmanNode that defaults the other parameters to null.

• Implement Comparable<HuffmanNode> directly for natural ordering instead of supplying a separate Comparator to the priority queue.

• Be careful not to include too much code detail in the comments. As the code changes, the comments become incorrect. Case in point:

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

  The first line is unnecessary since it's in the method signature, and the second line mentions the parameter should be a TreeSet which is not correct.

• Thanks to the garbage collector this is totally unnecessary:

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

  Since nodeQueue is local and never exposed externally, it will be collected along with its reference to the root node.

Answer 2

1. Currently both compress() and expand() are static methods in the class which limits its usability. Only one thread can compress/expand only one string. It could have a better API which stores the encoded in memory and allows creating multiple encoded data at the same time.

2. The code contains a lot of hard-coded paths, like /Users/ap/Desktop/tree. The tests fail with FileNotFoundException because on my system the class could not create these files/directories due to file system permission settings. If they are temporary files they should be created in the java.io.tmpdir directory. If not, they should be set by the clients of the class.

3. It's great that you have self-checking test! They are usually in a Test file (HuffmanTest, in this case) run by JUnit. They are also in a separated source folder which enables to not package junit.jar (and other test dependencies) with production code.

   import static org.junit.Assert.assertEquals;
   
   import org.junit.Test;
   
   public class HuffmanTest {
   
       @Test
       public void testHuffman() throws Exception {
           Huffman.compress("some");
           assertEquals("some", Huffman.expand());
       }
   
       @Test
       public void testOddNumberOfCharacters() throws Exception {
           // odd number of characters
           Huffman.compress("someday");
           assertEquals("someday", Huffman.expand());
       }
   
       @Test
       public void testRepeatingEvenNumberOfCharactersAndSpaceAndNonAsciiCharacters() throws Exception {
           Huffman.compress("some some#");
           assertEquals("some some#", Huffman.expand());
   
       }
   
       @Test
       public void testOddNumberOfCharactersAndSpaceAndNonAscii() throws Exception {
           Huffman.compress("someday someday&");
           assertEquals("someday someday&", Huffman.expand());
       }
   }
   

   A few other modifications:

   • static import of assertEquals for less clutter,
   • separate test methods for defect localization (in the original code if the first assert throws an exception you won't know that the others are failed or not),
   • comments turned to test method names (see Clean Code by Robert C. Martin, Don’t Use a Comment When You Can Use a Function or a Variable, p67),
   • changed the three exceptions in the signature to only throws Exception. JUnit will catch all exceptions (as well as JRE, you can do the same with the main method).

Answer 3

Reading the code you assume that:

1. Data is always serialised to the same location on disk.
2. Data is always decoded from the same location on disk.
3. Your source alphabet can only consist of UTF-16 codepoints.

Number 1 and 2 are bad in my humble opinion. You might want to do something else with the compressed data at some point, like encode it in base64 and transmit to a webpage in text mode. Number 3 is so-so depending on how you use the Huffman coder.

I disagree with the accepted answer that the code is clear.

There is a limit when small functions become too many and I believe you have crossed that line. It is difficult to follow the algorithm in order to verify correct implementation (I understand Huffman it's just difficult to follow with jumping across all functions).

Test that your compressed data is smaller than the source data

Your tests should really be unit tests as palacsint says in their answer. Also the probably most important test that you should do is to see that the compressed data is smaller than the original data.

Specifically, any correctly implemented Huffman coder should perform very closely to Shannon's Source Coding Theorem. For sufficiently many samples you should be within 1% of the limit in that link.

Other comments

You are generating your prefix codes as strings and by doing string addition. I find this kind of code difficult to follow as you are covering up the fact that you are doing bit arithmetic.

I would use a natural ordering for the nodes instead of implementing a comparator class.

I do not see any mention of a stop symbol which prevents accidental decoding of junk when your output bitstream is not an even multiple of 8 bits.

And this:

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

I would do it like this to avoid the nesting:

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

The IntObject class seems like a work around for a problem with passing integers as arguments, I would structure my code so that this is not needed.