Цифровая фотоаппаратура. Трубникова Т.А - 55 стр.

UptoLike

ВУЗ: 

СПбГИКиТ | Санкт-Петербург

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

Рубрика: 

155 156
Один из первых алгоритмов сжатия, который впервые
сформулировали американские учёные Шеннон и Фано. Код
Шеннона- Фано является префиксным, то есть в таком коде
ни одна комбинация не совпадает с началом более длинной
комбинации, что позволяет обеспечить однозначное кодиро-
вание без введения разделительных символов. То есть- это
код, в котором код одного символа не может быть началом
кода другого символа. В таком коде не требуется указывать
длину кода, но коды получаются несколько длиннее.
Метод Шеннона – Фано заключается в том, что Вхо-
дящие символы располагают в порядке убывания их вероят-
ности, а затем последовательно делят на две части с прибли-
зительно равными вероятностями, к коду первой части добав-
ляют 0, а к коду второй- 1.
9.4.2. Кодирование Хаффмана
Метод был предложен Девидом Хаффманом (США) в
1952 году, это наиболее известный способ уменьшения кодо-
вой избыточности. За все эти годы со дня опубликования, код
Хаффмана не потерял своей значимости и актуальности. Мы
повседневно сталкиваемся с ним в той или иной форме, прак-
тически каждый раз, когда архивируем файлы, смотрим фото-
графии, фильмы, посылаем факс или слушаем музыку. Код
Хаффмана редко используется отдельно, чаще он работает в
связке с другими алгоритмами.
Основная идея: кодировать символы, которые встречаются
чаще, меньшим количеством бит, чем те, которые встречают-
ся реже.
Код Хаффмана является префиксным и двухпроход-
ным. На первом проходе строится частотный словарь и гене-
рируются коды. На втором происходит непосредственно ко-
дирование. В начале, составляется список символов в порядке
убывания вероятности их появления. Пусть имеется пять сим-
волов, расположим их в порядке убывания их вероятности:
с вероятностями соответ-
ственно: . Далее выбираются два символа с наименьшими
вероятностями, они образуют два свободных узла дерева
Хаффмана. Наименее вероятному символу присваивается би-
товый 0, а более вероятному- битовая 1. В нашем случае, это
. Символу присваиваем 1, символу при-
сваиваем 0. Далее символы условно объеди-
няются в один символ «родитель» его вероятность
будет равна сумме вероятностей . Вероятность
= 0,2 (рис.9.4.)
1 0

Страницы