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

то отсчет должен быть передан, иначе он является избыточным; здесь

и

— амплитуды реального и предсказанного отсчетов,

— допуск (допустимая погрешность представления амплитуд). Иллюстрация предсказывающего метода с линейной экстраполяцией представлена рис. 1. Здесь точками показаны предсказываемые значения сигнала. Если точка выходит за пределы "коридора" (допуска

), показанного пунктирными линиями, то происходит передача отсчета. На рисунке передаваемые отсчеты отмечены темными кружками в моменты времени

. Если передачи отсчета нет, то на приемном конце принимается экстраполированное значение.
Рис. 1. Предиктивное кодирование
Для сжатия текстовой информации часто применяют
метод Хаффмена, относящийся к статистическим методам сжатия. Идея метода — часто повторяющиеся символы нужно кодировать более короткими цепочками битов, чем цепочки редких символов. Строится двоичное дерево, листья соответствуют кодируемым символам, код символа представляется последовательностью значений ребер (эти значения в двоичном дереве суть 1 и 0), ведущих от корня к листу. Листья символов с высокой вероятностью появления находятся ближе к корню, чем листья маловероятных символов.
Распознавание кода, сжатого по методу Хаффмена, выполняется по алгоритму, аналогичному алгоритмам восходящего
грамматического разбора. Например, пусть набор из восьми символов

имеет следующие правила кодирования:

Тогда при распознавании входного потока

в стек распознавателя заносится

, но

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

. Полученная комбинация

распознается и заменяется на

. В стек поступает следующий символ

, затем

, затем

. Сочетание

совпадает с правой частью правила для

. Теперь в стеке

, заносятся следующие символы

и т.д.
Недостаток метода заключается в необходимости знать вероятности символов. Если заранее они не известны, то требуются два прохода: на одном в передатчике подсчитываются вероятности, на другом эти вероятности и сжатый поток символов передаются к приемнику. Однако двухпроходность не всегда возможна.
Этот недостаток устраняется в однопроходных алгоритмах адаптивного сжатия, в которых схема кодирования есть схема приспособления к текущим особенностям передаваемого потока символов. Поскольку схема кодирования известна как кодеру, так и
декодеру, сжатое сообщение будет восстановлено на приемном конце.
Для сжатия графической и видеоинформации широко используют методы RLE (Run Length Encoding), LZW (Lempel, Zif, Welch) или LZ, JPEG (Joint Photographic Expert Group) и MPEG (Moving Pictures Experts Group).
В
методе RLE вместо передачи цепочки из одинаковых символов передаются символ и значение длины цепочки. Метод эффективен при передаче растровых изображений, но малополезен при передаче текста. На основе этого метода созданы графические форматы TIFF, BMP, PCX.
В
LZW-методах (алгоритмах Лемпеля-Зива-Уэлча), называемых также LZ-алгоритмами, используется следующая идея: если в тексте сообщения появляется последовательность из двух ранее уже встречавшихся символов, то эта последовательность объявляется новым символом, для нее назначается код, который при определенных условиях может быть значительно короче исходной последовательности. В дальнейшем в сжатом сообщении вместо исходной последовательности записывается назначенный код. При декодировании повторяются аналогичные действия и потому становятся известными последовательности символов для каждого кода. Один из LZW-алгоритмов применен в
протоколе V.42bis, используемом для
модемной связи.
Для пояснения LZW-кодирования воспользуемся примером, приведенным Д.С.Ватолиным в работе "Алгоритмы cжатия изображений".
Пусть мы сжимаем последовательность байтов 45, 55, 55, 151, 55, 55, 55. Сначала в выходной поток заносится код очистки <256>, а в таблицу символов записываются 256 строк, соответствующих каждая одному из 256 одиночных символов. Работа продолжается следующим образом. Рассматривается первый символ 45. Строка 45 в таблице символов есть. Тогда считывается следующий символ 55 из входного потока. Строки 45, 55 в таблице нет. Поэтому в таблицу записывается строка 45, 55 (с первым свободным кодом 258) и в выходной поток записывается код <45>. Можно коротко представить архивацию так:
“45” — есть в таблице; “45, 55” — нет. Добавляем в таблицу <258>“45, 55”. В поток: <45>; “55, 55” — нет. В таблицу: <259>“55, 55”. В поток: <55>; “55, 151” — нет. В таблицу: <260>“55, 151”. В поток: <55>; “151, 55” — нет. В таблицу: <261>“151, 55”. В поток: <151>; “55, 55” — есть в таблице; “55, 55, 55” — нет. В таблицу: <262> “55, 55, 55” . В поток: <259>;
Последовательность кодов для данного примера, попадающих в выходной поток: <256>, <45>, <55>, <55>, <151>, <259>.
Существенно то, что для декомпрессии не требуется передавать таблицу символов, приемник сам создаст эту таблицу тем же способом, который использовался в передатчике.
Разновидности методов LZW нашли применение в ряде форматов, например GIF, ZIP, TIFF.
Методы JPEG, используемые в одноименном
формате JPEG, основаны на исключении из видеоданных малосущественной информации, что не приводит к сколько-нибудь заметному ухудшению качества изображений, поскольку не различимые для глаза оттенки кодируются одинаково. В методах JPEG передаваемая последовательность пикселей делится на блоки, в каждом блоке производится преобразование Фурье, устраняются высокие частоты, передаются коэффициенты разложения для оставшихся частот, по ним в приемнике изображение восстанавливается.
Формат GIF наиболее приемлем для чертежей и рисунков, он позволяет сохранить высокое качество цветных фотографий, но за счет большого объема занимаемой памяти. Формат JPEG более экономичен при представлении фотографий с богатой палитрой цветов.
Графический формат
PNG создан как альтернатива устаревшему формату GIF и более сложному формату TIFF.
Формат PNG имеет ряд преимуществ перед форматом GIF: неограниченное количество цветов в изображении (для GIF ограничено 256), двумерная чересстрочная прогрессивная развёртка, позволяет более высокий уровень сжатия, он открыт для использования (формат GIF принадлежит фирме Compuserve, что ограничивает возможности его использования в свободном программном обеспечении).
Форматы PNG и JPEG являются основными форматами графических файлов.
В
методах MPEG (MPEG-1 и MPEG-2) применяют предсказывающее кодирование изображений для сжатия данных о движущихся объектах вместе со звуком. Сжатие заключается в передаче только изменившихся во времени частей изображения, при этом достигается степень сжатия в несколько десятков раз. MPEG-1 используют при пропускных способностях до 1,5 -2,0 Мбит/с, MPEG-2 — до 10 и более Мбит/с. Если в формате MPEG-1 используются фиксированные частоты смены кадров (25 Гц для размеров кадров 352×288 и 384×288 пикселов или 30 Гц для размеров 352×240 и 320×240), то в форматах MPEG-2 и MPEG-4 — переменные. Телевизионные передачи ведутся с помощью разновидностей формата .MPEG-2.
Основным преимуществом метода MPEG-4 является более высокая, чем у MPEG-2, эффективность сжатия данных.
Сжатая видеоинформация упаковывается в файлы, имеющие форматы AVI, MOV, MPG, WMV и др. Формат AVI разработан для операционных систем Windows. Формат MOV (точнее формат Quick Time, имеющий расширение MOV) создан компанией Apple, он может использоваться не только с среде ОС Macintosh, но и ОС Windows. В AVI- и MOV-файлах объединяются последовательности кадров и звук. Формат MPG, реализующий методы сжатия MPEG, отличается высокой степенью компрессии видеоинформации.
Для представления звуковых данных используют другой ряд форматов — MP3, WAVE, WMA, VQF и др. К числу наиболее популярных относится
формат MP3, в котором компрессия основана на устранении элементов, малозначимых для качества воспроизведения звука. Формат WAVE (в наименованиях файлов используется расширение wav) используется во многих звуковых картах для представления результатов аналого-цифрового преобразования.
Среди форматов представления текстовой информации наиболее популярными являются форматы DOC, PDF, HTML, XML.
Документы в формате DOC создаются с помощью редактора MS Word, входящего в комплект офисных средств MS Office.
Отличительными особенностями
формата PDF (Portable Document Format) являются следующие свойства:
- независимость от программно-аппаратной платформы, в которой документ воспроизводится; документ представляется в таком виде, в каком он создавался;
- возможность использования гиперссылок, встраивания интерактивных элементов, звуковых и видеофрагментов, поддержка языка JavaScript.
Форматы
HTML и
XML соответствуют одноименным
языкам разметки, они являются основными форматами для представления документов в
Web.
Для уменьшения размеров файлов в форматах DOC, PDF, HTML, XML, BMP и др. при их передаче и хранении используют средства архивации, переводящие эти файлы в форматы ZIP или RAR.