Архиватор собственными руками! (Часть II)

Содержание:

Часть первая

Часть вторая (текущая страница)

Исходный текст архиватора (алгоритм Хаффмана)

Мультимедиа-сжатие

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

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

Так вот, соседние пиксели, отличающиеся друг от друга по цвету незначительно, отождествляются (коэффициент "похожести" соседних пикселей определяет баланс качества изображения и степени сжатия, см. рис.). Одинаковые группы пикселей объединяются в блоки и, далее, применяется один из методов сжатия без потери качества. Например, в формате JPEG сначала производится разбиение изображения на блоки 8x8. Затем данные блоки изображения подвергаются так называемому дискретному косинус-преобразованию (ДКП, на данном этапе происходит потеря качества) и, на заключительном этапе, применяется метод Хаффмана. Данный формат очень эффективен при хранении фотографий и прочей полноцветной графики.

Кроме того, ключевым моментом является количество бит, выделяемых для хранения цвета одного пикселя. Чем больше бит выделено под хранение одного пикселя, тем реалистичнее картинка и тем больше объем графического файла. Так, в большинстве случаев мы имеем дело с графикой, цветовая палитра которой - 16 или 24 бит (Hi и True color соответственно). Всем известный формат графических файлов GIF ограничивает цветовую палитру одним байтом (всего 256 цветов для каждого пикселя), тем самым, достигая значительной экономии в объеме файла. Следует учесть, что фотографии в данном формате хранить не следует. Приличное качество недостижимо, а объем уменьшается незначительно. Преимуществом данного формата является возможность хранения простейшей анимации.

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

Основные параметры, определяющие качество сжатого файла - это битрейт и частота дискретизации. Битрейт (bit rate, битовая частота) определяет количество передаваемой за единицу времени информации; чем больше битрейт, тем выше реалистичность и соответствие исходному звуковому потоку (оптимальное значение, обеспечивающее качество компакт-диска - 128 kBit/s).

Убедиться в обоснованности этого числа можно так: для прослушивания обычного, несжатого потока аудио (записанного на Audio CD) требуется привод CD-ROM с формулой 1x. Скорость линейного чтения у такого привода равна 150 kByte/s (т.е. 1200 kBit/s). Разделим это число на отношение объемов несжатого и сжатого аудио-потоков. Как мы уже говорили, коэффициент сжатия в формате mp3 примерно равен десяти. Получаем 120 kBit/s (что и требовалось доказать).

Частота дискретизации - еще один очень важный параметр, определяющий максимальную частоту выходного сигнала (и, соответственно, чем он больше, тем ближе звучание mp3 файла к оригиналу). Общепринята точка зрения, согласно которой восприятие человеком звука ограничено частотным диапазоном от 20Hz до 20kHz. Чаще всего значение частоты дискретизации устанавливается в два раза большее, чем верхний порог восприятия (44.1 или 48 kHz).

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

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

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

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

Формат видео MPEG2 (и его VBR-реализация) используется в рамках технологии DVD и обеспечивает высокое качество выходного видео. Особой степенью сжатия не характеризуется, в силу того, что носители, используемые в технологии DVD, обладают достаточной емкостью (DVD-Disk имеет емкость от 4,7 GByte). Соответственно процесс декодирования не особенно требователен к аппаратным ресурсам ПК.

Формат MPEG4 обладает очень высокой степенью сжатия при довольно приличном качестве. Основным недостатком этого формата являются довольно высокие требования к вычислительной мощности ПК. Так, при просмотре фильмов в этом формате на системе с процессором ниже Pentium III с частотой 600 MHz, иногда, можно наблюдать слайд-шоу. Удивляет тот факт, что аудио поток в таком случае будет воспроизводиться без искажений. Таким образом, при выборе ПК, одной из задач которого будет воспроизведение видео в данном формате, следует ориентироваться на систему на базе процессоров класса Pentium III или Athlon с частотой от 1GHz (или их дешевые аналоги Celeron и Duron). Особое внимание следует уделить производительности дисковой подсистемы (в силу того, что "картинка" и "звук" хранятся в видео-файле отдельно и требуется высокая скорость произвольного доступа к диску).

Если вы не программист

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

На сегодняшний день в Сети существует несколько наиболее распространенных форматов архивов. Чаще всего встречаются архивы в формате *.zip и *.rar. Самой удобной программой, поддерживающей почти все форматы архивов, считается WinRAR. При распаковке, можно выборочно указать: какие именно файлы вы хотите извлечь и куда. Кроме того, раскрытый архив можно проверить на ошибки или добавить к архиву комментарий.

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

Начало статьи

Главная страница.

Hosted by uCoz