Методы динамического сжатия данных


	Сайт о сжатии >> Новинки \| О сервере (Compression Catalog! \| ENGLISH) Книга "Методы сжатия данных" >> Без потерь \| Изображений \| Видео Разделы >> Cтатьи \| Видео \| Arctest \| Ссылки \| Ru.compress \| Форум Проекты >> Д.Ватолина \| А.Ратушняка \| М.Смирнова \| В.Юкина \| Е.Шелвина \| Д.Шкарина

Методы динамического сжатия данных

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

Самым распространенным методом динамического сжатия данных сегодня является метод "Lempel - Ziv Welch", который является наиболее скоростным методом, но к сожалению не дает большой компрессии данных. Коэффициент сжатия данных с использованием этого алгоритма, в зависимости от типа данных (текст, исполняемые модули, графика, музыка или уже сжатые файлы), колеблется от 0 до 35 процентов сжатия. В это же время существуют, на мой взгляд, более производительные методы динамического сжатия данных, которые практически ни где не используются такие как: Adapted Huffman, Bit-oriented (LZ-2), Cleary and Witten (CW), Dynamic Marcov (DMC), Ariphmetic и другие. Исходя из вышесказанного следует, что следует обратить на эту проблему пристальное внимание.

Предлагается рассмотреть три динамических метода сжатия данных: Dynamic Marcov (DMC), Ariphmetic, Lempel - Ziv Welch и сделать их сравнительный анализ.

Проведя сравнительный анализ этих трех методов динамического сжатия можно видеть, что при практически одинаковом времени сжатия, на 100000 байт время сжатия колеблется от 70 до 1330 микросекунд, коэффициент сжатия колеблется от 1.6 до 72.5% и максимальное качество (отношение коэффициента сжатия к времени сжатия) показывает Арифметический метод динамического сжатия данных.

Метод сжатия	Форматированный текст	Неформатированный текст	Объектный код	С-текст
Dynamic Marcov (DMC)	47.8	52.4	59.6	49.2
Lempel-Ziv Welch (LZW)	38.2	42.9	48.4	40.8
Ariphmetic	59.7	61.6	79.6	62.9
Размер файла	74510	61536	68608	31479

Таблица №1

Результаты сжатия, достигнутые при использовании адаптивного метода кодирования варьируются от 4.8-5.3 битов/символ для коротких английских текстов (10^3-10^4 байтов) до 4.5-4.7 битов/символ для длинных (10^5-10^6 байтов). Хотя существуют и адаптивные техники Хаффмана, они все же испытывают недостаток концептуальной простоты, свойственной арифметическому кодированию. При сравнении они оказываются более медленными. Например, таблица №2 приводит характеристики сpеднеоптимизиpованной реализации арифметического кодирования на Си с той из программ compact UNIXa, что реализует адаптивное кодирование Хаффмана с применением сходной модели.

Небрежная проверка compact показывает, что внимание к оптимизации для обоих систем сравнимо при том, что арифметическое кодирование выполняется в 2 раза быстрее. Показатели сжатия в некоторой степени лучше у арифметического кодирования для всех тестовых файлов. Различие будет заметным в случае применения более сложных моделей, предсказывающих символы с вероятностями, зависящими от определенных обстоятельств (например, следования за буквой q буквы u).

	Арифметическое кодирование			Кодирование Хаффмана
	Вывод (байты)	Код. (мкс)	Дек. (мкс)	Вывод (байты)	Код. (мкс)	Дек. (мкс)
Текстовые файлы	57718	214	262	57781	550	414
Си-программы	62991	230	288	63731	596	441
Объектные файлы	73501	313	406	76950	822	606
Алфавит	59292	223	227	60127	589	411
Асимметричные показатели	12092	143	170	16257	215	132

Таблица №2

Неадаптированное кодирование может быть выполнено арифметическим методов с помощью постоянной модели. При этом сжатие будет лучше, чем при кодировании Хаффмана. В порядке минимизации времени выполнения, сумма частот будет выбираться равной степени двойки, чтобы операции деления при вычислении границ выполнялись через сдвиги. Для реализации на ассемблере время кодирования/декодирования составило 60-90 мкс. Аккуратно написанная реализация кодирования Хаффмана с использованием таблиц просмотра для кодирования и декодирования будет выполнятся немного быстрее.

Ворслов А.С.
(Москва МГТУ "Станкин")