https://pastein.ru/t/QcV
скопируйте уникальную ссылку для отправки
from collections import Counter
from heapq import heappush, heappop, heapify
def build_huffman_tree(frequencies):
heap = [[weight, [symbol, ""]] for symbol, weight in frequencies.items()]
heapify(heap)
while len(heap) > 1:
lo = heappop(heap)
hi = heappop(heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
return sorted(heappop(heap)[1:], key=lambda p: (len(p[-1]), p))
def build_huffman_code(tree):
huff_code = {}
for pair in tree:
symbol, code = pair
huff_code[symbol] = code
return huff_code
def calculate_redundancy(text, huff_code):
encoded_text = ''.join(huff_code[symbol] for symbol in text)
original_length = len(text)
encoded_length = len(encoded_text)
redundancy = original_length / encoded_length
return redundancy
text = "ОНА ЗАБОТЛИВО ПОГЛЯДЫВАЛА НА НЕГО В ТО ВРЕМЯ КАК ОН ПОДОШЕЛ ПОСЛУШАТЬ ТО ЧТО ГОВОРИЛОСЬ ОКОЛО МОРТЕМАРА И ОТОШЕЛ К ДРУГОМУ КРУЖКУ ГДЕ ГОВОРИЛ АББАТ ДЛЯ ПЬЕРА ВОСПИТАННОГО ЗА ГРАНИЦЕЙ ЭТОТ ВЕЧЕР АННЫ ПАВЛОВНЫ БЫЛ ПЕРВЫЙ КОТОРЫЙ ОН ВИДЕЛ В РОССИИ ОН ЗНАЛ ЧТО ТУТ СОБРАНА ВСЯ ИНТЕЛЛИГЕНЦИЯ ПЕТЕРБУРГА И У НЕГО КАК У РЕБЕНКА В ИГРУШЕЧНОЙ ЛАВКЕ РАЗБЕГАЛИСЬ ГЛАЗА ОН ВСЕ БОЯЛСЯ ПРОПУСТИТЬ УМНЫЕ РАЗГОВОРЫ КОТОРЫЕ ОН МОЖЕТ УСЛЫХАТЬ ГЛЯДЯ НА УВЕРЕННЫЕ И ИЗЯЩНЫЕ ВЫРАЖЕНИЯ ЛИЦ СОБРАННЫХ ЗДЕСЬ ОН ВСЕ ЖДАЛ ЧЕГО НИБУДЬ ОСОБЕННО УМНОГО НАКОНЕЦ ОН ПОДОШЕЛ К МОРИО РАЗГОВОР ПОКАЗАЛСЯ ЕМУ ИНТЕРЕСЕН И ОН ОСТАНОВИЛСЯ ОЖИДАЯ СЛУЧАЯ ВЫСКАЗАТЬ СВОИ МЫСЛИ КАК ЭТО ЛЮБЯТ МОЛОДЫЕ ЛЮДИ"
frequencies = Counter(text)
tree = build_huffman_tree(frequencies)
huff_code = build_huffman_code(tree)
redundancy = calculate_redundancy(text, huff_code)
print("Префиксный код Хаффмана:")
for symbol, code in huff_code.items():
print(f"{symbol}: {code}")
print(f"\nИзбыточность кода Хаффмана: {redundancy}")