Диапазон значений неподписанного qword (64-бит) с использованием меньших бит?

Question

Я ищу способ представления диапазона значений: 0 - 18446744073709551615 с использованием менее 8 байт.

Я попытался придумать, как это можно сделать, но ничего не работает. В теории, например: Использование одного байта для представления битовой последовательности не менее 2 байтов. Однако 2 байта имеют число 65536 различных комбинаций бит, тогда как один байт дает нам диапазон значений 0-255 (256 комбинаций).

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

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

Существует 2 правила: # 1 Не может быть прецизионных потерь (т. Е. Все числа 0 - 18446744073709551615 должны быть представлены). # 2 Преобразование из стандартной 64-битной формы не должно приводить к необходимости более 7 байтов (56 бит).

Эти правила делают это особенно сложным.

Answer 1

Эти правила делают это особенно сложным.

Да, трудно доказать, что это невозможно.

Если вы можете без потерь сжать 8 байтов до менее 8 байтов для каждые возможное значение 64b, вы можете продолжать повторять процесс до тех пор, пока ваш 1TB-файл не будет около 7 байтов.

Есть много других аргументов в теории информации, почему это невозможно. например принцип pigeonhole: n бит имеет только 2^n уникальных битовых шаблонов, поэтому все, что меньше 64 бит, не может иметь уникальных представлений для каждого возможного 64-битного значения.

---

То, что вы могли бы с пользой использовать это Huffman coding или похожи: не слишком сложной переменной длины схема кодирования может сохранить общее число байтов, если некоторые 64b значения являются более распространенными, чем другие. Но для всех значений 64b, которые должны быть представлены с использованием схемы кодирования с переменной длиной, кодировка для некоторых значений займет более 8 байтов.

Более современные методы энтропийного кодирования существуют и используются в современных видеокодеках. (например, CABAC x264).

---

Для получения дополнительной теории articls сжатия без потерь Википедии есть Limitations section.

Смотрите также:

• cstheory.SE: Which is the limit of lossless compression data? (if there exists such a limit)

• Kolmogorov complexity