压缩二进制矩阵

Question

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

在我看来,冗余的东西很容易实现.复杂的部分是压缩矩阵.我想在将矩阵重新整形为矢量后使用游程长度,因为会有更多的零,但是我只实现了40位压缩(我们正在处理小尺寸),尽管我认为它会更好.

此外,在游程后,一个想法是霍夫曼编码矩阵,但必须发送字典以恢复原始信息.

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

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

Answer 1

如果您有分发和表示,您只能谈论压缩某些内容.这就是你必须发送的字典的问题:你总是需要某种协议字典来解压缩一些东西.事情就是这样,.zip并且.mpeg已经拥有那些字典/编解码器.甚至像霍夫曼编码一样简单的算法也是算法; 在通信信道的另一端(您可以将压缩视为通信),另一个人已经有一些代码(字典)来执行霍夫曼解压缩方案.

因此,你甚至不能开始谈论压缩某些东西而不首先想到"我期望看到什么样的矩阵？","数据真的是随机的,还是有秩序的？",如果是这样的话"我怎么能代表矩阵利用数据中的顺序？"

您不能在不增加其他对象大小的情况下压缩某些矩阵(至少1位).如果所有矩阵都是同等可能的话,这是个坏消息,而且你同样关心它们.

附加物:

使用稀疏矩阵机制的答案不一定是正确的答案.例如,矩阵可以用python表示为[[(r+c)%2 for c in range (cols)] for r in range(rows)](棋盘图案),稀疏矩阵根本不会压缩它,但矩阵的Kolmogorov复杂度是上述程序的长度.

好吧,我知道每个矩阵都有相同数量的矩阵,所以这是确定性的.唯一的想法我不知道是1的位置.此外,如果我使用字典传输矩阵并且存在突发错误,那么字典可能会受到影响所以...不会导致结果信息损坏？这就是我尝试使用无损数据压缩(如游程长度)的原因,解码器只是不需要字典. - 原始海报

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

此外,这是一个不正确的断言,不应该用作期望行程长度编码的理由(它仍然需要一个程序); 当您通过通道传输数据时,您始终可以为此数据添加错误更正."数据"只是一点点.您可以通过频道传输数据和任何所需的词典.纠错机器根本不关心你传输的是什么.

附录2:

有(14*14) choose 20可能的安排,我认为是随机选择的.如果这个数字大于128^2你想要做的那个数字是不可能的.幸运的是log_2((14*14) choose 20) ~= 90bits < 128bits,这是可能的.

写下20个数字的简单解决方案32,2,67,175,52,...,168将无效,因为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 - 请参阅"生成k子集( n-set):Lexicographical Ordering"以及接下来几页的算法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