(* Content-type: application/mathematica *)

(*** Wolfram Notebook File ***)
(* http://www.wolfram.com/nb *)

(* CreatedBy='Mathematica 6.0' *)

(*CacheID: 234*)
(* Internal cache information:
NotebookFileLineBreakTest
NotebookFileLineBreakTest
NotebookDataPosition[       145,          7]
NotebookDataLength[     15209,        490]
NotebookOptionsPosition[     12887,        409]
NotebookOutlinePosition[     13362,        427]
CellTagsIndexPosition[     13319,        424]
WindowFrame->Normal
ContainsDynamic->False*)

(* Beginning of Notebook Content *)
Notebook[{

Cell[CellGroupData[{
Cell["Huffman Coding and Entropy", "Title",
 CellChangeTimes->{{3.421431042796875*^9, 3.421431044359375*^9}, {
  3.452343150539456*^9, 3.4523431573820343`*^9}}],

Cell["\<\
Wavelet Workshop
June 2-5, 2009
University of South Florida\
\>", "Subtitle",
 CellChangeTimes->{{3.421426484890625*^9, 3.42142648821875*^9}, {
  3.452342828495509*^9, 3.4523428384751987`*^9}}],

Cell["\<\
Catherine Beneteau
Caroline Haddad
David Ruch
Patrick Van Fleet\
\>", "Subsubtitle",
 CellChangeTimes->{{3.42144927371875*^9, 3.42144928703125*^9}}],

Cell[CellGroupData[{

Cell["Overview", "Section",
 CellChangeTimes->{{3.421428159890625*^9, 3.421428161*^9}}],

Cell[CellGroupData[{

Cell["Objectives", "Subsection"],

Cell["\<\
The purpose of this notebook is to give you a brief introduction to the \
software package DiscreteWavelets and show you how to use it to load images.  \
Some basic image manipulation is illustrated as well.  You will learn how to \
use tools such as Huffman coding and measures such as entropy.\
\>", "Text",
 CellChangeTimes->{{3.421456620265625*^9, 3.421456650625*^9}, {
  3.452342844124681*^9, 3.452342853741496*^9}, {3.45234311028869*^9, 
  3.452343115765317*^9}}]
}, Open  ]],

Cell[CellGroupData[{

Cell["DiscreteWavelets", "Subsection"],

Cell[TextData[{
 "You should run this cell each time you open this notebook!!  It loads the \
",
 StyleBox["Mathematica",
  FontSlant->"Italic"],
 " package DiscreteWavelets for use in subsequent computations."
}], "Text",
 CellChangeTimes->{{3.421429438203125*^9, 3.421429441265625*^9}}],

Cell[BoxData[
 RowBox[{"<<", "DiscreteWavelets`DiscreteWavelets`"}]], "Input",
 CellChangeTimes->{{3.421448451359375*^9, 3.42144845165625*^9}}]
}, Open  ]],

Cell[CellGroupData[{

Cell["Help on DiscreteWavelets", "Subsection"],

Cell["\<\
If you ever need help with DiscreteWavelets, go to Help, then Documentation \
Center.  On the bottom right, you will find a link for Installed Add-Ons.  \
Click this link and then the link to  DiscreteWavelets to access \
documentation, examples, and applications of the software package.\
\>", "Text",
 CellChangeTimes->{{3.42142653203125*^9, 3.421426604453125*^9}}]
}, Open  ]]
}, Open  ]],

Cell[CellGroupData[{

Cell["Huffman Coding", "Section",
 CellChangeTimes->{{3.421448365703125*^9, 3.42144836790625*^9}}],

Cell[CellGroupData[{

Cell["MakeHuffmanCodes", "Subsection",
 CellChangeTimes->{{3.4214523053125*^9, 3.421452307875*^9}}],

Cell["\<\
The DiscreteWavelets module MakeHuffmanCodes can be used to generate Huffman \
codes for a list of integers, a string, or a matrix of integers. Note that \
integer input must be nonnegative.

The routine returns three pieces of information.  The first is a list of \
triples.  Each triple consists of an integer or character that appeared in \
the input, its relative frequency in the input, and its Huffman code.  The \
second output is the original bitstream length and the third output is the \
new bitstream length.\
\>", "Text",
 CellChangeTimes->{{3.42145173325*^9, 3.42145177953125*^9}, {
  3.42145186346875*^9, 3.42145196303125*^9}}],

Cell[BoxData[{
 RowBox[{
  RowBox[{
   RowBox[{"{", 
    RowBox[{"codes", ",", "origlen", ",", "newlen"}], "}"}], "=", 
   RowBox[{"MakeHuffmanCodes", "[", "\"\<pitterpatter\>\"", "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{"MatrixForm", "[", "codes", "]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"Print", "[", 
   RowBox[{
   "\"\<The original bitstream length is \>\"", ",", "origlen", ",", " ", 
    "\"\< and the new bitstream length is \>\"", ",", "newlen", ",", 
    "\"\<.\>\""}], "]"}], ";"}]}], "Input",
 CellChangeTimes->{{3.421451636859375*^9, 3.421451643765625*^9}, {
   3.421451698828125*^9, 3.42145170846875*^9}, 3.42145178834375*^9, {
   3.42145196678125*^9, 3.421452049109375*^9}}],

Cell["We can also find the Huffman codes of an image:", "Text",
 CellChangeTimes->{{3.4214522941875*^9, 3.421452317640625*^9}}],

Cell[BoxData[{
 RowBox[{
  RowBox[{"img", "=", 
   RowBox[{"ImageNames", "[", 
    RowBox[{
     RowBox[{"ImageType", "\[Rule]", "GrayScale"}], ",", 
     RowBox[{"ListThumbnails", "\[Rule]", "True"}]}], "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"A", "=", 
   RowBox[{"ImageRead", "[", 
    RowBox[{"img", "[", 
     RowBox[{"[", "1", "]"}], "]"}], "]"}]}], ";"}], "\[IndentingNewLine]", 
 RowBox[{"ImagePlot", "[", "A", "]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"{", 
    RowBox[{"codes", ",", "origlen", ",", "newlen"}], "}"}], "=", 
   RowBox[{"MakeHuffmanCodes", "[", "A", "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"Print", "[", 
   RowBox[{
   "\"\<The original bitstream length was \>\"", ",", "origlen", ",", 
    "\"\< and the new bitstream length is \>\"", ",", "newlen", ",", 
    "\"\<.\>\""}], "]"}], ";"}]}], "Input",
 CellChangeTimes->{{3.42145231940625*^9, 3.42145239225*^9}, {
  3.421452574234375*^9, 3.421452574375*^9}}]
}, Open  ]],

Cell[CellGroupData[{

Cell["HuffmanTree", "Subsection",
 CellChangeTimes->{{3.421452415953125*^9, 3.4214524175*^9}}],

Cell[TextData[{
 "For small input, we can use ",
 StyleBox["HuffmanTree",
  FontWeight->"Bold"],
 " to visualize the output of ",
 StyleBox["MakeHuffmanCodes",
  FontWeight->"Bold"],
 ".  The input of ",
 StyleBox["HuffmanTree",
  FontWeight->"Bold"],
 " is the first output of ",
 StyleBox["MakeHuffmanCodes",
  FontWeight->"Bold"],
 ".  There are several graphics options for ",
 StyleBox["HuffmanTree",
  FontWeight->"Bold"],
 ".  See the Documentation Center for more information."
}], "Text",
 CellChangeTimes->{{3.42145242296875*^9, 3.421452504625*^9}}],

Cell[BoxData[{
 RowBox[{
  RowBox[{
   RowBox[{"{", 
    RowBox[{"codes", ",", "origlen", ",", "newlen"}], "}"}], "=", 
   RowBox[{"MakeHuffmanCodes", "[", "\"\<tennessee\>\"", "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{"MatrixForm", "[", "codes", "]"}], "\[IndentingNewLine]", 
 RowBox[{"HuffmanTree", "[", "codes", "]"}]}], "Input",
 CellChangeTimes->{{3.42145252715625*^9, 3.421452570078125*^9}}]
}, Open  ]],

Cell[CellGroupData[{

Cell["Exercises", "Subsection",
 CellChangeTimes->{{3.421452655984375*^9, 3.421452658140625*^9}}],

Cell[CellGroupData[{

Cell["Exercise 1", "Subsubsection",
 CellChangeTimes->{{3.421452668578125*^9, 3.42145266946875*^9}, {
  3.4214527864375*^9, 3.4214527865*^9}}],

Cell["\<\
Load the surfer image (small version) from the DiscreteWavelets package and \
find the bits per pixel that results from the Huffman coded version of the \
image.\
\>", "Text",
 CellChangeTimes->{{3.42145279340625*^9, 3.421452815484375*^9}, {
  3.42145294334375*^9, 3.4214529630625*^9}}],

Cell[BoxData[
 RowBox[{"(*", " ", 
  RowBox[{"put", " ", "your", " ", "code", " ", "here"}], " ", 
  "*)"}]], "Input",
 CellChangeTimes->{{3.42145296796875*^9, 3.42145297325*^9}}]
}, Open  ]],

Cell[CellGroupData[{

Cell["Exercise 2 (Challenge)", "Subsubsection",
 CellChangeTimes->{{3.42145297578125*^9, 3.421452978171875*^9}, {
  3.4214532173125*^9, 3.421453219765625*^9}}],

Cell[TextData[{
 "Suppose you pass a string ",
 StyleBox["s",
  FontWeight->"Bold"],
 " to MakeHuffmanCodes.  Write a module that will take the codes returned by \
MakeHuffmanCodes and s and return the new bitstream.  Call the module ",
 StyleBox["MakeBitstream",
  FontWeight->"Bold"],
 ".\n\nFor example:"
}], "Text",
 CellChangeTimes->{{3.421453221859375*^9, 3.42145331728125*^9}, {
  3.421453409640625*^9, 3.421453419328125*^9}}],

Cell[BoxData[{
 RowBox[{
  RowBox[{"s", "=", "\"\<boohoo\>\""}], ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{
   RowBox[{"{", 
    RowBox[{"codes", ",", "origlen", ",", "newlen"}], "}"}], "=", 
   RowBox[{"MakeHuffmanCodes", "[", "s", "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{"HuffmanTree", "[", "codes", "]"}]}], "Input",
 CellChangeTimes->{{3.42145331946875*^9, 3.421453355625*^9}, {
  3.421453462390625*^9, 3.4214534625*^9}}],

Cell["\<\
Using the tree above and s, we see that the new bitstream for \"boohoo\" is \
01110011.\
\>", "Text",
 CellChangeTimes->{{3.42145336553125*^9, 3.42145340290625*^9}}],

Cell[BoxData[
 RowBox[{
  RowBox[{
   RowBox[{
    RowBox[{"MakeBitStream", "[", 
     RowBox[{"s_", ",", "codes_"}], "]"}], ":=", 
    RowBox[{"Module", "[", 
     RowBox[{"{", 
      RowBox[{"(*", " ", 
       RowBox[{"put", " ", "local", " ", "variables", " ", "here"}], " ", 
       "*)"}], ",", "\[IndentingNewLine]", 
      RowBox[{"(*", " ", 
       RowBox[{"put", " ", "code", " ", "here"}], " ", "*)"}], 
      "\[IndentingNewLine]"}]}]}], "]"}], ";"}]], "Input",
 CellChangeTimes->{{3.421453432890625*^9, 3.421453454046875*^9}}]
}, Open  ]]
}, Open  ]]
}, Closed]],

Cell[CellGroupData[{

Cell["Entropy", "Section",
 CellChangeTimes->{{3.42144834953125*^9, 3.421448350828125*^9}}],

Cell[TextData[{
 "The DiscreteWavelets command for entropy is ",
 StyleBox["Entropy",
  FontWeight->"Bold"],
 ".  The module takes either a vector or matrix as input.  Here are some \
example calls:"
}], "Text",
 CellChangeTimes->{{3.4214483785625*^9, 3.42144841728125*^9}}],

Cell[BoxData[{
 RowBox[{"v", "=", 
  RowBox[{"Range", "[", "16", "]"}]}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"Print", "[", 
   RowBox[{"\"\<The entropy of vector v is \>\"", ",", 
    RowBox[{"Entropy", "[", "v", "]"}], ",", "\"\<.\>\""}], "]"}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"A", "=", 
   RowBox[{"IdentityMatrix", "[", "8", "]"}]}], 
  ";"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"Print", "[", 
   RowBox[{"\"\<The entropy of the 8x8 identity matrix\>\"", ",", 
    RowBox[{"MatrixForm", "[", "A", "]"}], ",", "\"\< is \>\"", ",", 
    RowBox[{"Entropy", "[", "A", "]"}], ",", "\"\<.\>\""}], "]"}], 
  ";"}]}], "Input",
 CellChangeTimes->{{3.42144842671875*^9, 3.421448561765625*^9}, {
  3.421449231546875*^9, 3.421449231984375*^9}}],

Cell[CellGroupData[{

Cell["Exercises", "Subsection",
 CellChangeTimes->{{3.421448580109375*^9, 3.421448581125*^9}}],

Cell[CellGroupData[{

Cell["Exercise 1 (Challenge)", "Subsubsection",
 CellChangeTimes->{{3.421448587578125*^9, 3.421448599765625*^9}}],

Cell[TextData[{
 "Write a module that will compute the entropy of a vector or matrix.  Hint:  \
Commands that will be useful are ",
 StyleBox["Map",
  FontWeight->"Bold"],
 ", ",
 StyleBox["Length",
  FontWeight->"Bold"],
 ", ",
 StyleBox["Sort",
  FontWeight->"Bold"],
 ", ",
 StyleBox["Split",
  FontWeight->"Bold"],
 ", ",
 StyleBox["Flatten",
  FontWeight->"Bold"],
 ",  and ",
 StyleBox["Log",
  FontWeight->"Bold"],
 ".  See the Documentation Center."
}], "Text",
 CellChangeTimes->{{3.421448602203125*^9, 3.42144862403125*^9}, {
  3.421449006453125*^9, 3.4214490630625*^9}}],

Cell[BoxData[
 RowBox[{
  RowBox[{
   RowBox[{"MyEntropy", "[", "v_", "]"}], ":=", 
   RowBox[{"Module", "[", 
    RowBox[{
     RowBox[{"{", 
      RowBox[{"(*", " ", 
       RowBox[{"Place", " ", "local", " ", "variables", " ", "here"}], " ", 
       "*)"}], "}"}], ","}], "\[IndentingNewLine]", 
    RowBox[{"(*", " ", 
     RowBox[{"Place", " ", "commands", " ", "here"}], " ", "*)"}], 
    "\[IndentingNewLine]", "]"}]}], ";"}]], "Input",
 CellChangeTimes->{{3.42144906565625*^9, 3.421449203046875*^9}, 
   3.421495791069819*^9}],

Cell["Use the cell below to test your code.", "Text",
 CellChangeTimes->{{3.421449205578125*^9, 3.421449211453125*^9}}],

Cell[BoxData[{
 RowBox[{
  RowBox[{"v", "=", 
   RowBox[{"Table", "[", 
    RowBox[{
     RowBox[{"RandomInteger", "[", 
      RowBox[{"{", 
       RowBox[{"0", ",", "10"}], "}"}], "]"}], ",", 
     RowBox[{"{", "10", "}"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", 
 RowBox[{"Entropy", "[", "v", "]"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"MyEntropy", "[", "v", "]"}], "\n"}], "\[IndentingNewLine]", 
 RowBox[{
  RowBox[{"A", "=", 
   RowBox[{"Table", "[", 
    RowBox[{
     RowBox[{"RandomInteger", "[", 
      RowBox[{"{", 
       RowBox[{"0", ",", "10"}], "}"}], "]"}], ",", 
     RowBox[{"{", "8", "}"}], ",", 
     RowBox[{"{", "8", "}"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", 
 RowBox[{"Entropy", "[", "A", "]"}], "\[IndentingNewLine]", 
 RowBox[{"MyEntropy", "[", "A", "]"}]}], "Input",
 CellChangeTimes->{{3.42144906565625*^9, 3.421449219484375*^9}, {
  3.421495793663519*^9, 3.4214957955541077`*^9}}]
}, Open  ]]
}, Open  ]]
}, Closed]]
}, Open  ]]
},
AutoGeneratedPackage->None,
ScreenStyleEnvironment->"Presentation",
WindowSize->{1272, 683},
WindowMargins->{{-3, Automatic}, {Automatic, 0}},
FrontEndVersion->"6.0 for Mac OS X x86 (32-bit) (June 19, 2007)",
StyleDefinitions->FrontEnd`FileName[{"Creative"}, "NaturalColor.nb", 
  CharacterEncoding -> "UTF-8"]
]
(* End of Notebook Content *)

(* Internal cache information *)
(*CellTagsOutline
CellTagsIndex->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[CellGroupData[{
Cell[590, 23, 160, 2, 107, "Title"],
Cell[753, 27, 203, 6, 140, "Subtitle"],
Cell[959, 35, 158, 6, 96, "Subsubtitle"],
Cell[CellGroupData[{
Cell[1142, 45, 87, 1, 104, "Section"],
Cell[CellGroupData[{
Cell[1254, 50, 32, 0, 57, "Subsection"],
Cell[1289, 52, 479, 8, 80, "Text"]
}, Open  ]],
Cell[CellGroupData[{
Cell[1805, 65, 38, 0, 57, "Subsection"],
Cell[1846, 67, 288, 7, 57, "Text"],
Cell[2137, 76, 143, 2, 54, "Input"]
}, Open  ]],
Cell[CellGroupData[{
Cell[2317, 83, 46, 0, 57, "Subsection"],
Cell[2366, 85, 377, 6, 57, "Text"]
}, Open  ]]
}, Open  ]],
Cell[CellGroupData[{
Cell[2792, 97, 98, 1, 104, "Section"],
Cell[CellGroupData[{
Cell[2915, 102, 99, 1, 61, "Subsection"],
Cell[3017, 105, 651, 12, 167, "Text"],
Cell[3671, 119, 711, 16, 160, "Input"],
Cell[4385, 137, 127, 1, 37, "Text"],
Cell[4515, 140, 1000, 27, 228, "Input"]
}, Open  ]],
Cell[CellGroupData[{
Cell[5552, 172, 94, 1, 61, "Subsection"],
Cell[5649, 175, 559, 18, 63, "Text"],
Cell[6211, 195, 408, 9, 126, "Input"]
}, Open  ]],
Cell[CellGroupData[{
Cell[6656, 209, 97, 1, 61, "Subsection"],
Cell[CellGroupData[{
Cell[6778, 214, 142, 2, 39, "Subsubsection"],
Cell[6923, 218, 296, 6, 63, "Text"],
Cell[7222, 226, 179, 4, 57, "Input"]
}, Open  ]],
Cell[CellGroupData[{
Cell[7438, 235, 159, 2, 39, "Subsubsection"],
Cell[7600, 239, 433, 11, 115, "Text"],
Cell[8036, 252, 446, 11, 126, "Input"],
Cell[8485, 265, 175, 4, 37, "Text"],
Cell[8663, 271, 538, 14, 126, "Input"]
}, Open  ]]
}, Open  ]]
}, Closed]],
Cell[CellGroupData[{
Cell[9262, 292, 91, 1, 66, "Section"],
Cell[9356, 295, 274, 7, 37, "Text"],
Cell[9633, 304, 776, 19, 194, "Input"],
Cell[CellGroupData[{
Cell[10434, 327, 94, 1, 61, "Subsection"],
Cell[CellGroupData[{
Cell[10553, 332, 113, 1, 39, "Subsubsection"],
Cell[10669, 335, 581, 23, 63, "Text"],
Cell[11253, 360, 534, 14, 126, "Input"],
Cell[11790, 376, 119, 1, 37, "Text"],
Cell[11912, 379, 923, 24, 262, "Input"]
}, Open  ]]
}, Open  ]]
}, Closed]]
}, Open  ]]
}
]
*)

(* End of internal cache information *)