HuffmanTree.java.html

  1  import java.util.HashMap;
  2  import java.util.Map;
  3  import java.util.PriorityQueue;
  4  
  5  /**
  6     A tree for decoding Huffman codes.
  7  */
  8  public class HuffmanTree
  9  {
 10     private Node root;
 11  
 12     /**
 13        Constructs a Huffman tree from given character frequencies.
 14        @param frequencies a map whose keys are the characters to be encoded
 15        and whose values are the frequencies of the characters
 16     */
 17     public HuffmanTree(Map<Character, Integer> frequencies) 
 18     {
 19        PriorityQueue<Node> nodes = new PriorityQueue<Node>();
 20        for (char ch : frequencies.keySet())
 21        {
 22           Node newNode = new Node();
 23           newNode.character = ch;
 24           newNode.frequency = frequencies.get(ch);
 25           nodes.add(newNode);
 26        }
 27  
 28        while (nodes.size() > 1)
 29        {
 30           Node smallest = nodes.remove();
 31           Node nextSmallest = nodes.remove();
 32           Node newNode = new Node();
 33           newNode.frequency = smallest.frequency + nextSmallest.frequency;
 34           newNode.left = smallest;
 35           newNode.right = nextSmallest;
 36           nodes.add(newNode);
 37        }
 38  
 39        root = nodes.remove();      
 40     }
 41  
 42     /**
 43        Decodes an encoded string.
 44        @param input a string made up of 0 and 1
 45     */
 46     public String decode(String input)
 47     {
 48        String result = "";
 49        Node n = root;
 50        for (int i = 0; i < input.length(); i++)
 51        {
 52           char ch = input.charAt(i);
 53           if (ch == '0')
 54           {
 55              n = n.left;
 56           }
 57           else
 58           {
 59              n = n.right;
 60           }
 61           if (n.left == null) // n is a leaf
 62           {
 63              result = result + n.character;
 64              n = root;
 65           }
 66        }
 67        return result;
 68     }
 69  
 70     public Map<Character, String> getEncodingMap()
 71     {
 72        Map<Character, String> map = new HashMap<Character, String>();
 73        if (root != null) { root.fillEncodingMap(map, ""); }
 74        return map;
 75     }
 76  
 77     class Node implements Comparable<Node>
 78     {
 79        public char character;
 80        public int frequency;
 81        public Node left;
 82        public Node right;
 83  
 84        public int compareTo(Node other) { return frequency - other.frequency; }
 85  
 86        public void fillEncodingMap(Map<Character, String> map, String prefix)
 87        {
 88           if (left == null) // it's a leaf
 89           {
 90              map.put(character, prefix);
 91           }
 92           else
 93           {
 94              left.fillEncodingMap(map, prefix + "0");
 95              right.fillEncodingMap(map, prefix + "1");
 96           }
 97        }
 98     }
 99  }
100