При передачі та зберіганні даних основними проблемами є обсяг даних і швидкість їх передачі. При підготовці даних до передачі або зберігання виконується їх сериализация. Продуктивність процесу передачі залежить від характеристик обраного алгоритму сериализации (швидкість сериализации, можливість стиснення даних, споживана пам'ять). Метою роботи є дослідження існуючих алгоритмів автоматичної сериализации і пошук можливих шляхів їх оптимізації для виконання специфічних завдань.

Анотація наукової статті з комп'ютерних та інформаційних наук, автор наукової роботи - Кравцов А.А., Тропченко А.А., Кріхелі А.М.


AUTOMATIC SERIALIZATION AND COMPRESSION ALGORITHM

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.


Область наук:
  • Комп'ютер та інформатика
  • Рік видавництва діє до: 2016
    Журнал: Міжнародний науково-дослідний журнал

    Наукова стаття на тему 'АЛГОРИТМ АВТОМАТИЧНОЇ Серіалізация зі стисненим'

    Текст наукової роботи на тему «Алгоритм АВТОМАТИЧНОЇ Серіалізация зі стисненим»

    ?DOI: 10.18454 / IRJ.2016.54.119 Кравцов А.А.1, Тропченко А.А.2, Кріхелі А.М.3

    Магістр, 2кандідат технічних наук, доцент, 3магістр, Санкт-Петербурзький національний дослідницький університет інформаційних технологій,

    механіки і оптики

    АЛГОРИТМ АВТОМАТИЧНОЇ Серіалізация зі стисненим

    анотація

    При передачі та зберіганні даних основними проблемами є обсяг даних і швидкість їх передачі. При підготовці даних до передачі або зберігання виконується їх сериализация. Продуктивність процесу передачі залежить від характеристик обраного алгоритму сериализации (швидкість сериализации, можливість стиснення даних, споживана пам'ять). Метою роботи є дослідження існуючих алгоритмів автоматичної сериализации і пошук можливих шляхів їх оптимізації для виконання специфічних завдань.

    Ключові слова: автоматична сериализация, стиснення даних, стиснення числових послідовностей

    Kravtsov A.A.1, Tropchenko A.A.2, Krikheli A.M.3

    faster, 2PhD in Engineering, associate professor, 3master, Saint-Petersburg National Research University of Information Technologies, Mechanics and Optics AUTOMATIC SERIALIZATION AND COMPRESSION ALGORITHM

    Abstract

    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 - Порівняння результатів роботи різних алгоритмів

    На етапі перетворення відбувається розбиття масиву вихідних об'єктів Л [1..К] на кілька масивів примітивних типів Р1 [1..К] ... Рт [1..К] (де N - кількість елементів у вихідному масиві, т - кількість полів об'єкта), причому значення елементів масивів Р1 [х] .., Рт [х] дорівнюють значенням відповідних полів об'єкта Л [х].

    Далі відбувається стиснення кожного масиву примітивних типів. Розглянемо його на прикладі масиву повідомлень автомобільного датчика рівня палива.

    Нехай є деякий масив повідомлень, кожне з яких складається з рівня палива (ціле число, що відображає обсяг палива в баці в мілілітрах) і тимчасової мітки (ціле число). Для простоти буде розглядатися стиснення тільки показань обсягу палива.

    Вихідні дані виглядають наступним чином (Рис. 2)

    t, min

    Мал. 2 - Тимчасові періоди, коли машина перебувала в русі, на стоянці і заправлялася

    і відповідний рівень палива

    Аналіз даних для стиснення проходить в три етапи.

    На першому етапі весь масив розбивається на рівні блоки [3, С. 6] (Рис. 3).

    Мал. 3 - Розбиття на рівні ділянки

    На другому етапі (Рис. 4) для кожного блоку вибирається найкраща стратегія стиснення, що дає на виході найменший обсяг інформації. У поточній реалізації вибір відбувається між алфавітним кодуванням, диференціальним кодуванням і записом без стиснення.

    Мал. 4 - Блоки даних і мінімальна кількість інформації, необхідне для запису одного повідомлення

    в бітах при кодуванні по граничним значенням

    На останньому етапі (Рис. 5) відбувається злиття блоків, для яких обрана однакова стратегія стиснення, а також однакову кількість інформації, що зменшує кількість заголовків. Якщо значення в блоці не змінювалися, відбувається кешування заголовка. В цьому випадку записується тільки заголовок з мінімальним і максимальним значенням (які в даному випадку рівні), а дані блоку не записуються. При читанні всі дані блоку будуть рівні мінімального значення з заголовка.

    Мал. 5 - Макро-блоки, отримані злиттям декількох вихідних блоків Отримані блоки даних мають структуру, описану на рис. 6. 1. Кодування по межах величин

    2 4 1 .. 63 1 .. 63 1 .. N

    II »_11_ II 1

    т

    7

    Г

    Стратегія Кількість Нижня межа верхня межа стиснення блоків

    дані

    2. Диференціальне кодування

    2 4 1 .. 63 1 .. 63 1 .. 63 1 .. N

    і "_11_ _11_ 11

    Т

    Т

    Г

    Стратегія Кількість Мінімальна Максимальна Перше значення стиснення блоків різниця різниця

    I

    дані

    3. Без стиснення

    2 4 1 .. N

    II I

    1--1 - Г

    Стратегія Кількість Дані стиснення блоків

    Мал. 6 - Структура заголовків блоків 113

    Цифрами позначено кількість біт, якими кодується елемент заголовка. У заголовках присутні наступні поля:

    1) Стратегія стиснення. Присутній у всіх типах заголовків. Позначає вибрану стратегію стиснення.

    2) Кількість блоків. Присутній у всіх типах заголовків. Позначає кількість блоків з цим заголовком. При формуванні на етапі аналізу завжди дорівнює одиниці, може змінитися на етапі злиття заголовків

    3) Нижня межа. Дещо специфічною є для алфавітного кодування. Позначає мінімальне значення в блоці.

    4) Верхня межа. Дещо специфічною є для алфавітного кодування. Позначає максимальне значення в блоці.

    5) Мінімальна різниця. Дещо специфічною є для диференціального кодування. Позначає мінімальну різницю між сусідніми значеннями.

    6) Максимальна різниця. Дещо специфічною є для диференціального кодування. Позначає максимальну різницю між сусідніми значеннями.

    7) Перше значення. Специфічно для диференціального кодування. Перше значення в блоці.

    8) Дані. Присутній у всіх типах заголовків. Містить вихідні дані, до яких не застосовувалося стиснення.

    Запис проводиться за допомогою бітових операцій. Кожен байт заповнюється за принципом 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 Framework 4.0 мовою С # / Ріхтер Дж. - 3-е изд. - СПб .: Пітер - 2012. - 928 с.

    2. Serialization (C # and Visual Basic). [Електронний ресурс] // Microsoft. URL: https://msdn.microsoft.com/ru-ru/library/ms233843.aspx (дата звернення 15.12.2011);

    3. Ватолин Д. Методи стиснення даних. Пристрій архіваторів, стиснення зображень і відео / Ватолин Д., Ратушняк А., Смирнов М. та ін. - М .; ДІАЛОГ-МІФІ - 2003. - 384 с.

    4. Вірт Н. Алгоритми + структури даних = програми / Вірт Н. - 7-е вид. - М .; Вільямс - 2001. - 410 c.

    Список літератури англійською мовою / References in English

    1. Richter J. CLR via C #. Programmirovanie na platforme Microsoft .NET Framework 4.0 na jazyke C # [CLR via C #. Programming in Microsoft .NET Framework 4.0 platform in C #] / Richter J. - 3rd edition. - SPb .: Piter. - 2012. - 928 p. [In Russian]

    2. Serialization (C # and Visual Basic). [Electronic resource] // Microsoft. URL: https://msdn.microsoft.com/ru-ru/library/ms233843.aspx (accessed 15.12.2011). [In Russian]

    3. Vatolin D. Metody szhatija dannyh. Ustrojstvo arhivatorov, szhatie izobrazhenij i video [Data compression methods. Implementation of archivers, image and video compression] / Vatolin D., Ratushnjak A., Smirnov M. and others. - M .; DIALOG-MIFI - 2003. - 384 p. [In Russian]

    4. Wirth N. Algoritmy + struktury dannyh = programmy [Algorithms + data structures = programs] / Wirth N. - 7th edition. - M .; Viljams - 2001. - 410 p. [In Russian]


    Ключові слова: АВТОМАТИЧЕСКАЯ Серіалізация / AUTOMATIC SERIALIZATION / СТИСК ДАНИХ / DATA COMPRESSION / СТИСК числових послідовностей / NUMERIC SEQUENCE COMPRESSION

    Завантажити оригінал статті:

    Завантажити