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

Question

Каков наилучший способ кодирования переменной длины беззнакового целочисленного значения в C#?

---

«Фактическое намерение заключается в добавлении целочисленного размера (байтов) переменной длины в заголовок файла».

Для бывших: "Content-Length" - Http Header

Может ли это быть достигнуто с некоторыми изменениями в следующей логике.

---

Я написал код, который делает это ....

Answer 1

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

Answer 2

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

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

Способ кодирования работает как это:

• Grab наименьшие 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-битного значения, дополнительный байт будет полностью использоваться, так что по-прежнему будет только один байт дополнительных накладных расходов.

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

Изменяется и их размер кодированного:

 
      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 

Вот 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"); 

     bool first = true; 
     while (first || value > 0) 
     { 
      first = false; 
      byte lower7bits = (byte)(value & 0x7f); 
      value >>= 7; 
      if (value > 0) 
       lower7bits |= 128; 
      writer.Write(lower7bits); 
     } 
    } 

    /// <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 3

BinaryReader.Read7BitEncodedInt Method?

BinaryWriter.Write7BitEncodedInt Method?

Answer 4

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

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

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

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

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

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

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