Алгоритм автоматической сериализации со сжатием
Исследование алгоритмов автоматической сериализации и поиск возможных путей их оптимизации для выполнения специфических задач. Общая концепция процесса сериализации. формат объекта, сериализованного стандартными средствами. Этапы анализа для сжатия.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | статья |
Язык | русский |
Дата добавления | 30.04.2018 |
Размер файла | 514,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Статья
на тему: Алгоритм автоматической сериализации со сжатием
Выполнил:
Кравцов А.А.
При передаче и хранении данных основными проблемами являются объем данных и скорость их передачи. При подготовке данных к передаче или хранению выполняется их сериализация. Производительность процесса передачи зависит от характеристик выбранного алгоритма сериализации (скорость сериализации, возможность сжатия данных, потребляемая память). Целью работы является исследование существующих алгоритмов автоматической сериализации и поиск возможных путей их оптимизации для выполнения специфических задач.
Ключевые слова: автоматическая сериализация, сжатие данных, сжатие числовых последовательностей
In transmission and storage of data among the main problems is the amount of information transmitted and its transmission speed. In the preparation of objects for the transmission and storage performed their serialization. The performance of transmission process depends on characteristics of serialization algorithm (serialization speed, data compression ability, memory consumption). The objective is to analyze the existing algorithms of automatic serialization and finding possible ways of their optimization for specific tasks.
Keywords: automatic serialization; data compression; numeric sequence compression.
Сериализация - это процесс перевода объекта в последовательность байт, который применяется для сохранения их состояния [1, С. 710]. В частности, она широко используется в таких технологиях, как REST, RPC и им подобных. Например, вызове удаленной процедуры, объекты, переданные как ее параметры, сериализуются в поток байт и отправляются на сервер вместе с информацией о вызываемой процедуре. В современных фреймворках междоменного взаимодействия (таких как WCF), описанный процесс происходит автоматически. Также сериализованный объект может быть сохранен в файл и позже восстановлен, как это часто бывает при сохранении конфигурации. Целью исследования был поиск возможных путей улучшения существующих решений для автоматической сериализации.
Общая концепция процесса состоит в следующем. Бизнес-объект является некоторой сущностью, моделирующей реальный объект. В большинстве случаев он состоит из логических типов, поэтому сохранение состояния такого объекта не представляется возможным. Для выполнения этой задачи создается data transfer object (DTO). Это объект, формирующийся в результате обхода дерева логических типов, и состоящий из его листьев - примитивных типов. На следующем этапе записывается полученный набор примитивных типов, согласно выбранному алгоритму. В рефлексивных языках, где доступна метаинформация о типах данных, возможна автоматическая сериализация, которая полезна в случае значительной ширины и глубины дерева типов бизнес-объекта. Также автоматическая сериализация применяется в динамически-типизированных языках, где структура типа часто изменяется, либо вообще не определена во время компиляции.
Существует множество готовых решений для автоматической сериализации объектов. По сравнению с ручной сериализацией, готовые решения обладают рядом существенных недостатков, таких как большее время работы и низкий коэффициент сжатия данных (значительно меньше единицы). Эти недостатки вызваны накладными расходами на запись метаданных, необходимых для десериализации объекта. Необходимость в обходе дерева типов с помощью инструментов рефлексии также негативно сказывается на времени работы средств автоматической сериализации.
Рассмотрим подробнее формат объекта, сериализованного стандартными средствами .NET [2]. Заголовок содержит описание контракта. За ним следует структура данных и сами данные. Этой метаинформации достаточно, чтобы восстановить исходный объект. Но метаинформация имеет значительный объем, поэтому было принято решение записывать только данные, а структуру данных и контракт предоставлять непосредственно в момент чтения или записи. Контрактом в таком случае служит порядок обхода полей объекта, а структура описывается структурой сериализуемого типа. Для дальнейшего уменьшения объема объектов используется сжатие последовательностей однотипных объектов. Таким образом, разработанный алгоритм сериализации имеет следующую структуру (Рис. 1).
Рис. 1 - Сравнение результатов работы различных алгоритмов
На этапе преобразования происходит разбиение массива исходных объектов A[1..N] на несколько массивов примитивных типов P1[1..N]…Pm[1..N] (где N - количество элементов в исходном массиве, m - количество полей объекта), причем значения элементов массивов P1[x]…Pm[x] равны значениям соответствующих полей объекта A[x].
Далее происходит сжатие каждого массива примитивных типов. Рассмотрим его на примере массива сообщений автомобильного датчика уровня топлива.
Пусть имеется некоторый массив сообщений, каждое из которых состоит из уровня топлива (целое число, отражающее объем топлива в баке в миллилитрах) и временной метки (целое число). Для простоты будет рассматриваться сжатие только показаний объема топлива.
Исходные данные выглядят следующим образом (Рис. 2)
Рис. 2 - Временные периоды, когда машина находилась в движении, на стоянке и заправлялась и соответствующий уровень топлива
Анализ данных для сжатия проходит в три этапа.
На первом этапе весь массив разбивается на равные блоки [3, С. 6] (Рис. 3).
Рис. 3 - Разбиение на равные участки
На втором этапе (Рис. 4) для каждого блока выбирается лучшая стратегия сжатия, дающая на выходе наименьший объем информации. В текущей реализации выбор происходит между алфавитным кодированием, дифференциальным кодированием и записью без сжатия.
Рис. 4 - Блоки данных и минимальное количество информации, необходимое для записи одного сообщения в битах при кодировании по граничным значениям
На последнем этапе (Рис. 5) происходит слияние блоков, для которых выбрана одинаковая стратегия сжатия, а также одинаковое количество информации, что уменьшает количество заголовков. Если значения в блоке не изменялись, происходит кеширование заголовка. В этом случае записывается только заголовок с минимальным и максимальным значением (которые в данном случае равны), а данные блока не записываются. При чтении все данные блока будут равны минимальному значению из заголовка.
Рис. 5 - Макро-блоки, полученные слиянием нескольких исходных блоков алгоритм автоматическая сериализация сжатие
Полученные блоки данных имеют структуру, описанную на рис. 6.
Рис. 6 - Структура заголовков блоков
Цифрами обозначено количество бит, которыми кодируется элемент заголовка. В заголовках присутствуют следующие поля:
· Стратегия сжатия. Присутствует во всех типах заголовков. Обозначает выбранную стратегию сжатия.
· Количество блоков. Присутствует во всех типах заголовков. Обозначает количество блоков с этим заголовком. При формировании на этапе анализа всегда равно единице, может измениться на этапе слияния заголовков
· Нижняя граница. Специфична для алфавитного кодирования. Обозначает минимальное значение в блоке.
· Верхняя граница. Специфична для алфавитного кодирования. Обозначает максимальное значение в блоке.
· Минимальная разница. Специфична для дифференциального кодирования. Обозначает минимальную разницу между соседними значениями.
· Максимальная разница. Специфична для дифференциального кодирования. Обозначает максимальную разницу между соседними значениями.
· Первое значение. Специфично для дифференциального кодирования. Первое значение в блоке.
· Данные. Присутствует во всех типах заголовков. Содержит исходные данные, к которым не применялось сжатие.
Запись проводится с помощью битовых операций. Каждый байт заполняется по принципу FIFO, после чего отправляется в поток. Чтение происходит в обратном порядке. Такая организация записи даёт максимальную компактность данных, так как отсутствует избыточная информация. После проведения замеров получились следующие значения.
Таблица 1 - Сравнение результатов работы различных алгоритмов
Алгоритм |
Данные |
Коэффициент сжатия |
Время работы, с |
|
Автоматическая сериализация |
Числовые |
0.31 |
1.342 |
|
Изображение |
0.18 |
1.356 |
||
Текст |
0.43 |
1.298 |
||
Ручная сериализация |
Числовые |
0.97 |
0.121 |
|
Изображение |
0.99 |
0.143 |
||
Текст |
0.99 |
0.107 |
||
Сериализация со сжатием (разработанный алгоритм) |
Числовые |
4.71 |
0.534 |
|
Изображение |
1.64 |
0.542 |
||
Текст |
1.37 |
0.517 |
По полученным результатам можно сделать следующие выводы:
· В отличие от ручной сериализации, и автоматических решений, полученный алгоритм производит сжатие данных.
· Сжатие рассчитано на обработку числовых последовательностей, вследствие чего коэффициент сжатия числовых объектов получается больше, чем у универсальных алгоритмов сжатия.
· Благодаря отсутствия метаинформации в полученном массиве данных, сериализация происходит быстрее.
Ввиду некоторой специфичности алгоритма появляются следующие ограничения и недостатки:
· Так как описание структуры объекта не записывается вместе с данными, она должна быть известна при чтении и записи. Это накладывает ограничения на использование алгоритма в динамически-типизируемых языках.
· Способ записи FIFO обеспечивает максимальную плотность данных, но при этом теряется возможность доступа к N-ному элементу, пока не будут прочитаны предыдущие [4, С. 198-202].
· При сжатии таких данных, как изображения, текст и звук коэффициент сжатия получается ниже, чем у специализированных алгоритмов сжатия без потерь.
Список литературы / References
1. Рихтер Дж. CLR via С#. Программирование на платформе Microsoft .NET Framework0 на языке С# / Рихтер Дж. - 3-е изд. -- СПб.: Питер -- 2012. -- 928 с.
2. Serialization (C# and Visual Basic). [Электронный ресурс] // Microsoft. URL: https://msdn.microsoft.com/ru-ru/library/msaspx (дата обращения 15.12.2011);
3. Ватолин Д. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео / Ватолин Д., Ратушняк А., Смирнов М. и др. -- М.; ДИАЛОГ-МИФИ -- 2003. - 384 с.
4. Вирт Н. Алгоритмы + структуры данных = программы / Вирт Н. -- 7-е изд. -- М.; Вильямс -- 2001. - 410 c.
Размещено на Allbest.ru
...Подобные документы
Методика сериализации объектов и её практическое применение. Клонирование объектов при помощи сериализации. Обработка действий мыши и клавиатуры. Изучение классов Menu, MenuBar, MenuItem, Dialog, FileDialog пакета java.awt, использование таблиц.
лабораторная работа [180,8 K], добавлен 30.06.2009Реализация информационно-справочной системы "Отдел кадров" на языке программирования, с использованием технологии сериализации объектов. Средства конструктора баз данных Windows Forms. Обработка информации и соответствующие организационные ресурсы.
отчет по практике [95,7 K], добавлен 09.08.2015Роль классификации документов в решении задач информационного поиска. Методы автоматической классификации документов и этапы построения классифицирующей системы: индексация документа, построение классификаторов на базе обучающих данных, оценка их работы.
курсовая работа [354,2 K], добавлен 13.01.2013Структурная схема автоматической системы регулирования. Построение амплитудно-фазовой характеристики объекта по каналам регулирующего и возмущающего воздействия. Определение эффективной полосы пропускания частот и оптимальных настроек ПИД–регулятора.
курсовая работа [1,2 M], добавлен 20.08.2013Способы организации вычислительного процесса в системах с несколькими процессорами. Разработка программы на основе алгоритмов мультипроцессорных систем при пакетной обработке задач. Вычисление основных показателей эффективности для каждого алгоритма.
курсовая работа [102,3 K], добавлен 21.06.2013Положения алгоритмов сжатия изображений. Классы приложений и изображений, критерии сравнения алгоритмов. Проблемы алгоритмов архивации с потерями. Конвейер операций, используемый в алгоритме JPEG. Характеристика фрактального и рекурсивного алгоритмов.
реферат [242,9 K], добавлен 24.04.2015Описание генетических алгоритмов. Применение генетического алгоритма для решения задачи коммивояжера. Постановка задачи безусловной оптимизации. Изучение распространения генетических алгоритмов на модель с несколькими взаимодействующими популяциями.
дипломная работа [979,1 K], добавлен 30.05.2015Исследование типовых примеров задач оптимизации. Реализация программы в среде MatLab для их решения. Изучение функций нелинейной оптимизации. Определение оптимума целевой функции одной или нескольких переменных. Поиск оптимальных настроек регулятора.
лабораторная работа [188,8 K], добавлен 07.12.2016Краткий обзор основных теорий сжатия. Концепции идей и их реализация. Сжатие данных с использованием преобразования Барроуза-Вилера. Статический алгоритм Хафмана. Локально адаптивный алгоритм сжатия. Алгоритм Зива-Лемпеля (Welch) и метод Шеннона-Фано.
практическая работа [188,5 K], добавлен 24.04.2014Использование методики управления жизненным циклом разработки программного обеспечения при внедрении реальной информационной системы. Предварительное исследование, проектирование, разработка, применение и обслуживание системы автоматической регистрации.
контрольная работа [30,6 K], добавлен 16.10.2010Современные методы цифрового сжатия. Классификация алгоритмов сжатия. Оцифровка аналогового сигнала. Алгоритм цифрового кодирования. Последовательное двойное сжатие. Чересстрочность и квантование. Сокращение цифрового потока. Профили, уровни формата MPEG.
реферат [784,9 K], добавлен 22.01.2013Изучение аналитических и численных методов поиска одномерного и многомерного безусловного экстремума. Решение поставленной задачи с помощью Mathcad и Excel. Реализация стандартных алгоритмов безусловной оптимизации средствами языка программирования С++.
курсовая работа [488,5 K], добавлен 21.10.2012Составление матрицы непосредственных связей для структуры сети автоматической системы управления, заданной графом. Определение возможных путей доведения и ранжирование их по приоритетам. Этап разложения матрицы с одновременным раскрытием скобок.
контрольная работа [326,1 K], добавлен 03.12.2011Составление и программная реализация в среде Borland Delphi 7.0 алгоритмов итерационного и рекурсивного вариантов решения задачи поиска с возвращением. Исследование асимптотической временной сложности решения в зависимости от количества ячеек на плате.
курсовая работа [57,5 K], добавлен 25.06.2013Критерии и основные стратегии планирования процессора. Разработка моделей алгоритмов SPT (Shortest-processing-task-first) и RR (Round-Robin). Сравнительный анализ выбранных алгоритмов при различных условиях и различном количестве обрабатываемых данных.
курсовая работа [179,3 K], добавлен 21.06.2013Рассмотрение теоретических подходов к алгоритму сжатия LZW, который по мере поступления информации динамически вычисляет целочисленные признаки частоты появления входных символов. Возможности использования современных GPU. Графические форматы GIF и TIFF.
дипломная работа [559,8 K], добавлен 03.10.2011Способ улучшения сжатия файлов формата DjVu. Общая схема алгоритма классификации букв. Основной алгоритм сравнения пары букв. Быстрый отказ для пары разных букв. Дерево разрезов. Получение монохромных изображений. Алгоритм для устранения мусора.
курсовая работа [64,7 K], добавлен 28.10.2008Изучение пространственных характеристик АГК и структур НС при обработке ими стохастических сред, подбор алгоритмов. Рекомендаций по использованию разработанных адаптивных алгоритмов с корреляционными методами получения оценок для регрессионных моделей.
дипломная работа [5,1 M], добавлен 06.05.2011Знакомство с этапами разработки автоматической информационной системы для учета продаж бытовой техники для автоматизации документооборота. Рассмотрение особенностей выявления бизнес-процесса продаж бытовой техники, анализ этапов составления инструкции.
дипломная работа [1,4 M], добавлен 28.11.2014Представление задач в виде графов AND/OR, примеры. Задача с ханойской башней. Формулировка процесса игры в виде графа. Основные процедуры поиска по заданному критерию. Эвристические оценки и алгоритм поиска. Пример отношений с определением задачи.
лекция [154,6 K], добавлен 17.10.2013