40 lines
1.1 KiB
Python
40 lines
1.1 KiB
Python
|
from __future__ import annotations
|
||
|
|
from dataclasses import dataclass
|
||
|
|
from queue import Queue
|
||
|
|
|
||
|
|
@dataclass
|
||
|
|
class Node:
|
||
|
|
character: str = None
|
||
|
|
frequency: int = None
|
||
|
|
left: Node = None
|
||
|
|
right: Node = None
|
||
|
|
|
||
|
|
def buildTree(message: str):
|
||
|
|
frequencies = { k: v for k, v in sorted([(i, message.count(i)) for i in set(message)], key = lambda x: x[1], reverse = True )}
|
||
|
|
frequencies = list(frequencies.items())
|
||
|
|
|
||
|
|
subtrees = Queue()
|
||
|
|
|
||
|
|
for i in range(len(frequencies)):
|
||
|
|
subtree = Node(None, sum(map(lambda x: x[1], frequencies[i:])))
|
||
|
|
subtree.right = Node(frequencies[i][0], frequencies[i][1])
|
||
|
|
subtrees.put(subtree)
|
||
|
|
|
||
|
|
tree = subtrees.get()
|
||
|
|
current = tree
|
||
|
|
|
||
|
|
for _ in range(subtrees.qsize()):
|
||
|
|
subtree = subtrees.get()
|
||
|
|
current.left = subtree
|
||
|
|
current = current.left
|
||
|
|
|
||
|
|
return tree
|
||
|
|
|
||
|
|
def encode(message: str):
|
||
|
|
tree = buildTree(message)
|
||
|
|
print(tree)
|
||
|
|
frequencies = { i: message.count(i) for i in set(message) }
|
||
|
|
frequencies = { k: v for k, v in sorted(frequencies.items(), key = lambda x: x[1] )}
|
||
|
|
|
||
|
|
print(encode("Hello World"))
|