Групповое кодирование (сжатие методом RLE)

Для уменьшения размеров графических файлов многие форматы используют алгоритмы сжатия данных. Объем файла растрового изображения весьма значительно возрастает при увеличении параметров пиксельного изображения. При этом также очевидно, что существует громадная избыточность данных, которая никак не улучшает качество, но требует большого расхода дисковой памяти. Выбор формата, использующего алгоритмы сжатия может сэкономить место на жестком диске или носителе для пере­дачи файла на другой компьютер.

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

В этой области компьютерной теории разработаны два основных способа уменьшения объема хранения:

сжатие без потерь (lossless), когда информация полностью восстанавливается;

сжатие с потерями (lossy), когда информация до сжатия и после сжатия отличается в определенной и регулируемой степени.

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

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

Среди многочисленных существующих форматов хранения графических изображений невозможно выбрать самый лучший, что объясняется существенными различиями в их назначении. Таким образом, при выборе того или иного формата необходимо ориенти­роваться только на его соответствие выполняемой работе. В част­ности, форматы, предназначенные для подготовки изображений к печати, не подходят для размещения в Internet, и наоборот.

Растровые форматы устроены проще, чем векторные. Компьютер считывает информацию, хранящуюся в файле в следующей последовательности:

1. Определяется размер изображения.

2. Определяется размер пикселя, т.е. пространственное разрешение изображения.

3. Определяется глубина цвета (битовая глубина).

Теперь давайте подумаем как же и на чем можно экономить место при сжатии файлов. В некоторых файлах встречаются довольно длинные подцепочки одинаковых байтов. Представьте себе такой файл:

Aaaaabbbccccccccccccccadddddddddddddddd

Файл занимает на диске 39 Byte. Очевидно, что информация в файле несколько избыточна и хранение файла в таком виде не оправдано. Совсем другое дело, если файл будет выглядеть так:

5a3b14ca16d

В таком случае файл будет занимать всего 11 byte. В итоге файл можно записать экономичнее в 39/11=3,5 раза. На этом же примере можно описать еще один способ экономии дискового пространства. Как видно файл состоит всего из четырех символов. Если сопоставить каждому из них пару битов, то получим:

a - "00",
b - "01",
c - "10",
d - "11".

Иными словами файл можно закодировать таким образом, что каждый из символов будет кодироваться не восемью, а двумя битами. И тогда экономия будет четырехкратной (8/2=4). Следует заметить, что этот вариант алгоритма более общий, и одинаково эффективен, даже если в файле нет ни одной однородной подцепочки. Итак, если вы вникли в суть приведенных примеров, то вам в общих чертах должны быть понятны идеи, согласно которым происходит сжатие файлов. Заметьте, что, зная, каким именно правилом руководствовались при сжатии, архивы можно будет распаковать и получить исходные файлы. Это варианты архивации без потери качества (они обратимы).

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

Достоинством такого алгоритма является простота (что очень важно, т. к. позволяет выполнять процедуры компрессии и декомпрессии достаточно быстро). Недостатками являются - необходимость различать собственно данные и числа повторений, а также возможное увеличение объема файла, если в документе мало повторений (например, серия АВСАВС не уменьшит, а увеличит объем документа, поскольку будет иметь следующий вид: 1А1В1С1А1В1С, т. е. вместо 6 символов получится вдвое больше).