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

Сжатие без потерь (англ. Lossless data compression) - метод сжатия информации, при использовании которого закодированная информация может быть восстановлена с точностью до бита. При этом оригинальные данные полностью восстанавливаются из сжатого состояния. Этот тип сжатия принципиально отличается от сжатия данных с потерями. Для каждого из типов цифровой информации, как правило, существуют свои оптимальные алгоритмы сжатия без потерь.

Сжатие данных без потерь используется во многих приложениях. Например, оно используется в популярном файловом формате ZIP и Unix-утилите Gzip. Оно также используется как компонент в сжатии с потерями.

Сжатие без потерь используется, когда важна идентичность сжатых данных оригиналу. Обычный пример - исполняемые файлы и исходный код. Некоторые графические файловые форматы, такие как PNG или GIF, используют только сжатие без потерь; тогда как другие (TIFF, MNG) могут использовать сжатие как с потерями, так и без.

Техника сжатия без потерь

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

Многоцелевые алгоритмы сжатия отличаются тем, что способны уменьшать широкий диапазон данных - исполняемые файлы, файлы данных, тексты, графику и т.д., и применяются в архиваторах. Специализированные же алгоритмы рассчитаны на некоторый тип файлов (текст, графику, звук и т.д.), зато сжимают такие файлы намного сильнее. Например: архиваторы сжимают звук примерно на треть (в 1,5 раза), в то время как FLAC - в 2,5 раза. Большинство специализированных алгоритмов малопригодны для файлов «чужих» типов: так, звуковые данные плохо сжимаются алгоритмом, рассчитанным на тексты.

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

Статистические модели алгоритмов для текста (или текстовых бинарных данных, таких как исполняемые файлы) включают:

Преобразование Барроуза - Уилера (блочно-сортирующая предобработка, которая делает сжатие более эффективным)

LZ77 и LZ78 (используется DEFLATE)

Алгоритмы кодирования через генерирование битовых последовательностей:

• · Алгоритм Хаффмана (также используется DEFLATE)
• · Арифметическое кодирование

Методы сжатия без потерь

• · Многоцелевые
• · Кодирование длин серий - простая схема, дающая хорошее сжатие данных, которые содержат много повторяющихся значений
• · LZW - используется в gif и во многих других.
• · Deflate - используется в gzip, усовершенствованной версии zip и как часть процесса сжатия PNG.
• · LZMA - используется в 7-zip.
• v Сжатие аудио:
  • · Apple Lossless - ALAC (Apple Lossless Audio Codec);
  • · Audio Lossless Coding - также известен как MPEG-4 ALS;
  • · Direct Stream Transfer - DST;
  • · Free Lossless Audio Codec - FLAC;
• v Сжатие графики
• · ABO - Adaptive Binary Optimization;
• · GIF - (без потерь только для изображений содержащих менее 256 цветов);
• · JBIG2 - (с потерями или без Ч/Б изображений);
• · JPEG-LS - (стандарт сжатия без потерь / почти без потерь);
• · JPEG 2000 - (включает сжатие без потерь; также, испытан Sunil Kumar, профессором университета штата Сан-Диего);
• · PGF - Progressive Graphics File (сжатие с/без потерь);
• · PNG - Portable Network Graphics;
• · TIFF;
• · WMPhoto - (включая метод сжатия без потерь);
• v Сжатие видео
• · Animation codec;
• · CamStudio Video Codec;
• · CorePNG;
• · FFV1.

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

RAW — мысли от Радоживы

Я буду писать только про систему Nikon, так как я работаю с ней, и за долгие годы у меня появился какой-то опыт работы с RAW файлами.

Цифрозеркальные камеры Nikon имеют некоторые особенности работы с RAW. Сами RAW файлы имеют расширение NEF (Nikon Electronic Format – электронный формат Nikon) . В меню камеры, чтобы не сбить с толку человека, который много начитался и наслышался про RAW, маркетологи аккуратно пишут NEF (RAW) .

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

Например, в продвинутых камерах по типу , и даже в можно выбрать глубину цвета для RAW.

Также, в некоторых продвинутых камерах, например в тех же , можно выбрать уровень сжатия для файлов формата RAW, за это отвечает настройка «ТИП»:

1. Сжатие без потерь
2. Обычное сжатие
3. Без сжатия

Таким образом, мы можем использовать комбинацию из 6-ти вариантов записи RAW

1. 12 бит сжатие без потерь
2. 12 бит обычное сжатие
3. 12 бит без сжатия
4. 14 бит сжатие без потерь
5. 14 бит обычное сжатие
6. 14 бит без сжатия

Внимание: RAW с глубиной цвета в 14 бит уменьшает скорость серийной съемки в некоторых камерах, например, в , в режиме RAW 14 бит скорость серийной съемки падает до 2.5 к\с. с глубиной цвета 14 бит не может снимать со скоростью 7 к\с в режиме 1.3х. и с глубиной цвета 14 бит не могут снимать со скоростью 5 к\с.

Главный вопрос, на сколько сжатие влияет на качество изображения?

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

Внимание: счетчик кадров правильно показывает количество кадров, которые могут поместиться на карточке фотоаппарата только в режиме «БЕЗ СЖАТИЯ», так как в данном режиме все файлы имеют одинаковый вес и камера точно знает, сколько снимков можно будет поместить. В режимах «Сжатие без потерь» и «Обычное сжатие» счетчик кадров на камерах Nikon сильно ошибается, так как камера не знает точно, на сколько же можно будет «ужать» полученный снимок, потому, она берет максимально возможный объем и именно по нему рассчитывает количество. Это иногда нервирует.

Какой же тип сжатия выбрать?

1. Сжатие без потерь – оптимальный вариант, небольшие потери при сжатии, сильная экономия места и сохранение почти всего потенциала RAW файла
2. Обычное сжатие – вариант подойдет тем, кто с одной стороны хочет снимать в RAW, а с другой стороны сильно экономит на дисковом пространстве
3. Без сжатия – самый лучший вариант, никаких потерь в качестве, абсолютный максимум, который может выдать камера. Серьезным недостатком формата является огромнейший размер файла.

Для примера, чтобы не говорить про абстрактные вещи, мой в режиме RAW 14 bit и без сжатия производит файлы объемом по 25МБ . При переключении в RAW 14 bit с сжатием без потерь, файлы в среднем весят 15МБ . Получаем экономию в 10МБ на одном снимке, согласитесь, выигрыш просто колоссальный. Ну, а если использовать RAW 14 bit с обычным сжатием, то файл весит от 10 до 15МБ .

Какую глубину цвета выбрать? 12 бит или 14бит?

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

Личный опыт:

В интернете можно встретить немало баталий на тему 12 или 14 бит , но я уверен, что если показать два снимка с разной глубиной цвета, даже профессионалам будет очень сложно отличить друг от друга. Я использую RAW 14 bit + сжатие без потерь на камерах по типу ,

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

Если вы возьмете обыкновенный Audio CD диск с аналоговым звуком запишете его в формате WAV для звука без компрессии, затем выполните компрессию WAV с использованием кодека lossless, далее полученный звуковой файл декомпрессируете в WAV и результат запишете на чистый CD, то можете получить два совершенно идентичных Audio CD.

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

Звуковые форматы без потери качества

Подлинного любителя музыки вряд ли устроит звучание музыки, записанной в форматах со сжатием Ogg Vorbis или MP3. Конечно, если аудиозаписи прослушивать на бытовой аудиоаппаратуре, недостатки звучания невозможно уловить на слух, но если попытаться проиграть сжатый файл на высококачественной аппаратуре класса Hi-Fi, сразу обнаружатся недочеты звука. Безусловно, создать коллекцию качественной музыки на CD или виниловых пластинках нелегко. Есть разумная альтернатива этому пути для любителей качественного звука - lossless музыка. Ее можно хранить на ПК в виде, дающем возможность сохранить неизменными исходные параметры музыки, даже если применено сжатие. Этот путь одновременно решает проблемы высокого качества музыки и компактного ее хранения, ведь аудиоаппаратура для прослушивания (наушники, колонки, усилители) имеет вполне доступную цену.

Несжатые форматы звука без потери качества:

• CDDA — является стандартом аудио CD;
• WAV — Microsoft Wave;
• IFF-8SVX;
• IFF-16SV;
• AIFF;

Сжатые форматы:

• FLAC;
• APE - Monkey’s Audio;
• M4A - Apple Lossless - формат качественной музыки от Apple;
• WV - WavPack;
• WMA - Windows Media Audio 9;
• TTA - True Audio.
• LPAC;
• OFR - OptimFROG;
• RKA - RKAU;
• SHN - Shorten.

Формат FLAC

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

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

Формат APE

В отличие от FLAC, для формата APE имеются только лишь кодеки и плагины, рассчитанные на платформу Windows. Для других платформ имеются дорогие решения от сторонних производителей ПО. Алгоритм способен достичь сжатия звуковой информации без потерь примерно в 1,5-2 раза. В него входит три главных этапа кодирования, из которых лишь один основан на применении свойств, присущих звуку для сжатия. Остальные схожи с обычными архиваторами. Несмотря на то что алгоритм сжатия распространяется бесплатно, ограничения лицензии таковы, что для музыкантов-любителей он практически недоступен.

Формат Apple Lossless

Музыка высокого качества lossless может прослушиваться с использованием кодека сжатия звука без ущерба качеству от компании Apple. Этот формат разработан компанией Apple для использования в собственных устройствах. Формат совместим плеерами iPod, имеющими специальные док-разъемы и новейшие прошивки. В формате не применен специфический инструментарий управления правами (DRM), но формат контейнера содержит такие возможности. Также он поддерживается приложением QuickTime и входит в качестве функции в программу iTunes.

Формат входит в состав библиотек, находящихся в свободном доступе, что дает возможность организовать прослушивание файлов в приложениях Windows. В 2011 году компания Apple обнародовала исходные коды формата, что открывает широкие перспективы перед кодеком. В будущем он может составить серьезную конкуренцию прочим форматам. Тесты продемонстрировали неплохие результаты. Сжатые файлы имеют размер от 40-60% от размера оригиналов. Впечатляет также скорость декодирования, что оправдывает его применение для мобильных устройств, производительность которых невелика.

Одним из недостатков кодека является совпадение расширения звуковых файлов с аудиокодеком Это приводит к путанице, ведь AAC не является форматом музыки высокого качества. Поэтому решено было данные хранить в MP4 контейнере с расширением.m4a.

Из других форматов стоит упомянуть Windows Media Audio 9 Lossless, входящий в состав приложения Windows Media. Он работает с Windows и Mac OS X. Правда, пользователи отзываются о нем не очень одобрительно. Часто возникают проблемы с совместимостью кодека, да и количество поддерживаемых каналов ограничено шестью.

Формат WavPack

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

Заслуживает также внимания видеокодек с высококачественным звуком - lagarith lossless codec. Он работает быстро и качественно.

Софт для прослушивания lossless-аудио

Программные плееры не сразу научились работать со специфическими lossless кодеками, которые могут без потерь воспроизвести звук.

Плеер WinAmp

Способен справиться практически со всеми форматами воспроизведения музыки без потерь качества lossless. Что такое хороший плеер lossless, можно понять на его примере. Он способен корректно справляться с обработкой отдельных треков в формате lossless. Это типичная проблема кодеков FLAC или APE. Она состоит в том, что оцифровывается сразу весь звуковой диск и записывается одним файлом без разделения на треки. Проблему разделения на треки призван решить добавочный файл, имеющий расширение.cue. Он содержит описание параметров доступа к каждому треку альбома. Обыкновенный плеер воспроизводит весь lossless файл целиком. Проигрыватель для lossless AIMP замечательно воспроизводит большую часть звуковых форматов и распознает треки в файле lossless формата.

Цифровые плееры с поддержкой lossless

Хорошо отзываются пользователи о цифровых плеерах jetAudio, Foobar2000, Spider Player. Кардинальных отличий между ними нет. Выбор любого устройства основывается на субъективном мнении меломана об удобстве интерфейса для воспроизведения lossless. Что такое lossless формат, можно узнать протестировав эти плееры.

Формат Apple Lossless проигрывается с использованием iTunes. Кроме того, данный кодек поддерживается популярным видеоплеером VLC.

Хозяева компьютеров, совместимых с Apple, могут использовать две интересные программы: Vox и Cog.

Они поддерживают такие lossless форматы:

• Apple Lossless;
• FLAC;
• Monkeys Audio;
• Wavpack.

Дополнительно к этому имеется много полезных возможностей, например поддерживаются сервисы Last.fm.

Владельцы компьютеров с системой Windows могут использовать любое приложение, которое совместимо с кодеками музыки без потери качества: Foobar2000 или WinAmp. Для Winamp требуются специальные плагины. Lossless музыка хорошо воспроизводится на iTunes и KMPlayer. Достоинство iTunes, которого нет в других плеерах - возможность поддержки тегов.

Устройства, совместимые с lossless

Вряд ли хозяин фонотеки захочет расходовать время на то, чтобы преобразовать файлы из формата FLAC в MP3, чтобы иметь возможность прослушивания записей на своем гаджете. У смартфона или планшета ограниченные возможности, несравнимые с компьютером, но тем не менее многие из мобильных устройств проигрывают lossless-форматы.

Например, владельцы устройств под управлением Android могут воспользоваться плеером andLess. Он способен проигрывать файлы в форматах FLAC, APE, несжатый WAV и другие форматы, поддерживаемые Android.

Хуже обстоят дела у владельцев устройств на платформе Blackberry. Лишь обладатели моделей Bold 9000 и 8900 и более поздних версий могут прослушивать lossless формат.

Обладатели устройств Apple без проблем могут использовать кодек ALAC. Он поддерживается плеером iPod (кроме shuffle), телефоном iPhone и планшетом iPad. Для формата FLAC можно скачать FLAC Player в App Store.

Кодек FLAC поддерживается устройствами Samsung Galaxy, некоторыми смартфонами Sony Ericsson и плеерами iriver.

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

Пока еще до полной поддержки абсолютно всех форматов далеко, но вполне хватает того, что медиаплеер понимает кодек FLAC - самый распространенный кодек качественной музыки lossless. Что такое аппаратура воспроизведения lossless?

Аппаратура для прослушивания

Чтобы получить настоящее удовольствие от качества звука, необходима специальная аппаратура: наушники, усилители, колонки. Проще всего, конечно, с наушниками. Если вы намерены наслаждаться музыкой сидя за компьютером, они подойдут лучше всего. Хорошо отзываются пользователи о продукции компаний Koss и Sennheiser. Особенное внимание нужно обратить на размер мембраны. Чем он больше, тем лучше звучание. Важно не обмануться. Некоторые производители ставят маленькую мембрану в большие амбушюры - выглядят такие наушники солидно, а звук пригоден лишь для прослушивания mp3.

Почитателям аппаратуры качественного звука (Hi-Fi или Hi-End) трудно что-либо рекомендовать. Выбор в этой области ограничивается лишь бюджетом и вкусами. Эквалайзер, усилитель, акустика - выбор этих устройств имеет множество вариантов. Владельцам ПК, выбирающим себе качественную лучше остановиться на бюджетных мониторных колонках любого известного бренда. Хорошо отзываются пользователи об акустике Microlab серии SOLO. Чтобы музыка в lossless качестве звучала хорошо, важно приобрести акустику с наличием сабвуфера. не под силу справиться с воспроизведением нижней полосы частот.

Итоги

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

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

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

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

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

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

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

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

Действительно, ответ поражает своей нелепостью. Совершенно очевидно, что в семизначном наборе цифр достаточно ошибиться в одном символе, чтобы остальная информация стала абсолютно бесполезной. Однако представим себе, что тот же самый телефон написан словами русского языка и, скажем, при передаче этого текста часть букв потеряна - что произойдет в подобном случае? Для наглядности рассмотрим себе конкретный пример: телефонный номер 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 кодирует строки символов, анализируя входной поток для построения расширенного алфавита, основанного на строках, которые он обрабатывает. Оба подхода обеспечивают уменьшение избыточной информации во входных данных.

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

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

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

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

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

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

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

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

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

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

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

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

На сегодняшний день сжатие информации является достаточно важной процедурой, которая необходима каждому пользователю ПК. Сегодня любой пользователь может позволить себе приобрести современный накопитель данных, в котором предусмотрена возможность использования большого объема памяти. Подобные устройства, как правило, оснащаются высокоскоростными каналами для транслирования информации. Однако, стоит отметить, что с каждым годом объем необходимой пользователям информации становится все больше и больше. Всего $10$ лет назад объем стандартного видеофильма не превышал $700$ Мб. В настоящее время объем фильмов в HD-качестве может достигать нескольких десятков гигабайт.

Когда необходимо сжатие данных?

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

Передача по электронной почте.

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

Публикация данных на интернет -сайтах и порталах.

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

Экономия свободного места на диске.

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

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

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

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

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

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

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

Пример 1

Приведем простой пример. Русский язык включает в себя $33$ буквы, $10$ цифр и еще примерно $15$ знаков препинания и других специальных символов. Для текста, записанного только прописными русскими буквами (например как в телеграммах) вполне хватило бы $60$ разных значений. Тем не менее, каждый символ обычно кодируется байтом, содержащим, как нам известно, 8 битов, и может выражаться $256$ различными кодами. Это один из первых факторов, характеризующих избыточность. Для телеграфного текста вполне хватило бы и $6$ битов на символ.

Пример 2

Рассмотрим другой пример. В международной кодировке символов ASCII для кодирования любого символа выделяется одинаковое количество битов ($8$), в то время, как всем давно и хорошо известно, что наиболее часто встречающиеся символы имеет смысл кодировать меньшим количеством знаков. Так, к примеру, в азбуке Морзе буквы «Е» и «Т», которые встречаются очень часто, кодируются $1$ знаком (соответственно это точка и тире). А такие редкие буквы, как «Ю» ($ - -$) и «Ц» ($- - $), кодируются $4$ знаками.

Замечание 1

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

Алгоритмы, в основу которых положено перекодирование информации, называются алгоритмами Хаффмана.

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

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

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

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

Замечание 2

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

Решением этой проблемы является статистический анализ кодируемых данных, выполняемый в ходе первого прохода по данным, и составление на его основе кодового дерева. Собственно кодирование при этом выполняется вторым проходом.

Еще одним недостатком кодов является то, что минимальная длина кодового слова для них не может быть меньше единицы, тогда как энтропия сообщения вполне может составлять и $0,1$, и $0,01$ бит/букву. В этом случае код становится существенно избыточным. Проблема решается применением алгоритма к блокам символов, но тогда усложняется процедура кодирования/декодирования и значительно расширяется кодовое дерево, которое нужно в конечном итоге сохранять вместе с кодом.

Данные коды никак не учитывают взаимосвязей между символами, которые присутствуют практически в любом тексте.

Замечание 3

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