Comments 15
UFO just landed and posted this here
UFO just landed and posted this here
Спасибо, ознакомился!
По поводу ASN.1 — это уже глубокое и очень сложное кодирование. Да и 11 типов строк из которых реально я бы использовал штуки 3-5 — сильно избыточно.
По поводу KLV — концепция ключ-значение очень фундаментальна.
Ключи в KLV могут быть 1,2,4 или 16 байт (не понятно почему нет 8-ми). Нельзя использовать строку как ключ. Меня это не устраивает.
Длина (BER) кодируется очень похожим способом, но обладает большей избыточностью на диапазоне [256;256^7].
Карта std::map< DSV1, DSV2 > позволяет представить более широкий диапазон ключей и значений, которые с легкостью могут быть сериализированы.
По поводу ASN.1 — это уже глубокое и очень сложное кодирование. Да и 11 типов строк из которых реально я бы использовал штуки 3-5 — сильно избыточно.
По поводу KLV — концепция ключ-значение очень фундаментальна.
Ключи в KLV могут быть 1,2,4 или 16 байт (не понятно почему нет 8-ми). Нельзя использовать строку как ключ. Меня это не устраивает.
Длина (BER) кодируется очень похожим способом, но обладает большей избыточностью на диапазоне [256;256^7].
Карта std::map< DSV1, DSV2 > позволяет представить более широкий диапазон ключей и значений, которые с легкостью могут быть сериализированы.
Protocol Buffers, Thrift.
Protocol Buffers — очень хорошая библиотека для сериализации статических типов данных, буду использовать для других целей — спасибо!
Похоже, что Thrift не умеет работать с составными типами. Это очень существенный минус.
Похоже, что Thrift не умеет работать с составными типами. Это очень существенный минус.
> Похоже, что Thrift не умеет работать с составными типами.
В каком смысле? struct (аналогичные Protobuf) и union там есть.
В каком смысле? struct (аналогичные Protobuf) и union там есть.
Моё (ложное) высказывание было основано на неправильно понятой строке «Композитные расширения типов» из ru.wikipedia.org/wiki/Apache_Thrift. Можете подсказать что это значит?
Когда-то мне очень не хватало такого инструмента…
Когда-то мне очень не хватало такого инструмента…
Думаю, что это developers.google.com/protocol-buffers/docs/proto#extensions.
ProtoBuf знаковые инты еще и зигзагом кодирует, чтобы отрицательные меньше места занимали
Всё-таки есть как минимум один недостаток у такого формата. Нет никакой проверки целостности данных. Если вы её добавите, то формат будет уже не такой экономный.
Во-первых: UTF-8. Нет, это, конечно не формат упаковки и сериализации, но идея подобная.
Во-вторых: Колмогоров как бы намекает нам, что при равномерном распределении байт (нам интересен включенный/выключенный старший бит, который равновероятно встречается) такая схема кодирования будет приводить к увеличению конченого размера сообщения. То есть, на каждые 8 байт данных будет получаться (в среднем) 4 избыточных бита. Таким образом выигрыш будет только на относительно коротких «объектах».
В-третьих: обработка таких данных потребует промежуточного буфера, в который будет разворачиваться декодированная последовательность. А это у нас сплошные минусы: время на декодирование, плюс память, размер объекта неизвестен до декодирования.
Иными словами, схему кодирования данных нужно выбирать из их статистических свойств. Теория информации не позволяет изобрести серебрянную пулю 'zip', такую, что для любого d будет выполнятся size(d) > size(zip(d)). Всегда можно подобрать такие условия, в которых выбранная схема кодирования будет давать худший результат (в смысле размера или скорости доступа к данным), по сравнению с исходным представлением.
В качестве альтернативы способом описанным в статье можно кодировать только поле «длина объекта». Тогда на сообщениях длиной больше 4 байт (в случае равномерного распределения) будет значительный выигрыш и в размере и в скорости обработки, по сравнению с предложенным в статье (не требуется промежуточный буфер, не требуется «распаковка», размер сообщения известен сразу).
А вообще не очень понятно, почему бы сразу не сжимать данные Лемпелем-Зивом или что там сейчас в моде?
Во-вторых: Колмогоров как бы намекает нам, что при равномерном распределении байт (нам интересен включенный/выключенный старший бит, который равновероятно встречается) такая схема кодирования будет приводить к увеличению конченого размера сообщения. То есть, на каждые 8 байт данных будет получаться (в среднем) 4 избыточных бита. Таким образом выигрыш будет только на относительно коротких «объектах».
В-третьих: обработка таких данных потребует промежуточного буфера, в который будет разворачиваться декодированная последовательность. А это у нас сплошные минусы: время на декодирование, плюс память, размер объекта неизвестен до декодирования.
Иными словами, схему кодирования данных нужно выбирать из их статистических свойств. Теория информации не позволяет изобрести серебрянную пулю 'zip', такую, что для любого d будет выполнятся size(d) > size(zip(d)). Всегда можно подобрать такие условия, в которых выбранная схема кодирования будет давать худший результат (в смысле размера или скорости доступа к данным), по сравнению с исходным представлением.
В качестве альтернативы способом описанным в статье можно кодировать только поле «длина объекта». Тогда на сообщениях длиной больше 4 байт (в случае равномерного распределения) будет значительный выигрыш и в размере и в скорости обработки, по сравнению с предложенным в статье (не требуется промежуточный буфер, не требуется «распаковка», размер сообщения известен сразу).
А вообще не очень понятно, почему бы сразу не сжимать данные Лемпелем-Зивом или что там сейчас в моде?
1 В UTF-8 идея похожая, но система кодирования значительно сложнее и позволяет представить 6 байт максимум. Если вместо UTF-8 использовать эту схему, то ASCII алфавит остается валидным, а остальные символы на много легче обрабатывать.
2,3 Уровни 2 и 3 описывают применение формата DSV как раз для кодирования длины последующих данных. Такой формат обеспечивает фрактальность объектов.
Задача о сжатии данных не стояла, только «эффективная упаковка данных».
2,3 Уровни 2 и 3 описывают применение формата DSV как раз для кодирования длины последующих данных. Такой формат обеспечивает фрактальность объектов.
А вообще не очень понятно, почему бы сразу не сжимать данные Лемпелем-Зивом или что там сейчас в моде?
Задача о сжатии данных не стояла, только «эффективная упаковка данных».
MessagePack
Нашел эту идею уже ранее реализованной в формате MIDI:
https://en.wikipedia.org/wiki/Variable-length_quantity
http://web.archive.org/web/20051129113105/http://www.borg.com/~jglatt/tech/midifile/vari.htm
https://en.wikipedia.org/wiki/Variable-length_quantity
http://web.archive.org/web/20051129113105/http://www.borg.com/~jglatt/tech/midifile/vari.htm
Sign up to leave a comment.
Данные переменной длинны — DataSizeVariable (DSV)