組み込みアルゴリズム: ビッグデータ可変長ストレージアルゴリズム

1. 適用シナリオ

高精度のサンプリング結果の場合、最大値には 3 バイト、最小値には 1 バイトが必要になる場合があります。標準 C の基本データ型を使用すると、U16 は要件を満たすには小さすぎ、U32 はメモリを無駄にします。サンプルサイズが大きい場合、それが占めるスペースが問題になります。可変長データ型をストレージに使用できますか? 小さなデータには U8 を使用し、大きなデータには U32 を使用し、値のサイズに応じてストレージ領域を動的に割り当てます。これがこの記事の焦点です。

2. データの冗長性の除去

U32 空間の最大値の範囲は 2^32 に近く、非常に大きな値です。実際の値の範囲はそれよりもはるかに小さく、上位ビットは 0 である必要があります。たとえば、U32 は 0x00000001 を使用して 1 を表し、最初のビットはすべて 0 です。これが表す値は、U8 の 0x01 と同じです。先頭の 0 の繰り返し文字列は冗長データ領域に属し、削除できます。

5 つのデータ D0..4 があり、それぞれが元々 U32 型に固定されていると仮定します。上位ビットの冗長な 0 を削除し、それらを U8 の 1 次元配列に連結すると、占有スペースが大幅に削減されます。基本的な考え方は、U32またはU64アレイをU8アレイに切り取ってつなぎ合わせ、それが使用できるようにすることです。

U8配列に保存されている情報に従って、対応する値を復元します。

0x00000001、0x00000101、0x00000001 の 3 つのデータがあり、その有効部分は 0x01、0x0101、0x01 であるとします。これらをそのまま連結すると、0x01010101 の意味を区別できなくなります。したがって、上位の 0 を削除した後も、後続の分析と復元を容易にするために、データをエンコードしてマークする必要があります。

3. データのエンコード

データエンコーディングの主な機能は、現在のデータが占める連続バイト数をマークすることです。次の 2 つの方式があります。

1. バイト長を定義する固定ビット（2ビットで4バイトを表すことができます）

1バイト: 00******

2 バイト: 01******、00******

3 バイト: 10******、01******、00******

4 バイト: 11******、10******、01******、00******

5バイト: 2ビットを使用サポートされていません

各バイトの最上位 2 ビットは、元のデータの番号 (0 から始まる) を示します。前の例の 3 バイトは次のように表すことができます。

0x01 エンコードされたバイナリは 00-000001 で、最上位 2 ビットは 0 であり、これは現在がエンコードされたデータの最後のバイトであることを示します。

0x0101 は、2 進数で 01-000001--00-000001 としてエンコードされます。解析するときは、各バイトの 2 ビットを判定に使用します。00 の場合は、コード化された値の終了を意味します。

最初の 2 ビットはバイト数を示すために固定されているため、各バイトの実際の使用可能範囲は 6 ビットのみです。元のデータが 1000 0001 の場合、上位 2 桁の 10 を表すには別のバイトを占有する必要があり、最終的なコードは 01-000010--00-000001 になります。

このエンコード方式では、すべてのバイトの有効ビットが固定されており、エンコードとデコードが簡単に実装できます。欠点は、4 バイトには有効なデータが 24 ビットしかないことです。元のデータが最大 25 ビットの場合、各バイトを表すために 3 ビットが割り当てられます。ただし、このような大きなデータは組み込みシステムではほとんど使用されません。

2. バイトの最上位ビットは、UTF8でエンコードされた残りのデータがあることを示します。

1バイト: 0*******

2 バイト: 110*****、10******

3 バイト: 1110****、10******、10******

4 バイト: 11110***、10******、10******、10******

5 バイト: 111110**、10******、10******、10******、10******

6 バイト: 1111110*、10******、10******、10******、10******、10******

7バイト: サポートされていません

このエンコード方式では、最上位バイトの有効ビットが変更され、他のバイトの有効ビットは 6 ビットになります。

2 つのエンコード方式の選択は、主に元のデータの分布確率に基づいています。元のデータ範囲が 24 ビット以内の場合、先頭の固定ビット方式が優勢です。32 ビットを超える場合は、動的方式が適切です。データ範囲が 16 ビット以内の場合、それほど面倒な作業を行う必要はありません。

ソースコードや詳細なコミュニケーションについては、WeChat パブリックアカウント Embedded Systems をフォローしてください。

4. データアクセス

元のデータの各値は固定バイト長を占め、配列の添え字を使用して簡単にトラバースできます。つまり、アドレスオフセットは (単一の数値が占めるバイト数) * (バイト数) です。可変長データにエンコードした後、元のデータの特定のエンコードされた値を取得する場合、配列の先頭からトラバースを開始すると、効率が非常に低くなります。もっと良い方法はありますか?

前の 1 次元配列を 2 次元配列に変換します。配列の各行は、前のエンコードに従って実装されます。データには 4 バイトが予約されています。各行がいっぱいになると、末尾は現在の行の終わりと、含まれている元のデータの累積量を示します。次のエンコード値は次の行に格納され、以下同様に続きます。

上の図に示すように、2 次元配列の行は 1 次元配列に縮退し、各行は固定された位置に格納する番号をマークします。 C10 を検索する必要がある場合は、まずマークされた番号のバイトアドレスに従ってトラバースし、2 行目 (0 から始まる) が 13 であることがわかります。これは、検索する必要のあるデータがこの行にあることを意味します。この行をトラバースし、C9 以降からクエリを実行するだけで済みます。