#!/usr/bin/env python3 import sys import string differences= { -2 : 9, -1 : 19, 0 : 40, 1 : 18, 2 : 13 } class HuffmanTreeNode(object): def __lt__(self, other): return(other.get_propability() < self.get_propability()) class HuffmanTreeBranch(HuffmanTreeNode): def __init__(self, child_b, child_a): self.child_a= child_a self.child_b= child_b def get_encodings(self): side_a= list((l, '1' + enc) for (l, enc) in self.child_a.get_encodings()) side_b= list((l, '0' + enc) for (l, enc) in self.child_b.get_encodings()) return (side_a + side_b) def format_subtree(self): sub_a= self.child_a.format_subtree() sub_b= self.child_b.format_subtree() fmt= list() fmt_char= ' ' middle_text= '─({:2.2f}%)─┤'.format(self.get_propability()) pad= ' '*(len(middle_text) - 1) for e in sub_a: if e.startswith('─'): fmt_char= '│' fmt.append(pad + '╭' + e) else: fmt.append(pad + fmt_char + e) fmt.append(middle_text) for e in sub_b: if e.startswith('─'): fmt_char= ' ' fmt.append(pad + '╰' + e) else: fmt.append(pad + fmt_char + e) return(fmt) def get_propability(self): return(self.child_a.get_propability() + self.child_b.get_propability()) class HuffmanTreeLeaf(HuffmanTreeNode): def __init__(self, letter, propability): self.letter= letter self.propability= propability def get_encodings(self): return([(self.letter, '')]) def get_propability(self): return(self.propability) def format_subtree(self): return(['─({}%)─╼ {}'.format(self.propability, repr(self.letter))]) class HuffmanTable(object): def __init__(self, letters): tree= sorted(list(HuffmanTreeLeaf(letter, prop) for (letter, prop) in letters.items())) def print_tree(): headline='Noch {} Schritte:'.format(len(tree) - 1) print('\n'.join(('','', headline, '-'*len(headline), ''))) for n in tree: print('\n'.join(n.format_subtree())) print_tree() while(len(tree) != 1): new_branch= HuffmanTreeBranch(tree.pop(), tree.pop()) tree.append(new_branch) tree= sorted(tree) print_tree() root= tree[0] self.table= dict(root.get_encodings()) def main(argv): ht= HuffmanTable(differences) if __name__ == '__main__': main(sys.argv[1:])