Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Huffman Encode by Moff
from collections import Counter
class TreeNode(object):
def __init__(self, value, weight):
self.left = None
self.right = None
self.value = value
self.weight = weight
self.code = '0'
@classmethod
def join(cls, left, right):
node = cls(left.value + right.value, left.weight + right.weight)
node.left = left
node.right = right
return node
def process_codes(self, prefix=''):
if self.left is None and self.right is None:
if prefix:
self.code = prefix
else:
self.left.process_codes(prefix + '0')
self.right.process_codes(prefix + '1')
def leafs(self):
if self.left is None and self.right is None:
return [self]
else:
return self.left.leafs() + self.right.leafs()
def huffman_encode(s: str) -> str:
if not s:
return ''
queue = [TreeNode(c, w) for c, w in Counter(s).items()]
while len(queue) > 1:
queue.sort(key=lambda r: (r.weight, r.value))
queue.append(TreeNode.join(queue.pop(0), queue.pop(0)))
root = queue[0]
root.process_codes()
d = {n.value: n.code for n in root.leafs()}
return ''.join(d[c] for c in s)
Jan. 12, 2023