Упражнения. 1. Сжатие данных является процессом, обеспечивающим уменьшение объема данных путем сокращения их избыточности

Вопросы

Набор для практики

Краткие итоги

1. Сжатие данных является процессом, обеспечивающим уменьшение объема данных путем сокращения их избыточности.

2. Сжатие данных может происходить с потерями и без потерь.

3. Отношение сжатия характеризует степень сжатия данных.

4. Существуют два основных способа проведения сжатия: статистические методы и словарное сжатие.

5. Алгоритм Хаффмана относится к статистическим методам сжатия данных.

6. Идея алгоритма Хаффмана состоит в следующем: зная вероятности вхождения символов в исходный текст, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов.

7. Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину.

8. Алгоритм Хаффмана универсальный, его можно применять для сжатия данных любых типов, но он малоэффективен для файлов маленьких размеров.

9. Классический алгоритм Хаффмана на основе кодового дерева требует хранения кодового дерева, что увеличивает его трудоемкость.

1. При кодировании каких данных можно использовать сжатие данных с потерями? Ответ обоснуйте.

2. В чем преимущества и недостатки статических методов и словарного сжатия?

3. Каким образом кодирование по алгоритму Хаффмана через префиксный код гарантирует минимальную длину кода?

4. За счет чего в методе Хаффмана поддерживается однозначность соответствия кода кодируемому символу?

5. Почему алгоритм Хаффмана малоэффективен для файлов маленьких размеров?

6. Выполните кодирование по методу Хаффмана через префиксный код символов, которые встречаются с вероятностями 0,3; 0,2; 0,1; 0,1; 0,1; 0,05; 0,05; 0,04; 0,03; 0,03. Сравните полученный результат с данными программной реализации.

7. Докажите, что метод Хаффмана кодирует информацию без потерь.

1. На основании приведенных в лекции кодов реализуйте алгоритмы сжатия по методу Хаффмана через префиксные коды и на основе кодовых деревьев.

2. Алфавит содержит 7 букв, которые встречаются с вероятностями 0,4; 0,2; 0,1; 0,1; 0,1; 0,05; 0,05. Осуществите кодирование по методу Хаффмана.

3. Закодируйте по алгоритму Хаффмана строку с вашим именем, отчеством, фамилией, датой и местом рождения (например, «Иванова Наталья Николаевна, 1 января 1990 года, город Тверь»). При кодировании не округляйте частоты менее, чем четыре знака после запятой – сокращение точности понижает эффективность кодирования. Подсчитайте коэффициент сжатия.

4. При кодировании по методу Фано все сообщения записываются в таблицу по степени убывания вероятности и разбиваются на две группы примерно (насколько это возможно) равной вероятности. Соответственно этой процедуре из корня кодового дерева исходят два ребра, которым в качестве весов присваиваются полученные вероятности. Двум образовавшимся вершинам приписывают кодовые символы 0 и 1. Затем каждая из групп вероятностей вновь делится на две подгруппы примерно равной вероятности. В соответствии с этим из каждой вершины 0 и 1 исходят по два ребра с весами, равными вероятностям подгрупп, а вновь образованным вершинам приписывают символы 00 и 01, 10 и 11. В результате многократного повторения процедуры разделения вероятностей и образования вершин приходим к ситуации, когда в качестве веса, приписанного ребру бинарного дерева, выступает вероятность одного из данных сообщений. В этом случае вновь образованная вершина оказывается листом дерева, т.к. процесс деления вероятностей для нее завершен. Задача кодирования считается решенной, когда на всех ветвях кодового бинарного дерева образуются листья. Закодируйте по алгоритму Фано данные текстового файла.

Литература

1. Ахо А., Хопкрофт Дж., Ульман Д. Структуры данных и алгоритмы. Уч. пособие. — М.: Вильямс, 2000. – 384с.

2. Кнут Д.Э. Искусство программирования. Том 3. Сортировка и поиск, 3-е изд.: Пер. с англ.: Уч. пос. – М.: Вильямс, 2000. – 832 с.

3. Кормен Т., Леверсон Ч.., Ртвест Р. Алгоритмы. Построение и анализ. — М.: МЦНМО, 1999. – 960 с.

4. Подбельский, В.В. Программирование на языке Си: учеб. пособие / В.В. Подбельский, С.С. Фомин. – М.: Финансы и статистика, 2004. – 600 с.

5. Подбельский, В.В. Язык Си++: учеб. пособие / В.В. Подбельский. – М.: Финансы и статистика, 2005. – 560 с.

6. Сэджвик Р. Фундаментальные алгоритмы на С++. Части 1-4. Анализ, структуры данных, сортировка, поиск. — М.: Диасофт, 2001. – 687 с.

7. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учебное пособие. – М.: Финансы и статистика, 2004. – 464 с.

Дата добавления: 2014-01-04