---

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}")