可变长度整数编码

Question

在我的Python应用程序中，我想找到一种在文件中对无符号整数序列进行空间高效编码的方法，小整数非常常见，而大整数相对不常见。我知道我需要的是某种形式的variable-length quantity encoding（VLQ）

我有一个（可能有缺陷和/或可能是特定于CPython的）内存来读取Python在内部使用VLQ策略来表示int的某个地方。这些编码/解码例程是否可以从Python访问？和/或在Python中是否有另一种快速执行VLQ的方法

我调查过的可能性：

• 我在struct模块文档中没有看到任何相关内容
• 我没有从python VLQ或python "group varint"的网络搜索中得到任何有意义的点击
• 我可以用纯Python实现我自己的实现，但我觉得这速度太慢了，因为肯定有更快的现成解决方案，或者已经潜伏在Python或其标准库中了
• 我试图滥用内置UTF-8编码器和解码器（这至少可以使我的整数达到1114111，这对我的应用程序来说是一个好的开始），说encode = lambda n: chr(n).encode('utf-8')和decode = lambda x: ord(x.decode('utf-8'))，但不幸的是encode(n)在55296 <= n <= 57343时引发了一个带有消息“代理不允许”的UnicodeEncodeError

更新：@don'ttalkjustcode正确地将pickle模块标识为Python标准库执行类似于这样的操作的地方，特别是在pickle.encode_long()和pickle.decode_long()中。它们是纯Python实现，在Python 2.7中，它们围绕一个名为pickle._binascii的二进制子模块，但在Python 3.2+中，工作似乎是通过int类的内置方法完成的，从而导致：

encode = lambda n: n.to_bytes(n.bit_length()//8 + 1, 'little', signed=False)

decode = lambda x: int.from_bytes(x, 'little', signed=False)

然而，我猜这些是不完整的（或者，对于小整数，效率低下）可变长度编码，因为您需要花费另一个字节来单独编码编码的长度

我真正需要的是类似LEB128编码的东西，对于它pure-Python solutions exist，但是现在我看到了int.to_bytes()和int.from_bytes()，我猜Python并不是本机实现的

Answer 1

是的，pickle做了类似的事情。在我看来，这很体面。例如，一百万个随机大小为1到16字节的随机整数被编码到~10.75 MB。然后lzma.compress将其降低到~10MB。与8.5MB的“原始数据大小”（100万个整数平均每个8.5字节）相比，情况还不错。LEB128还占用约10 MB的空间，非常小

import os, random, pickle, lzma, leb128

n = 10 ** 6
a = [int.from_bytes(os.urandom(random.randint(1, 16)), 'big') for _ in range(n)]
p = pickle.dumps(a)
print("pickle'd:", f'{len(p):,}', type(p))
z = lzma.compress(p)
print("+ lzma'd:", f'{len(z):,}', type(z))
leb = b''.join(map(leb128.u.encode, a))
print("leb128'd:", f'{len(leb):,}', type(leb))

输出：

pickle'd: 10,751,961 <class 'bytes'>
+ lzma'd: 10,060,252 <class 'bytes'>
leb128'd: 10,016,053 <class 'bytes'>

Try it online!