可変データが長い-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」の場合、次のバイトでは数値が継続します。 データは、重要度の高い部分から重要度の低い部分へ、左から右(ビッグエンディアン)に一度に1バイトずつ割り当てられます。 数値のすべての有用なビットは、7ビットでDSV形式の1バイトにパックされ、必要に応じて拡張値の符号が追加されます(高、8ビット目)。 例:



画像



レベル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倍少ないメモリを使用します(データをテキストに、またはその逆に変換する必要がないため)。



機能が似ているプロジェクトを知っている人がいたら教えてください。

もし誰かが実装に興味があるなら、 ここにミニライブラリのソースコードへのリンクがあります。



All Articles