Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
... unless you're Dutch. solution in Clear category for Huffman Encode by veky
import collections, heapq, operator
class Tree:
def __init__(self, item, sub=None): self.item, self.sub = tuple(item), sub
def __xor__(left, right):
return Tree(map(operator.add, left.item, right.item), (left, right))
def __lt__(self, other): return self.item[::-1] < other.item[::-1]
def huffman_encode(s: str) -> str:
table = list(map(Tree, collections.Counter(s).items()))
heapq.heapify(table)
if len(table) <= 1: return '0' * len(s)
while len(table) > 1:
heapq.heappush(table, heapq.heappop(table) ^ heapq.heappop(table))
tree, = table
def visit(tree, *path):
try: translation[ord(tree.item[0])] = ''.join(map(str, path))
except TypeError:
for branch, sub in enumerate(tree.sub): visit(sub, *path, branch)
translation = {}
visit(tree)
return s.translate(translation)
Dec. 16, 2022
Comments: