Cho*_*rop 7 optimization performance encoding bitmap bitvector
目前使用行程长度编码来编码位向量,当前运行时间是2log(i),其中是运行的大小.还有另一种方法可以将其归结为log(i)吗？谢谢.
编码位向量的最有效方法是隔离位源的任何特定属性.如果它是完全随机的,则没有明显的增益(实际上,完全随机的比特流不能以任何方式压缩).
如果您可以在比特流中找到属性,则可以尝试定义一组矢量,这些矢量将定义矢量空间的基础.在这种情况下,结果将非常有效.
我们需要您的比特流的更多细节.
(编辑)
还有一些细节可以理解前面的陈述:"完全随机的比特流不能以任何方式压缩"
如果通过"压缩"我们指的是"变换/压缩流" 加上 "矢量基定义" 加上解压缩程序,则不可能压缩完全随机的比特矢量.但在大多数情况下,解压缩程序(通常也是矢量库)都嵌入在客户端软件中.因此,仅需要"压缩流".
一个很好的解释(和有趣的故事)是Patrick Craig 5000 $压缩挑战
更科学的信息理论,特别是熵部分
而且,最后一个,全文.
但无论解决方案是什么,如果您有未知数量的未知流来压缩,您将无法做任何事情.你必须找到一个模式.