Кодирование переменной длины целого числа

Метод, который я использовал, который заставляет меньшие значения использовать меньше байтов, заключается в кодировании 7 бит данных + 1 бит служебных данных pr. байт.

Кодировка работает только для положительных значений, начинающихся с нуля, но при необходимости может быть изменена для обработки и отрицательных значений.

Кодировка работает следующим образом:

• Возьмите младшие 7 бит вашего значения и сохраните их в байте, это то, что вы собираетесь вывести
• Сдвиньте значение на 7 бит вправо, избавившись от тех 7 бит, которые вы только что захватили
• Если значение не равно нулю (т. е. после того, как вы отошли от него на 7 бит), установите старший бит байта, который вы собираетесь выводить, до его вывода.
• Вывести байт
• Если значение не равно нулю (т. е. такая же проверка, которая привела к установке старшего бита), вернитесь назад и повторите шаги с самого начала.

Чтобы расшифровать:

• Начать с битовой позиции 0
• Прочитать один байт из файла
• Сохраните, установлен ли старший бит, и замаскируйте его
• ИЛИ в оставшейся части байта в ваше окончательное значение, в битовой позиции, в которой вы находитесь
• Если был установлен старший бит, увеличьте битовую позицию на 7 и повторите шаги, пропустив первый (не сбрасывайте битовую позицию)

          39    32 31    24 23    16 15     8 7      0
value:            |DDDDDDDD|CCCCCCCC|BBBBBBBB|AAAAAAAA|
encoded: |0000DDDD|xDDDDCCC|xCCCCCBB|xBBBBBBA|xAAAAAAA| (note, stored in reverse order)

Как видите, закодированное значение может занимать один дополнительный байт, который используется только наполовину из-за накладных расходов на управляющие биты. Если вы расширите это до 64-битного значения, дополнительный байт будет использован полностью, поэтому останется только один байт дополнительных служебных данных.

Примечание. Поскольку кодировка сохраняет значения по одному байту за раз, всегда в одном и том же порядке, системы с прямым или прямым порядком байтов не изменят макет этого. Младший байт всегда сохраняется первым и т. д.

Диапазоны и их закодированный размер:

          0 -         127 : 1 byte
        128 -      16.383 : 2 bytes
     16.384 -   2.097.151 : 3 bytes
  2.097.152 - 268.435.455 : 4 bytes
268.435.456 -   max-int32 : 5 bytes

Вот реализации С# для обоих:

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

Если маленькие значения встречаются чаще, чем большие, вы можете использовать кодирование Голомба.

Вы должны сначала сделать гистограмму вашего значения. Если распределение является случайным (то есть каждая ячейка вашей гистограммы близка к другой), то вы не сможете кодировать более эффективно, чем двоичное представление для этого числа.

Если ваша гистограмма несбалансирована (то есть, если одни значения присутствуют больше, чем другие), то может иметь смысл выбрать кодировку, которая использует меньше битов для этих значений, но использует больше битов для других маловероятных значений.

Например, если число, которое вам нужно закодировать, с вероятностью в 2 раза меньше 15 бит, чем больше, вы можете использовать 16-й бит, чтобы указать это, и сохранить/отправить только 16 бит (если это ноль, то следующий байт сформирует 16-битное число, которое может поместиться в 32-битное число). Если это 1, то следующие 25 битов сформируют 32-битные числа. Здесь вы теряете один бит, но маловероятно, что в конце концов при большом количестве вы выиграете больше битов.

Очевидно, что это тривиальный случай, и расширение этого более чем на 2 случая представляет собой алгоритм Хаффмана, который воздействует на «кодовое слово», которое близко к оптимальному на основе вероятности появления чисел. .

Есть также алгоритм арифметического кодирования, который делает то же самое (и, возможно, другое).

Во всех случаях нет решения, которое могло бы хранить случайные значения более эффективно, чем то, что делается в настоящее время в памяти компьютера.

Вы должны подумать о том, насколько долгой и сложной будет реализация такого решения по сравнению с экономией, которую вы получите в итоге, чтобы понять, стоит ли оно того. Сам язык здесь не при чем.

Я знаю, что этот вопрос задавали несколько лет назад, однако для разработчиков MIDI я решил поделиться кодом из личного проекта midi, над которым я работаю. Блок кода основан на отрывке из книги «Максимум MIDI» Пола Мессика (этот пример является измененной версией для моих собственных нужд, однако вся концепция там...).

    public struct VariableLength
    {
        // Variable Length byte array to int
        public VariableLength(byte[] bytes)
        {
            int index = 0;
            int value = 0;
            byte b;
            do
            {
                value = (value << 7) | ((b = bytes[index]) & 0x7F);
                index++;
            } while ((b & 0x80) != 0);

            Length = index;
            Value = value;
            Bytes = new byte[Length];
            Array.Copy(bytes, 0, Bytes, 0, Length);
        }

        // Variable Length int to byte array
        public VariableLength(int value)
        {
            Value = value;
            byte[] bytes = new byte[4];
            int index = 0;
            int buffer = value & 0x7F;

            while ((value >>= 7) > 0)
            {
                buffer <<= 8;
                buffer |= 0x80;
                buffer += (value & 0x7F);
            }
            while (true)
            {
                bytes[index] = (byte)buffer;
                index++;
                if ((buffer & 0x80) > 0)
                    buffer >>= 8;
                else
                    break;
            }

            Length = index;
            Bytes = new byte[index];
            Array.Copy(bytes, 0, Bytes, 0, Length);
        }

        // Number of bytes used to store the variable length value
        public int Length { get; private set; }
        // Variable Length Value
        public int Value { get; private set; }
        // Bytes representing the integer value
        public byte[] Bytes { get; private set; }
    }

Как использовать:

public void Example()
{   
//Convert an integer into a variable length byte
int varLenVal = 480;     
VariableLength v = new VariableLength(varLenVal);
byte[] bytes = v.Bytes;

//Convert a variable length byte array into an integer
byte[] varLenByte = new byte[2]{131, 96};     
VariableLength v = new VariableLength(varLenByte);
int result = v.Length;
}

Метод BinaryReader.Read7BitEncodedInt< /а> ?

Метод BinaryWriter.Write7BitEncodedInt ?

Как указал Гримбли, существуют BinaryReader.Read7BitEncodedInt и BinaryWriter.Write7BitEncodedInt. Однако это внутренние методы, которые нельзя вызывать из объекта BinaryReader или -Writer.

Однако вы можете взять внутреннюю реализацию и скопировать ее из читатель и автора:

public static int Read7BitEncodedInt(this BinaryReader br) {
    // Read out an Int32 7 bits at a time.  The high bit 
    // of the byte when on means to continue reading more bytes.
    int count = 0;
    int shift = 0;
    byte b;
    do {
        // Check for a corrupted stream.  Read a max of 5 bytes.
        // In a future version, add a DataFormatException.
        if (shift == 5 * 7)  // 5 bytes max per Int32, shift += 7
            throw new FormatException("Format_Bad7BitInt32");

        // ReadByte handles end of stream cases for us. 
        b = br.ReadByte();
        count |= (b & 0x7F) << shift;
        shift += 7;
    } while ((b & 0x80) != 0); 
    return count;
}   

public static void Write7BitEncodedInt(this BinaryWriter br, int value) {
    // Write out an int 7 bits at a time.  The high bit of the byte,
    // when on, tells reader to continue reading more bytes.
    uint v = (uint)value;   // support negative numbers
    while (v >= 0x80) {
        br.Write((byte)(v | 0x80));
        v >>= 7;
    }
    br.Write((byte)v);
}   

Когда вы включите этот код в любой класс вашего проекта, вы сможете использовать методы для любого объекта BinaryReader/BinaryWriter. Они были лишь слегка изменены, чтобы заставить их работать вне своих исходных классов (например, путем изменения ReadByte() на br.ReadByte()). Комментарии взяты из первоисточника.