1 какие способы сжатия информации вы знаете

2.6 Методы сжатия информации

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

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

Первые теоретические разработки в области сжатия информации относятся к концу 40-х годов. В конце семидесятых появились работы Шеннона, Фано и Хафмана. К этому времени относится и создание алгоритма FGK (Faller, Gallager, Knuth), где используется идея «сродства», а получатель и отправитель динамически меняют дерево кодов (смотри, например, http://www.ics.uci.edu/~dan/plus/DC-Sec4.html).

В этом разделе пойдет речь о методах сжатия без потери информации. К таким методам относятся:

Алгоритм Хафмана
Арифметическое кодирование
Контекстное кодирование (PPM — Prediction by Partial Matching)
Алгоритм Зива-Лемпеля(-Welch)
Алгоритм Барроуза-Веллера
Brotli

Полное число алгоритмов сжатия данных без потерь информации существенно более десяти.

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

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

Сжатие информации без потерь осуществляется статистическим кодированием или на основе предварительно созданного словаря. Статистические алгоритмы (напр., схема кодирования Хафмана) присваивают каждому входному символу определенный код. При этом наиболее часто используемому символу присваивается наиболее короткий код, а наиболее редкому — более длинный. Распределение частот отдельных букв английского алфавита показано на рис. 2.6.1. Такое распределение может быть построено и для русского языка. Таблицы кодирования создаются заранее и имеют ограниченный размер. Этот алгоритм обеспечивает наибольшее быстродействие и наименьшие задержки. Для получения высоких коэффициентов сжатия статистический метод требует больших объемов памяти.

Рис. 2.6.1. Распределение английских букв по их частоте использования

Величина сжатия определяется избыточностью обрабатываемого массива бит. Каждый из естественных языков обладает определенной избыточностью. Среди европейских языков русский обладает одной из самых высоких уровней избыточности. Об этом можно судить по размерам русского перевода английского текста. Обычно он примерно на 30% больше. Если речь идет о стихотворном тексте, избыточность может быть до двух раз выше.

В 1977 году Абрахам Лемпель и Якоб Зив предложили алгоритм сжатия данных, названный позднее LZ77. Этот алгоритм используется в программах архивирования текстов compress, lha, pkzip и arj. Модификация алгоритма LZ78 применяется для сжатия двоичных данных. Эти модификации алгоритма защищены патентами США. Алгоритм предполагает кодирование последовательности бит путем разбивки ее на фразы с последующим кодированием этих фраз. Суть алгоритма заключается в следующем.

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

Альтернативой статистическому алгоритму стала схема сжатия, основанная на динамически изменяемом словаре (напр., алгоритмы Лемпеля-Зива). Данный метод предполагает замену потока символов кодами, записанными в памяти в виде словаря (таблица перекодировки). Соотношение между символами и кодами меняется вместе с изменением данных. Таблицы кодирования периодически меняются, что делает метод более гибким. Размер небольших словарей лежит в пределах 2-32 килобайт, но более высоких коэффициентов сжатия можно достичь при заметно больших словарях до 400 килобайт.

Реализация алгоритма возможна в двух режимах: непрерывном и пакетном. Первый использует для создания и поддержки словаря непрерывный поток символов. При этом возможен многопротокольный режим (например, TCP/IP и DECnet). Словари сжатия и декомпрессии должны изменяться синхронно, а канал должен быть достаточно надежен (напр., X.25 или PPP), что гарантирует отсутствие искажения словаря при повреждении или потере пакета. При искажении одного из словарей оба ликвидируются и должны быть созданы вновь.

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

При передаче пакетов иногда применяется сжатие заголовков, например, алгоритм Ван Якобсона (RFC-1144). Этот алгоритм используется при скоростях передачи менее 64 Kбит/с. При этом достижимо повышение пропускной способности на 50% для скорости передачи 4800 бит/с. Сжатие заголовков зависит от типа протокола. При передаче больших пакетов на сверх высоких скоростях по региональным сетям используются специальные канальные алгоритмы, независящие от рабочих протоколов. Канальные методы сжатия информации не могут использоваться для сетей, базирующихся на пакетной технологии, SMDS (Switched Multi-megabit Data Service), ATM, X.25 и Frame Relay. Канальные методы сжатия дают хорошие результаты при соединении по схеме точка-точка, а при использовании маршрутизаторов возникают проблемы — ведь нужно выполнять процедуры сжатия/декомпрессии в каждом маршрутизаторе, что заметно увеличивает суммарное время доставки информации. Возникает и проблема совместимости маршрутизаторов, которая может быть устранена процедурой идентификации при у становлении виртуального канала.

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

Если при работе с пакетами заголовки оставлять неизмененными, а сжимать только информационные поля, ограничение на использование стандартных маршрутизаторов может быть снято. Пакеты будут доставляться конечному адресату, и только там будет выполняться процедура декомпрессии. Такая схема сжатия данных приемлема для сетей X.25, SMDS, Frame Relay и ATM. Маршрутизаторы корпорации CISCO поддерживают практически все режимы сжатия/декомпрессии информации, перечисленные выше.

Этой проблеме посвящено много книг, например, David Salomon, Giovanni Motta, «Handbook of Data Compression», Springer, или Khalid Sayood, «Introduction to data compression». Обе книги можно, по крайней мере частично, просмотреть через Интернет. За последние 15 лет эти технологии достаточно мало изменились.

Алгоритм сжатия данных brotli для каналов Интернет разработан Юрки Алакуйяла (фин. Jyrki Alakuijala) и Золтаном Сабадка (2015г). Он использует методику Зива-Лемпеля ( LZ77), алгоритм Хафмана и моделирование контекста 2-го порядка. Алгоритм эффективно сжимает WEB-шрифты и поставляется со встроенным 120 килобайтным словарем. Метод опубликован в RFC-7932.

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

Сжатие информации с потерями и без потерь

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

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

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

Совсем немного теории для непрофессионалов

Позволю себе начать эту весьма серьезную тему со старой шутки. Беседуют два пенсионера:

— Вы не могли бы сказать мне номер вашего телефона? — говорит один.

— Вы знаете, — признается второй, — я, к сожалению, точно его не помню.

— Какая жалость, — сокрушается первый, — ну скажите хотя бы приблизительно…

Действительно, ответ поражает своей нелепостью. Совершенно очевидно, что в семизначном наборе цифр достаточно ошибиться в одном символе, чтобы остальная информация стала абсолютно бесполезной. Однако представим себе, что тот же самый телефон написан словами русского языка и, скажем, при передаче этого текста часть букв потеряна — что произойдет в подобном случае? Для наглядности рассмотрим себе конкретный пример: телефонный номер 233 34 44.

Соответственно запись «Двсти трцать три трицть четре сорк чтре», в которой имеется не один, а несколько пропущенных символов, по-прежнему легко читается. Это связано с тем, что наш язык имеет определенную избыточность, которая, с одной стороны, увеличивает длину записи, а с другой — повышает надежность ее передачи. Объясняется это тем, что вероятность появления каждого последующего символа в цифровой записи телефона одинакова, в то время как в тексте, записанном словами русского языка, это не так. Очевидно, например, что твердый знак в русском языке появляется значительно реже, чем, например, буква «а». Более того, некоторые сочетания букв более вероятны, чем другие, а такие, как два твердых знака подряд, невозможны в принципе, и так далее. Зная, какова вероятность появления какой-либо буквы в тексте, и сравнив ее с максимальной, можно установить, насколько экономичен данный способ кодирования (в нашем случае — русский язык).

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

Избыточность естественных языков

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

R = (Hmax — H)/ Hmax

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

Кодирование информации

Факт избыточности свидетельствует о возможностях перехода на иную систему кодирования, которая уменьшила бы избыточность передаваемого сообщения. Говоря о переходе на коды, которые позволяют уменьшить размер сообщения, вводят понятие «коды сжатия». В принципе, кодирование информации может преследовать различные цели:

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

Сжатие с потерями

Говоря о кодах сжатия, различают понятия «сжатие без потерь» и «сжатие с потерями». Очевидно, что когда мы имеем дело с информацией типа «номер телефона», то сжатие такой записи за счет потери части символов не ведет ни к чему хорошему. Тем не менее можно представить целый ряд ситуаций, когда потеря части информации не приводит к потери полезности оставшейся. Сжатие с потерями применяется в основном для графики (JPEG), звука (MP3), видео (MPEG), то есть там, где в силу огромных размеров файлов степень сжатия очень важна, и можно пожертвовать деталями, не существенными для восприятия этой информации человеком. Особые возможности для сжатия информации имеются при компрессии видео. В ряде случаев большая часть изображения передается из кадра в кадр без изменений, что позволяет строить алгоритмы сжатия на основе выборочного отслеживания только части «картинки». В частном случае изображение говорящего человека, не меняющего своего положения, может обновляться только в области лица или даже только рта — то есть в той части, где происходят наиболее быстрые изменения от кадра к кадру.

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

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

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

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

Сжатие без потерь

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

Наиболее известны два алгоритма сжатия без потерь: это кодирование Хаффмена (Huffman) и LZW-кодирование (по начальным буквам имен создателей Lempel, Ziv, Welch), которые представляют основные подходы при сжатии информации. Кодирование Хаффмена появилось в начале 50-х; принцип его заключается в уменьшении количества битов, используемых для представления часто встречающихся символов и соответственно в увеличении количества битов, используемых для редко встречающихся символов. Метод LZW кодирует строки символов, анализируя входной поток для построения расширенного алфавита, основанного на строках, которые он обрабатывает. Оба подхода обеспечивают уменьшение избыточной информации во входных данных.

Кодирование Хаффмена

Кодирование Хаффмена [1] — один из наиболее известных методов сжатия данных, который основан на предпосылке, что в избыточной информации некоторые символы используются чаще, чем другие. Как уже упоминалось выше, в русском языке некоторые буквы встречаются с большей вероятностью, чем другие, однако в ASCII-кодах мы используем для представления символов одинаковое количество битов. Логично предположить, что если мы будем использовать меньшее количество битов для часто встречающихся символов и большее для редко встречающихся, то мы сможем сократить избыточность сообщения. Кодирование Хаффмена как раз и основано на связи длины кода символа с вероятностью его появления в тексте.

Статическое кодирование

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

Динамическое кодирование

В том случае, когда вероятности символов входных данных неизвестны, используется динамическое кодирование, при котором данные о вероятности появления тех или иных символов уточняются «на лету» во время чтения входных данных.

LZW-сжатие

Алгоритм LZW [2], предложенный сравнительно недавно (в 1984 году), запатентован и принадлежит фирме Sperry.

LZW-алгоритм основан на идее расширения алфавита, что позволяет использовать дополнительные символы для представления строк обычных символов. Используя, например, вместо 8-битовых ASCII-кодов 9-битовые, вы получаете дополнительные 256 символов. Работа компрессора сводится к построению таблицы, состоящей из строк и соответствующих им кодов. Алгоритм сжатия сводится к следующему: программа прочитывает очередной символ и добавляет его к строке. Если строка уже находится в таблице, чтение продолжается, если нет, данная строка добавляется к таблице строк. Чем больше будет повторяющихся строк, тем сильнее будут сжаты данные. Возвращаясь к примеру с телефоном, можно, проведя весьма упрощенную аналогию, сказать, что, сжимая запись 233 34 44 по LZW-методу, мы придем к введению новых строк — 333 и 444 и, выражая их дополнительными символами, сможем уменьшить длину записи.

Какой же выбрать архиватор?

Наверное, читателю будет интересно узнать, какой же архиватор лучше. Ответ на этот вопрос далеко не однозначен.

Если посмотреть на таблицу, в которой «соревнуются» архиваторы (а сделать это можно как на соответствующем сайте в Интернете [3], так и на нашем CD-ROM), то можно увидеть, что количество программ, принимающих участие в «соревнованиях», превышает сотню. Как же выбрать из этого многообразия необходимый архиватор?

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

Если вас не волнуют меркантильные соображения, то прежде всего необходимо уяснить, что имеется целый ряд архиваторов, которые оптимизированы на решение конкретных задач. В связи с этим существуют различные виды специализированных тестов, например на сжатие только текстовых файлов или только графических. Так, в частности, Wave Zip в первую очередь умеет сжимать WAV-файлы, а мультимедийный архиватор ERI лучше всех упаковывает TIFF-файлы. Поэтому если вас интересует сжатие какого-то определенного типа файлов, то можно подыскать программу, которая изначально предназначена специально для этого.

Существует тип архиваторов (так называемые Exepackers), которые служат для сжатия исполняемых модулей COM, EXE или DLL. Файл упаковывается таким образом, что при запуске он сам себя распаковывает в памяти «на лету» и далее работает в обычном режиме.

Одними из лучших в данной категории можно назвать программы ASPACK и Petite. Более подробную информацию о программах данного класса, а также соответствующие рейтинги можно найти по адресу [4].

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

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

Поддержка различных форматов

Большинство программ поддерживают один или два формата. Однако некоторые, такие, например, как программа WinAce, поддерживают множество форматов, осуществляя компрессию в форматах ACE, ZIP, LHA, MS-CAB, JAVA JAR и декомпрессию в форматах ACE, ZIP, LHA, MS-CAB, RAR, ARC, ARJ, GZip, TAR, ZOO, JAR.

Умение создавать solid-архивы

Создание solid-архивов — это архивирование, при котором увеличение сжатия возрастает при наличии большого числа одновременно обрабатываемых коротких файлов. Часть архиваторов, например ACB, всегда создают solid-архивы, другие, такие как RAR или 777, предоставляют возможность их создания, а некоторые, например ARJ, этого делать вообще не умеют.

Возможность создавать многотомные архивы

Многотомные архивы необходимы, когда файлы переносятся с компьютера на компьютер с помощью дискет и архив не помещается на одной дискете.

Возможность работы в качестве менеджера архивов

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

Возможность парольной защиты

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

Удобство в работе

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

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

ПК и комплектующие

Настольные ПК и моноблоки
Портативные ПК
Серверы
Материнские платы
Корпуса
Блоки питания
Оперативная память
Процессоры
Графические адаптеры
Жесткие диски и SSD
Оптические приводы и носители
Звуковые карты
ТВ-тюнеры
Контроллеры
Системы охлаждения ПК
Моддинг
Аксессуары для ноутбуков

Принтеры, сканеры, МФУ
Мониторы и проекторы
Устройства ввода
Внешние накопители
Акустические системы, гарнитуры, наушники
ИБП
Веб-камеры
KVM-оборудование

Сетевые медиаплееры
HTPC и мини-компьютеры
ТВ и системы домашнего кинотеатра
Технология DLNA
Средства управления домашней техникой

Планшеты
Смартфоны
Портативные накопители
Электронные ридеры
Портативные медиаплееры
GPS-навигаторы и трекеры
Носимые гаджеты
Автомобильные информационно-развлекательные системы
Зарядные устройства
Аксессуары для мобильных устройств

Цифровые фотоаппараты и оптика
Видеокамеры
Фотоаксессуары
Обработка фотографий
Монтаж видео

Операционные системы
Средства разработки
Офисные программы
Средства тестирования, мониторинга и диагностики
Полезные утилиты
Графические редакторы
Средства 3D-моделирования

Веб-браузеры
Поисковые системы
Социальные сети
«Облачные» сервисы
Сервисы для обмена сообщениями и конференц-связи
Разработка веб-сайтов
Мобильный интернет
Полезные инструменты

Средства защиты от вредоносного ПО
Средства управления доступом
Защита данных

Проводные сети
Беспроводные сети
Сетевая инфраструктура
Сотовая связь
IP-телефония
NAS-накопители
Средства управления сетями
Средства удаленного доступа

Системная интеграция
Проекты в области образования
Электронный документооборот
«Облачные» сервисы для бизнеса
Технологии виртуализации

1999	1	2	3	4	5	6	7	8	9	10	11	12
2000	1	2	3	4	5	6	7	8	9	10	11	12
2001	1	2	3	4	5	6	7	8	9	10	11	12
2002	1	2	3	4	5	6	7	8	9	10	11	12
2003	1	2	3	4	5	6	7	8	9	10	11	12
2004	1	2	3	4	5	6	7	8	9	10	11	12
2005	1	2	3	4	5	6	7	8	9	10	11	12
2006	1	2	3	4	5	6	7	8	9	10	11	12
2007	1	2	3	4	5	6	7	8	9	10	11	12
2008	1	2	3	4	5	6	7	8	9	10	11	12
2009	1	2	3	4	5	6	7	8	9	10	11	12
2010	1	2	3	4	5	6	7	8	9	10	11	12
2011	1	2	3	4	5	6	7	8	9	10	11	12
2012	1	2	3	4	5	6	7	8	9	10	11	12
2013	1	2	3	4	5	6	7	8	9	10	11	12

Методы сжатия информации

WFst

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

Метод кодирования длины серий

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

Пример. Используя метод кодирования длины серий последовательность: 111111111100000000000000000 — можно представить в следующем виде: 1[10]0[17].

Метод относительного кодирования

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

Пример. Используя метод относительного кодирования, последовательность цифр: 1476; 1473; 1480; 1477 — можно представить в следующем виде: 1476; -3; +7; -3.

Частотно-зависимое кодирование

Этот метод сжатия данных предполагает применение частотно-зависимого кодирования, при котором длина битовой комбинации, представляющей элемент данных, обратно пропорциональна частоте использования этого элемента. Такие коды входят в группу кодов переменной длины, т.е. элементы данных в этих кодах представляются битовыми комбинациями различной длины. Если взять английский текст, закодированный с помощью частотно-зависимого метода, то чаще всего встречающиеся символы [е, t, а, i] будут представлены короткими битовыми комбинациями, а те знаки, которые встречаются реже [z, q, x], — более длинными битовыми комбинациями. В результате мы получим более короткое представление всего текста, чем при использовании обычного кода, подобного Unicode или ASCII. Построение алгоритма, который обычно используется при разработке частотно-зависимых кодов, приписывают Девиду Хаффману [David Huffman], поэтому такие коды часто называются кодами Хаффмана. Большинство используемых сегодня частотно-зависимых кодов является кодами Хаффмана.

Пример. Пусть требуется закодировать частотно-зависимым методом последовательность: αγααβααγααβαλααβαβαβαβαα, которая состоит из четырех символов α, β, γ и λ. Причем в этой последовательности α встречается 15 раз, β — 6 раз, γ — 2 раза и λ — 1 раз.

Выберем в соответствии с методом Хаффмана следующий двоичный код для представления символов:

α — 1
β — 01
γ — 001
λ — 000

Метод Лемпеля-Зива

Данный метод назван в честь его создателей, Абрахама Лемпеля [Abraham Lempel] и Джэкоба Зива [Jacob Ziv]. Системы кодирования по методу Лемпеля-Зива используют технологию кодирования с применением адаптивного словаря. В данном контексте термин словарь означает набор строительных блоков, из которых создается сжатое сообщение. Если сжатию подвергается английский текст, то строительными блоками могут быть символы алфавита. Если потребуется уменьшить размер данных, которые хранятся в компьютере, то компоновочными блоками могут стать нули и единицы. В процессе адаптивного словарного кодирования содержание словаря может изменяться. Например, при сжатии английского текста может оказаться целесообразным добавить в словарь окончание ing и артикль the. В этом случае место, занимаемое будущими копиями окончания ing и артикля the, может быть уменьшено за счет записи их как одиночных ссылок вместо сочетания из трех разных ссылок. Системы кодирования по методу Лемпеля-Зива используют изощренные и весьма эффективные методы адаптации словаря в процессе кодирования или сжатия. В частности, в любой момент процесса кодирования словарь будет состоять из тех комбинаций, которые уже были закодированы [сжаты].

В качестве примера рассмотрим, как можно выполнить сжатие сообщения с использованием конкретной системы метода Лемпеля-Зива, известной как LZ77. Процесс начинается практически с переписывания начальной части сообщения, однако в определенный момент осуществляется переход к представлению будущих сегментов с помощью триплетов, каждый из которых будет состоять из, двух целых чисел и следующего за ними одного символа текста. Каждый триплет описывает способ построения следующей части сообщения. Например, пусть распакованный текст имеет следующий вид:

Строка αβααβλβ является уже распакованной частью сообщения. Для того чтобы разархивировать остальной текст сообщения, необходимо сначала расширить строку, присоединив к ней ту часть, которая в ней уже встречается. Первый номер в триплете указывает, сколько символов необходимо отсчитать в обратном направлении в строке, чтобы найти первый символ добавляемого сегмента. В данном случае необходимо отсчитать в обратном направлении 5 символов, и мы попадем на второй слева символ а уже распакованной строки. Второе число в триплете задает количество последовательных символов справа от начального, которые составляют добавляемый сегмент. В нашем примере это число 4, и это означает, что добавляемым сегментом будет ααβλ. Копируем его в конец строки и получаем новое значение распакованной части сообщения: αβααβλβααβλ.

Наконец, последний элемент [в нашем случае это символ α] должен быть помещен в конец расширенной строки, в результате чего получаем полностью распакованное сообщение: αβααβλβααβλα.

Сжатие изображений

Растровый формат, используемый в современных цифровых преобразователях изображений, предусматривает кодирование изображения в формате по три байта на пиксель, что приводит к созданию громоздких, неудобных в работе растровых файлов. Специально для этого формата было разработано множество схем сжатия, предназначенных для уменьшения места, занимаемого подобными файлами на диске. Одной из таких схем является формат GIF [Graphic Interchange Format], разработанный компанией CompuServe. Используемый в ней метод заключается в уменьшении количества цветовых оттенков пикселя до 256, в результате чего цвет каждого пикселя может быть представлен одним байтом вместо трех. С помощью таблицы, называемой цветовой палитрой, каждый из допустимых цветовых оттенков пикселя ассоциируется с некоторой комбинацией цветов «красный-зеленый-синий». Изменяя используемую палитру, можно изменять цвета, появляющиеся в изображении.

Обычно один из цветов палитры в формате GIF воспринимается как обозначение «прозрачности». Это означает, что в закрашенных этим цветом участках изображения отображается цвет того фона, на котором оно находится. Благодаря этому и относительной простоте использования изображений формат GIF получил широкое распространение в тех компьютерных играх, где множество различных картинок перемещается по экрану.

Другим примером системы сжатия изображений является формат JPEG. Это стандарт, разработанный ассоциацией Joint Photographic Experts Group [отсюда и название этого стандарта] в рамках организации ISO. Формат JPEG показал себя как эффективный метод представления цветных фотографий. Именно по этой причине данный стандарт используется производителями современных цифровых фотокамер. Следует ожидать, что он окажет немалое влияние на область цифрового представления изображений и в будущем.

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

К сожалению, при использовании режима «без потерь» создаваемые файлы растровых изображений настолько велики, что они с трудом обрабатываются методами современной технологии, а потому и применяются на практике крайне редко. Большинство существующих приложений использует другой стандартный метод формата JPEG — режим «базовых строк». В этом режиме каждый из пикселей также представляется тремя составляющими, но в данном случае это уже один компонент яркости и два компонента цвета. Грубо говоря, если создать изображение только из компонентов яркости, то мы увидим черно-белый вариант изображения, так как эти компоненты отражают только уровень освещенности пикселя.

Смысл подобного разделения между цветом и яркостью объясняется тем, что человеческий глаз более чувствителен к изменениям яркости, чем цвета. Рассмотрим, например, два равномерно окрашенных синих прямоугольника, которые абсолютно идентичны, за исключением того, что на один из них нанесена маленькая яркая точка, тогда как на другой — маленькая зеленая точка той же яркости, что и синий фон. Глазу проще будет обнаружить яркую точку, а не зеленую. Режим «базовых строк» стандарта JPEG использует эту особенность, кодируя компонент яркости каждого пикселя, но усредняя значение цветовых компонентов для блоков, состоящих из четырех пикселей, и записывая цветовые компоненты только для этих блоков. В результате окончательное представление изображения сохраняет внезапные перепады яркости, однако оставляет размытыми резкие изменения цвета. Преимущество этой схемы состоит в том, что каждый блок из четырех пикселей представлен только шестью значениями [четыре показателя яркости и два — цвета], а не двенадцатью, которые необходимы при использовании схемы из трех показателей на каждый пиксель.

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

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

Разработаны и применяются два типа алгоритмов сжатия:

• сжатие с изменением структуры данных (оно происходит без потери данных);
• сжатие с частичной потерей данных.

Алгоритмы первого типа предусматривают две операции: сжатие информации для хранения, передачи и восстановление данных точно в исходном виде, когда их требуется использовать. Такой тип сжатия применяется, например, для хранения текстов (наиболее известны алгоритмы Хаффмана и Лемпела—Зива). Алгоритмы второго типа не позволяют полностью восстановить оригинал и применяются для хранения графики или звука; для текстов, чисел или программ они неприменимы.

Алгоритмы сжатия

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

1. Сжатие без потерь (lossless compression) — собственно сжатие в смысле приведенного выше определения.
2. Сжатие с потерями (lossy compression) — процесс, состоящий из двух этапов:
- • выделение сохраняемой части информации в зависимости от цели сжатия и особенностей приемника и источника;
- • собственно сжатие без потерь.
Методы сжатия без потерь

В основе всех методов сжатия лежит простая идея: если представлять часто используемые элементы короткими кодами, а редко используемые — длинными кодами, то для хранения блока данных требуется меньший объем памяти, чем если бы все элементы представлялись кодами одинаковой длины. Точная связь между вероятностями и кодами установлена в теореме Шеннона о кодировании источника: элемент а., вероятность появления которого равняется р., выгоднее всего представлять —log ₁p_j бит. Если при кодировании размер элементарных кодов в точности получается равным —log^., то длина кода будет минимальной из всех возможных способов алфавитного кодирования и равна энтропии tf = -2>, log_2jP|. Сжатие всегда осуществляется за счет устранения статистической избыточности в представлении информации. Компрессор не может сжать любой файл. Размер некоторых файлов уменьшается, а остальных остается неизменным или увеличивается.

Коды Хаффмана (Huffman Coding), или коды с минимальной избыточностью

Характеристики: степени сжатия — от 1 до 8, средняя — 1,5; не увеличивает размер файла (не считая таблицы перекодировки).

Кодирование длин повторов, Run Length Encoding (RLE)

Один из наиболее старых методов сжатия. Идея метода состоит в замене идущих подряд одинаковых символов (бит или байт) парой (количество, символ). В основном используется для кодирования растровых изображений. Характеристика: степень сжатия от 0,5 до 32.

Алгоритмы Зива-Лемпеля (LZ-методы)

Реализации LZ77, LZ78, LZW и LZH. Относятся к словарным методам сжатия, т. е. сообщение кодируется не побуквенно (алфавитное кодирование), а по словам. Характеристики LZ78: степень сжатия в зависимости отданных, обычно 2—3, алгоритмы универсальны, но лучше всего подходят для сжатия текстов, рисованных картинок или других однородных данных.

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

Рассмотрим подробнее алгоритм LZ78. Кодируемый текст разбивается на слова, каждое из которых кодируется парой (номер, символ). За один проход по тексту динамически строится словарь и сжатый текст. Изначально словарь содержит одно слово с номером 0 — пустое Л. На каждом шаге алгоритма считываются символы, начиная с текущего, и формируется слово наибольшей длины, совпадающее с каким-нибудь из уже имеющихся в словаре, плюс еще один символ.

Рассмотрим, например, входную последовательность 010 001 011 001 010 001 101 011 00.

На первом шаге рассматривается слово из одного символа 0, оно добавляется в словарь под номером 1 и кодируется в выходной последовательности (0,0), что означает слово из словаря под номером 0 (пустое слово) + символ 0. На втором шаге в словарь добавляется слово 1 под номером 2, имеющее код (1,0). На третьем шаге имеем совпадение с непустым словом в словаре 0, в словарь добавляется слово 00, имеющее код (1,0), и т. д. На шестом шаге мы уже закодировали последовательность 010001011, словарь имеет вид , остался текст 0010100011. Максимальное совпадение с третьим словом словаря «00». Данная последовательность вместе со следующим символом (здесь 1) кодируется парой чисел (номер совпадающего слова в словаре, следующий символ) (здесь (3,1)) и добавляется в словарь (теперь словарь имеет вид (Л, 0, 1, 00, 01, 011, 001>. На следующем шаге считывается следующий за уже закодированными символ и т. д. до конца входного текста.

В результате последовательности 010 001 011 001 010 001 101 011 00 соответствует словарь , разбиение последовательности на слова и код (см. табл. 7):
Похожие публикации: