<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 mFrequancy.
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_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.  Here  $c$ is a letter
from the alphabet $\Sigma$ and $f$ is the number of times that the letter $c$ occurs 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 mFrequancy.
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$.
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.
This module represents heaps as arrays.
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:
        a = heapq.heappop(H)
        b = heapq.heappop(H)
        heapq.heappush(H, (a[0] + b[0], Node(a[1], b[1])))
    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)
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 log2(n) computes $\log_2(n)$.
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)
        if f != 0:
            Frequencies[c] += 1
        else:
            Frequencies[c] = 1
    M = { (c, f) for (c, f) in Frequencies.items() }
    print(M)
    return demo(M)
!type 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>