18 сентября

Метод Хаффмана

Заключается в построения бинарного дерева с учетом частоты встречаемости символов, например


Можно представить что мы уравновешиваем взвешивание

Шаг 1. Упорядочиваем символы исходного алфавита в порядке невозрастания их вероятностей. (Записываем их в столбец.)

Шаг 2. Объединяем два символа с наименьшими вероятностями. Символу с большей вероятностью приписываем "1", символу с меньшей – "0" в качестве элементов их кодов.

Шаг 3. Считаем объединение символов за один символ с вероятностью, равной сумме вероятностей объединенных символов.

Шаг 4. Возвращаемся на Шаг 2 до тех пор, пока все символы не будут объединены в один с вероятностью, равной единице.

Попробуем закодировать неравномерным двоичным кодом фразу КОЛ ОКОЛО КОЛОКОЛА


Постройте дерево Хаффмана для следующих символов в тетради (покажите на след уроке)

СимволЧастота
'b'3
'e'4
'p'2
' '2
'o'2
'r'1
'!'1

Методы сжатия 


Распакуйте файл сжатый по способу RLE

00000010 00001111 11110000 10000110 11000011 00000011 00001111 00111100 01010101

Последовательность запишите в тетрадь



Last modified: Friday, 17 September 2021, 7:34 AM