Сжатие измерительной информации методом Хаффмана с использованием таблицы уникальных величин
Проблемы хранения большого объёма данных. Применение алгоритма Хаффмана для сжатия измерительной информации в контроллере. Формирование статической таблицы частот. Анализ частоты появления уникальных символов от положения границ диапазона кодирования.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 24.03.2018 |
| Размер файла | 243,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://allbest.ru
Волжский политехнический институт (филиал)
Волгоградского государственного технического университета
Сжатие измерительной информации методом Хаффмана с использованием таблицы уникальных величин
Капля Виктор Иванович,
кандидат технических наук, доцент,
Бурцев Андрей Георгиевич, аспирант,
Тимофеев Илья Игоревич, студент
Процессы хранения большого объёма информации в памяти контроллера и последующей её передачи на ЭВМ ограничены ресурсами устройства, а также временными рамками. В данной работе рассматривается возможность модернизации алгоритма Хаффмана для сжатия измерительной информации в контроллере.
Особенностью измерительных данных является то, что они изменяются во времени с небольшой скоростью. Следовательно, выгодней работать не с абсолютными значениями, а с разностями значений соседних измерений, т. к. они располагаются в более узком интервале.
Алгоритм Хаффмана требует построения бинарного дерева на основе частот появления символов алфавита (в данном случае подразумеваются величины разностей) в сообщении, т. е. перед формированием динамической таблицы частот необходимо проанализировать все данные [1]. Эта операция приводит к затратам по ресурсам и по времени, что недопустимо при использовании алгоритма в контроллере. Целесообразней использовать статическую таблицу частот.
Формирование статической таблицы частот основано на статистической обработке представительной выборки последовательности измерений. В работе используются экспериментальные данные о мощности электрической энергии, расходуемой в процессе плавки кристаллического материала. Результаты измерений периодически заносятся в память ПЛК в виде вектора.
Статическая таблица частот формируется для вектора разностных величин смежных измерений путём усреднения экспериментальных данных по всем выборкам. Целесообразно аппроксимировать элементы статической таблицы частот, что позволит сгладить шумы, присущие ограниченным выборкам экспериментальных данных.
Пример результата усреднения экспериментальных данных приведён на рисунке 1. Тонкими линиями обозначены количества появлений различных значений разностей N для выборок с чётными индексами, а толстой линией -- усреднённое значение по всем наборам.
Рис. 1. Частоты экспериментальных выборок и результат их усреднения.
Сглаживание осуществлялось для логарифмированных значений с помощью полиномов.
График усреднённых частот в точке N = 0 имеет острый пик, поэтому положительные значения были аппроксимированы полиномом 11 степени, а отрицательные -- полиномом 9 степени.
Результат аппроксимации для диапазона разностей [-25; 18] приведён на рисунке 2.
информация хаффман контроллер кодирование
Рис. 2. Аппроксимированные значения таблицы частот.
Частоты больших значений разностных величин весьма малы, поэтому с целью уменьшения размера статической таблицы целесообразно оставить в ней только те величины, которые попадают в диапазон кодирования.
Величины, не попадающие в этот диапазон, заносятся в специальную таблицу уникальных величин, в кодируемой последовательности все они заменяются единым уникальным символом.
Частота этого символа очевидно равна сумме значений частот символов, не попавших в диапазон кодирования.
Рассмотренные алгоритмы сжатия были реализованы в среде CoDeSys на языке ST.
С помощью этой программы была исследована зависимость коэффициента сжатия и частоты появления уникальных символов от положения границ диапазона кодирования. Результаты исследования представлены на рисунке 3.
Рис. 3. Зависимость логарифма коэффициента сжатия и частоты уникальных символов от положения границ диапазона кодирования. Dl -- расстояние от 0 до левой границы отрезка, Dh -- расстояние от 0 до правой границы отрезка.
Анализ зависимости коэффициента сжатия от положения диапазона кодирования показывает, что образуется плато значений, соответствующих предельной степени сжатия.
Статическая таблица позволяет сразу кодировать очередное измерение, при этом вычислительные ресурсы и время расходуются только на поиск кодовой замены.
Например, выбор диапазона [_13; 3] вместо [-25; 18] приводит к тому, что коэффициент сжатия изменяется с 11.02 до 9.97, т. е. в 1.11 раз, но при этом размер таблицы Хаффмана и соответствующее время поиска замены уменьшается в 2.38 раза.
Пример построения дерева Хаффмана по полученным данным при Dl = Dh = 5 приведён на рисунке 4.
Длина интервала выбрана небольшой, т. к. её увеличение приводит к усложнению графического изображения дерева (в скобках указано количество символов в кодируемом сообщении).
Рис. 4. Дерево Хаффмана.
Выводы
Ограничение диапазона кодируемых величин позволяет управлять размером таблицы Хаффмана. Результаты измерений, которые не попали в диапазон кодирования, необходимо сохранять в специальном массиве, что несколько увеличивает размер архива, но при этом существенно сокращается длительность цикла архивирования.
Наличие представительной выборки результатов измерений позволяет создать статическую таблицу Хаффмана для заданного диапазона кодирования и освободить контроллер от ресурсоёмкой задачи постоянного обновления кодируемой таблицы.
Литература
1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2003. - 384 с.
Размещено на Allbest.ru
...Подобные документы
Особенности кодирования информации с помощью метода Хаффмана. Реализация кодера и декодера с использованием статического алгоритма Хаффмана. Структура программы, оценка ее эффективности (степени сжатия) в зависимости от типа и размера сжимаемых файлов.
курсовая работа [136,2 K], добавлен 15.06.2013Оценка вычислительной сложности программы. Реализация алгоритма кодирования информации Хаффмана. Кодировка теста двоичным кодом и в дереве Хаффмана. Бинарный код символов. Символ и частота его появления в тексте. Вычисление трудоемкости алгоритма.
контрольная работа [21,0 K], добавлен 16.12.2012Описание и особенности некоторых алгоритмов архивации. Построение кода Хаффмана. Динамический алгоритм построения кода Хаффмана. Обратное восстановление текста. Способы двухступенчатого кодирования информации. Практическая реализация алгоритма LZ77.
курсовая работа [51,7 K], добавлен 24.12.2012Описание метода сжатия информации на основе двоичных кодирующих деревьев Хаффмана. Среда разработки Delphi версии 7.0. Понятия объектно-ориентированного программирования. Программа, разработанная в Delphi. Реализация на Delphi метода кодирования Хаффмана.
курсовая работа [2,1 M], добавлен 26.03.2013Обзор существующих программ сжатия данных без потерь. Анализ методов сжатия: алгоритмов группы, KWE, Lossless JPEG, кодирование Хаффмана. Обзор составляющих компонентов. Разработка кода программы-архиватора, работающей на основе алгоритма Хаффмена.
курсовая работа [487,3 K], добавлен 14.07.2011Типы сжатия данных: с потерями (lossy) и без потерь (lossless). Сжатие с минимальной избыточностью. Кодирование методом Шеннона-Фано. Проверка работы программы по сжатию файлов формата bmp и xls. Реализация на Delphi алгоритма сжатия Шеннона и Хаффмана.
курсовая работа [2,6 M], добавлен 26.01.2011Рассмотрение теоретических подходов к алгоритму сжатия LZW, который по мере поступления информации динамически вычисляет целочисленные признаки частоты появления входных символов. Возможности использования современных GPU. Графические форматы GIF и TIFF.
дипломная работа [559,8 K], добавлен 03.10.2011Изучение методов кодирования Хаффмана, Фано. Модель информационной системы Шеннона. Среднестатистическая информационная емкость сообщений для эргодических источников с заданным распределением частот символов. Формулы Хартли для удельной емкости на символ.
презентация [528,9 K], добавлен 19.10.2014Методы арифметического кодирования. Основные функции программ, реализующие алгоритмы кодирования по методам Хаффмана, Голомба, Фибоначчи и Элиаса. Разработка программно-аппаратных средств оптимального арифметического кодирования и их экономический расчет.
дипломная работа [1,1 M], добавлен 26.05.2012Определение среднего количества информации. Зависимость между символами матрицы условных вероятностей. Кодирование методом Шеннона–Фано. Пропускная способность канала связи. Эффективность кодирования сообщений методом Д. Хаффмана, характеристика кода.
контрольная работа [94,6 K], добавлен 04.05.2015Задачи обработки и хранения информации при помощи ЭВМ. Сжатие и кодирование информации в информационно-вычислительных комплексах. Метод Лавинского как простейший метод сжатия информации (числовых массивов) путем уменьшения разрядности исходного числа.
курсовая работа [66,0 K], добавлен 09.03.2009Энтропия и количество информации. Комбинаторная, вероятностная и алгоритмическая оценка количества информации. Моделирование и кодирование. Некоторые алгоритмы сжатия данных. Алгоритм арифметического кодирования. Приращаемая передача и получение.
курсовая работа [325,1 K], добавлен 28.07.2009Общее понятие архивации. Особенности программ архиваторов. Основные методы сжатия информации. Методические основы изучения темы "Архивация данных и сжатие информации" на уроках информатики в базовом курсе. Разработка блока уроков по сжатию информации.
курсовая работа [3,0 M], добавлен 03.06.2012Получение изображения объекта с помощью оптико-электронных систем, построенных на основе ПЗС-приемника. Методы обработки первичной измерительной информации. Реализация алгоритма обработки графической информации с помощью языка программирования Python.
лабораторная работа [1,1 M], добавлен 30.05.2023Краткий обзор основных теорий сжатия. Концепции идей и их реализация. Сжатие данных с использованием преобразования Барроуза-Вилера. Статический алгоритм Хафмана. Локально адаптивный алгоритм сжатия. Алгоритм Зива-Лемпеля (Welch) и метод Шеннона-Фано.
практическая работа [188,5 K], добавлен 24.04.2014Сущность метода зонного сжатия буквенной информации. Описание классов, определяющих место хранения символов и алфавита. Реализация асимметричного алгоритма RSA. Логика построения шифра и структура ключевой информации в криптографическом алгоритме ГОСТ.
контрольная работа [3,2 M], добавлен 30.11.2013Основные понятия и методы сжатия данных. Преобразование информации, хранящейся в файле, к виду, при котором уменьшается избыточность в ее представлении. Статистический и словарный способы сжатия. Программы-архиваторы, основные возможности WinRAR.
контрольная работа [27,5 K], добавлен 12.03.2011Методы компрессии информации. Обзор и характеристика существующих методов сжатия информации, основанных на процедуре кодирования Хаффмена. Алгоритмы динамического кодирования методом FGK и Виттера. Программная реализация и руководство пользователя.
курсовая работа [33,2 K], добавлен 09.03.2009Двоичные деревья в теории информации. Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Обоснование выбора, описание алгоритма и структур данных. Обоснование набора тестов. Построение оптимального кода. Сущность алгоритма Хаффмана.
курсовая работа [241,6 K], добавлен 17.10.2008Применение табличных процессоров в обработке экономической информации. Характеристика пакетов прикладных программ, содержащих электронные таблицы. Элементы электронной таблицы. Типы данных, используемых в электронных таблицах. Функции обработки данных.
курсовая работа [64,8 K], добавлен 25.04.2009
