Как хранить много маленьких целых чисел в байтовом массиве?

Question

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

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

Редактировать: да, плохой пример, позвольте мне изменить значения ...

Координата X (скажем, от -32 до 32). (65 различных возможных значений) Координата Y (от -32 до 32). (65 различных возможных значений) Координата Z (от -16 до 16). (33 различных возможных значения)

я знаю, что X был сохранен до Y, который был сохранен до Zв байтовом массиве перед отправкой.

Я знаю на сервере, что X не может быть ниже -31 или выше 32, то же самое для других значений.

65 * 65 * 33 =139,425 различных возможных комбинаций значений для 3 чисел = 17 битов.

7 + 7 + 5 = 19 битов.

, поэтому, если бы я хранил X в первых 7 битах, то Yв следующих 7 битах, а затем Z в следующих 5 битах это займет 19 бит, и яЯ мог бы легко прочитать их на другой стороне, но, поскольку все возможные комбинации значений, которые могут принять эти 3 числа, заняли бы только 17 бит, я чувствую, что теряю здесь место.Есть ли хороший способ сжать эти 3 числа, используя менее 19 бит?

Конечно, для 19 бит и 17 бит нужно 3 байта, но если бы это было 17 бит и 15 бит, это бы имело огромную разницу.

Answer 1

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

Для алгоритма кодирования: у вас есть 65 * 65 * 33 = 139,425 различных возможных значений.Log2 (139.425) ~ 17.09, поэтому вам потребуется как минимум 18 бит для кодирования любого из этих возможных значений.Простая схема кодирования будет такой же, как вы сказали:

Value = Z*65*65 + Y*65 + X

Затем для ее декодирования:

X = Value % 65
Y = (Value/65) % 65
Z = (Value/65/65) % 33

Теперь значение является целым числомЕсли вы хотите сохранить его в байтовом массиве, вы можете разбить это целое число на 3 байта:

Byte1 = Value & 255;
Byte2 = (Value>>8) & 255;
Byte3 = (Value>>16) & 255;

Answer 2

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

Answer 3

Вы можете взглянуть на gelasia-compacter .

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

Answer 4

Сжатие переменной целого числа используется в буферах протокола Google. Он называется varint и довольно прост.

http://code.google.com/apis/protocolbuffers/docs/encoding.html#varints

Answer 5

Я нашел этот вариант BitSet, который использует сжатие, вы должны взглянуть на него. Автор утверждает, что алгоритм оптимизирован по скорости запросов, а не по пространству, но всегда эффективнее по сравнению с классом Java BitSet. Я думаю, что если вы отправляете большой объем координат по проводу, вы можете увидеть улучшение по сравнению с простой сериализацией битов в BitSet, а затем преобразовать в байт [].