Алгоритм RLE

Алгоритм RLE

1.       Используя алгоритм RLE, закодируйте последовательность символов

BBBBBBACCCABBBBBB

Запишите результат в виде шестнадцатеричных кодов (каждый символ кодируется в виде байта, который представлен двумя шестнадцатеричными цифрами ). Проверьте полученный результат с помощью программы RLE.

Ответ:

6B1A3C1A6B

2.       Раскодируйте последовательность, упакованную с помощью алгоритма RLE (приводятся шестнадцатеричные коды): 01 4D 8E 41 01 4D 8E 41₁₆. Для определения символов по их шестнадцатеричным кодом используйте таблицу ASCII.  В приведённой таблице в первом столбце записана первая цифра шестнадцатеричного кода символа, а в первой строке – вторая. Например,  символ «&» имеет шестнадцатеричный код 26₁₆.

Ответ:

66.67 % коэффициент сжатия, MAAAAAAAAAAAAAAMAAAAAAAAAAAAAA

3.       Определите количество байтов в исходной и распакованной последовательности (см. предыдущее задание) и вычислите коэффициент сжатия:

4.       Проверьте результат, полученный в предыдущем пункте, с помощью программы RLE. Предложите два способа проверки.

1.Сжатие без потерь и 2. сжатие с потерей

5.       Постройте последовательности, которые сжимаются алгоритмом RLE ровно в 2 раза, в 4 раза, в 5 раз. Проверьте свои ответы с помощью программы RLE.

1. SSSSOOOEEERROOOAAYYYYYDDDDOEUUUUUWWWWJJJORRUUUUUUUUUUXXXKHHHHHHMMMMMMGGGLLLLLLLJJJJTTTTTTTTTTTTTTTTT

2. QWERTYYYYYYDFGHJJJJJJJVBNMQQQQQWWWWWWWWWWWEEEEEYYYYYUUUUUUQWERRRRRRASDFGHJKLVVVVCXZWWWWWWWWWWWWEEEEE

6.       Придумайте три последовательности, которые невозможно сжать с помощью алгоритма RLE:

1. QWERTYUIOPLKJHGFDSAZXCVBNM

2. QWERTYUIOPASDFGHJKLMNBVCXZEEEEEEEEEEEEEEEEEEWWPPPOOOOOOOQQQQQYYYWWW

3. BDNN

7.       Используя программу RLE, примените RLE-сжатие к следующим файлам и найдите для каждого из них коэффициент сжатия:

8.       Объясните результаты, полученные в предыдущем пункте:

·    почему не удается сжать рисунки в формате JPEG?

Ответ:

Потому, что jpeg - это уже сжатые данные. Причём сжатые куда эффективнее, чем может обеспечить RLE.

·    почему для двух рисунков в формате BMP одинакового размера коэффициенты сжатия по алгоритму RLE так сильно отличаются? Подсказка: откройте эти рисунки в любой программе просмотра.

Ответ:

Степень сжатия зависит от размера последовательности одинаковых байт, а не от размера файла. Чем она длиннее тем лучше сжатие, от самой картинки зависит так же как и архивирование, размер исходного файла может быть один и тот же, а коэффициент сжатия сильно отличаться

9.       Оцените максимально достижимый коэффициент сжатия с помощью рассмотренного в учебнике варианта RLE-алгоритма. В каком случае его удастся достичь?

Ответ:

Максимальное значение при одной длинной серии, минимальное при отсутствии серий

10.   Оцените коэффициент сжатия с помощью RLE-алгоритма в худшем случае. Опишите этот худший случай.

Ответ:

В худшем случае размер сжатых данных окажется больше исходного размера. Для кодирования пробега с помощью алгоритма RLE требуется информация, состоящая не менее чем из двух символов. В связи с чем запуск одиночных символов на самом деле занимает больше места. По тем же причинам данные, состоящие полностью из 2-символьных прогонов, остаются неизменными после кодирования.