Современные методы хранения информации в сжатом виде

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

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

       Существует  несколько разновидностей стандарта JPEG. Среди них - формат JPEG Baseline Optimized, основанный на более совершенном  алгоритме компрессии изображений. Недостатком данной реализации JPEG является то, что она не распознается целым рядом часто используемых приложений. Так называемый Progressive JPEG был оптимизирован специально для представления графики во Всемирной сети, изображения в этом формате сжимаются чуть лучше, чем в стандартном JPEG, но хуже, чем в JPEG Baseline Optimized. Отличительная особенность Progressive JPEG - возможность сохранять графику в чересстрочном режиме, как это реализовано в стандарте GIF.

       При работе со стандартом JPEG следует учитывать, что сжатию с наименьшей потерей  качества поддаются изображения, сохраненные с высоким разрешением, от 150 до 300 dpi. В процессе обработки иллюстраций лучше всего сохранять картинку в формате TIFF и переводить в JPEG лишь готовый результат, поскольку каждое промежуточное сохранение файла JPEG на диск приводит к удалению второстепенной информации и ухудшению качества рисунка.

       PNG

       Описанная чуть ранее криминальная история  с неожиданным изменением статуса  алгоритма сжатия LZW с бесплатного  на платный спровоцировала стремление пользователей избавиться от формата GIF, дальнейшая судьба которого становилась все более туманной. С этой целью во второй половине девяностых годов была создана инициативная группа программистов и исследователей, которую возглавил американский специалист по электронным технологиям Том Боутелл (Thomas Bowtell). Перед инициативной группой стояла нелегкая задача: разработать стандарт, который не только включал бы в себя все лучшие качества GIF, нo и превосходил бы его по всем характеристикам, оставаясь при этом совершенно бесплатным для пользователей. Основной областью применения данного формата должен был стать Интернет. Такой стандарт был создан и получил название Portable Network Graphics - PNG, хотя многие пользователи Всемирной сети придумали этой аббревиатуре иную расшифровку: Picture is Not GIF.

       PNG, как и GIF, поддерживает interlacing (чересстрочность), но в отличие от последнего  не только по горизонтали, но  и по вертикали. Палитра PNG не  ограничивается 256 цветами, данный  формат позволяет создавать изображения  с глубиной цвета до 48 бит. Весьма любопытные изменения внесены в режим прозрачности графики: PNG также поддерживает альфа-канал, по состоит он не из одного уровня, как альфа-канал файлов GIF, а из 254 уровней для каждого элемента изображения, с диапазоном прозрачности рт 0 до 99 %. Благодаря этому дизайнер получил возможность создавать картинки с переменной прозрачностью, например, логотипы, фон которых плавно сливается с фоновым цветом html-документа, каким бы тот ни был.

       Помимо  альфа-канала изображения PNG содержат так называемый блок описания гамма-коррекции. Под переменной гамма в данном случае подразумевается некая величина, выражающая зависимость яркости свечения каждой точки экрана пользователя от напряжения на электродах кинескопа, которое берется из файлов управления видеоподсистемой компьютера. Таким образом, при открытии изображения, созданного с помощью IBM-совместимой машины, на компьютере другого производителя, например на Apple Macintosh, в яркость цветопередачи вводится соответствующая поправка, и картинка отображается совершенно идентично на разных типах оборудования. Этим стандарт PNG еще более приблизился к основной идее Интернета единообразию отображения web-страниц на компьютерах от различных производителей.

       Поскольку данный формат появился на свет относительно недавно, его поддерживают далеко не все браузеры, в отличие от GIF и JPEG, которые распознаются без проблем любыми программами, предназначенными для отображения графики. PNG поддерживается Microsoft Internet Explorer, начиная с версии 4.0, и Netscape Communicator версий 4.04 и выше. Старые браузеры отобразить картинку в формате PNG не смогут.

       3.Хранение данных в сжатом виде. 

       Характерной особенностью большинства типов  данных является их избыточность. Степень  избыточности данных зависит от типа данных. Например, для видеоданных степень избыточности в несколько раз больше чем для графических данных, а степень избыточности графических данных, в свою очередь, больше чем степень избыточности текстовых данных. Другим фактором, влияющим на степень избыточности является принятая система кодирования. Примером систем кодирования могут быть обычные языки общения, которые являются ни чем другим, как системами кодирования понятий и идей для высказывания мыслей. Так, установлено, что кодирование текстовых данных с помощью средств русского языка дает в среднем избыточность на 20-25% большую, чем кодирование аналогичных данных средствами английского языка.

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

       В зависимости от того, в каком объекте  размещены данные, подлежащие сжатию различают:

       Сжатие (архивация) файлов: используется для  уменьшения размеров файлов при подготовке их к передаче каналами связи или  к транспортированию на внешних  носителях маленькой емкости;

       Сжатие (архивация) папок: используется как  средство уменьшения объема папок перед долгим хранением, например, при резервном копировании;

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

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

       Если  при сжатии данных происходит изменение  их содержимого, то метод сжатия называется необратимым, то есть при восстановлении (разархивировании) данных из архива не происходит полное восстановление информации. Такие методы часто называются методами сжатия с регулированными потерями информации. Понятно, что эти методы можно применять только для таких типов данных, для которых потеря части содержимого не приводит к существенному искажению информации. К таким типам данных относятся видео- и аудиоданные, а также графические данные. Методы сжатия с регулированными потерями информации обеспечивают значительно большую степень сжатия, но их нельзя применять к текстовым данным. Примерами форматов сжатия с потерями информации могут быть:

       JPEG - для графических данных;

       MPG - для для видеоданных;

       MP3 - для аудиоданных.

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

       GIF, TIFF - для графических данных;

       AVI - для видеоданных;

       ZIP, ARJ, RAR, CAB, LH - для произвольных типов  данных.

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

       алгоритм RLE (Run Length Encoding);

       алгоритмы группы KWE(KeyWord Encoding);

       алгоритм  Хаффмана.

       Алгоритм RLE

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

       1 1 1 1 2 2 3 4 4 4

       В алгоритме RLE предлагается заменить ее следующей структурой: 1 4 2 2 3 1 4 3, где первое число каждой пары чисел - это код данных, а второе - коэффициент повторения. Если для хранения каждого элемента данных входной последовательности отводится 1 байт, то вся последовательность будет занимать 10 байт памяти, тогда как выходная последовательность (сжатый вариант) будет занимать 8 байт памяти. Коэффициент сжатия, характеризующий степень сжатия, можно вычислить по формуле:

       где Vx- объем памяти, необходимый для  хранения выходной (результирующей) последовательности данных, Vn- входной последовательности данных.

       Чем меньше значение коэффициента сжатия, тем эффективней метод сжатия. Понятно, что алгоритм RLE будет давать лучший эффект сжатия при большей  длине повторяющейся последовательности данных. В случае рассмотренного выше примера, если входная последовательность будет иметь такой вид: 1 1 1 1 1 1 3 4 4 4, то коэффициент сжатия будет равен 60%. В связи с этим большая эффективность алгоритма RLE достигается при сжатии графических данных (в особенности для однотонных изображений).

       Алгоритмы группы KWE

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

       Существует  довольно много реализаций этого алгоритма, среди которых наиболее распространенными являются алгоритм Лемпеля-Зіва (алгоритм LZ) и его модификация алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словарем в данном алгоритме является потенциально бесконечный список фраз. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. При считывании очередного символа входной последовательности данных, он прибавляется к текущей строке. Процесс продолжается до тех пор, пока текущая строка соответствует какой-нибудь фразе из словаря. Но рано или поздно текущая строка перестает соответствовать какой-нибудь фразе словаря. В момент, когда текущая строка представляет собой последнее совпадение со словарем плюс только что прочитанный символ сообщения, кодер выдает код, который состоит из индекса совпадения и следующего за ним символа, который нарушил совпадение строк. Новая фраза, состоящая из индекса совпадения и следующего за ним символа, прибавляется в словарь. В следующий раз, если эта фраза появится в сообщении, она может быть использована для построения более длинной фразы, что повышает меру сжатия информации.

       Алгоритм LZW построен вокруг таблицы фраз (словаря), которая заменяет строки символов сжимаемого сообщения в коды фиксированной длины. Таблица имеет так называемое свойством опережения, то есть для каждой фразы словаря, состоящей из некоторой фразы w и символа К, фраза w тоже заносится в словарь. Если все части словаря полностью заполнены, кодирование перестает быть адаптивным (кодирование происходит исходя из уже существующих в словаре фраз).

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

       Алгоритм  Хаффмана

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