Description
Description
For this project, you will implement a program to encode text using
[Huffman coding](https://en.wikipedia.org/wiki/Huffman_coding).
Huffman coding is a method of lossless (the original
can be reconstructed perfectly) data compression. Each character is
assigned a variable length code consisting of ’0’s and ’1’s. The length
of the code is based on how frequently the character occurs; more
frequent characters are assigned shorter codes.
The basic idea is to use a binary tree, where each leaf node represents
a character and frequency count. The Huffman code of a character is then
determined by the unique path from the root of the binary tree to that
leaf node, where each ’left’ accounts for a ’0’ and a ’right’ accounts
for a ’1’ as a bit. Since the number of bits needed to encode a
character is the path length from the root to the character, a character
occurring frequently should have a shorter path from the root to their
node than an “infrequent” character, i.e. nodes representing frequent
characters are positioned less deep in the tree than nodes for
infrequent characters.
The key problem is therefore to construct such a binary tree based on
the frequency of occurrence of characters. A detailed example of how to
construct such a Huffman tree is provided here: [Huffman_Example.pdf](./Huffman_Example.pdf)
Note:
* You must provide test cases for all functions (Only test the provided
functions, with the exact name provided)
* Use descriptive names for data structures and helper functions.
Source Files
Start with the source files provided to you as part of GitHub Classroom,
or the ones in the [src directory](./src/) of this repository.
Functions
The following bullet points provide a guide to implement some of the
data structures and individual functions of your program. Start by
creating a file huffman.py and add functions and data definitions to
this file, if not otherwise stated. You should develop incrementally,
building test cases for each function as it is implemented.
Count Occurrences: cnt_freq(filename)
* Implement a function called cnt_freq(filename) that opens a text file
with a given file name (passed as a string) and counts the frequency
of occurrences of all the characters within that file. Use the
built-in Python List data structure of size 256 for counting the
occurrences of characters. This will provide efficient access to a
given position in the list. (In non-Python terminology you want an
array.) You can assume that in the input text file there are only
8-bit characters resulting in a total of 256 possible character
values. This function should return the 256 item list with the counts
of occurrences. There can be issues with extra characters in some
systems.
* Suppose the file to be encoded contained: ddddddddddddddddccccccccbbbbaaff
* Numbers in positions of freq counts [96:104] = [0, 2, 4, 8, 16, 0, 2, 0]
* For an empty file, this function should return a list of size 256 filled with all 0s.
Data Definition for Huffman Tree
A Huffman Tree is a binary tree of HuffmanNodes.
* A HuffmanNode class represents either a leaf or an internal node
(including the root node) of a Huffman tree. A HuffmanNode contains a
character (stored as an ASCII value) an occurrence count for that
character, as well as references to left and right Huffman subtrees,
each of which is a binary tree of HuffmanNodes. The character value
and occurrence count of an internal node are assigned as described
below. You may add fields in your HuffmanNode definition if you feel
it is necessary for your implementation. Do not change the names of
the fields specified in the huffman.py starter file given to you via
GitHub.
Build a Huffman Tree
Since the code depends on the order of the left and right branches take
in the path from the root to the leaf (character node), it is crucial to
follow a specific convention about how the tree is constructed. To do
this we need an ordering on the Huffman nodes.
* Start by defining the __lt__ (self, other) method for HuffmanNode
objects that returns true if self should come before other when added
to an OrderedList. A HuffmanNode ‘a’ should come before HuffmanNode
‘b’ if the occurrence count of ‘a’ is smaller than that of ‘b’. In
case of equal occurrence counts, break the tie by using the ASCII
value of the character to determine the order. If, for example, the
characters ’d’ and ’k’ appear exactly the same number of times in your
file, then ’d’ comes before ’k’, since the ASCII value of character
’d’ is less than that of ’k’.
* Write a function that builds a Huffman tree from a given list of the
number of occurrences of characters returned by cnt_fref() and returns
the root node of that tree. Call this function
create_huff_tree(list_of_freqs).
* Start by creating an OrderedList (your implementation from Lab 4) of
individual Huffman trees each consisting of a single HuffmanNode
containing the character and its occurrence counts. Building the
actual tree involves removing the two nodes with the lowest
frequency count from the sorted list and connecting them to the left
and right field of a new created Huffman Node as in the example
provided. The node that comes before the other node should go in
the left field.
* Note that when connecting two HuffmanNodes to the left and right
field of a new parent node, that this new node is also a
HuffmanNode, but does not contain an actual character to
encode. Instead this new parent node should contain an occurrence
count that is the sum of the left and right child occurrence counts
as well as the minimum of the left and right character
representation in order to resolve ties in the __lt__ method.
* Once a new parent node has been created from the two nodes with the
lowest occurrence count as described above, that parent node is
inserted into the list of sorted nodes.
* This process of connecting nodes from the front of the sorted list
is continued until there is a single node left in the list, which is
the root node of the Huffman tree. create_huff_tree(list_of_freqs)
then returns this node.
* If there are no entries in the list of occurrences passed to this
function, it should return None.
* If there is only one entry in the list of occurrences passed to this
function, the tree returned by this function will consist of a
single node.
Build an Array for the Character Codes
* We have completed our Huffman tree, but we are still lacking a way to
get our Huffman codes. Implement a function named
create_code(root_node) that traverses the Huffman tree that was passed
as an argument and returns an array (using a Phython list) of 256
strings. Use the character’s respective integer ASCII representation
as the index into the arrary, with the resulting Huffman code for that
character stored at that location. Traverse the tree from the root to
each leaf node and adding a ’0’ when we go ’left’ and a ’1’ when we go
’right’ constructing a string of 0’s and 1’s. You may want to:
* use the built-in ’+’ operator to concatenate strings of ’0’s and ’1’s here.
* You may want to initialize a Python list of strings that is
initially consists of 256 empty strings in create_code. When
create_code completes, this list will store for each character
(using the character’s respective integer ASCII representation as
the index into the list) the resulting Huffman code for the
character. The code will be represented by a sequence of ’0’s and
’1’s in a string. Note that many entries in this list may still be
the empty string. Return this list.
2.5 Huffman Encoding
* Write a function called huffman_encode(in_file, out_file) (use that
exact name) that reads an input text file and writes to an output file
the following:
* A header (see below for format) on the first line in the file
(should end with a newline)
* Using the Huffman code, the encoded text into an output file.
* Write a function called create_header(list_of_freqs) that takes as
parameter the list of freqs previously determined from
cnt_freq(filename). The create_header function returns a string of the
ASCII values and their associated frequencies from the input file
text, separated by one space. For example,
create_header(list_of_freqs) would return “97 3 98 4 99 2” for the
text “aaabbbbcc”
* The huffman_encode function accepts two file names in that order:
input file name and output file name, represented as strings. If the
specified output file already exists, its old contents will be erased.
See example files in the test cases provided to see the format.
* Note: Writing the generated code as a string for each character into a
file will actually enlarge the file size instead compress it. The
explanation is simple: although we encoded our input text characters
in sequences of ’0’s and ’1’s, representing actual single bits, we
write them as individual ’0’ and ’1’ characters, i.e. 8 bits.
* To actually obtain a compressed the file you will also write the ’0’
and ’1’ characters as individual bits. Do this by taking the out_file
string and:
* Add _compressed to the name of the file before the .txt file. (Ex:
if out_file is named “output.txt”, you will create the string
“output_compressed.txt”)
* Use the filename created above to create a HuffmanBitWriter object
using the huffman_bit_writer module.
* Use the methods in the HuffmanBitWriter object to write the header
and individual bits of the character codes to the compressed file.
Tests
* Write sufficient tests using unittest to ensure full functionality and
correctness of your program. Start by using the supplied
huffman_tests.py, and the various text files (e.g. file1.txt and
file1_soln.txt) to begin testing your programs. You may want to
initially comment out some of the tests, or ignore failures when
testing functionality that hasn’t been fully implemented.
* When testing, always consider edge conditions like the following cases:
* If the input file consists only of some number of a single
character, say “aaaaa”, it should write just that character followed
by a space followed by the number of occurrences with a newline: “97
5\n”
* In case of an empty input text file, your program should also
produce an empty file.
* If an input file does not exist, your program should raise a
FileNotFoundError.
Some Notes
When writing your own test files or using copy and paste from an editor,
take into account that most text editors will add a newline character to
the end of the file. If you end up having an additional newline
character ’\n’ in your text file, that wasn’t there before, then this
’\n’ character will also be added to the Huffman tree and will therefore
appear in your generated string from the Huffman tree. In addition, an
actual newline character is treated different, depending on your
computer platform. Different operating systems have different codes for
“newline”. Windows uses ’\r\n’ = 0x0d 0x0a, while Unix and Mac use ’\n’
= 0x0a. It is always useful to use a hex editor to verify why certain
files that appear identical in a regular text editor are actually not
identical.
Submission
You must submit (commit and push) the following files:
* huffman.py, containing the functions specified and any helper
functions necessary
* cnt_freq(filename): returns a Python list of 256 integers
representing the frequencies of characters in file (indexed by ASCII
value of characters)
* create_huff_tree(list_of_freqs): returns the root node of a Huffman
Tree, a Huffman node object
* create_code(root_node): returns a Python list of 256 strings
representing the code for each character (indexed by ASCII value of
the character). Note: Use an empty string to represent the code for
ASCII characters that do not appear in the file being compressed.
* create_header(list_of_freqs): returns a header for the output file
with ascii values and their associated counts, space separated.
* huffman_encode(in_file, out_file): encodes in_file and writes the it
to out_file
* huffman_tests.py, containing testcases for the functions specified by
the assignment
* This file should contain tests only for the functions specified
above and should only test functionality required by the
specification. These tests must run properly on any valid solution
and will be tested to see if they can catch bugs in incorrect
solutions.
* huffman_helper_tests.py, containing all testcases used in developing
your solution
* This file should contain all tests for your solution, including
tests for any helper functions that you may have used. These tests
will be used to verify that you have 100% coverage of your
solution. Your solution must pass these tests.
* ordered_list.py, your correct implementation of the OrderedList class
from Lab 4.
* huffman_bit_writer.py, unmodified, as provided to you.
