<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Huffman's Algorithm for Lossless Data Compression
Step1:  This notebook presents <em style="color
Step2:  The function make_string is a helper function that is used to simplify the implementation of __str__.
  - self is the object that is to be rendered as a string
  - attributes is a list of those member variables that are used to produce the string
Step3:  The method $t.\texttt{toDot}()$ takes a binary trie $t$ and returns a graph that depicts the tree $t$.
Step4:  The method $t.\texttt{collectIDs}(d)$ takes a coding tree $t$ and a dictionary $d$ and updates the dictionary so that the following holds
Step5:  The class Leaf represents a leaf of the form $\texttt{Leaf}(c, f)$.  It maintains two member variables.
  - $c$ represents the character that is encoded.  This character is stored in the member variable mCharacter.
  - $f$ represents the number of occurrences of the character $c$ in the string $s$ that is to be encoded and is stored in the member variable mFrequency.
The class Leaf implements the method __lt__. This way, nodes in a coding tree can be ordered.  The ordering between nodes is given as follows
Step6:  The class Node represents an inner node of the form $\texttt{Node}(l, r)$.  It maintains two member variables
Step7:  Building a Coding Tree
The module heapq provides priority queues.  The api is given at https
Step8:  The function coding_tree implements Huffman's algorithm for data compression. 
The input $M$ is a set of pairs of the form
$$ \bigl{ (c_1, f_1), \cdots, (c_k, f_k)\bigr} $$
where $c_i$ is a character and $f_i$ is the number of times this character occurs in the string $s$ that is to be encoded.  Huffman's algorithm is
<em style="color
Step9:  Let us test this with a trivial example.
Step10:  The function log2(n) computes $\log_2(n)$.
Step11:  The function demo(M)takes one argument M that is a set of pairs of the form
$$ M = \bigl{ \langle c_1, f_1 \rangle, \cdots,  \langle c_n, f_n \rangle \bigr} $$
Here, $c_1$, $\cdots$, $c_n$ are characters and $f_1, \cdots, f_n$ are the frequencies with which these 
characters occur in a given string that is to be encoded.
The function builds the Huffman tree that is optimal for these characters. Additionally the function prints the 
percentage of memory savings that can be achieved with a Huffman tree.  This number is also returned.
Step12:  The function demo_file(fn) reads the file with name fn  and calculates the frequency of all characters occurring in fn.  Using these frequencies it computes the Huffman coding tree.
<ASSISTANT_TASK:>
Python Code:
import graphviz as gv
Explanation: Huffman's Algorithm for Lossless Data Compression
End of explanation
class CodingTree:
    sNodeCount = 0
    
    def __init__(self):
        CodingTree.sNodeCount += 1
        self.mID = CodingTree.sNodeCount
        
    def count(self):
        "compute the number of characters"
        pass
        
    def cost(self):
        "compute the number of bits used by this coding tree"
        pass
        
    def getID(self):
        return self.mID  # used only by graphviz
Explanation: This notebook presents <em style="color:blue;">coding trees</em>.  Given an alphabet $\Sigma$ of characters, 
we define the set $\mathcal{K}$ of coding trees by induction:
$\texttt{Leaf}(c,f) \in \mathcal{K} $ if $c \in \Sigma$ and $f \in \mathbb{N}$
An expression of the form $\texttt{Leaf}(c,f)$ represent a leaf in a coding tree.
 $c$ is a letter from the alphabet $\Sigma$ and 
* $f$ is the frequency* of the letter $c$ in the string $s$ that is to be encoded.
$\texttt{Node}(l,r) \in \mathcal{K}$ if $l \in\mathcal{K}$ and $r \in \mathcal{K}$
The expressions $\texttt{Node}(l,r)$ represent the inner nodes of the coding-tree.
The class CodingTree is a superclass for constructing coding trees.  It has one static variable sNodeCount.  This variable is used to equip all nodes with a unique identifier.  This identifier is used to draw the trees using graphviz.
Every object of class CodingTree has a uniques identifier mID that is stored as a member variable.  This identifier is only used by graphviz.
End of explanation
def _make_string(self, Attributes):
        # map the function __str__ to all attributes and join them with a comma
        name = self.__class__.__name__
        return f"{name}({', '.join(map(str, [getattr(self, at) for at in Attributes]))})"
    
CodingTree._make_string = _make_string
Explanation: The function make_string is a helper function that is used to simplify the implementation of __str__.
  - self is the object that is to be rendered as a string
  - attributes is a list of those member variables that are used to produce the string
End of explanation
def toDot(self):
    dot = gv.Digraph(node_attr={'shape': 'record', 'style': 'rounded'})
    nodeDict = {}
    self._collectIDs(nodeDict)
    for n, t in nodeDict.items():
        if isinstance(t, Leaf):
            if t.mCharacter == ' ':
                dot.node(str(n), label='{ \' \' |' + "{:,}".format(t.mFrequency) + '}') 
            elif t.mCharacter == '\t':
                dot.node(str(n), label='{ \'\\\\t\' |' + "{:,}".format(t.mFrequency) + '}') 
            elif t.mCharacter == '\n':
                dot.node(str(n), label='{ \'\\\\n\' |' + "{:,}".format(t.mFrequency) + '}')     
            elif t.mCharacter == '\v':
                dot.node(str(n), label='{ \'\\\\v\' |' + "{:,}".format(t.mFrequency) + '}')     
            else:
                dot.node(str(n), label='{' + str(t.mCharacter) + '|' + "{:,}".format(t.mFrequency) + '}') 
        elif isinstance(t, Node):
            dot.node(str(n), label="{:,}".format(t.count()))
        else:
            assert False, f'Unknown node {t}'
    for n, t in nodeDict.items():
        if isinstance(t, Node):
            dot.edge(str(n), str(t.mLeft .getID()), label='0')
            dot.edge(str(n), str(t.mRight.getID()), label='1')
    return dot
CodingTree.toDot = toDot
Explanation: The method $t.\texttt{toDot}()$ takes a binary trie $t$ and returns a graph that depicts the tree $t$.
End of explanation
def _collectIDs(self, nodeDict):
    nodeDict[self.getID()] = self
    if isinstance(self, Node):
        self.mLeft ._collectIDs(nodeDict)
        self.mRight._collectIDs(nodeDict)
        
CodingTree._collectIDs = _collectIDs
Explanation: The method $t.\texttt{collectIDs}(d)$ takes a coding tree $t$ and a dictionary $d$ and updates the dictionary so that the following holds:
$$ d[\texttt{id}] = n \quad \mbox{for every node $n$ in $t$.} $$
Here, $\texttt{id}$ is the unique identifier of the node $n$, i.e. $d$ associates the identifiers with the corresponding nodes.
End of explanation
class Leaf(CodingTree):
    def __init__(self, c, f):
        CodingTree.__init__(self)
        self.mCharacter = c
        self.mFrequency = f
        
    def count(self):
        return self.mFrequency
    
    def cost(self):
        return 0
    
    def __str__(self):
        return _make_string(self, ['mCharacter', 'mFrequency'])
    
    def __lt__(self, other):
        if isinstance(other, Node):
            return True
        return self.mCharacter < other.mCharacter
Explanation: The class Leaf represents a leaf of the form $\texttt{Leaf}(c, f)$.  It maintains two member variables.
  - $c$ represents the character that is encoded.  This character is stored in the member variable mCharacter.
  - $f$ represents the number of occurrences of the character $c$ in the string $s$ that is to be encoded and is stored in the member variable mFrequency.
The class Leaf implements the method __lt__. This way, nodes in a coding tree can be ordered.  The ordering between nodes is given as follows:
* $\texttt{Leaf}(c, f) < Node(l, r)$, 
i.e. leaf nodes are smaller than inner nodes.
* $\texttt{Leaf}(c_1, f_1) < \texttt{Leaf}(c_2, f_2) \Leftrightarrow c_1 < c_2$, 
i.e. leaf nodes are compared by comparing their characters lexicographically.
End of explanation
class Node(CodingTree):
    def __init__(self, l, r):
        CodingTree.__init__(self)
        self.mLeft  = l
        self.mRight = r
    def count(self):
        return self.mLeft.count() + self.mRight.count()
        
    def cost(self):
        return self.mLeft.cost() + self.mRight.cost() + self.count()
    
    def __str__(self):
        return _make_string(self, ['mLeft', 'mRight'])
    
    def __lt__(self, other):
        if isinstance(other, Leaf):
            return False
        return self.mLeft < other.mLeft
Explanation: The class Node represents an inner node of the form $\texttt{Node}(l, r)$.  It maintains two member variables:
  - self.mLeft is the left subtree $l$,
  - self.mRight is the right subtree $r$.
The class Node implements the method __lt__. This way, nodes in a coding tree can be ordered.  The ordering between nodes is given as follows:
* $\texttt{Leaf}(c, f) < Node(l, r)$, 
i.e. leaf nodes are smaller than inner nodes.
* $\texttt{Node}(l_1, r_1) < \texttt{Node}(l_2, r_2) \Leftrightarrow l_1 < l_2$, 
i.e. inner nodes are compared by comparing their left subtrees.
End of explanation
import heapq
H = []
heapq.heappush(H, 7)
heapq.heappush(H, 1)
heapq.heappush(H, 0)
heapq.heappush(H, 6)
H
a = heapq.heappop(H)
print('a = ', a)
H
Explanation: Building a Coding Tree
The module heapq provides priority queues.  The api is given at https://docs.python.org/3/library/heapq.html.
We will use two methods:
* heapq.heappush(H, p)
  pushes the priority p onto the heap.  For this to be possible, p has to be an object of a class that provides the 
  method __lt__.  The expression p.__lt__(q) is True if p is smaller than q.
* heapq.heappop(H) 
  removes and returns the element from the heap H that has the highest priority, i.e. the smallest element.
The implementation of this module represents heaps as arrays.  Therefore, 
* to test whether a heap H is empty we can write H == [] since [] is the empty heap.
* to create an empty heap we write H = [],
* to get the element with the highest priority in the heap H we write H[0],
* to get the number of elements in H we can write len(H).
End of explanation
def coding_tree(M):
    H = []  # empty priority queue
    for c, f in M:
        heapq.heappush(H, (f, Leaf(c, f)))
    while len(H) > 1:
        ac, a = heapq.heappop(H)
        bc, b = heapq.heappop(H)
        heapq.heappush(H, (ac + bc, Node(a, b)))
    return H[0][1]
Explanation: The function coding_tree implements Huffman's algorithm for data compression. 
The input $M$ is a set of pairs of the form
$$ \bigl{ (c_1, f_1), \cdots, (c_k, f_k)\bigr} $$
where $c_i$ is a character and $f_i$ is the number of times this character occurs in the string $s$ that is to be encoded.  Huffman's algorithm is
<em style="color:blue;">greedy</em>:  It always combines those coding trees that have the least character count so far as this results in the smallest cost increase.
The heap H that is maintained by this function is a priority queue which is represented by an array that is structured as a heap.  The items in this priority queue are pairs of the form
$$ \bigl( t.\texttt{count}(), t \bigr)  $$
where $t$ is a coding tree and $t.\texttt{count}()$ is the count of this coding tree.
End of explanation
import math
Explanation: Let us test this with a trivial example.
End of explanation
def log2(n):
    return math.log(n) / math.log(2)
log2(8)
Explanation: The function log2(n) computes $\log_2(n)$.
End of explanation
def demo(M):
    K = coding_tree(M)
    display(K.toDot())
    n = math.ceil(log2(len(M)))
    cost_huffman  = K.cost()
    cost_constant = n * K.count()
    savings       = (cost_constant - cost_huffman) / cost_constant
    print(f'cost of encoding with Huffman coding tree : {"{:,}".format(cost_huffman)} bits')
    print(f'cost of encoding with {n} bits              : {"{:,}".format(cost_constant)} bits')
    print(f'savings: {100 * savings}%')
    return savings
demo({ ('a', 990), ('b', 8), ('c', 1), ('d', 1) })
demo({ ('a', 4), ('b', 9), ('c', 16), ('d', 25), ('e', 36), ('f', 49), ('g', 64) })
demo({ ('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7), ('h', 8), ('i', 9), ('j', 10) })
demo({ ('a', 1), ('b', 1), ('c', 2), ('d', 3), ('e', 5), ('f', 8), ('g', 13) })
Explanation: The function demo(M)takes one argument M that is a set of pairs of the form
$$ M = \bigl{ \langle c_1, f_1 \rangle, \cdots,  \langle c_n, f_n \rangle \bigr} $$
Here, $c_1$, $\cdots$, $c_n$ are characters and $f_1, \cdots, f_n$ are the frequencies with which these 
characters occur in a given string that is to be encoded.
The function builds the Huffman tree that is optimal for these characters. Additionally the function prints the 
percentage of memory savings that can be achieved with a Huffman tree.  This number is also returned.
End of explanation
def demo_file(fn):
    with open(fn, 'r') as file:
        s = file.read() # read file as string s
    Frequencies = {}
    for c in s:
        f = Frequencies.get(c, 0)
        f += 1
        Frequencies[c] = f
    M = { (c, f) for (c, f) in Frequencies.items() }
    print(M)
    return demo(M)
!cat alice.txt
demo_file('alice.txt')
demo_file('moby-dick.txt')
Explanation: The function demo_file(fn) reads the file with name fn  and calculates the frequency of all characters occurring in fn.  Using these frequencies it computes the Huffman coding tree.
End of explanation
<END_TASK>