Сайт о сжатии  >>  ARCTEST

Сравнительные тесты
    Текстовые файлы
    Текстовые файлы (Mac)
    EXE-файлы
    EXE-файлы (Mac)
    Исполнимые EXE-сжатые
    Аудио: Wav-файлы
    Аудио: Wav-файлы (Mac)
    Графика: TIFF-файлы
    Графика: TIFF-файлы (Mac)
    Разноформатные файлы
    Разноформатные файлы (Mac)
    Файлы демо-игры
    Файлы демо-игры (Mac)
Альтернативные тесты
    Русский текст
    Английский текст
    Исходники
    WinWord-файл
    Excel-файл
    EXE-файл
    Новые тесты
Графические тесты
    Сжатие изображений без потерь
Новости
    Архив новостей
    Архив рассылки
Утилиты
    Просмотра-распаковки
    Идентификации-распаковки
    COM/EXE-распаковки, анализа
    Распаковки инсталляций
    Создания SFX-архивов/инсталляций
    Конвертирования
    Починки архивов
    Поиска
    Универсальные оболочки
    Управления баннерами
    Управления файлами
    Резервного копирования
    Тестирования
    Разные
Файл-менеджеры
    Файл-менеджеры
    Арх.-модули для FAR
    Арх.-модули для Win. Commander
Описания
    Статьи, интервью
    Теория, алгоритмы
    Self-описания архиваторов
    FAQ
    Разное
Линки
    Архиваторные
    COM/EXE/DLL-пакеров
Necromancer's DN
    О программе
    Новости свежих версий
    Архив новостей
Поддержка
   
    Подписка на рассылку новостей
    Архиваторные опросы
    Об авторе
Все о сжатии / arctest. Авторский проект.
---------------------------------------------------------

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

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

Самым распространенным методом динамического сжатия данных сегодня является метод "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 мкс. Аккуратно написанная реализация кодирования Хаффмана с использованием таблиц просмотра для кодирования и декодирования будет выполнятся немного быстрее.

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

Последнее обновление: 12-May-2022

Сайт о сжатии  >>  ARCTEST  >>  Сравнительные тесты  |  Альтернативные тесты  |  Графические тесты  |  Новости  |  Утилиты  |  Файл'менеджеры  |  Описания  |  Линки  |  Necromancer's DN  |  Поддержка

Поиск:
Справка Детальный запрос

Сайт о сжатии >>
  Новинки | О сервере | Статистика

  Книга "Методы сжатия данных" >>
     Универсальные | Изображений | Видео

  Разделы >> Download (статьи+исходники) | Ссылки | Ru.compress | Arctest | Видео | Каталог ссылок | Форум
  Проекты >> Д.Ватолина | А.Ратушняка | М.Смирнова | В.Юкина | Е.Шелвина | А.Филинского | Д.Шкарина | С.Оснача

  Оставьте ваши замечания, предложения, мнения!
  О найденных ошибках пишите на compression_на_graphicon.ru
  © Д.Ватолин, А.Ратушняк, М.Смирнов, В.Юкин и др., текст, состав., 2001-2003
    Project supported by Graphics & Media Lab

   ЭТОТ ДОКУМЕНТ МОЖНО СКАЧАТЬ C http://www.compression.ru/compression.ru/arctest/descript/dyn-comp.htm

Rambler's Top100 Рейтинг@Mail.ru