Самый эффективный способ кодировать 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

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

Answer 2

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

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

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

Answer 3

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

Биты 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 <32, поэтому нужно всего 5 бит <br> если n> 48, то вы знаете, что m <16, поэтому нужно только 4 бита <br> если n> 56, то вы знаете, что m <8, поэтому требуется только 3 бита <br> если n> 60, то вы знаете, что m <4, поэтому нужно только 2 бита <br> если n = 63, то вы знаете, что m <2, поэтому требуется только 1 бит </p>

Answer 4

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

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

Answer 5

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

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

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

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

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