Самый эффективный способ кодировать 2 позиции от 0 до 64?

Question

У меня есть 64-битные значения, которые я хочу сжать, используя тот факт, что только часть где-то посередине содержит данные, а до и после этого - нули.

Скажем, фактические данные имеют длину 1 бит и дополняются n 0 с фронта и m 0 с конца, так что n + l + m = 64. Вместо передачи / сохранения 64 бит, я могу передать 1 бит плюс все, что я необходимо кодировать положение данных в 64-битном интервале.

Например, скажем, я хранил l, m и биты данных, затем я восстановил бы исходный 64-битный шаблон, прочитав l, прочитав l бит данных, прочитав m и сдвинув m бит данных влево.

Наименьшие накладные расходы, которые я могу придумать, - это два раза по 6 бит для хранения двух из l, n и m (каждый может быть между 0 и 64). Можно ли уменьшить это число?

Answer 1

l может быть от 0 до 64, поэтому не отправляйте l, отправляйте n и m, так как они могут быть равны нулю и не должны идти до 64 (им просто нужно иметь возможность добавлять в 64).

Биты l должны начинаться и заканчиваться на 1, поэтому их не нужно передавать.

отправить 6 бит для n
отправить до 6 бит для m (см. ниже)
вычислить l = 64 - (n + m)
если l = 0, число равно 0, больше ничего не отправлять
если l = 1, число равно 1 * 2 ^ m, больше ничего не отправляйте
если l = 2, число равно 3 * 2 ^ m, больше ничего не отправляйте
Послать середину l - 2 бита.

Максимальные издержки = 10 бит.

Сокращение битов для m связано с тем, что
если n > 32 тогда ты знаешь m & Lt; 32, поэтому нужно всего 5 бит
если n > 48 тогда ты знаешь m & Lt; 16, так что нужно всего 4 бита
если n > 56 тогда ты знаешь m & Lt; 8, так что нужно всего 3 бита
если n > 60 тогда ты знаешь м & Lt; 4, поэтому нужно всего 2 бита
если n = 63, то вы знаете, что m < 2, поэтому требуется только 1 бит

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

Есть 64 возможные начальные позиции n последовательности единиц, и длина последовательности l не может быть больше, чем 64 - n. Так что есть

r = sum(n = 0..63, 64 - n) + 1

Всего

последовательностей. Добавлен один для последовательности всех нулей. Выполнение некоторой математики приводит к следующему.

r = 64 * 64 - (63 * 64) / 2 + 1
  = 2081

Для представления 2081 возможных значений требуется log2(2081) = 11.023 бит. Поэтому ваше предложение кодировать информацию с использованием двух 6 битовых чисел, для которых требуется 12 бит, является оптимальным (при условии равного распределения всех возможных значений).