Download code

Jump to: navigation, search

Back to Huffman_coding_(Java)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

Hufftree.java

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Huffman_coding_(Java)?oldid=12343
 14 */
 15 
 16 import java.util.Stack;
 17 import java.util.Map;
 18 import java.util.HashMap;
 19 import java.util.PriorityQueue;
 20 import java.util.Arrays;
 21 import java.util.List;
 22 import java.util.ArrayList;
 23 import java.util.Collection;
 24 
 25 public class Hufftree<E extends Comparable<? super E>>
 26 {
 27   public Hufftree(Map<E,Double> frequencies)
 28   {
 29     PriorityQueue<Node<E>> pqueue = new PriorityQueue<Node<E>>();
 30     assert frequencies.size() > 1; // will not work with 0 or 1 symbols
 31 
 32     for (Map.Entry<E,Double> e : frequencies.entrySet())
 33     {
 34       pqueue.offer(new Leaf<E>(e.getValue(), e.getKey()));
 35     }
 36     while (true)
 37     {
 38       Node<E> top = pqueue.poll();
 39       if (pqueue.isEmpty())
 40       {
 41         tree = top;
 42         break;
 43       }
 44       else
 45       {
 46         Node<E> top2 = pqueue.poll();
 47         pqueue.offer(new Internal<E>(top, top2));
 48       }
 49     }
 50     Stack<Boolean> bitvec = new Stack<Boolean>();
 51     tree.fill(encoding, bitvec);
 52   }
 53   public List<Boolean> encode(E value)
 54   {
 55     return Arrays.asList(encoding.get(value));
 56   }
 57   public List<Boolean> encode(Iterable<E> c)
 58   {
 59     List<Boolean> result = new ArrayList<Boolean>();
 60     for (E x : c)
 61     {
 62       result.addAll(encode(x));
 63     }
 64     return result;
 65   }
 66   public Collection<E> decode(List<Boolean> v)
 67   {
 68     Collection<E> result = new ArrayList<E>();
 69     Node<E> node = tree;
 70     for (Boolean b : v)
 71     {
 72       Internal<E> i = (Internal<E>)node;
 73       node = b ? i.rightChild : i.leftChild;
 74       if (node instanceof Leaf)
 75       {
 76         result.add(((Leaf<E>)node).data);
 77         node = tree;
 78       }
 79     }
 80 
 81     assert node == tree;
 82     return result;
 83   }
 84   public static void main(String[] args)
 85   {
 86     Map<Character,Double> frequencies = new HashMap<Character,Double>();
 87     frequencies.put('e', 0.124167);
 88     frequencies.put('a', 0.0820011);
 89     frequencies.put('t', 0.0969225);
 90     frequencies.put('i', 0.0768052);
 91     frequencies.put('n', 0.0764055);
 92     frequencies.put('o', 0.0714095);
 93     frequencies.put('s', 0.0706768);
 94     frequencies.put('r', 0.0668132);
 95     frequencies.put('l', 0.0448308);
 96     frequencies.put('d', 0.0363709);
 97     frequencies.put('h', 0.0350386);
 98     frequencies.put('c', 0.0344391);
 99     frequencies.put('u', 0.028777);
100     frequencies.put('m', 0.0281775);
101     frequencies.put('f', 0.0235145);
102     frequencies.put('p', 0.0203171);
103     frequencies.put('y', 0.0189182);
104     frequencies.put('g', 0.0181188);
105     frequencies.put('w', 0.0135225);
106     frequencies.put('v', 0.0124567);
107     frequencies.put('b', 0.0106581);
108     frequencies.put('k', 0.00393019);
109     frequencies.put('x', 0.00219824);
110     frequencies.put('j', 0.0019984);
111     frequencies.put('q', 0.0009325);
112     frequencies.put('z', 0.000599);
113     Hufftree<Character> hufftree = new Hufftree<Character>(frequencies);
114     for (char ch = 'a'; ch <= 'z'; ++ch)
115     {
116       System.out.println(ch + ": " + hufftree.encode(ch));
117     }
118     String source = "literateprogramming";
119     System.out.println(source);
120 
121     List<Character> sourceArray = new ArrayList<Character>();
122     for (int i = 0; i < source.length(); i++)
123       sourceArray.add(source.charAt(i));
124 
125     List<Boolean> encoded = hufftree.encode(sourceArray);
126     System.out.println(encoded);
127 
128     Collection<Character> destination = hufftree.decode(encoded);
129     System.out.println(destination);
130   }
131   private Node<E> tree;
132 
133   private final Map<E,Boolean[]> encoding = new HashMap<E,Boolean[]>();
134 }
135 abstract class Node<E extends Comparable<? super E>> implements Comparable<Node<E>>
136 {
137   protected final double frequency;
138   protected Node(double f) { frequency = f; }
139 
140   public abstract void fill(Map<E,Boolean[]> encoding,
141                             Stack<Boolean> prefix);
142   public int compareTo(Node<E> b)
143   {
144     if (frequency != b.frequency)
145       return Double.compare(frequency, b.frequency);
146     else if (this instanceof Leaf && b instanceof Internal)
147       return -1;
148     else if (this instanceof Internal && b instanceof Leaf)
149       return 1;
150     else if (this instanceof Internal && b instanceof Internal)
151     {
152       Internal<E> a = (Internal<E>)this,
153                   z = (Internal<E>)b;
154       if (!a.leftChild.equals(z.leftChild))
155         return a.leftChild.compareTo(z.leftChild);
156       else
157         return a.rightChild.compareTo(z.rightChild);
158     }
159     else
160       return ((Leaf<E>)this).data.compareTo(((Leaf<E>)b).data);
161   }
162 }
163 class Leaf<E extends Comparable<? super E>> extends Node<E>
164 {
165   public final E data;
166   public Leaf(double f, E d) {
167     super(f);
168     data = d;
169   }
170 
171   public void fill(Map<E,Boolean[]> encoding,
172                    Stack<Boolean> prefix)
173   {
174       encoding.put(data, prefix.toArray(new Boolean[0]));
175   }
176 }
177 class Internal<E extends Comparable<? super E>> extends Node<E>
178 {
179   public final Node<E> leftChild, rightChild;
180   public Internal(Node<E> l, Node<E> r) {
181     super(l.frequency + r.frequency);
182     leftChild = l;
183     rightChild = r;
184   }
185 
186   public void fill(Map<E,Boolean[]> encoding,
187                    Stack<Boolean> prefix)
188   {
189       prefix.push(false);
190       leftChild.fill(encoding, prefix);
191       prefix.pop();
192       prefix.push(true);
193       rightChild.fill(encoding, prefix);
194       prefix.pop();
195   }
196 }
197 


hijacker
hijacker
hijacker
hijacker