打包数据，在 Python 中进行极端 Bitpacking

Question

我需要将信息尽可能紧密地打包到比特流中。

我的变量具有不同数量的不同状态：

Number_of_states=[3,5,129,15,6,2]# A bit longer in reality

目前我最好的选择是创建一个位域，使用

2+3+8+4+3+1位->21位

然而，应该可以将这些状态打包成 np.log2(3*5*129*15*6*2)=18.4 位，从而节省两位。（实际上我有298位需要保存一些）

在我的例子中，这将节省大约 >5% 的数据流，这会有很大帮助。

python有没有可行的方案可以这样打包数据？我试过 packalgorithms，但它们仅用几个字节的数据就产生了太多的开销。字符串没问题，是常量，会提前传

这是我目前使用的代码：

from bitstring import pack
import numpy as np

DATA_TO_BE_PACKED=np.zeros(6)

Number_of_states=[3,5,129,15,6,2]#mutch longer in reality

DATA_TO_BE_PACKED=np.random.randint(Number_of_states)

string=''

for item in Number_of_states:
    string+='uint:{}, '.format(int(np.ceil(np.log2(item))))

PACKED_DATA = pack(string,*DATA_TO_BE_PACKED)

print(len(PACKED_DATA ))

print(PACKED_DATA.unpack(string))

Answer 1

您可以将状态解释为形状为 (3, 5, 129, 15, 6, 2) 的多维数组的索引。该索引可以编码为长度为 3*5*129*15*6*2 = 348300 的扁平一维数组中的整数索引。 NumPy 具有函数 ravel_multi_index 和 unravel_index 可以为您完成此操作。

例如，设 num_states 为您所在州每个组成部分的州数：

In [86]: num_states = [3, 5, 129, 15, 6, 2]

假设state持有数据的一个实例；即记录了各个组件的状态：

In [87]: state = [2, 3, 78, 9, 0, 1]

要对该状态进行编码，请将其传递给 ravel_multi_index。 idx是编码状态：

In [88]: idx = np.ravel_multi_index(state, num_states)

In [89]: idx
Out[89]: 316009

通过构造，0 <= idx < 348300，所以它只需要 19 位。

要从 idx 恢复 state，请使用 unravel_index:

In [90]: np.unravel_index(idx, num_states)
Out[90]: (2, 3, 78, 9, 0, 1)

Answer 2

这看起来像是 mixed radix numeral system 的用例。

概念的快速证明：

num_states = [3, 5, 129, 15, 6, 2]
input_data = [2, 3, 78, 9, 0, 1]
print("Input data: %s" % input_data)

要编码，从 0 开始，每个状态先乘以状态数，然后加上当前状态：

encoded = 0
for i in range(len(num_states)):
    encoded *= num_states[i]
    encoded += input_data[i]

print("Encoded: %d" % encoded)

要解码，你要反过来，得到除以状态数的余数，然后除以状态数：

decoded_data = []
for n in reversed(num_states):
    v = encoded % n
    encoded = encoded // n
    decoded_data.insert(0, v)

print("Decoded data: %s" % decoded_data)

示例输出：

Input data: [2, 3, 78, 9, 0, 1]
Encoded: 316009
Decoded data: [2, 3, 78, 9, 0, 1]

另一个具有更多值的示例：

Input data: [2, 3, 78, 9, 0, 1, 84, 17, 4, 5, 30, 1]
Encoded: 14092575747751
Decoded data: [2L, 3L, 78L, 9L, 0L, 1L, 84L, 17L, 4L, 5L, 30L, 1L]

打包数据，在 Python 中进行极端 Bitpacking

Pack data, extreme Bitpacking in Python

python

compression

numpy

bitstring