. Его необходимо с помощью преобразования V~ перевести в бинарный объект B2 объемом V2
Работа добавлена на сайт samzan.net: 2016-03-13
Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Технология сжатия информационных данных (Алгоритмы Шеннона-Фано, Хаффмана).
Метод Шеннона-Фано.
Пусть имеется бинарный объект B1 объемом V1. Его необходимо с помощью преобразования V’ перевести в бинарный объект B2 объемом V2. Причем V1>V2. Следует отметить, что бинарное исходное множество описывается информационным пространством (x,N), которое называют кортеж, где x – множество последовательностей символов алфавита N, а буква алфавита N – это образ представляющий собой бинарную цепочку фиксированной длины. Тогда, (x1 N1) взаимно однозначно преобразуется в (x2 N2) через V’. Длина бинарной цепочки для B1 – постоянна. Для B2 бинарные цепочки будут иметь переменную длину.
Смысл V’:
- В операциях кодирования B1 в B2 мы должны будем заменять цепочки постоянной длины на цепочки переменной длины.
- При декодировании B2 в B1 мы должны обеспечить правильность выделения буквы алфавита N2 без внесения в объект B2 символов разделения.
- Чтобы не вводить этот символ, алфавиты N1 и N2 должны удовлетворять условию префиксности.
- Условие префиксности для элементов алфавита N2: более короткие образы букв (бинарные цепочки) не являются началом более длинных бинарных цепочек N2.
1. Строим таблицу информационной насыщенности B1. Таблица информационной насыщенности - дискретное распределение букв алфавита N в исходном бинарном множестве.
2. Определяем по заданной модели буквы алфавита N2.
- Разделяем на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы.
- Всем знакам верхней половины в качестве первого символа присваиваем 0, а всем нижним – 1.
- Каждую из полученных групп в свою очередь разбиваем на две подгруппы с одинаковыми суммарными вероятностями и т.д. до одного знака в каждой подгруппе.
3. Строим кодер.
4. Строим декодер.
5. Разрабатываем заголовок, который содержит словарь и другую служебную информацию.
Метод Хаффмана.
- Строим таблицу информационной насыщенности, где в основной столбец выписываем буквы алфавита сообщений в порядке убывания вероятностей.
- Две последние буквы объединяем в одну вспомогательную букву, которой приписываем суммарную вероятность и вновь располагаем буквы в порядке убывания вероятностей. Процесс продолжаем до тех пор, пока не получим единственную вспомогательную букву.
- Строим граф. Из точки, соответствующей вероятности 1, направляем две ветви, причем ветви с большей вероятностью присваиваем символ 1, а с меньшей – 0. Такое ветвление продолжаем до тех пор, пока не дойдем до вероятности каждой буквы.
- Двигаясь по графу сверху вниз, можем записать для каждой буквы соответствующую ей кодовую комбинацию.
- Строим кодер.
- Строим декодер.
- Разрабатываем заголовок, который содержит словарь и другую служебную информацию.