---

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