.. _Huffman:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "Huffman";ODSA.SETTINGS.MODULE_LONG_NAME = "Huffman Coding Trees";ODSA.SETTINGS.MODULE_CHAPTER = "Week 6"; ODSA.SETTINGS.BUILD_DATE = "2016-11-29 20:59:56"; ODSA.SETTINGS.BUILD_CMAP = false;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='java';</script>


.. |--| unicode:: U+2013   .. en dash
.. |---| unicode:: U+2014  .. em dash, trimming surrounding whitespace
   :trim:


.. This file is part of the OpenDSA eTextbook project. See
.. http://algoviz.org/OpenDSA for more details.
.. Copyright (c) 2012-2013 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Cliff Shaffer

.. odsalink:: DataStructures/huffman.css


==============
Huffman Coding
==============

Huffman Coding
--------------

Coding
~~~~~~
   * ASCII codes are fixed length (7 + 1 bits)
      * In general, $n$ bits can store $2^n$ codes
   * An alternative is variable-length coding

   * The relative frequencies for eight selected letters.

      .. math::

         \begin{array}{|c|cccccccc|}
         \hline
         \textrm Letter & C & D & E & K & L & M & U & Z\\
         \textrm Frequency & 32 & 42 & 120 & 7 & 42 & 24 & 37 & 2\\
         \hline
         \end{array}

Huffman Coding Trees
~~~~~~~~~~~~~~~~~~~~
   .. odsalink:: AV/Binary/huffmanCON.css

   .. inlineav:: huffmanBuildCON ss
      :long_name: Huffman Coding Tree Slideshow: Build
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: DataStructures/huffman.js
   .. odsascript:: AV/Binary/huffmanBuildCON.js


Assigning Codes
~~~~~~~~~~~~~~~

   .. inlineav:: huffmanLabelCON ss
      :long_name: Huffman Coding Tree Slideshow: Label Edges
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/Binary/huffmanLabelCON.js


Using Codes
~~~~~~~~~~~

   .. inlineav:: huffmanCodesCON ss
      :long_name: Huffman Coding Tree Slideshow: Setting Codes
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/Binary/huffmanCodesCON.js


Decoding
~~~~~~~~

   .. inlineav:: huffmanDecodeCON ss
      :long_name: Huffman Coding Tree Slideshow: Decoding
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/Binary/huffmanDecodeCON.js


Tree vs. Trie (1)
~~~~~~~~~~~~~~~~~
   .. odsalink:: AV/Development/TreeTrieCON.css

   .. inlineav:: TreeTimelineCON ss
      :long_name: Tree timeline Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/Development/TreeTimelineCON.js


Tree vs. Trie (2)
~~~~~~~~~~~~~~~~~
   .. inlineav:: TrieTimelineCON ss
      :output: show

   .. odsascript:: AV/Development/TrieTimelineCON.js