. Его необходимо с помощью преобразования V~ перевести в бинарный объект B2 объемом V2
Работа добавлена на сайт samzan.net:
Технология сжатия информационных данных (Алгоритмы Шеннона-Фано, Хаффмана).
Метод Шеннона-Фано.
Пусть имеется бинарный объект 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. Такое ветвление продолжаем до тех пор, пока не дойдем до вероятности каждой буквы.
- Двигаясь по графу сверху вниз, можем записать для каждой буквы соответствующую ей кодовую комбинацию.
- Строим кодер.
- Строим декодер.
- Разрабатываем заголовок, который содержит словарь и другую служебную информацию.
2. Развитие культуры 1920 1930гг
3. Тема Дата Колво часов Стоимость янв
4. Аргументи- 1 учасник наводить принаймні два доречні докази підстави для обґрунтування підтвердження вис
5. Школьный психолог- Н
6. ВВЕДЕНИЕ10
7. это маркетинг направленный внутрь фирмы на ее служащих
8. Тема 4 Спортивные достижения критерии их оценки и тенденции развития План- Спортивное достиж
9. Интервальные оценки
10. Г Учитель ГЯ Гильмиярова
11. 2013 г по 2013 г
12. Geisteswissenschft und verstehen общественные науки и понимание- осознание роли человека
13. современное средство разработки экспертных систем ЭС ориентиро ванное на решение сложных задач в режи
14. і. Сонды'тан 'азіргі заман'ы автомобильдерге 'ойылатын негізгі талаптарды' бірі ж'ріс жайлылы'ын жа'сарту ж
15. СУЩНОСТЬ И СОДЕРЖАНИЕ ЭФФЕКТИВНОСТИ УПРАВЛЕНИЯ
16. РЕФЕРАТ дисертації на здобуття наукового ступеня кандидата філологічних наук Херс
17. Автоматизация учета материалов на складе с применением баз данных
18. КИШЕЧНЫЕ КРОВОТЕЧЕНИЯ Одной из сложных проблем в хирургии детского возраста являются состояние сопровож
19. Эволюция Земли
20. РЕФЕРАТ дисертації на здобуття наукового ступеня кандидата економічних наук Львів ~ 2000 Д