Задание Хафмана. Задания Хафман. Bbbbbbacccabbbbbb
 Скачать 134.5 Kb.
|
И нформатика, 11 класс К.Ю. Поляков, Е.А. Еремин |
| | .0 | .1 | .2 | .3 | .4 | .5 | .6 | .7 | .8 | .9 | .A | .B | .C | .D | .E | .F |
| 0. | NUL | SOH | STX | ETX | EOT | ENQ | ACK | BEL | BS | TAB | LF | VT | FF | CR | SO | SI |
| 1. | DLE | DC1 | DC2 | DC3 | DC4 | NAK | SYN | ETB | CAN | EM | SUB | ESC | FS | GS | RS | US |
| 2. | | ! | " | # | $ | % | & | ' | ( | ) | * | + | , | — | . | / |
| 3. | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | : | ; | < | = | > | ? |
| 4. | @ | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O |
| 5. | P | Q | R | S | T | U | V | W | X | Y | Z | [ | \ | ] | ^ | _ |
| 6. | ` | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o |
| 7. | p | q | r | s | t | u | v | w | x | y | z | { | | | } | | DEL |
Ответ: 66.67 % коэффициент сжатия, MAAAAAAAAAAAAAAMAAAAAAAAAAAAAA
Определите количество байтов в исходной и распакованной последовательности (см. предыдущее задание) и вычислите коэффициент сжатия:
| Сжатая последовательность | Несжатая последовательность | Коэффициент сжатия |
| 10 | 30 | 66.67 |
Проверьте результат, полученный в предыдущем пункте, с помощью программы RLE. Предложите два способа проверки. Сжатие без потерь, сжатие с потерей
Постройте последовательности, которые сжимаются алгоритмом RLE ровно в 2 раза, в 4 раза, в 5 раз. Проверьте свои ответы с помощью программы RLE.
| Несжатая последовательность | Сжатая последовательность | Коэффициент сжатия |
| 100 | 50 50 | 2 |
| 100 | 75 25 | 4 |
| 100 | 80 20 | 5 |
Придумайте три последовательности, которые невозможно сжать с помощью алгоритма RLE:
| Несжатая последовательность | «Сжатая» последовательность | Коэффициент сжатия |
| 40 | 80 | 100 |
| 8 | 12 | 50 |
| 100 | 100 | 0 |
Используя программу RLE, примените RLE-сжатие к следующим файлам и найдите для каждого из них коэффициент сжатия:
| Файл | Размер без сжатия | Размер после сжатия | Коэффициент сжатия |
| grad_vert.bmp | 11 | 22 | 100 |
| grad_horz.bmp | 11 | 22 | 100 |
| grad_diag.jpg | 11 | 20 | 82 |
Объясните результаты, полученные в предыдущем пункте:
почему не удается сжать рисунки в формате JPEG?
Ответ:
Потому, что jpeg - это уже сжатые данные. Причём сжатые куда эффективнее, чем может обеспечить RLE.
почему для двух рисунков в формате BMP одинакового размера коэффициенты сжатия по алгоритму RLE так сильно отличаются? Подсказка: откройте эти рисунки в любой программе просмотра.
Ответ:
Степень сжатия зависит от размера последовательности одинаковых байт, а не от размера файла. Чем она длиннее тем лучше сжатие, от самой картинки зависит так же как и архивирование, размер исходного файла может быть один и тот же, а коэффициент сжатия сильно отличаться
Оцените максимально достижимый коэффициент сжатия с помощью рассмотренного в учебнике варианта RLE-алгоритма. В каком случае его удастся достичь?
Ответ:
Максимальное значение при одной длинной серии, минимальное при отсутствии серий
Оцените коэффициент сжатия с помощью RLE-алгоритма в худшем случае. Опишите этот худший случай.
Ответ:
В худшем случае размер сжатых данных окажется больше исходного размера. Для кодирования пробега с помощью алгоритма RLE требуется информация, состоящая не менее чем из двух символов. В связи с чем запуск одиночных символов на самом деле занимает больше места. По тем же причинам данные, состоящие полностью из 2-символьных прогонов, остаются неизменными после кодирования.
Сравнение алгоритмов сжатия
При выполнении этой работы используются программы RLE (алгоритм сжатия RLE) и Huffman (кодирование Хаффмана и Шеннона-Фано).
Запустите программу Huffman.exe и закодируйте строку «ЕНОТ НЕ ТОНЕТ», используя методы Шеннона-Фано и Хаффмана. Запишите результаты в таблицу:
| | Шеннон и Фано | Хаффман |
| Длина основного кода | | |
| Длина кодовой таблицы (дерева) | | |
| Коэффициент сжатия (по основным кодам) | | |
| Коэффициент сжатия (с учетом дерева кодов) | | |
Сделайте выводы.
Ответ:
Как, по вашему мнению, будет изменяться коэффициент сжатия при увеличении длины текста, при условии, что набор символов и частота их встречаемости останутся неизменной? Проверьте ваш вывод с помощью программы (например, можно несколько раз скопировать ту же фразу).
Ответ:
Используя кнопку Анализ файла в программе Huffman, определите предельный теоретический коэффициент сжатия для файла a.txt1 при побайтном кодировании.
Ответ:
С помощью программ RLE и Huffman выполните сжатие файла a.txt разными способами. Запишите результаты в таблицу:
| | RLE | Шеннон и Фано | Хаффман |
| Размер сжатого файла | | | |
| Коэффициент сжатия | | | |
Объясните результат, полученный с помощью алгоритма RLE.
Ответ:
Используя кнопку Анализ файла в программе Huffman, определите предельный теоретический коэффициент сжатия для файла a.txt.huf при побайтном кодировании. Объясните результат.
Ответ:
Примените несколько раз повторное сжатие этого файла с помощью алгоритма Хаффмана (новые файлы получат имена a.txt.huf2, a.txt.huf3 и т.д.) и заполните таблицу, каждый раз выполняя анализ полученного файла.
| | Размер файла | Предельный коэффициент сжатия |
| a.txt | | |
| a.txt.huf | | |
| a.txt.huf2 | | |
| a.txt.huf3 | | |
| a.txt.huf4 | | |
| a.txt.huf5 | | |
| a.txt.huf6 | | |
Объясните, почему с некоторого момента при повторном сжатии файла его размер увеличивается.
Ответ:
Выполните те же действия, используя метод Шеннона-Фано.
| | Размер файла | Предельный коэффициент сжатия |
| a.txt | | |
| a.txt.shf | | |
| a.txt.shf2 | | |
| a.txt.shf3 | | |
| a.txt.shf4 | | |
| a.txt.shf5 | | |
| a.txt.shf6 | | |
Объясните, почему с некоторого момента при повторном сжатии файла его размер увеличивается.
Ответ:
Сравните результаты сжатия этого файла с помощью алгоритма RLE, лучшие результаты, полученные методами Шеннона-Фано и Хаффмана, а также результат сжатия этого файла каким-нибудь архиватором.
| | Размер файла | Предельный коэффициент сжатия |
| RLE | | |
| Хаффман | | |
| Шеннон и Фано | | |
| ZIP | | |
| RAR | | |
| 7Z | | |
Объясните результаты и сделайте выводы.
Ответ:
1 Этот файл имеет объем 1 Мбайт и состоит из одних символов «А».
http://kpolyakov.spb.ru