language-agnostic - 压缩二进制矩阵

Question

我们被要求找到一种尽可能压缩正方形二进制矩阵的方法，并在可能的情况下增加冗余位以检查并纠正错误。

在我看来，冗余的事情很容易实现。复杂的部分是压缩矩阵。我考虑过将矩阵重整为向量后再使用游程，因为零比1多，但我只实现了40位压缩(我们正在研究小尺寸)，尽管我认为这样做会更好。

同样，经过游程后，一个想法是霍夫曼编码矩阵，但是必须发送字典才能恢复原始信息。

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

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

Answer 1

如果您具有分布和表示形式，则只能谈论压缩某些内容。这就是您必须发送的词典的问题:您始终需要某种协议(protocol)词典来解压缩某些内容。碰巧的是，像.zip和.mpeg这样的东西已经有了那些字典/编解码器。甚至像霍夫曼编码这样简单的事情也是一种算法。在通信 channel 的另一端(您可以将压缩视为通信)，另一个人已经有一些代码(字典)可以执行霍夫曼解压缩方案。

因此，您甚至必须先思考“我希望看到什么样的矩阵？”，“数据确实是随机的，还是有序的？”，以及如果是这样的话，“首先如何思考矩阵”就谈不上压缩。利用数据中的顺序？”。

您不能在不增加其他对象大小(至少增加1位)的情况下压缩某些矩阵。如果所有矩阵都是同等概率的，而您同样关心它们，那么这将是个坏消息。

附录:

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

Well, I know every matrix will have the same number of ones, so this is kind of deterministic. The only think I don't know is where the 1's will be. Also, if I transmit the matrix with a dictionary and there are burst errors, maybe the dictionary gets affected so... wouldnt be the resulting information corrupted? That's why I was trying to use lossless data compression such as run-length, the decoder just doesnt need a dictionary. --original poster

矩阵的大小只有几分之一，它的大小是多少( NxN-什么是 N)？

此外，这是一个错误的断言，不应用作需要游程长度编码的原因(仍然需要程序)。通过 channel 传输数据时，您始终可以向该数据添加纠错功能。 “数据”只是一小块。您可以通过 channel 传输数据和任何所需的字典。纠错机制根本不关心您传输的比特是什么。

附录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而不起作用。这将等效于游程长度编码。我们想做这样的事情，但是我们的预算非常严格，不能“浪费”一些零碎的东西。

因为您同样关心每种可能性，所以您的“字典”/“程序”将模拟一个巨大的查找表。 Matlab的稀疏矩阵实现可能有效，但不能保证一定有效，因此不是正确的解决方案。

如果您可以在数字范围 [0,2^128)和大小为20的子集之间创建双射，那很好。这对应于枚举将 http://en.wikipedia.org/wiki/Binomial_coefficient中的金字塔下降到行196的第20个元素的方式。这与 枚举所有“k组合”相同。参见 http://en.wikipedia.org/wiki/Combination#Enumerating_k-combinations

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

因此，我们进行了更多搜索，并遇到了一些神秘的Fortran代码，例如 http://people.sc.fsu.edu/~jburkardt/m_src/subset/ksub_rank.m和 http://people.sc.fsu.edu/~jburkardt/m_src/subset/ksub_unrank.m

我们可以对其进行逆向工程，但是它有点密集。但是现在我们有足够的信息来搜索 k-subset rank unrank，这将我们引至 http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf －请参阅本节
“生成(n个集合的)k个子集:词典
排序”以及接下来几页的 rank和 unrank算法。

为了获得精确的理论上最佳压缩，在均匀随机分布为1s的情况下，因此我们必须使用此技术将矩阵对分到我们输出的范围< 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