Классификация методов сжатия данных

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

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

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

Используются следующие признаки:

· восстанавливаемость (с определенной точностью) исходного сигнала;

· тип источника (аналоговый или дискретный источники);

· априорное знание статистики источника;

· адаптивность;

· вид воздействия на исходный сигнал.

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

Пусть, например, нас заинтересовало название «Кодирование длин серий» (блок В6). Из классификации выясняем (следуя снизу вверх), что этот метод относятся к рациональному кодированию, предполагает известной статистику источника сообщений, используется для кодирования дискретных источников, является квазиобратимым преобразованием. Наоборот, пусть требуется подобрать квазиобратимый метод сжатия аналогового источника, не зависящий от знания статистики и не требующий создания сложных адаптивных систем. Следуя сверху вниз, приходим к группе «Фиксированные процедуры СД» (блок Е5) .

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

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

К квазиобратимому СД относятся все методы допускающие восстановление исходного представления исследуемого процесса с заданной точностью. Их можно разделить на две основные группы - рациональное кодирование дискретного источника (блок С3) и рациональное преобразование аналогового сигнала в цифровой (блок F3).

Ко второй группе относятся методы дискретизации и квантования непрерывного сигнала, учитывающие его естественную избыточность. Если статистика известна, наиболее применяемые процедуры – предсказание, интерполяция, передача вместо исходного непрерывного процесса коэффициентов разложения его в какой - либо ряд (блоки D6,7,8). Если статистика неизвестна, как правило, на практике применяются апертурные алгоритмы (блок Е6), поскольку они не требуют знания статистики источника, легко реализуются практически и обеспечивают высокие коэффициенты сжатия.

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

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

В случае известной статистики источника, как правило, применяют различные варианты кодирования длин серий и адресно-позиционного кодирования (блоки В6,7), поскольку эти методы легко реализуются и не требуют громоздких таблиц соответствия. В тех случаях, когда наблюдается изменение во времени какой - либо величины, используется кодирование с предсказанием (блок В8). Для кодирования дискретных источников с небольшими алфавитами используются оптимальные методы статистического кодирования (коды Шеннона - Фано, Хафмана) (блок В5) , позволяющие полностью устранить избыточность при известной статистике.

Задача сжатия данных дискретного источника существенно усложняется, если статистические характеристики источника не известны, известны не полностью, меняются во

времени (блоки С5 – С9). Основные теоретические работы, посвященные решению этой задачи. Долгое время в литературе не удавалось найти сведений о практическом применении результатов этих работ. В основном это связало со следующими причинами:

§ высокая трудоемкость реализации («адаптивное кодирование», «универсальное кодирование» блоки С8,9,);

§ недостаточная эффективность простых в реализации методов (например, «итерации простых подстановок», «разностное кодирование» блоки С5,6);

§ узкие классы источников, на которые ориентированы методы, например, «матричное кодирование» (блок – С7) используется в случае монотонности дискретных данных.

В настоящее время, в связи с развитием флэш – технологий, методы универсального кодирования, трудоемкость которых раньше казалась немыслимой стали вполне реализуемы на практике.

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

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

1. Космические исследования.

2. Физические эксперименты.

3. Вычислительная техника.

4. Средства связи.

5. Телеметрические системы.

6. Интернет.

7. Метеорология.

8. Библиотеки.

9. Архивы.

10. Системы видеонаблюдения.

11. Телевидение.

Рис. 2. Классификация методов сжатия данных

Таблица 2. Методы сжатия данных

И в заключение

Постоянный рост объемов предаваемой и хранимой информации

приводит к перегрузкам средств хранения и каналов передачи

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

данных. Методов сжатия много. Они отличаются по ряду признаков.

В данной лекции мы рассмотрели подходы к систематизации и

упорядоченью этих признаков. С этой целью в лекции

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

§ Обобщенная структурная схема информационной системы.

§ Конкретных примеры применения методов СД.

§ Подробная классификация методов СД.

§ Таблица соответствия областей применения и методов СД.

Использование результатов лекции поможет облегчить

ориентирование в широкой области науки и техники под названием

«сжатие данных».

Дата добавления: 2014-05-28; просмотров: 538; Нарушение авторских прав

Мы поможем в написании ваших работ!