压缩二进制矩阵

Question

我们被要求找到一种方法来尽可能地压缩方形二进制矩阵，如果可能的话，添加冗余比特来检查并可能纠正错误。

在我看来，冗余的事情很容易实现。复杂的部分是压缩矩阵。

此外，在游程长度之后，一个想法是霍夫曼对矩阵进行编码，但为了恢复原始信息，必须发送字典。

我想知道压缩二进制矩阵的最好方法是什么？

在阅读了一些评论后，yes @Adam你是对的，14x14矩阵应该被压缩为128位，所以如果我只使用每个非零元素的坐标(行和列)，它仍然是160位(因为有20位)。我不是在寻找一个确切的解决方案，而是在寻找一个有用的想法。

Answer 1

只有当你有分布和表示时，你才能谈论压缩一些东西。这就是你必须发送的字典的问题:你总是需要某种协议字典来解压缩一些东西。碰巧像.zip和.mpeg这样的东西已经有了这些字典/编解码器。即使像Huffman编码这样简单的东西也是一种算法；在通信通道的另一端(您可以将压缩视为通信)，另一个人已经有了一些代码(字典)来执行Huffman解压缩方案。

因此，如果不考虑“我希望看到什么类型的矩阵？”、“数据是否真的是随机的，还是有顺序的？”，如果是这样，“我如何表示矩阵以利用数据中的顺序？”，您甚至不能开始谈论压缩某些东西。

如果所有矩阵都是等概率的，并且你对所有矩阵都同样关心，那么这是个坏消息。

附录：

使用稀疏矩阵机器的答案不一定是正确的答案。例如，在Python语言中，矩阵可以表示为[[(r+c)%2 for c in range (cols)] for r in range(rows)] (棋盘模式)，稀疏矩阵根本不会对其进行压缩，但是矩阵的Kolmogorov复杂度就是上面程序的长度。

我知道每个矩阵都会有相同数量的1，所以这是确定性的。，

。我唯一不知道的是1会在哪里。此外，如果我将矩阵与字典一起传输，并且存在突发错误，则字典可能会受到影响，因此...结果信息不会被破坏吗？这就是为什么我尝试使用无损数据压缩，比如游程长度，解码器不需要字典。--原创海报

矩阵有多少个1作为其大小的一部分，它的大小是多少(NxN --什么是N)？

此外，这是一个不正确的断言，不应该被用作需要运行长度编码(这仍然需要程序)的理由；当您通过通道传输数据时，您总是可以对此数据添加纠错。"Data“只是一大堆比特。您可以通过通道传输数据和任何所需的字典。纠错机器根本不关心你传输的比特是做什么用的。

附录2:

有(14*14) choose 20可能的安排，我假设这些安排是随机选择的。如果这个数字大于128^2，那么您想要做的事情将是不可能的。幸运的是log_2((14*14) choose 20) ~= 90bits < 128bits，所以这是可能的。

像32,2,67,175,52,...,168这样写下20个数字的简单解决方案不会起作用，因为log_2(14*14)*20 ~= 153bits > 128bits。这等同于游程编码。

这与枚举所有的“k组合”是一样的。请参阅http://en.wikipedia.org/wiki/Combination#Enumerating_k-combinations

幸运的是，我知道Mathematica、Sage和其他CAS软件显然可以生成“第5个”或“第12个”或任意编号的k-子集。查看他们的文档，我们发现了一个名为“排名”的函数，例如http://www.sagemath.org/doc/reference/sage/combinat/subset.html

我们可以对其进行反向工程，但它的密度很高。但是现在我们有了足够的信息来搜索k-subset rank unrank，这将我们引向http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf --参见“生成(n-集合的)k-子集:字典序”一节，以及接下来的几页上的rank和unrank算法。

为了实现精确的理论上最优压缩，在1的均匀随机分布的情况下，我们因此必须使用此技术将我们的矩阵双向映射到范围<2^128的输出数。恰好组合有一个自然的顺序，称为组合的排序和未排序。你给每个组合分配一个数字(排名)，如果你知道数字，你就会自动知道组合(未排名)。在谷歌上搜索k-subset rank unrank可能会产生其他算法。

因此，您的解决方案将如下所示：

serialize the matrix into a list
    e.g. [[0,0,1][0,1,1][1,0,0]] -> [0,0,1,0,1,1,1,0,0]
take the indices of the 1s:
    e.g. [0,0,1,0,1,1,1,0,0] -> [3,5,6,7]
          1 2 3 4 5 6 7 8 9      a k=4-subset of an n=9 set
take the rank
    e.g. compressed = rank([3,5,6,7], n=9)
         compressed==412 (or something, I made that up)
you're done!
    e.g. 412 -binary-> 110011100 (at most n=9bits, less than 2^n=2^9=512)
to uncompress, unrank it

Answer 2

我将在一秒钟内达到128位，首先是如何将一个14x14布尔矩阵拟合成136位，该矩阵恰好有20个非零。它基于CSC稀疏矩阵格式。

您有一个具有14个4位计数器的数组c，这些计数器告诉您每列中有多少个非零。您有另一个具有20个4位行索引的数组r。

56位(c) + 80位(r) = 136位。

让我们从c中挤出8位:使用2位而不是4位计数器。c现在是2*14 = 28位，但每列不能支持超过3个非零。这给我们留下了128-80-28 = 20位。将该空间用于具有5个4位元素的数组a4c，这些元素由4位元素指定，“将4加到c的元素上”。所以，如果是a4c={2,2,10,15, 15}，就意味着c[2] += 4; c[2] += 4 (again); c[10] += 4;。

非零的“最浪费”分布是列计数需要一个加数-4才能支持1个额外的非零:即5列，每列有4个非零。幸运的是，我们正好有5个add-4可用。

总空间= 28位(c) + 20位(a4c) + 80位(r) = 128位。

Answer 3

您的输入是稀疏矩阵的最佳候选者。您说您正在使用Matlab，所以您已经为您构建了一个很好的稀疏矩阵。

spm = sparse(dense_matrix)

Matlab的稀疏矩阵实现使用了压缩的稀疏列，它的内存使用量约为2*(# of nonzeros) + (# of columns)，对于20个非零和14列的情况来说，这应该是非常好的。存储20个值肯定比存储196个值要好…

还要记住，Matlab中的所有矩阵都将由双精度组成。仅仅因为您的矩阵可以存储为1位布尔值，并不意味着Matlab不会将其转换为64位浮点值……如果你确实需要它作为一个布尔值，你将不得不在C中创建你自己的类型，并使用.mex文件来与Matlab接口。