Проблемы Python: получить словарь, отображающий ключи к кодам Хаффмана для таблицы частот, отображающий ключи к частотам.

Проблемы Python — 1: Упражнение 58 с решением

Из Википедии,
В информатике и теории информации код Хаффмана — это особый тип оптимального префиксного кода. это обычно используется для сжатия данных без потерь. Процесс поиска или использования такого кода происходит с помощью кодирования Хаффмана, алгоритма, разработанного Дэвидом А. Хаффманом, когда он был доктором наук. студент Массачусетского технологического института и опубликован в статье 1952 года «Метод построения кодов с минимальной избыточностью».

Напишите программу на Python, чтобы получить ключи отображения словаря в коды Хаффмана для отображения таблицы частот ключи к частотам.

Пример решения :

Код Python:

  def huffman (freqtable): # Ссылка: https://bit.ly/3cWJD22 из коллекций import defaultdict из heapq import heappush, heappop, heapify # отображение букв в коды code = defaultdict  (list) # Использование кучи позволяет легко извлекать элементы с наименьшей частотой.  # Элементы в куче - это кортежи, содержащие список букв и # комбинированные частоты букв в списке.  heap = [(freq, [ltr]) for ltr, freq in freqtable.items ()] heapify (heap) # Уменьшите размер кучи до одного элемента, объединив два элемента # с наименьшими частотами.  в то время как len (куча)> 1: freq0, letter0 = heappop (куча) для ltr в буквах 0: код [ltr] .insert (0, '0') freq1, letter1 = heappop (куча) для ltr в письмах1: код [ltr  ] .insert (0, '1') heappush (heap, (freq0 + freq1, letter0 + letter1)) для k, v в code.items (): code [k] = '' .join (v) return codefreqtable =  dict (a = 45, b = 13, c = 12, d = 16, e = 9, f = 5) print (sorted (huffman (freqtable) .items ()))  

Пример вывода:

 [('a', '0'), ('b', '101'), ('c', '100'), ('d'  , '111'), ('e', '1101'), ('f', '1100')] 

Блок-схема:

Редактор кода Python:

Оцените статью
nanomode.ru
Добавить комментарий