huffman.py

from __future__ importannotations

importsys


classLetter:
def__init__(self, letter: str, freq: int):
self.letter: str=letter
self.freq: int=freq
self.bitstring: dict[str, str] = {}

def__repr__(self) ->str:
returnf"{self.letter}:{self.freq}"


classTreeNode:
def__init__(self, freq: int, left: Letter|TreeNode, right: Letter|TreeNode):
self.freq: int=freq
self.left: Letter|TreeNode=left
self.right: Letter|TreeNode=right


defparse_file(file_path: str) ->list[Letter]:
"""
 Read the file and build a dict of all letters and their
 frequencies, then convert the dict into a list of Letters.
 """
chars: dict[str, int] = {}
withopen(file_path) asf:
whileTrue:
c=f.read(1)
ifnotc:
break
chars[c] =chars[c] +1ifcincharselse1
returnsorted((Letter(c, f) forc, finchars.items()), key=lambdax: x.freq)


defbuild_tree(letters: list[Letter]) ->Letter|TreeNode:
"""
 Run through the list of Letters and build the min heap
 for the Huffman Tree.
 """
response: list[Letter|TreeNode] =list(letters)
whilelen(response) >1:
left=response.pop(0)
right=response.pop(0)
total_freq=left.freq+right.freq
node=TreeNode(total_freq, left, right)
response.append(node)
response.sort(key=lambdax: x.freq)
returnresponse[0]


deftraverse_tree(root: Letter|TreeNode, bitstring: str) ->list[Letter]:
"""
 Recursively traverse the Huffman Tree to set each
 Letter's bitstring dictionary, and return the list of Letters
 """
ifisinstance(root, Letter):
root.bitstring[root.letter] =bitstring
return [root]
treenode: TreeNode=root
letters= []
letters+=traverse_tree(treenode.left, bitstring+"0")
letters+=traverse_tree(treenode.right, bitstring+"1")
returnletters


defhuffman(file_path: str) ->None:
"""
 Parse the file, build the tree, then run through the file
 again, using the letters dictionary to find and print out the
 bitstring for each letter.
 """
letters_list=parse_file(file_path)
root=build_tree(letters_list)
letters= {
k: vforletterintraverse_tree(root, "") fork, vinletter.bitstring.items()
 }
print(f"Huffman Coding of {file_path}: ")
withopen(file_path) asf:
whileTrue:
c=f.read(1)
ifnotc:
break
print(letters[c], end=" ")
print()


if__name__=="__main__":
# pass the file path to the huffman function
huffman(sys.argv[1])