c# - 整数の可変長エンコーディング

Question

C# で符号なし整数値の可変長エンコーディングを行う最良の方法は何ですか?

---

「実際の意図は、可変長でエンコードされた整数 (バイト) をファイル ヘッダーに追加することです。」

例: "Content-Length" - HTTP ヘッダー

これは、以下のロジックを変更することで実現できますか。

---

私はそれを行うコードをいくつか書きました....

Answer 1

私が使用した方法は、値が小さいほど使用するバイト数が少なくなり、7ビットのデータ+1ビットのオーバーヘッドprをエンコードすることです。バイト。

エンコーディングは、ゼロから始まる正の値に対してのみ機能しますが、必要に応じて、負の値を処理するように変更することもできます。

エンコーディングの仕組みは次のとおりです。

• 値の下位7ビットを取得し、それらを1バイトに格納します。これが、出力する内容です。
• 値を7ビット右にシフトし、取得した7ビットを削除します
• 値がゼロ以外の場合（つまり、値から7ビットシフトした後）、出力する前に、出力するバイトの上位ビットを設定します。
• バイトを出力する
• 値がゼロ以外の場合（つまり、上位ビットを設定したのと同じチェック）、戻って最初から手順を繰り返します。

デコードするには：

• ビット位置0から開始
• ファイルから1バイトを読み取る
• 上位ビットが設定されているかどうかを保存し、マスクします
• または、バイトの残りの部分を最終値に、現在のビット位置で
• 上位ビットが設定されている場合は、ビット位置を7増やし、最初のビットをスキップして手順を繰り返します（ビット位置をリセットしないでください）。

          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;
    }
}

Answer 2

まず、値のヒストグラムを作成する必要があります。分布がランダムな場合 (つまり、ヒストグラムのカウントのすべてのビンが他のビンに近い場合)、この数値のバイナリ表現よりも効率的にエンコードすることはできません。

ヒストグラムのバランスが取れていない場合 (つまり、一部の値が他の値よりも多く存在する場合)、これらの値に対してより少ないビットを使用し、他の可能性が低い値に対してより多くのビットを使用するエンコーディングを選択することが理にかなっている場合があります。

たとえば、エンコードする必要がある数値が 15 ビットよりも小さい可能性が 2 倍高い場合、16 番目のビットを使用してそのことを伝え、16 ビットのみを保存/送信できます (ゼロの場合、次のバイト32 ビットの数値に収まる 16 ビットの数値を形成します)。1 の場合、次の 25 ビットは 32 ビットの数値を形成します。ここで 1 ビットを失いますが、その可能性は低いため、最終的に多くのビットを獲得すると、より多くのビットを獲得できます。

明らかに、これは些細なケースであり、これを 2 つ以上のケースに拡張したのが、出現する数値の確率に基づいて最適に近い「コード ワード」に影響を与えるハフマン アルゴリズムです。

これを行う算術符号化アルゴリズムもあります (おそらく他のアルゴリズムも)。

いずれの場合も、現在コンピューターのメモリで行われている方法よりも効率的にランダムな値を格納できるソリューションはありません。

その価値があるかどうかを知るには、最終的に得られる節約と比較して、そのようなソリューションの実装にどれくらいの時間と困難がかかるかを考える必要があります。言語自体はここでは関係ありません。

Answer 3

大きな値よりも小さな値の方が一般的である場合は、Golomb コーディングを使用できます。

Answer 4

BinaryReader.Read7BitEncodedInt メソッド?

BinaryWriter.Write7BitEncodedInt メソッド?