Хаффман

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

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

Коды без памяти

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

Сжатия данных - общие принципы

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

  • 752 просмотра

Поддиапазонные преобразования

Все преобразования, которые обсуждались в § 3.5, являются ортогональными, поскольку в их основе лежат ортогональные матрицы. Ортогональное преобразование можно также выразить с помощью скалярного произведения вектора данных (пикселов или звуковых фрагментов) и множества базисных функций. Результатом ортогонального преобразования служат преобразованные коэффициенты, которые можно сжимать с помощью RLE, кодирования Хаффмана или иного метода. Сжатие с потерей осуществляется путем квантования части преобразованных коэффициентов, которое делается до процедуры сжатия. ...

Вопросы для самоконтроля

1. На какой класс изображений ориентирован алгоритм RLE?

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

3. На какой класс изображений ориентирован алгоритм CCITT G-3?

4. Приведите пример "плохого" изображения для алгоритма CCITT G-3, для которого файл максимально увеличится в размере. (Приведенный в характеристиках алгоритма ответ не является полным, поскольку требу­ет более "умной" реализации алгоритма.)

5. Приведите пример "плохого" изображения для алгоритма ...

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

Алгоритм Хаффмана с фиксированной таблицей CCITT Group 3

Классический алгоритм Хаффмана был рассмотрен в разд. 1 данной кни­ги. Он практически не применяется к изображениям в чистом виде, а ис­пользуется как один из этапов компрессии в более сложных схемах.

Близкая модификация алгоритма используется при сжатии черно-белых изображений (1 бит на пиксел). Полное название данного алгоритма CCITT Group 3. Это означает, что данный алгоритм был предложен третьей груп­пой по стандартизации Международного консультационного комитета по телеграфии и телефонии (Consultative ...

Коды Голомба

Код Голомба неотрицательного целого числа п [Golomb 66] может быть эффективным кодом Хаффмана. Этот код зависит от выбора некоторого параметра Ь. Прежде всего необходимо вычислить две величины q — \р-^\ , r — п — qb — 1 (где выражение \х\ обозначает округление х), а затем построить код из двух частей; первая часть -это число д, закодированное с помощью унарного кода (см. стр. 195), а вторая - двоичное выражение для г, состоящее из [log2b\ бит (для малых остатков) или из [log2b~\ бит (для больших). Если взять ...

Мода без потери данных

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

Выбор метода сжатия

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

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

Прежде всего, следует учитывать, ...

Методы, используемые совместно с BWT

Как уже было сказано, само по себе преобразование Барроуза - Уилера не сжимает. Эту работу проделывают другие методы, призванные толково распо­рядиться теми свойствами, которыми обладают преобразованные данные.

Среди таких методов можно отметить следующие:

■ кодирование длин повторов (RLE);

■ метод перемещения стопки книг [35] (MTF);

■ кодирование расстояний (DC);

■ метод Хаффмана;

■ арифметическое кодирование.

Последовательность применения методов, используемых совместно с BWT: