Данные переменной длинны — DataSizeVariable (DSV)

от автора

Всем привет!

Давно хотел написать статью. Я сам мало люблю длинные тексты с небольшим количеством полезной информации, поэтому постараюсь сделать этот максимально насыщенным.

Обобщенная тема – эффективная упаковка данных, сериализация и десериализация объектов.
Основная цель – поделиться своими размышлениями по этому поводу и обсудить структуру данных DSV.

Проблема:
Известные мне на текущий момент (2013-09-19 18:09:56) механизмы бинарной сериализации обладают недостаточной гибкостью или избыточность занимаемого пространства. Например:
QString s1(“123”); -> 4 байта размера данных = 0x00000003, 3 байта полезных данных = “123”, эффективность = 3/7;
U32 val1(123); -> 4 байта данных (0x0000007B), 1 байт из которых является значимым = 123 (0x7B), эффективность = 1/4.

Возможное решение:
Уровень 1 – натуральные числа:
DataSizeVariable (DSV) – данные переменной длинны с минимальными избыточными расходами по объему памяти. Формат DSV описывает сохранение и восстановление целых неотрицательных чисел в диапазоне [0;∞]. Это обеспечивает теоретически неограниченную масштабируемость и бинарную совместимость данных по одним и тем же правилам от 8-битных контроллеров до серверов и кластеров.

Суть формата заключается в том, что старший бит каждого (8-битного) байта является признаком его расширенности, остальные биты (7 бит) – информационные. Таким образом, проанализировав его, мы имеем возможность определить границу текущего значения (числа). Если он равен «0», то число закончилось, если «1» – в следующем байте число продолжится. Данные размещаются от более значимых частей к менее значимым, слева направо (big-endian), по одному байту. Все полезные биты числа упаковываются по 7 бит в один байт формата DSV и при необходимости добавляется признак расширенности значения (старший, 8-ой бит). Примеры:

image

Уровень 2 – объекты:
На этом уровне число в формате DSV используется для объектов произвольного размера.
Object1_SizeDataInDSV, Object1_Data, Object2_SizeDataInDSV, Object2_Data, …

Уровень 3 – последовательности объектов:
На этом уровне число в формате DSV используется для указания размера последовательности объектов, элементами которой являются объекты в формате DSV.
Sequence1_SizeDataInDSV, Sequence1_Data (Object1_SizeDataInDSV, Object1_Data, Object2_SizeDataInDSV, Object2_Data, …), Sequence2_SizeDataInDSV, Sequence2_Data (…), …

Таким образом можно строить иерархию объектов наподобие XML.
Так как формат DSV двоичный в отличие от XML, то прямые и обратные преобразования проходят в 10…1000 раз быстрее и занимают в 2…5 раз меньше памяти (за счет отсутствия необходимости конвертации данных в текстовый вид и обратно).

Если кто-то знает похожие по функциональности проекты, прошу подсказать.
Если кто-то заинтересовался реализацией, то вот ссылка на исходный код мини-библиотеки.

ссылка на оригинал статьи http://habrahabr.ru/post/194492/


Комментарии

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *