Методические указания к заданию 3.1

Несмотря на то, что объемы внешней памяти ЭВМ постоянно растут, по-требность в сжатии информации не уменьшается. Это объясняется тем, что сжатие необходимо не только для экономии места в памяти ЭВМ, но и для бы-строй передачи информации по Сети.

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

Сжатие информации (архивация)—это такое преобразование информа-ции, при котором объем файла уменьшается, а количество информации, содер-жащейся в архиве, остается прежним.

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

K_c ^Vo.

V_c

Чем больше величина K_c, тем выше степень сжатия информации.

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

В настоящее время разработано много алгоритмов архивации без потерь. Однако все они используют две простые идеи.

Первая идея, основанная на учете частот появления символов в тексте, бы-ла разработана Клодом Шенноном и независимо от него Робертом Фано, а за-тем в 1952 г. развита Дэвидом Хаффманом - аспирантом Массачусетского технологического института при написании им курсовой работы. Идея базиру-ется на том факте, что в обычном тексте частоты появления различных симво-лов неодинаковые.

Вторая основная идея сжатия состоит в учете того факта, что в файлах час-то встречаются несколько подряд идущих одинаковых байтов, а некоторые по-следовательности байтов повторяются многократно. При архивации такие мес-та файла можно заменить командами вида «повторить данный байт n раз» или «взять часть данных длиной k байтов, которая встречалась m байтов назад». Та-кой алгоритм архивации носит имя RLE (Run Length Encoding — кодирование путем учета повторений или кодирование длин серий).

Рассмотрим детально метод сжатия RLE.

Упакованная методом RLE последовательность состоит из управляющих

8

_______________________________________________________________________________

байтов,за которыми следуют один или несколько байтов данных.При этом ес-ли старший бит управляющего байта равен 1, то следующий за ним байт дан-ных нужно повторить при декодировании столько раз, сколько указано в ос-тавшихся 7 битах управляющего байта.

Например, управляющий байт 10001001 говорит, что следующий за ним байт нужно повторить 9 раз, так как 1001₂ = 9₁₀.

Если старший бит управляющего байта равен 0, то при декодировании нужно взять несколько следующих байтов без изменений. Число байтов, кото-рые берутся без изменений, указывается в оставшихся 7 битах. Например, управляющий байт 00000011 говорит, что следующие за ним 3 байта нужно взять без изменений.

Рассмотрим пример сжатия методом RLE.

Пусть дана некоторая последовательность из 12 байтов:

11111111 11111111 11111111 11111111 11111111 11110000

00001111 11000011 10101010 10101010 10101010 10101010.

В начале исходной двоичной последовательности 5 раз повторяется байт 11111111. Чтобы упаковать эти 5 байтов, нужно записать сначала управляющий байт 10000101, а затем повторяемый байт 11111111. В результате сжатия этого фрагмента данных выигрыш составит 3 байта. Далее идут 3 разных (неповто-ряющихся) байта: 11110000 00001111 и 11000011. Чтобы их «упаковать», нуж-но записать управляющий байт 00000011, а затем указать эти 3 неповторяю-щихся байта. В результате архивации этого фрагмента двоичной последова-тельности получается увеличение объема архива на 1 байт. Далее в последова-тельности 4 раза повторяется байт 10101010. Для архивации этого фрагмента двоичных данных нужно сформировать управляющий байт 10000100 и записать повторяемый байт 10101010. Сжатие последнего фрагмента даст выигрыш 2 байта.

В результате такой архивации получена новая последовательность данных (архив), состоящая из 8 байтов:

10000101 11111111 00000011 11110000

00001111 11000011 10000100 10101010.

Таким образом, 12 байт исходной двоичной последовательности удалось сжать до 8 байт.

12

^Kc ₈ ^{1, 5 .}

9

_______________________________________________________________________________

Пример.

Выполним сжатие сообщения методом RLE. Текст сообщения:

ИНН 222221333.

Таким образом, тринадцать байт исходного текста сжаты до двенадцати байт.

Для упрощения проверки результата сжатия были вычислены контрольные суммы (КС) в двоичной и шестнадцатеричной системах счисления.

Коэффициент сжатия в данном случае составил:

13

^Kc ₁₂ ^{1, 08 .}

10

_______________________________________________________________________________