稀疏矩阵的最小表示

Question

我有一个大的二进制稀疏矩阵(任何单元格都可以保存0或1作为值).我不时想拍摄整个矩阵的快照. 快照必须尽可能小.

矩阵表示2d地图和发生在区域中的事件,因此它更像是看起来像示例A的快照而不是看起来像示例B的快照(它们都具有相同数量的"1"),尽管我需要支持算法中的两个示例.

Example A:
000000000000
000000011000
001100111100
001111111100
000000111100
000001111100
000000000000

Example B:
010010010010
001000001000
010010100100
000100101010
001000010010
010010001100
001000010000

由于数据可以从单个"1"单元格到100%单元格变为"1"(在非常非常后的情况下)我认为我需要使用多个算法 - 并且当加载数据以加载它时存储它的算法相同.

例如,当只有一个单元格时,我只存储它的索引(和"索引"算法的标识符),当99%的矩阵为"1"时,我将它存储为位图(和"位图"算法的标识符) ).

所以我得到一个像这样的通用算法:

1. 对于每个表示算法 - 代表矩阵
2. 选择最小的表示
3. 使用最小的表示存储数据

我的问题

1. 我可以使用哪些算法 - 除了存储索引/位图？
2. 处理这个问题有很好的依据吗？
3. 我怎样才能证明我的解决方案是最小的？

底线: 如何以最小的方式存储位图矩阵？

编辑 用例:我有一个稀疏矩阵,我需要通过一个非常低的带宽介质传输.因此,假设介质两侧的计算能力很强,发送矩阵应包含尽可能少的位.

Answer 1

数据压缩是一个很大的领域(你可以从这里开始),并且你的问题没有明确的答案.如果我们知道如何以最佳速率压缩数据,那么每年都不会有新的压缩算法;)

话虽这么说,你建议的是一个好主意:从集合中选择最佳算法并在标题中识别它.实际上,大多数压缩格式都使用这种方案.

回答你的问题:

什么算法:

• 使用现有格式:PNG,GIF或7zip会浮现在脑海中.
• 没有压缩:显然是位图,但为了确保我们说的是同一个东西,你需要为每个元素编码1位(而不是1个字节).大多数语言都不容易获得位访问(大多数bool/ boolean类型存储在一个完整的字节中).您必须使用按位运算,专用语言功能(如bitfields/ bitsets或库).例如C++,std::vector<bool>实现一个真正的位图(一个简单的bool[]没有).
• 熵编码:使用比不太可能的存储更少的存储来编码大多数可能的配置的想法.
  • 稀疏存储,你所谓的索引,但与你暗示的相反,当有很多的时候它很有用,但也有很多零(只是否定结果!).只有一个0或只有一个1是对称的情况应该以相同的方式处理.备用存储的最坏情况是使用零作为零.
  • 块编码,意味着1111如果您知道它是一种可能的模式,您可以存储少于4位.但这意味着将使用超过4位存储另一个(不太可能)的4位模式,因此在选择模式时要小心.有很多方法可以做到这一点:固定大小或可变大小的单词,编码可以是静态的,也可以是数据相关的.一些例子是:RLE,Huffman,LZ变体(在你最喜欢的压缩程序中使用的基于字典的算法)
  • 算术编码基于相同的想法,即基于其概率调整每个符号/块的存储空间,但是它在一次通过中对整个数据进行编码,而不是将其分成块,这通常导致更好的编码方案.
  • 由于您的数据是二维的,因此通过2D块而不是1D块处理它是有意义的,因此例如您可以编码8x8块.例如JPEG就是这样.
• 数据准备:在应用熵编码算法(实际上减少数据大小的算法)之前,应用双向(双向函数,不减小数据大小)来编码您的数据模型知识通常很有趣.在您的情况下,您说您的数据代表事件,而这些事件通常是特别聚集的.有没有办法将其表示为事件列表+它们传播的方式？或者你可以使用一些图像压缩方案,如傅立叶变换或某种小波变换.或者你可以简单地使用轮廓矩阵(一个值在两个单元格之间变化时,当值恒定时为零),这可能会增加矩阵的稀疏性(它在你的例如A)

极简证明:

由于压缩实际上取决于数据的概率分布,因此通常没有最佳的压缩算法.实际上,你知道你的矩阵总是一样的,你甚至不需要编码它.你知道它是两个可能的矩阵之一,只有一个就足以编码它是哪一个.

在一般情况下,Shanon 熵估计编码消息所需的理论最小位数:

min = E( -log2(P(message)) )

E对所有可能消息的期望在哪里,P是概率函数.在实践中,你不知道P,所以你能做到的最好比以前的最佳算法做得更好;)

通常,您尝试压缩数据的次数越多,程序就越昂贵,无论是在运行时资源(CPU周期和内存)还是开发工作方面.

一个例子

只是把它放在你的例子1的实践中,给你灵感 - 即使从一个例子设计是一个非常糟糕的主意,因为它几乎没有给你代表性的概率!

初始数据(我将始终省略大小标题,因为它将保持不变) - 位图,84位(25个):

000000000000
000000011000
001100111100
001111111100
000000111100
000001111100
000000000000

在您的index方案中,您输出一个列表position.如果您进行概括,则可以使用position+ 列表pattern.例如,pattern可以是连续的数量,因此您不需要为一个块输出多个位置.让我们进一步说,我们编码2D模式,定义如下:

• 3位大小(0到7)

• 1位形状:

  • 0表示一行 - 例如1111,一行大小为4;

  • 1 意味着一个正方形 - 例如:

    11
    11
    

    是一个2号的正方形.

然后让我们说取相对而不是绝对位置,这意味着每个位置position编码自前一个位置以来你前进了多少.以您为例,我选择5位位置.以下是解码的工作原理:

-- block #1
00001 position +1
      absolute position from top-left, since this is the first block
001   pattern-size 1
0     pattern-shape is row
      for size 1, square and row are the same
      (which means my coding isn't optimal)
-- block #2
00100 position +4
      relative to last position 1, this means position 5
010   pattern-size 2
1     pattern-shape is square
-- decoded output below
0100011000...
0000011000...
0000000000...
.............

因此,使用此方案,您可以使用45位对数据进行编码:

10100 (position [0]+20 from top-left)
010 0 (size: 2, shape: row)
00110 (position [20]+6)
010 1 (size: 2, shape: square)
00100 (position +4)
100 1 (size: 4, shape: square)
01000 (position +8)
100 0 (size: 4, shape: row)
11011 (position +27)
001 0 (size 1, shape: row)

注意:通常您需要存储标题以了解块的数量(在本例中为5),但您可以从文件/网络有效负载大小中推断出它.同样在这个例子中,我们只需要3个模式大小(1,2,4),因此我们可以将大小存储在两个位上并将其增加到功率2,使有效负载为40位,但这使得该方案过于专业化.此外,shape如果您没有足够的位position来编码模式之间的大"洞" ,则必须至少有一个无意义的(这里有两个:000/0和000/1).例如,这个20 x 3矩阵:

10000000000000000000
00000000000000000000
00000000000000000001

在0和59位置有一个.由于我不能将59编码为5位跳转,我们必须跳两次,我们将其编码为:

00000 (+0)  001 0 (a single 1)
11111 (+31) 000 0 (nothing)
11100 (+28) 001 0 (a single 1)