Главная страница

Префексный код. Префиксное кодирование


Скачать 14.31 Kb.
НазваниеПрефиксное кодирование
Дата29.09.2021
Размер14.31 Kb.
Формат файлаdocx
Имя файлаПрефексный код.docx
ТипДокументы
#238753

Префиксное кодирование

Когда мы представляем в цифровом виде информацию, такую как изображение, это значит, что нам нужно разделять её на маленькие кусочки. Это позволит на отправить изображение как последовательность цветовых символов.

Представьте себе ситуацию: Алеша должен выслать Вове сообщение в двоичном коде. Они тратят по 1 копейке за 1 бит переданной информации. Алеша высылает сообщение длиной в 1 тысячу символов. Обычно такие сообщения посылаются 2-хбитным кодом, что приводит к выставлению счёта ща 2000 бит. Однако Вова изучил, что посланное ранее сообщение. Он понял, что вероятности разных символов в сообщении отличаются. Могут ли они использовать эти вероятности для сжатия передаваемого сообщения и увеличить прибыль?

Если у нас имеются символы с разной частотой встречаемости, то не обязательно для них использовать равномерный код.

Этот код должен удовлетворять двум условиям:

  • Однозначное декодирование

  • Минимальность

Один из таких методов кодирования – метод Хаффмана. Чтобы реализовать данный метод надо сделать следующие шаги:

  • Упорядочить символы исходного алфавита в порядке не возрастания их вероятностей

  • Объединяем два символа с наименьшими вероятностями. Символы с большей вероятность приписываем “1”; с меньшей - “0”.

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

  • Возвращаемся ко второму пункту до тех пор, пока вероятность не будет равна 1


написать администратору сайта