3. Классификация алгоритмов компрессии

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

Основные понятия техники компрессии информации могут быть описаны следующими образом:

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

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

2. Кодирование основанное на энтропии и на структуре оригинала: Алгоритмы, основанные на использовании свойств энтропии оригинала, не различают входные данные по типам. Анализ и работа алгоритма идет только на основе статистических свойств оригинала и все направлено на уменьшение длины выхода алгоритма.

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

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

4. Программное и аппаратное кодирование: Процесс кодирования и декодирования информации может выполняться как на программном, так и на аппаратном уровне. Ясно, что аппаратные КОДЕКи (КОдер-ДЕКодер, т.е. специальные программы, выполняющие процесс кодирования и декодирования) являются более быстрыми и используются там, где нужна обработка больших объемов информации и требуется обработка в реальном режиме времени. Также аппаратные кодеки нередко предлагают более высокое качество и более высокий коэффициент сжатия, т.е., соответственно, лучшие результаты.

Следует заметить, что аппаратное решение возможно только для некоторых платформ и требует больших вложений в аппаратную часть и очень сильно зависит от нее (аппаратные алгоритмы JPEG, MPEG1, MPEG2, DVI, etc). Программные кодеки подходят для приложений менее критичных к скоростям обработки и не могут использоваться для обработки данных в реальном режиме времени. Будучи менее требовательными к аппаратным ресурсам, они обеспечивают лучшую совместимость, меньшую стоимость и большую доступность (Intel Indeo, Radius Cinepack, Duck Corporation TrueMotion-S, Motion Pixels, Video Beam, etc.).