Современные информационные технологии/1. Компьютерная
инженерия
Иркутский государственный
технический университет, Россия
Сжатие
данных с потерями и без потерь
На сегодняшний день нам доступно множество
высокообъемных носителей информации и высокоскоростные каналы передачи данных.
Однако, и объемы передаваемой нами информации постоянно растут. Если взять
любой фильм в HD качестве, то занимаемое им
место на носителе может достигать свыше десятка гигабайт. Казалось бы, зачем
тогда нам нужно сжатие данных, но есть такие ситуации, когда без него обойтись
крайне затруднительно или даже невозможно, например:
·
пересылка документов по
электронной почте (особенно больших объемов документов с использованием
мобильных устройств);
·
при публикации
документов на сайтах, потребность в экономии трафика;
·
экономия дискового
пространства в тех случаях, когда замена или добавление средств хранения
затруднительно. Например, подобное бывает в тех случаях, когда выбить бюджет
под капитальные расходы непросто, а дискового пространства не хватает. И т.д.
Все методы сжатия можно разделить на две
большие группы: сжатие с потерями и сжатие без потерь. Сжатие без потерь
применяется в тех случаях, когда информацию нужно восстановить с точностью до
бита. Например, такой подход является единственно возможным при сжатии
текстовых данных.
В некоторых случаях точного восстановления
информации не требуется и можно сжатие с потерями, которое, в отличие от сжатия
без потерь, обычно проще реализуется и обеспечивает более высокую степень
архивации.
Сжатие с потерями. Лучшие степени сжатия,
при сохранении «достаточно хорошего» качества данных. Применяются в основном
для сжатия аналоговых данных — звука, изображений. В таких случаях
распакованный файл может очень сильно отличаться от оригинала на уровне
сравнения «бит в бит», но практически неотличим для человеческого уха или глаза
в большинстве практических применений.
Сжатие без потерь. Данные
восстанавливаются с точностью до бита, что не приводит к каким-либо потерям
информации. Однако, сжатие без потерь показывает обычно худшие степени сжатия.
Но какой же из этих типов сжатия лучше,
какой из них нам следует выбрать для того или иного типа данных, рассмотрим
основные виды сжатия для первого и второго вариантов. В общем, можно выделить
три базовых варианта, на которых строятся алгоритмы сжатия.
Первая группа методов – преобразование
потока. Это предполагает описание новых поступающих несжатых данных через уже
обработанные. При этом не вычисляется никаких вероятностей, кодирование
символов осуществляется только на основе тех данных, которые уже были
обработаны, как например в LZ – методах (названных по первым буквам фамилий
создателей данного метода Абрахама Лемпеля и Якоба Зива). В этом случае, второе
и дальнейшие вхождения некой подстроки, уже известной кодировщику, заменяются
ссылками на ее первое вхождение. LZ — используется в gif и во многих других.
Вторая группа методов – это статистические
методы сжатия. В свою очередь, эти методы делятся на адаптивные (или поточные),
и блочные. В первом (адаптивном) варианте, вычисление вероятностей для новых
данных происходит по данным, уже обработанным при кодировании. К этим методам
относятся адаптивные варианты алгоритмов Хаффмана и Шеннона-Фано. Во втором
(блочном) случае, статистика каждого блока данных высчитывается отдельно, и
добавляется к самому сжатому блоку. Сюда можно отнести статические варианты
методов Хаффмана, Шеннона-Фано, и арифметического кодирования. Кодирование
Хаффмена, вероятно, самый известный метод сжатия данных. Простота и
элегантность способа сделали его на долгое время академическим фаворитом. Но
коды Хаффмена имеют и практическое применение; например, статические коды
Хаффмена используются на последнем этапе сжатия JPEG. Стандарт сжатия данных
для модемов MNP-5 использует динамическое сжатие Хаффмена в качестве части его
процесса. Наконец, кодирование Шеннона-Фано (Shannon-Fano), довольно близкое к
кодированию Хаффмена, используется как один из этапов в мощном
"imploding"-алгоритме программы PkZip.
Третья группа методов – это так называемые
методы преобразования блока. Входящие данные разбиваются на блоки, которые
затем трансформируются целиком. При этом некоторые методы, особенно основанные
на перестановке блоков, могут не приводить к существенному (или вообще
какому-либо) уменьшению объема данных. Однако после подобной обработки,
структура данных значительно улучшается, и последующее сжатие другими
алгоритмами проходит более успешно и быстро.
Существуют две основных схемы сжатия с
потерями:
В трансформирующих кодеках фреймы
изображений или звука трансформируются в новое базисное пространство и
производится квантование. Трансформация может осуществляться либо для всего
фрейма целиком (как, например, в схемах на основе wavelet-преобразования), либо
поблочно (характерный пример — JPEG). Результат затем сжимается энтропийными
методами.
В предсказывающих кодеках предыдущие и/или
последующие данные используются для того, чтобы предсказать текущий сэмпл
изображения или звука. Ошибка между предсказанными данными и реальными вместе с
добавочной информацией, необходимой для производства предсказания, затем
квантуется и кодируется. В некоторых системах эти две техники комбинируются
путём использования трансформирующих кодеков для сжатия ошибочных сигналов,
сгенерированных на стадии предсказания.
Сжатие с потерями применяется в основном
для графики (JPEG), звука (MP3), видео (MPEG), то есть там, где в силу огромных
размеров файлов степень сжатия очень важна, и можно пожертвовать деталями, не
существенными для восприятия этой информации человеком. Особые возможности для
сжатия информации имеются при компрессии видео. В ряде случаев большая часть
изображения передается из кадра в кадр без изменений, что позволяет строить
алгоритмы сжатия на основе выборочного отслеживания только части «картинки». В
частном случае изображение говорящего человека, не меняющего своего положения,
может обновляться только в области лица или даже только рта — то есть в той
части, где происходят наиболее быстрые изменения от кадра к кадру.
В заключение можно сказать, что оба типа
сжатия данных хороши по-своему для определенных видов данных, для текстовых или
же для графических, имеющей значение лишь при своем хорошем и четком качестве.
Список использованной
литературы:
1.
Смирнов
Ю.К. Секреты восстановления жестких дисков ПК. Изд-во: БХВ-Петербург, 2011.-272
с.: ил.
2.
Электоронный
ресурс. Режим доступа:http://www.computerbooks.ru/книга/