https://pastein.ru/t/LCX
скопируйте уникальную ссылку для отправки
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):
"""Вычисление избыточности кода Хаффмана."""
encodtext = ''.join(huff_code[symbol] for symbol in text)
origlen = len(text)
encodlen = len(encodtext)
redun = origlen / encodlen
return redun
text = "БЫТЬ ЭНТУЗИАСТКОЙ СДЕЛАЛОСЬ ЕЕ ОБЩЕСТВЕННЫМ ПОЛОЖЕНИЕМ И ИНОГДА КОГДА ЕЙ ДАЖЕ ТОГО НЕ ХОТЕЛОСЬ ОНА ЧТОБЫ НЕ ОБМАНУТЬ ОЖИДАНИЙ ЛЮДЕЙ ЗНАВШИХ ЕЕ ДЕЛАЛАСЬ ЭНТУЗИАСТКОЙ СДЕРЖАННАЯ УЛЫБКА ИГРАВШАЯ ПОСТОЯННО НА ЛИЦЕ АННЫ ПАВЛОВНЫ ХОТЯ И НЕ ШЛА К ЕЕ ОТЖИВШИМ ЧЕРТАМ ВЫРАЖАЛА КАК У ИЗБАЛОВАННЫХ ДЕТЕЙ ПОСТОЯННОЕ СОЗНАНИЕ СВОЕГО МИЛОГО НЕДОСТАТКА ОТ КОТОРОГО ОНА НЕ ХОЧЕТ НЕ МОЖЕТ И НЕ НАХОДИТ НУЖНЫМ ИСПРАВЛЯТЬСЯ В СЕРЕДИНЕ РАЗГОВОРА ПРО ПОЛИТИЧЕСКИЕ ДЕЙСТВИЯ АННА ПАВЛОВНА РАЗГОРЯЧИЛАСЬ АХ НЕ ГОВОРИТЕ МНЕ ПРО АВСТРИЮ Я НИЧЕГО НЕ ПОНИМАЮ МОЖЕТ БЫТЬ НО АВСТРИЯ НИКОГДА НЕ ХОТЕЛА И НЕ ХОЧЕТ ВОЙНЫ ОНА ПРЕДАЕТ НАС РОССИЯ ОДНА ДОЛЖНА БЫТЬ СПАСИТЕЛЬНИЦЕЙ ЕВРОПЫ"
frequencies = Counter(text) #Подсчет частот символов в тексте
tree = build_huffman_tree(frequencies)
huffcode = build_huffman_code(tree)
redun = calculate_redundancy(text, huffcode)
print("Префиксный код Хаффмана:")
for symbol, code in huffcode.items():
print(f"{symbol}: {code}")
print(f"\nИзбыточность кода Хаффмана: {redun}")