import heapq  
from collections import Counter  
from collections import namedtuple

class Node(namedtuple("Node", ["left", "right"])):  
    def walk(self, code, acc):
        self.left.walk(code, acc + "0")  
        self.right.walk(code, acc + "1") 

class Leaf(namedtuple("Leaf", ["char"])):  
    def walk(self, code, acc):
        
        code[self.char] = acc or "0"  

def huffman_encode(s):  
    h = []  
    for ch, freq in Counter(s).items(): 
        h.append((freq, len(h), Leaf(ch)))  
    heapq.heapify(h)  
    count = len(h) 
    while len(h) > 1: 
        freq1, _count1, left = heapq.heappop(h)  
        freq2, _count2, right = heapq.heappop(h)  
        
        heapq.heappush(h, (freq1 + freq2, count, Node(left, right))) 
                                                                     
        count += 1  
    code = {}  
    if h:  
        [(_freq, _count, root)] = h  
        root.walk(code, "")  
    return code  


s = open('en8bit.bin','r')  
code = huffman_encode(s)  
encoded = "".join(code[ch] for ch in s)  
b = open('56.bin', 'wb')
pickle.dump(encoded, b)
b.close()                                            
  
    

 import struct
class Node:
    def __init__(self, value, priority):
        self.value = value
        self.priority = priority
        self.side = None
        self.parent = None
        self.linked_l = None
        self.linked_r = None
    def link(self, node: 'Node', side: int):
        node.parent = self
        if side == 0:
            self.linked_l = node
            node.side = 0
        else:
            self.linked_r = node
            node.side = 1
class Pq:
    def __init__(self):
        self.elements = []
    def push(self, node: Node):
        self.elements.append(node)
    def pop(self):
        min = None
        for i in range(len(self.elements)):
            e = self.elements[i]
            if min is None or e.priority < min.priority:
                min = e
        if min is not None:
            self.elements.remove(min)
        return min
class HuffmansCode:
    @staticmethod
    def build_tree(bytes):
        alpha = {}
        for b in bytes:
            if b in alpha:
                alpha[b] += 1
            else:
                alpha[b] = 1
        tree = Pq()
        for k in alpha:
            tree.push(Node(k, alpha[k]))
        while len(tree.elements) > 1:
            n1 = tree.pop()
            n2 = tree.pop()
            node = Node(None, n1.priority + n2.priority)
            node.link(n1, 0)
            node.link(n2, 1)
            tree.push(node)
        return tree
    @staticmethod
    def build_table(tree):
        def walk_tree(root_node: Node, out_table):
            if root_node.value is not None:
                out_table.append(root_node)
            if root_node.linked_l is not None:
                walk_tree(root_node.linked_l, out_table)
            if root_node.linked_r is not None:
                walk_tree(root_node.linked_r, out_table)
        def trace_path(node, out_table):
            if node.parent is not None:
                out_table.insert(0, node.side)
                trace_path(node.parent, out_table)
        nodes = []
        walk_tree(tree.elements[0], nodes)
        table = {}
        for node in nodes:
            t = []
            trace_path(node, t)
            table[node.value] = t
        return table
    @staticmethod
    def get_bit_str(table, bytes):
        bitstr = ''
        for byte in bytes:
            for k in table:
                if int(byte) == int(k):
                    for bit in table[k]:
                        bitstr += str(bit)
        return bitstr
    @staticmethod
    def bitstr_to_bytes(bitstr):
        def align(str):
            l = len(str)
            if l % 8 != 0:
                l2 = l + 1
                while l2 % 8 != 0:
                    l2 += 1
                return str + '0' * (l2 - l), l2 - l
            return str, 0
        bitstr, diff = align(bitstr)
        bytes = []
        for i in range(0, len(bitstr), 8):
            byte = 0x00
            for j in range(8):
                if bitstr[i + j] == '1':
                    byte |= (0x01 << j)
            bytes.append(byte)
        return bytes, diff
    @staticmethod
    def bytes_to_bitstr(bytes):
        bitstr = ''
        for byte in bytes:
            for i in range(8):
                bitstr += '1' if (byte >> i) & 0x01 == 1 else '0'
        return bitstr
    @staticmethod
    def decode_bitstring(tree, bitstr):
        data = []
        node = tree.elements[0]
        for bit in bitstr:
            node = node.linked_l if bit == '0' else node.linked_r
            if node.value is not None:
                data.append(node.value)
                node = tree.elements[0]
        return data
def read_bytes(file):
    bytes = None
    with open(file, 'rb') as file:
        bytes = file.read()
    return bytes
def save_file(file, bytes):
    with open(file, 'wb') as file:
        for b in bytes:
            file.write(struct.pack('B', b))
def encode_file(file, target):
    bytes = read_bytes(file)
    # Build tree
    tree = HuffmansCode.build_tree(bytes)
    # Build table
    table = HuffmansCode.build_table(tree)
    # Code data to bit string
    bitstr = HuffmansCode.get_bit_str(table, bytes)
    # code bit string to bytes
    encoded_bytes, diff = HuffmansCode.bitstr_to_bytes(bitstr)
    save_file(target, encoded_bytes)
    return bytes, tree, table, bitstr
def decode_file(tree, file):
    bytes = read_bytes(file)
    bitstr = HuffmansCode.bytes_to_bitstr(bytes)
    return HuffmansCode.decode_bitstring(tree, bitstr)
bytes, tree, table, bitstr = encode_file('data.bin', 'enc.bin')
print("Original bytes: ", [b for b in bytes])
print("Coded bitstring: ", bitstr)
decoded_data = decode_file(tree, 'enc.bin')
print("Decoded data", decoded_data)