Префексный код. Префиксное кодирование
 Скачать 14.31 Kb.
|
|
Префиксное кодирование Когда мы представляем в цифровом виде информацию, такую как изображение, это значит, что нам нужно разделять её на маленькие кусочки. Это позволит на отправить изображение как последовательность цветовых символов. Представьте себе ситуацию: Алеша должен выслать Вове сообщение в двоичном коде. Они тратят по 1 копейке за 1 бит переданной информации. Алеша высылает сообщение длиной в 1 тысячу символов. Обычно такие сообщения посылаются 2-хбитным кодом, что приводит к выставлению счёта ща 2000 бит. Однако Вова изучил, что посланное ранее сообщение. Он понял, что вероятности разных символов в сообщении отличаются. Могут ли они использовать эти вероятности для сжатия передаваемого сообщения и увеличить прибыль? Если у нас имеются символы с разной частотой встречаемости, то не обязательно для них использовать равномерный код. Этот код должен удовлетворять двум условиям: Однозначное декодирование Минимальность Один из таких методов кодирования – метод Хаффмана. Чтобы реализовать данный метод надо сделать следующие шаги: Упорядочить символы исходного алфавита в порядке не возрастания их вероятностей Объединяем два символа с наименьшими вероятностями. Символы с большей вероятность приписываем “1”; с меньшей - “0”. Считаем объединение символов за один символ с вероятностью, равной сумму вероятностей объединенных символов. Возвращаемся ко второму пункту до тех пор, пока вероятность не будет равна 1 |