有序整数列表的压缩

Question

我正在读这本书《信息检索导论》，我有一些实际的疑问。书中有一个章节专门讨论索引（字典和倒排列表）的压缩。对于发布列表，对文档列表进行了解释。

示例：术语“书”有一个发布列表，例如“1 4 7 19 20 25”，这意味着它包含在此文档 ids 中。

在这种情况下，id 之间的间隙计算为“1 3 3 12 1 5”，因此通过线性扫描，我们可以通过对前一个文档求和来检索每个文档。

然后解释说，在大多数情况下，两个 DocID 之间的差距很小，并且可以使用第二个，例如（可变字节代码或伽玛编码）。

通过伽玛编码我们得到：

1 -> 0
3 -> 101
3 -> 101
12 -> (binary 1100) -> (length(100) = 3) -> (unary(3) 1110) -> unary + length = 1110100 这是 12 的 gamma
1 -> 0
5 -> 110101

所以我用 gamme 编码对“1 3 3 12 1 5”进行压缩的结果是“010110111101000110101”

我的疑问是如何在实践中实现这种压缩？我实际上不了解如何存储这些数据以降低空间复杂度。因为现在我使用 pickle 来存储从 txt 文件加载的字典，而没有获得有序整数列表的好处。

def pickle_data(path: str, posting_list):
    out = open(path, 'wb')
    pickle.dump(posting_list, out)
    out.close()

有人可以解释如何使用（至多）小整数的有序整数的这种好处？

Answer 1

您的

010110111101000110101

是一个位序列。您尚未显示任何有关

str

是如何生成的或它是什么的代码。如果您将其存储为

和

字符的字符串，那么您就不必要地将二进制序列的长度扩展了八倍，从而无法实现您所寻求的压缩。

您需要将这些位打包成一系列字节，每个字节八位，以实现压缩。您还需要一种终止序列的方法，即知道它何时结束。如果没有这个，您最终可能会从仅部分填充位的最后一个字节中得到无关的输出。