СЖАТИЕ ДАННЫХ [data compression]

Сжатие данных - это, Что такое сжатие данных, Определение термина сжатие данных, Статическое сжатие данных, Физическое сжатие, Логическое сжатие, Симметричное сжатие, Асимметричное сжатие, Адаптивное кодирование, Неадаптивное кодирование, Полуадаптивное кодирование, Сжатие без потерь, Сжатие с потерями, Сжатие изображения, Сжатие диска, Метод сжатия Хаффмена, Фрактальное сжатие, ART, АСЗ Dolby, DJVU, DVI, EAD, Image compression manager, Сжатие JBIG, LZW, MP3, МРЗРго, RLE

Технический прием сокращения объема (размеров) записи данных на их носителе (например на жестком магнитном диске, дискете, магнитной ленте и т. п.). Реализуется разными методами, преимущественно использующими кодирование (повторяющихся слов, фраз, символов и т.п.). Условно можно выделить две группы режимов сжатия данных: статический и динамический. Различают также физическое и логическое сжатие; симметричное и асимметричное сжатие; адаптивное, полуадаптивное и неадаптивное кодирование; сжатие без потерь, с потерями и минимизацией потерь.
Способы (виды) сжатия данных
 - Статическое сжатие данных [static data compression] — используется при необходимости длительного хранения и архивации. Выполняется при помощи специальных сервисных программ-архиваторов, например ARJ, PKZIP/PKUNZIP. После восстановления (декомпрессии) исходная запись восстанавливается.
 - Динамическое сжатие, сжатие в реальном времени [dynamic compression, compression in real time] —сжатие любых видов данных, предназначенное для сокращения занимаемой области дисковой памяти данными, требующими оперативного доступа, и их вывода на внешние устройства ЭВМ (в том числе на экран монитора). Динамическое сжатие данных и их восстановление производится специальными программными средствами автоматически и "мгновенно".
 - Физическое сжатие [physical compression] — методология сжатия, при которой данные перестраиваются в более компактную форму "формально", т. е. без учета характера содержащейся в них информации.
 - Логическое сжатие [logical compression] — методология, в соответствии с которой один набор алфавитных, цифровых или двоичных символов заменяется другим. При этом смысловое значение исходных данных сохраняется. Одним из примеров может служить замена словосочетания его аббревиатурой. Логическое сжатие производится только на символьном или более высоком уровне и основано исключительно на содержании исходных данных. Не применяется для изображений.
 - Симметричное сжатие [symmetric compression] — методология сжатия, в соответствии с которой принципы построения алгоритмов упаковки и распаковки данных близки или тесно взаимосвязаны. При использовании симметричного сжатия время, затрачиваемое на сжатие и распаковку данных, соизмеримо. В программах обмена данными обычно используется симметричное сжатие.
 - Асимметричное сжатие [asymmetric compression] — методология, в соответствии с которой при выполнении работ "в одном направлении" времени затрачивается больше, чем при выполнении работ в другом направлении. Так, на сжатие изображений обычно затрачивается намного больше времени и системных ресурсов, чем на их распаковку. Эффективность этого подхода определяется тем, что сжатие изображений может производиться только один раз, а распаковываться с целью их отображения — многократно. Алгоритмы асимметричные "в обратном направлении" (на сжатие данных затрачивается меньше времени, чем на распаковку) используется при выполнении резервного копирования данных.
 - Адаптивное кодирование [adaptive encoding] — методология кодирования при сжатии данных, которая заранее не настраивается на какой-либо определенный вид данных. Программы, использующие адаптивное кодирование, настраиваются на любой тип сжимаемых данных, добиваясь максимального сокращения их объема.
 - Неадаптивное кодирование [nonadaptive encoding] — методология кодирования, ориентированная на сжатие определенного типа или типов данных. Кодировщики, построенные по этому принципу, имеют в своем составе статические словари "предопределенных подстрок, о которых известно, что они часто появляются в кодируемых данных. Примером может служить метод сжатия Хаффмена.
 - Полуадаптивное кодирование [half-adaptive coding] — методология кодирования при сжатии данных, которая использует элементы адаптивного и неадаптивного кодирования. Принцип действия полуадаптивного кодирования заключается в том, что кодировщик выполняет две группы операций: вначале —просмотр массива кодируемых данных и построение для них словаря, а затем —собственно кодирование.
 - Сжатие без потерь [lossless compression] — методология сжатия, при которой ранее закодированная порция данных восстанавливается после их распаковки полностью без внесения каких-либо изменений.
 - Сжатие с потерями [lossy compression] — методология, при которой для обеспечения максимальной степени сжатия исходного массива часть содержащихся в нем данных отбрасывается. Для текстовых, числовых и табличных данных использование программ, реализующих подобные методы сжатия, является неприемлемой. Однако для программ, работающих с графикой, это часто бывает целесообразно. Качество восстановленного изображения зависит от характера графического материала и корректности реализованного в программе алгоритма сжатия. Существует ряд алгоритмов сжатия, учитывающих допустимые уровни потерь исходного графического образа в конкретных вариантах использования его восстановленного изображения, например, путем просмотра его на экране монитора, распечатки принтером, в полиграфии т. п. Эти методы имеют общее наименование "сжатия с минимизацией потерь".
 - Сжатие изображения [image compression] — технический прием или метод сокращения объема (размеров) записи графических изображений (рисунков, чертежей, схем и т. п.) на их носителе (например на магнитном диске и магнитной ленте). По существу "сжатие изображения" является разновидностью динамического сжатия. Для его реализации используются различные способы кодирования данных, которые ориентированы на элементы графики, составляющие изображение, включая и движущиеся объекты. Применяется также при передаче факсимильной информации по каналам связи, в системах мультимедиа, видеофонах и т. д.
 - Сжатие диска [disk compression] — технический прием, основанный на динамическом сжатии разного вида данных непосредственно в процессе их записи на диск, а при считывании —их автоматическом восстановлении в исходную форму. Используется с целью увеличения емкости диска. В зависимости от характера записей последняя может быть увеличена примерно от 1,5 до 5 раз. Реализуется сжатие диска специальными прикладными программами, например DoubleSpace, Stacker, SuperStor.
Методы и средства сжатия данных
 - Метод сжатия Хаффмена [Huffman compression method]. Кодирование CCITT — метод разработан в 1952 г. Дэвидом Хаффменом (David Huffman). Международный консультативный комитет по телефонии и телеграфии (CCITT) разработал на его основе ряд коммуникативных протоколов для факсимильной передачи черно-белых изображений по телефонным каналам и сетям передачи данных (Стандарт Т.4 CCIT и Т.6 CCITT, они же — сжатие CCITT group 3 и сжатие CCITT group 4, соответственно). Используется так же, как составная часть в ряде других схем сжатия. Так в методе Хаффмена берется набор символов, который анализируется, чтобы определить частоту каждого символа. Затем для наиболее часто встречающихся символов используется представление в виде минимально возможного количества битов. Например, буква "е" чаще всего встречается в английских текстах. Используя кодировку Хаффмена, можно представить "е" всего лишь двумя битами (1 и 0) вместо восьми битов, необходимых для представления этой буквы в кодировке ASCII.
 - Фрактальное сжатие [fractal compression] — метод сжатия растровых изображений путем преобразования их в так называемые фракталы. Отличается высокой эффективностью сжатия: хранение изображений в виде фракталов требует в 4 раза меньше дисковой памяти, нежели представления этих же изображений пикселями. В процессе преобразования обычных растровых изображений во фрактальные данные реализуются два преимущества. Первое — возможность масштабировать фрактальное изображение без потери деталей и введения артефактов, что характерно для растровых изображений. Причем этот процесс не зависит от разрешения исходного изображения, а масштаб ограничивается только объемом свободной памяти компьютера. Второе преимущество состоит в том, что размер физических данных, используемых для записи фрактальных кодов, значительно меньше (иногда в 100 раз) объема растровых данных. Фрактальное сжатие сопровождается потерями, однако процессом кодирования можно управлять, доводя его до состояния, когда в изображении потери визуально не наблюдаются. Метод впервые использован при производстве CD-ROM в 1993 г.
 - ART —метод сжатия, созданный Стивом Джонсоном и Крисом Грейсом. С 1992 г. фирма Jonson-Grace разрабатывает и продает инструментальные программные средства для разного рода онлайновых, включая Интернет, приложений. Алгоритм ART считается универсальным. Предназначен для сжатия текста, графики, аудио и видео. Принцип работы алгоритма разработчик не разглашает, однако сообщается, что его цель —анализ изображения и выявление его ключевых признаков (цвет, помехи, края, повторяющиеся особенности). Этим признакам присваиваются "приоритеты" в соответствии с их относительным весом в анализируемом изображении. Для классификации и назначения приоритетов используется неясная логика (терминология фирмы). Повторяющиеся особенности выявляются и связываются в изображении методом, разработанным самой фирмой. Компоненты изображения квантуются, при этом низкоприоритетные компоненты игнорируются. Как и при использовании алгоритма JPEG, степень потерь данных повышается пропорционально росту степени сжатия и компенсируется при каждой степени сжатия избыточностью. Отмечается, что гибкое адаптирование процесса сжатия по отношению к характеру изображения дает хорошие результаты.
 - АСЗ Dolby —метод и формат сжатия, который позволяет сжимать, хранить и передавать в одном файле со скоростью от 32 до 640 кбит/с до 6 каналов аудиоданных. Формат позволяет сжимать аудиопотоки с частотой дискретизации 32, 44,1 и 48 кГц. Другое наименование —АСЗ, предназначен для передачи и воспроизведения 5 + 1-канального формата объемного цифрового звука —Dolby Digital АСЗ. Альтернативная система передачи звука обеспечивает многоканальную передачу в формате Dolby Surround Digital 5 + 1 каналов со скоростью 384 Кбит/с. Используется в домашних кинотеатрах, для звукового сопровождения видео- и ТВ-фильмов и т. п.
 - DJVU, DjVu, djvu, deja vu —технология и формат динамического сжатия отсканированных страниц изданий, содержащих текстовые и иллюстративные материалы. Разработка выполнена и доведена до практического использования в 2000 г. сотрудниками Исследовательской лаборатории фирмы AT&T (AT&T Labs-Research) — Леоном Боттоу (Leon Bottou), Яном ЛеКуном (Yann Le-Cun), Патриком Хаффнером (Patrick Haffner) и др. Особенностями формата являются:
1. Сохранение приемлемого для электронных изданий качества цветных изображений, сопоставимое с последними версиями формата JPEG, однако существенно более экономичное (сжатое цветное изображение, содержащее текст и рисунки, в 5-10 раз меньше сжатого по методу JPEG, черно-белые страницы сжимаются в 10—20 раз лучше, чем JPEG);
2. Качество передаваемого текста удовлетворительное, хотя и несколько хуже, чем в формате PDF;
3. Сохранение формата страницы в издании, содержащей оцифрованный текст и изображение;
4. Динамическое раскрытие скачиваемого из сети и выводимого на экран изображения страницы при скроллинге (оперативная память ПК не "держи/ невидимых частей документа);
5. Быстрая загрузка изображения и т.д.
Недостатками формата (например, по отношению к HTML) являются его излишняя сложность, необходимость использования специального редактора, громоздкая кодировка, не безупречное качество изображения.
В DJVU применяется специальная технология, отделяющая от сканированного образа весь текст и сжимающая его, сохраняя первоначальное качество. Картинки же переводятся в 100 dpi и подвергаются сжатию с использованием техники "вейвлетов" (популярный метод, часто использующийся для онлайновой декомпрессии данных). Дополнительно происходит обработка фоновых частей образа. При этом удается исключить из конечного файла фрагменты изображения, которые не видны (к примеру— стоят за картинками или за текстом). Каждая картинка подвергается некоторым преобразованиям, призванным сократить размер файла. Прежде всего, она разделяется на несколько слоев (подложку, маску, передний план и т.п.). Для этого используется следующий алгоритм: растровый файл просматривается пиксель за пикселем. Все светлые точки автоматически причисляются к фону, темные —к маске или переднему плану. Все пиксели, выводимые на экран, получают цвет на базе логических вычислений, построенных на значениях соответствующих цветов из всех слоев. Такое разделение помогает наиболее эффективно сжимать графику. При воспроизведении изображения слои соединяются. Маска, имеющая обычно всего один цвет, архивируется по методу сжатия документов, используемому в факсимильных аппаратах (JB2).
Основной сферой применения технологии DJVU разработчики называют обработку отсканированных книг, журналов, каталогов, руководств, исторических и редких документов и размещение их цифровых копий в Интернете. По оценкам разработчиков предлагаемая технология позволяет добиться коэффициента сжатия 1000: 1 (отсканированная при 300 dpi цветная страница занимает — 30-80 Кбайт, черно-белая —10-30 Кбайт).
 - DVI (Digital Video Interactive)система динамического сжатия и восстановления аудио- и видеозаписей в цифровой форме. Ее использование позволяет записать на CD-ROM полноформатный видеофильм вместе со звуковым сопровождением. Первая DVI система была разработана фирмой RCA (США). В настоящее время она принадлежит фирме Intel и используется рядом фирм, включая IBM и Microsoft.
 - EAD (Encoded Archival Description) —стандарт, разработанный подразделением Network Development and MARC Standards Office Библиотеки Конгресса США (LC) в сотрудничестве с Society of American Archivists в 1998 г. (последнее обновление —2002 г.). Устанавливает принципы создания, разработки и поддержки схем кодирования для архивных и библиотечных помощников поиска [finding aids]. В общем случае термин "помощник поиска" охватывает широкий спектр инструментов для описания, контроля и предоставления доступа к архивным коллекциям. В этом стандарте речь идет, прежде всего, о хранилищах и регистрах, хотя это не может служить препятствием для разработки собственных приложений. Стандарт поддерживает регистры и хранилища для записей любой длинны всех видов архивных единиц хранения, включая текстовые и электронные документы и аудиовизуальные материалы.
Схема кодирования основана на использовании SGML: ISO 8879 в форме DTD (Document Type Definition) и состоит из двух частей: собственно DTD и детальное руководство по использованию. Создано XML-представление DTD, а также специальное руководство по конвертированию "старых" SGML-файлов в XML. Эта версия стандарта известна под наименованием EAD DTD или EAD Document Type Definition.
Официально поддерживают данный стандарт ряд авторитетных организаций в США и Великобритании.
 - Image compression managerпрограмма управления динамическим сжатием изображений, которая обеспечивает возможность использования различных методов сжатия/восстановления изображений (MPEG, JPEG и др.).
 - Сжатие JBIG (Joint Bi-level Image Experts Group) —метод сжатия двухуровневых (т. е. двухцветных) изображений без потерь, создан Объединенной группой экспертов по двухуровневым изображениям ISO и CCIT в 1988 г. В 1993 г. утвержден как стандарт кодирования двухуровневых данных взамен ранее существовавших и менее эффективных алгоритмов сжатия MR (Modified READ) и MMR (Modified Modified READ). Его эффективность в десятки раз превысила ранее использовавшиеся методы. Принцип работы метода заключается в том, что он кодирует избыточные данные изображения путем сравнения значений пикселя в строке развертки со значениями групп пикселей, уже отсканированных кодировщиком. Эти пиксели называют шаблоном] они образуют простую схему комбинаций пикселей, которые окружают кодируемый пиксель. Их значения используются для идентификации избыточных комбинаций в данных изображения. Эти комбинации затем сжимаются с помощью адаптивного арифметического кодировщика.
 - LZW (Lempel-Ziv-Welch) — метод динамического сжатия; разработан в 1977 г. израильтянами Абрахамом Лемпелом и Джекобом Зивом, создавшими на его основе компрессор LZ77. В 1984 г. этот метод доработан в США Терри Велчем, модифицировавшим компрессор LZ78. Таким образом появился метод трех авторов — LZW. Принцип работы метода основан на поиске во всем файле и сохранении в словаре одинаковых последовательностей данных (они называются фразы). Каждой уникальной последовательности данных присваиваются более короткие маркеры (ключи). Так, если в изображении имеются наборы из розового, оранжевого и зеленого пикселей, повторяющиеся 50 раз, LZW выявляет это, присваивает данному набору отдельное число (например 7) и затем сохраняет эти данные 50 раз в виде числа 7. Существуют варианты реализации данного метода. Эффективность метода: LZW, так же, как и RLE, лучше действует на участках однородных, свободных от шума цветов. Он действует гораздо лучше, чем RLE, при сжатии произвольных графических данных, но процесс кодирования и распаковки происходит медленнее.
 - MP3 (Moving Pictures Experts Group, Layer 3) —метод (алгоритм) динамического сжатия и специальный формат записи файлов аудиоданных, разработанный Экспертной группой по движущимся изображениям. Было обнаружено, что MP3 обеспечивает более высокую степень сжатия звуковых записей, чем предыдущая версия MPEG (исходный размер файла он сократил в восемь раз). Широко используется в различных приложениях мультимедиа, в частности, в современных цифровых проигрывателях ("плейерах!’) и Интернете.
 - МРЗРго — новая версия динамического сжатия аудиоданных, разработанная фирмой Music Match и совместимая со спецификацией MP3, позволяет без заметного ухудшения качества воспроизведения сократить размер файла звуковой записи почти в два раза. Это достигается раздельным сжатием низкочастотной составляющей сигнала (0-8 кГц) по стандарту MP3. Высокочастотная компонента (8-16 кГц) не подвергается компрессии в файле, она копируется и воссоздается специальным кодом при воспроизведении совместимыми со стандартом плейерами, которые декодируют и собирают составляющие. Этот метод называется копированием полосы спектра — SBR (Spectral Band Replication). Типичный файл МРЗРго может передаваться со скоростью 64 кбит/с (т. е. вдвое ниже, чем для высокочастотного файла стандарта MP3). Около 94% (~ 60 кбит/с) всех данных составляет стандартный код MP3, а остальные 6% (~4 кбит/с) — данные, используемые принимающим устройством для восстановления высокочастотных сигналов. Технически стандарт МРЗРго совместим с MP3. Если плейеры не совместимы с МРЗРго, звук при воспроизведении будет приглушен за счет потери высокочастотной составляющей. Для ознакомления с возможностями МРЗРго можно загрузить плейер-кодировщик Thomson Demo МРЗРго с сайта. Там же можно ознакомиться со списком изделий, совместимых с этой технологией.
 - RLE (Run Length Encoding) — "Кодирование с переменной длиной строки" (также используется термин "Групповое кодирование"): метод динамического сжатия графических данных, в первую очередь изображений, основанный на уменьшении физического размера повторяющихся строк символов. Такие повторяющиеся строки, называемые группами, обычно кодируются в двух байтах. Первый байт определяет количество символов в группе и называется счетчиком группы, второй байт содержит значение символа в группе, которое находится в диапазоне от 0 до 255 и называется значением группы. Механизм работы RLE заключается в поиске одинаковых пикселей в одной строке. Если в строке имеется, например, 3 пикселя белого цвета, 21 — черного, затем 14 —белого, то применение RLE дает возможность не запоминать каждый из них (38 пикселей), а записать как 3 белых, 21 черный и 14 белых в первой строке. Существуют несколько вариантов реализации RLE. Метод RLE поддерживается большинством растровых файловых форматов, включая TIFF, BMP и PCX. Его эффективность зависит от типа данных изображения, подлежащего сжатию. Метод наиболее эффективен для сжатия изображений, имеющих сравнительно небольшое число деталей, тональных и цветовых переходов (например страница текста). Так же, как и LZW RLE хорошо работает с искусственными и пастеризованными картинками и полохо — с фотографиями. В действительности, если фотография детализирована, RLE может даже увеличить размер файла.