performance - 编码位向量的有效方法？

Question

当前使用运行长度编码对位向量进行编码，当前运行时间为 2log(i)，其中是运行的大小。是否有另一种方法可以将其降低到 log(i)？谢谢。

Answer 1

编码位向量的最有效方法是隔离位源的任何特定属性。如果它是完全随机的，则没有真正明显的增益（实际上，完全随机的比特流不能以任何方式压缩）。

如果您可以在比特流中找到属性，您可以尝试定义一组向量，这些向量将定义向量空间的基础。在这种情况下，结果将非常有效。

我们需要有关您的比特流的更多详细信息。

---

（编辑）

只需再了解一些细节即可理解前面的陈述：“不能以任何方式压缩完全随机的比特流”

如果“压缩”是指“转换/压缩流”加上“向量基定义”加上解压缩程序，则不可能压缩完全随机的位向量。但在大多数情况下，解压缩程序（通常也是矢量库）嵌入在客户端软件中。因此，只需要“压缩流”。

一个很好的解释（和有趣的故事）是Patrick Craig 5000$ 压缩挑战

更科学的信息论，尤其是熵部分

而且，最后一个，完整的故事。

但无论解决方案是什么，如果您有未知数量的未知流要压缩，您将无能为力。你必须找到一个模式。