C# で符号なし整数値の可変長エンコーディングを行う最良の方法は何ですか?
「実際の意図は、可変長でエンコードされた整数 (バイト) をファイル ヘッダーに追加することです。」
例: "Content-Length" - HTTP ヘッダー
これは、以下のロジックを変更することで実現できますか。
私はそれを行うコードをいくつか書きました....
私が使用した方法は、値が小さいほど使用するバイト数が少なくなり、7ビットのデータ+1ビットのオーバーヘッドprをエンコードすることです。バイト。
エンコーディングは、ゼロから始まる正の値に対してのみ機能しますが、必要に応じて、負の値を処理するように変更することもできます。
エンコーディングの仕組みは次のとおりです。
デコードするには:
39 32 31 24 23 16 15 8 7 0 値:| DDDDDDDD | CCCCCCCC | BBBBBBBB | AAAAAAAA | エンコード:| 0000DDDD | xDDDDCCC | xCCCCCBB | xBBBBBBA | xAAAAAAA | (注、逆の順序で保存されます)
ご覧のとおり、制御ビットのオーバーヘッドが原因で、エンコードされた値が半分だけ使用される1バイトを占める可能性があります。これを64ビット値に拡張すると、追加のバイトが完全に使用されるため、追加のオーバーヘッドは1バイトだけになります。
注:エンコーディングは一度に1バイトずつ、常に同じ順序で値を格納するため、ビッグエンディアンまたはリトルエンディアンのシステムはこのレイアウトを変更しません。最下位バイトは常に最初に格納されます。
範囲とそのエンコードされたサイズ:
0〜127:1バイト 128-16.383:2バイト 16.384-2.097.151:3バイト 2.097.152-268.435.455:4バイト 268.435.456-max-int32:5バイト
両方のC#実装は次のとおりです。
void Main()
{
using (FileStream stream = new FileStream(@"c:\temp\test.dat", FileMode.Create))
using (BinaryWriter writer = new BinaryWriter(stream))
writer.EncodeInt32(123456789);
using (FileStream stream = new FileStream(@"c:\temp\test.dat", FileMode.Open))
using (BinaryReader reader = new BinaryReader(stream))
reader.DecodeInt32().Dump();
}
// Define other methods and classes here
public static class Extensions
{
/// <summary>
/// Encodes the specified <see cref="Int32"/> value with a variable number of
/// bytes, and writes the encoded bytes to the specified writer.
/// </summary>
/// <param name="writer">
/// The <see cref="BinaryWriter"/> to write the encoded value to.
/// </param>
/// <param name="value">
/// The <see cref="Int32"/> value to encode and write to the <paramref name="writer"/>.
/// </param>
/// <exception cref="ArgumentNullException">
/// <para><paramref name="writer"/> is <c>null</c>.</para>
/// </exception>
/// <exception cref="ArgumentOutOfRangeException">
/// <para><paramref name="value"/> is less than 0.</para>
/// </exception>
/// <remarks>
/// See <see cref="DecodeInt32"/> for how to decode the value back from
/// a <see cref="BinaryReader"/>.
/// </remarks>
public static void EncodeInt32(this BinaryWriter writer, int value)
{
if (writer == null)
throw new ArgumentNullException("writer");
if (value < 0)
throw new ArgumentOutOfRangeException("value", value, "value must be 0 or greater");
do
{
byte lower7bits = (byte)(value & 0x7f);
value >>= 7;
if (value > 0)
lower7bits |= 128;
writer.Write(lower7bits);
} while (value > 0);
}
/// <summary>
/// Decodes a <see cref="Int32"/> value from a variable number of
/// bytes, originally encoded with <see cref="EncodeInt32"/> from the specified reader.
/// </summary>
/// <param name="reader">
/// The <see cref="BinaryReader"/> to read the encoded value from.
/// </param>
/// <returns>
/// The decoded <see cref="Int32"/> value.
/// </returns>
/// <exception cref="ArgumentNullException">
/// <para><paramref name="reader"/> is <c>null</c>.</para>
/// </exception>
public static int DecodeInt32(this BinaryReader reader)
{
if (reader == null)
throw new ArgumentNullException("reader");
bool more = true;
int value = 0;
int shift = 0;
while (more)
{
byte lower7bits = reader.ReadByte();
more = (lower7bits & 128) != 0;
value |= (lower7bits & 0x7f) << shift;
shift += 7;
}
return value;
}
}
まず、値のヒストグラムを作成する必要があります。分布がランダムな場合 (つまり、ヒストグラムのカウントのすべてのビンが他のビンに近い場合)、この数値のバイナリ表現よりも効率的にエンコードすることはできません。
ヒストグラムのバランスが取れていない場合 (つまり、一部の値が他の値よりも多く存在する場合)、これらの値に対してより少ないビットを使用し、他の可能性が低い値に対してより多くのビットを使用するエンコーディングを選択することが理にかなっている場合があります。
たとえば、エンコードする必要がある数値が 15 ビットよりも小さい可能性が 2 倍高い場合、16 番目のビットを使用してそのことを伝え、16 ビットのみを保存/送信できます (ゼロの場合、次のバイト32 ビットの数値に収まる 16 ビットの数値を形成します)。1 の場合、次の 25 ビットは 32 ビットの数値を形成します。ここで 1 ビットを失いますが、その可能性は低いため、最終的に多くのビットを獲得すると、より多くのビットを獲得できます。
明らかに、これは些細なケースであり、これを 2 つ以上のケースに拡張したのが、出現する数値の確率に基づいて最適に近い「コード ワード」に影響を与えるハフマン アルゴリズムです。
これを行う算術符号化アルゴリズムもあります (おそらく他のアルゴリズムも)。
いずれの場合も、現在コンピューターのメモリで行われている方法よりも効率的にランダムな値を格納できるソリューションはありません。
その価値があるかどうかを知るには、最終的に得られる節約と比較して、そのようなソリューションの実装にどれくらいの時間と困難がかかるかを考える必要があります。言語自体はここでは関係ありません。
大きな値よりも小さな値の方が一般的である場合は、Golomb コーディングを使用できます。