Введение в цифровую обработку изображений. Филатов А.К. - 28 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

28
До сжатия данных каждая буква представляется числом, которое лежит
между 0 и 255. Если применяется альтернативная кодовая таблица, то буквы
имеют значения между 128 и 159 (а-я), между 160 и 175 (а-н) и между 224 и
239 (р-я), а пробел – значение 32. Запись приведенного словосочетания потре-
бовала бы 39 байтов – как раз по одному байту на букву или пробел. Чтобы
снизить затраты емкости при записи, определим вначале частоту встречаемо-
сти отдельных букв:
Буква Частота Буква Частота
П 3 Н 1
Р 5 Е 3
О 4 С 2
Г 1 Б 1
А 2 З 1
М 3 Т 1
И 4 Ь 1
В 1 Пробел 3
Очевидно, что наиболее часто встречается буква "Р". Другие буквы
встречаются реже, а многие вообще не встречаются. Конечно, весьма расточи-
тельно кодировать каждую букву одинаковым числом битов. Было бы гораздо
экономичнее кодировать наиболее часто встречающиеся буквы такими корот-
кими численными значениями, как 0 или 1. При этом на кодирование затрачи-
вался бы всего один бит, т.е. в 8 раз меньше, чем согласно использованной ко-
довой таблице. Соответственно, по мере снижении частоты букв для их коди-
рования можно было бы использовать все более длинные численные значения.
В этом заключается принцип кодирования по Хаффману. После определения
частоты встречаемости знаков строится схема кодирования, в которой наибо-
лее часто встречаемые символы кодируются меньшим числом битов, и наобо-
рот, символы, частота встречаемости которых меньше, кодируются большим
числом битов. Задача состоит в том, чтобы найти эффективную схему кодиро-
вания/декодирования. В сжатый файл необходимо записать поток битов вме-
сте с информацией, указывающей, как этот поток следует интерпретировать. В
этом потоке битов отдельные знаки представляются уже не фиксированным, а
переменным числом битов, причем количество кодирующих битов уменьша-
ется с ростом частоты встречаемости символа.
Граница применимости этой схемы сжатия очевидна: данные можно
сжимать, только если отдельные элементы данных различаются по частоте
встречаемости. Если же элементы данных распределены статистически равно-
мерно, то сжатие невозможно. В методе сжатия, предложенном в работах Яко-
ба Зива и Абрахама Лемпеля и реализованном американцем Терри Велчем

Страницы