fork download
copy 
  1. import heapq  # модуль для работы с мин. кучей из стандартной библиотеки Python
  2. from collections import Counter  # словарь в котором для каждого объекта поддерживается счетчик
  3. from collections import namedtuple
  4.  
  5. # добавим классы для хранения информации о структуре дерева
  6. # воспользуемся функцией namedtuple из стандартной библиотеки
  7. class Node(namedtuple("Node", ["left", "right"])):  # класс для ветвей дерева - внутренних узлов; у них есть потомки
  8.     def walk(self, code, acc):
  9.         # чтобы обойти дерево нам нужно:
  10.         self.left.walk(code, acc + "0")  # пойти в левого потомка, добавив к префиксу "0"
  11.         self.right.walk(code, acc + "1")  # затем пойти в правого потомка, добавив к префиксу "1"
  12.  
  13. class Leaf(namedtuple("Leaf", ["char"])):  # класс для листьев дерева, у него нет потомков, но есть значение символа
  14.     def walk(self, code, acc):
  15.         # потомков у листа нет, по этому для значения мы запишем построенный код для данного символа
  16.         code[self.char] = acc or "0"  # если строка длиной 1 то acc = "", для этого случая установим значение acc = "0"
  17.  
  18. def huffman_encode(s):  # функция кодирования строки в коды Хаффмана
  19.     h = []  # инициализируем очередь с приоритетами
  20.     for ch, freq in Counter(s).items(): # постоим очередь с помощью цикла, добавив счетчик, уникальный для всех листьев
  21.         h.append((freq, len(h), Leaf(ch)))  # очередь будет представлена частотой символа, счетчиком и самим символом
  22.     heapq.heapify(h)  # построим очередь с приоритетами
  23.     count = len(h) # инициализируем значение счетчика длиной очереди
  24.     while len(h) > 1:  # пока в очереди есть хотя бы 2 элемента
  25.         freq1, _count1, left = heapq.heappop(h)  # вытащим элемент с минимальной частотой - левый узел
  26.         freq2, _count2, right = heapq.heappop(h)  # вытащим следующий элемент с минимальной частотой - правый узел
  27.         # поместим в очередь новый элемент, у которого частота равна суме частот вытащенных элементов
  28.         heapq.heappush(h, (freq1 + freq2, count, Node(left, right))) # добавим новый внутренний узел у которого
  29.                                                                      # потомки left и right соответственно
  30.         count += 1  # инкрементируем значение счетчика при добавлении нового элемента дерева
  31.     code = {}  # инициализируем словарь кодов символов
  32.     if h:  # если строка пустая, то очередь будет пустая и обходить нечего
  33.         [(_freq, _count, root)] = h  # в очереди 1 элемент, приоритет которого не важен, а сам элемент - корень дерева
  34.         root.walk(code, "")  # обойдем дерева от корня и заполним словарь для получения кодирования Хаффмана
  35.     return code  # возвращаем словарь символов и соответствующих им кодов
  36.  
  37. def main():
  38.     s = input()  # читаем строку длиной  до 10**4
  39.     code = huffman_encode(s)  # кодируем строку
  40.     encoded = "".join(code[ch] for ch in s)  # отобразим закодированную версию, отобразив каждый символ
  41.                                              # в соответствующий код и конкатенируем результат
  42.     print(len(code), len(encoded))  # выведем число символов и длину закодированной строки
  43.     for ch in sorted(code): # обойдем символы в словаре в алфавитном порядке с помощью функции sorted()
  44.         print("{}: {}".format(ch, code[ch]))  # выведем символ и соответствующий ему код
  45.     print(encoded)  # выведем закодированную строку
  46.  
  47. if __name__ == "__main__":
  48.     main(impossible)
Runtime error #stdin #stdout #stderr 0.01s 47720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Traceback (most recent call last):
  File "<builtin>/app_main.py", line 75, in run_toplevel
  File "prog.py", line 48, in <module>
    main(impossible)
NameError: global name 'impossible' is not defined
https://ideone.com/lwnGyV
language:
Python (PyPy 2.7.13)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!