So how I have a project due Saturday for my Python data structures class, and im

Question

So how I have a project due Saturday for my Python data structures class, and im truly confused as to how to start this .. I want to understand how to actually implement a Huffman compressions . These are the following guidelines, can someone direct me in the proper direction...

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. Use the built-in function ord (c) to get an integer value between 0...255 for a given character c (and chr () to go from the integer value back to the character as a Python string. This function should return the list with the counts of occurrences. There can be issues with extra characters in some systems.

Write a recursive data definition for a Huffman tree, which is a possibly empty 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 value (either as the character itself or the ord() of the character, your choice) and an occurrence count, 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 want additional fields in your HuffmanNodes if you feel it is necessary for your implementation.

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 a function comes_before (‘a’, ‘b’) for Huffman trees that returns true if tree ‘a’ comes before tree ‘b’. A Huffman tree ‘a’ comes before Huffman tree ‘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).

the following is what we have to follow given predefined parameters along with a text file that conatains a few characters of the alphabet (only one line) .....

class HuffmanNode:

def __init__(self, char, freq):

self.char = char # actually the character code

self.freq = freq

self.code = None

self.left = None

self.right = None

# add any necessary functions you need

#returns true if tree rooted at node a comes before tree rooted at node b

def comes_before (a, b) :

pass

def cnt_freq(filename):

pass

def create_huff_tree(char_freq):

pass

def create_code (node):

pass

def huffman_encode(in_file, out_file):

pass

def huffman_decode(freqs, encoded_file, decode_file):

pass

def tree_preord (node):

pass

ALSO i have to implement the read and write function using one of these two ways

#Name:
#Section:
#Data Definition
#Two different ways you can use to read from file one character
at a time.
fin = open('file1.txt')
print (fin)
#harder solution for reading file and adding second columns
while True:
ch = fin.read(1)#line.strip() #removes space between lines
if not ch:
break
print (ch, end=', ')
print(' ')
fin.close()
def fio(filename):
with open(filename, encoding='utf-8-sig') as fin:
for line in fin:
for ch in range(0, len(line)):
print(line[ch], end=', ')
fin.close()

#call function and pass the file name
fio('file1.txt')
For writing to a file you do the same steps and pass 'w' when
you open the file.
fout = open('file_out.txt', 'w')
fout.write('data or message')
fout.close()

Explanation / Answer

huffman.py:

import numpy as np
import functools

# Method for counting character frequency in the file text
def cnt_freq(filename):
    freq_count = np.zeros([256])
    with open(filename) as f:
        while True:
            c = f.read(1)
            if not c:
                # End of file
                break
            freq_count[ord(c)] += 1

    return freq_count

# This method compares the two HuffmanNodes return True
# if first node has lower frequency
def comes_before(a, b):
    if a.occurrence_count < b.occurrence_count:
        return True
    elif a.occurrence_count == b.occurrence_count:
        return a.ch < b.ch
    else:
        return False

# Returns the first two min HuffmanNode from the list.
# It first sorts the list and then returns the first two nodes
def find_min(lst):
    lst = sorted(lst, key=functools.cmp_to_key(comes_before))
    return lst[0], lst[1]

# This method creates the HuffmanTree
def create_huff_tree(list_of_freqs):
    list_of_nodes = []
    # Initially create all frequency nodes as leaf HuffmanNode
    for i in range(len(list_of_freqs)):
        if list_of_freqs[i] != 0:
            node = HuffmanNode(i, list_of_freqs[i], None, None, True)
            list_of_nodes.append(node)
    # It will keep removing first two smallest nodes and append the combined node
    # until there is only one node in the list
    while len(list_of_nodes) != 1:
        first_node, second_node = find_min(list_of_nodes)
        del list_of_nodes[0]
        del list_of_nodes[0]

        new_freq = first_node.occurrence_count + second_node.occurrence_count
        new_node = HuffmanNode(new_freq, new_freq, first_node, second_node, False)
        list_of_nodes.append(new_node)

    return list_of_nodes[0]

# This method does the coding for HuffmanTree.
# Also it returns the list of codes for each characters.
def create_code(root_node):
    lst_visited = []
    char_codes = ["" for x in range(256)]
    completed = False
    code = ''
    while not completed:
        if root_node is not None:
            lst_visited.append(root_node)

            root_node = root_node.left
            if root_node is not None and root_node.is_leaf:
                code += '0'
                char_codes[root_node.ch] = code

        else:
            if len(lst_visited) != 0:
                root_node = lst_visited.pop()
                root_node = root_node.right
                if root_node is not None and root_node.is_leaf:
                    code += '1'
                    char_codes[root_node.ch] = code

            else:
                completed = True
    print code
    return char_codes

# HuffmanNode class containing char, frequency, left & right node and is_leaf fields
class HuffmanNode:
    def __init__(self, c, freq, left, right, is_leaf):
        self.ch = c
        self.left = left
        self.right = right
        self.is_leaf = is_leaf
        self.occurrence_count = freq

# Main method: to create the HuffmanTree tree, read a text file
# then call count frequency followed by create_huff_tree.
# Finally call create node and pass the root of the tree.
if __name__ == '__main__':
    # Please change the text file name accordingly
    root = create_huff_tree(cnt_freq('input.txt'))
    char_codes = create_code(root)

    # Printing the code for each characters
    for i in range(256):
        if char_codes[i] is not "":
            print ('Character is: ' + chr(i) +
                   " and code is: " + char_codes[i])
Input file used in the above program for generating huffman code is shown below:

input.txt:

No one would have believed in the last years of the nineteenth
century that this world was being watched keenly and closely by
intelligences greater than man's and yet as mortal as his own; that as
men busied themselves about their various concerns they were
scrutinised and studied, perhaps almost as narrowly as a man with a
microscope might scrutinise the transient creatures that swarm and
multiply in a drop of water. With infinite complacency men went to
and fro over this globe about their little affairs, serene in their
assurance of their empire over matter. It is possible that the
infusoria under the microscope do the same. No one gave a thought to
the older worlds of space as sources of human danger, or thought of
them only to dismiss the idea of life upon them as impossible or
improbable.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.