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

Question

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

Скажем, что фактические данные имеют длину 1 бит и дополняются n 0s спереди и m 0s в конце, так что n + l + m = 64. Вместо передачи/хранения 64 бит я могу передавать l бит плюс все Мне нужно кодировать положение данных в 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 битов для п
отправить до 6 битов для м (смотри ниже)
высчитывает л = 64 - (п + т)
, если л = 0, то число равно 0, не отправлять все остальное
Если l = 1, номер 1 * 2^m, ничего не посылайте
, если l = 2, номер 3 * 2^m, ничего не посылайте
отправьте средний l - 2 бит.

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

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 бит, является оптимальным (в предположении равных распределений всех возможных значений).