Данные переменной длинны — 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 раз меньше памяти (за счет отсутствия необходимости конвертации данных в текстовый вид и обратно).

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

Комментарии 15

  • НЛО прилетело и опубликовало эту надпись здесь
    • НЛО прилетело и опубликовало эту надпись здесь
        0
        Спасибо, ознакомился!
        По поводу ASN.1 — это уже глубокое и очень сложное кодирование. Да и 11 типов строк из которых реально я бы использовал штуки 3-5 — сильно избыточно.
        По поводу KLV — концепция ключ-значение очень фундаментальна.
        Ключи в KLV могут быть 1,2,4 или 16 байт (не понятно почему нет 8-ми). Нельзя использовать строку как ключ. Меня это не устраивает.
        Длина (BER) кодируется очень похожим способом, но обладает большей избыточностью на диапазоне [256;256^7].
        Карта std::map< DSV1, DSV2 > позволяет представить более широкий диапазон ключей и значений, которые с легкостью могут быть сериализированы.
      +3
      Protocol Buffers, Thrift.
        0
        Protocol Buffers — очень хорошая библиотека для сериализации статических типов данных, буду использовать для других целей — спасибо!
        Похоже, что Thrift не умеет работать с составными типами. Это очень существенный минус.
          0
          > Похоже, что Thrift не умеет работать с составными типами.

          В каком смысле? struct (аналогичные Protobuf) и union там есть.
            0
            Моё (ложное) высказывание было основано на неправильно понятой строке «Композитные расширения типов» из ru.wikipedia.org/wiki/Apache_Thrift. Можете подсказать что это значит?

            Когда-то мне очень не хватало такого инструмента…
      +1
      ProtoBuf знаковые инты еще и зигзагом кодирует, чтобы отрицательные меньше места занимали
        0
        Всё-таки есть как минимум один недостаток у такого формата. Нет никакой проверки целостности данных. Если вы её добавите, то формат будет уже не такой экономный.
          +5
          Во-первых: UTF-8. Нет, это, конечно не формат упаковки и сериализации, но идея подобная.
          Во-вторых: Колмогоров как бы намекает нам, что при равномерном распределении байт (нам интересен включенный/выключенный старший бит, который равновероятно встречается) такая схема кодирования будет приводить к увеличению конченого размера сообщения. То есть, на каждые 8 байт данных будет получаться (в среднем) 4 избыточных бита. Таким образом выигрыш будет только на относительно коротких «объектах».
          В-третьих: обработка таких данных потребует промежуточного буфера, в который будет разворачиваться декодированная последовательность. А это у нас сплошные минусы: время на декодирование, плюс память, размер объекта неизвестен до декодирования.

          Иными словами, схему кодирования данных нужно выбирать из их статистических свойств. Теория информации не позволяет изобрести серебрянную пулю 'zip', такую, что для любого d будет выполнятся size(d) > size(zip(d)). Всегда можно подобрать такие условия, в которых выбранная схема кодирования будет давать худший результат (в смысле размера или скорости доступа к данным), по сравнению с исходным представлением.

          В качестве альтернативы способом описанным в статье можно кодировать только поле «длина объекта». Тогда на сообщениях длиной больше 4 байт (в случае равномерного распределения) будет значительный выигрыш и в размере и в скорости обработки, по сравнению с предложенным в статье (не требуется промежуточный буфер, не требуется «распаковка», размер сообщения известен сразу).

          А вообще не очень понятно, почему бы сразу не сжимать данные Лемпелем-Зивом или что там сейчас в моде?
            0
            1 В UTF-8 идея похожая, но система кодирования значительно сложнее и позволяет представить 6 байт максимум. Если вместо UTF-8 использовать эту схему, то ASCII алфавит остается валидным, а остальные символы на много легче обрабатывать.

            2,3 Уровни 2 и 3 описывают применение формата DSV как раз для кодирования длины последующих данных. Такой формат обеспечивает фрактальность объектов.

            А вообще не очень понятно, почему бы сразу не сжимать данные Лемпелем-Зивом или что там сейчас в моде?

            Задача о сжатии данных не стояла, только «эффективная упаковка данных».
            0
            MessagePack
              0
              Нашел эту идею уже ранее реализованной в формате MIDI:
              https://en.wikipedia.org/wiki/Variable-length_quantity
              http://web.archive.org/web/20051129113105/http://www.borg.com/~jglatt/tech/midifile/vari.htm

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое