Пространственное эффективное длинное представление

Question

Я хочу взять длинное значение в Java и преобразовать его в байтовый массив.

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

Алгоритмы кодирования и декодирования должны быть чрезвычайно эффективными.

Я уверен, что это было сделано, но я не могу найти пример кода, у кого-нибудь есть указатели?

Answer 1

Вы можете использовать кодирование стоп-битов, например,

public static void writeLong(OutputStream out, long value) throws IOException {
   while(value < 0 || value > 127) {
        out.write((byte) (0x80 | (value & 0x7F)));
        value = value >>> 7;
   }
   out.write((byte) value);
}

public static long readLong(InputStream in) throws IOException {
   int shift = 0;
   long b;
   long value = 0;
   while((b = in.read()) >= 0) {
      value += (b & 0x7f) << shift;
      shift += 7;
      if ((b & 0x80) == 0) return value;
   }
   throw new EOFException();
}

Это быстрая форма сжатия, но все сжатие обходится дорого.(Однако, если у вас ограниченная пропускная способность, передача может быть быстрее и стоит затрат)

Кстати: значения от 0 до 127 используют один byte.Вы также можете использовать ту же процедуру для значений short и int.

РЕДАКТИРОВАТЬ: После этого вы можете использовать универсальное сжатие, и оно может быть меньше, чем без него.

public static void main(String... args) throws IOException {
    long[] sequence = new long[1024];
    Random rand = new Random(1);
    for (int i = 0; i < sequence.length; i+=2) {
        sequence[i] = (long) Math.pow(2, rand.nextDouble() * rand.nextDouble() * 61);
        // some pattern.
        sequence[i+1] = sequence[i] / 2;
    }
    testDeflator(sequence);
    testStopBit(sequence);
    testStopBitDeflator(sequence);
}

private static void testDeflator(long[] sequence) throws IOException {
    ByteArrayOutputStream baos = new ByteArrayOutputStream();
    DataOutputStream dos = new DataOutputStream(new DeflaterOutputStream(baos));
    for (long l : sequence)
        dos.writeLong(l);
    dos.close();
    System.out.println("Deflator used " + baos.toByteArray().length);
}


private static void testStopBit(long[] sequence) throws IOException {
    ByteArrayOutputStream baos = new ByteArrayOutputStream();
    for (long l : sequence)
        writeLong(baos, l);
    baos.close();
    System.out.println("Stop bit used " + baos.toByteArray().length);
}

private static void testStopBitDeflator(long[] sequence) throws IOException {
    ByteArrayOutputStream baos = new ByteArrayOutputStream();
    DataOutputStream dos = new DataOutputStream(new DeflaterOutputStream(baos));
    for (long l : sequence)
        writeLong(dos, l);
    dos.close();
    System.out.println("Stop bit & Deflator used " + baos.toByteArray().length);
}

public static void writeLong(OutputStream out, long value) throws IOException {
    while (value < 0 || value > 127) {
        out.write((byte) (0x80 | (value & 0x7F)));
        value = value >>> 7;
    }
    out.write((byte) value);
}

Отпечатки

Deflator used 3492
Stop bit used 2724
Stop bit & Deflator used 2615

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

Дефлятор - это урезанная версия вывода GZip (за исключением заголовка и CRC32)

Answer 2

Просто используйте GZipOutputStream - энтропийное кодирование, например, GZip в основном делает то, что вы описываете, просто в общем.

Edit: Просто чтобы быть уверенным: понимаете ли вы, что для кодирования переменной длины, который использует только 1 байт для небольших чисел, обязательно нужно использовать более 8 байтов для большинства больших? Если вы не знаете, что у вас будет намного больше маленьких, чем больших чисел, это может даже привести к увеличению общего размера ваших данных. Принимая во внимание, что GZIP адаптируется к вашему фактическому набору данных и может сжимать наборы данных, которые искажены по-разному.

Answer 3

См. Read7BitEncodedInt в C #. (Это та же концепция.)

Answer 4

(я мог бы констатировать очевидное для некоторых людей ... но здесь.)

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

Однако, если вы пытаетесь сохранить память в Java-программе, вы, вероятно, тратите время впустую.Наименьшее представление byte[] в Java - это 2 или 3 32-битных слова.И это для байтового массива нулевой длины.Добавьте несколько кратных 32-битных слов для любой длины массива больше нуля.Затем вы должны разрешить хотя бы 1 32-битное слово для хранения ссылки на объект byte[].

Если вы добавите это, потребуется не менее 4 слов, чтобы представить любой данный long, отличный от 0L, как byte[].

Единственный случай, когда вы собираетесьполучить любое сохранение, если вы представляете количество long значений в одном byte[].Вам понадобится как минимум 3 long значений, прежде чем вы сможете достичь безубыточности, и даже тогда, если вы потеряете, если значения окажутся слишком большими в среднем.

Answer 5

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

Если вы ищете быструю библиотеку для хранения длинных значений (по 64 бит), я бы порекомендовал colt .Это это быстро.