稀疏矩阵的最小表示
Minimal representation of sparse matrix
我有一个大的二进制稀疏矩阵（任何单元格都可以包含 0 或 1 作为值）。有时我想拍下整个矩阵的快照。
快照必须尽可能小。
矩阵表示二维地图和发生在区域中的事件，因此它更有可能具有看起来像示例 A 的快照而不是看起来像示例 B 的快照（它们都具有相同数量的“1” ) 尽管我需要在算法中支持这两个示例。
Example A:
000000000000
000000011000
001100111100
001111111100
000000111100
000001111100
000000000000
Example B:
010010010010
001000001000
010010100100
000100101010
001000010010
010010001100
001000010000
由于数据可以从单个“1”单元格到 100% 的单元格为“1”（在非常非常落后的情况下），我认为我需要使用不止一种算法 - 并且在加载数据时使用与存储它相同的算法加载它。
例如，当只有一个单元格时，我将仅存储它的索引（以及 "index" 算法的标识符），当矩阵的 99% 为“1”时，我将其存储为位图（并且"bitmap" 算法的标识符）。
所以我得到了这样一个通用算法：
- 对于每个表示算法 - 表示矩阵
- Select最小表示
- 存储具有最小表示的数据
我的问题
- 我可以使用什么算法 - 除了存储 Index/bitmap？
- 是否有处理此问题的良好参考资料？
- 如何证明我的解决方案是最小可能的？
底线：
如何以最小的方式存储位图矩阵？
编辑
用例：我有一个稀疏矩阵，需要通过非常低的带宽介质进行传输。所以发送矩阵应该包含尽可能少的比特，假设介质两边的计算能力都很强。
您提到了一些明显的存储方式 - 1 单元格的位图和索引。通过编码 'indices' 方法的标识符和 1 单元格的数量，然后是那么多对坐标，可以很容易地扩展索引的想法。您甚至可以尝试通过按行（或列）分组进行压缩，例如
rowNumber colNumber1 colNumber2 ... -1
使用 -1 或其他一些标志值来指示行的结尾。对于只有几个条目的大型矩阵，这可以节省大量 space。您还需要存储矩阵大小。
对于示例 A，您将得到（使用 0 索引，白色 space 只是为了便于阅读）
7 12 //dimensions
1 7 8 -1
2 2 3 6 7 8 9 -1
3 2 3 4 5 6 7 8 9 -1
4 6 7 8 9 -1
5 5 6 7 8 9 -1
对于您的情况，另一种存储方式的示例可能如下所示 - 您必须进行试验，看看它在 'compressing' 信息方面的成功程度。该算法的想法来自观察，在您的 A 示例中，几乎所有行都只有一个大的 1 连接部分，被 0 包围。
假设您的矩阵可以有任何维度，第一步就是对其进行编码。所以对于 n * m 矩阵，只需存储这两个整数。
在此之后，对于每一行，以下内容如何：
- 存储左边连接0的个数。
- 存储此后连接的 1 的数量。
- 重复直到行尾。
要解码，您只需遵循如下过程：
- 对于每一行（在给定的行数中）
- 设
count为目前读取的矩阵条目数。初始化为 0
- 设
next为布尔值，表示下一个数字编码的值。初始化为 false.
- 读下一个数字
- 将等于
next 的数值插入相应的行。
- 翻转
next
- 增加
count那个数字
- 循环直到
count == m（如果 count > m 出现问题）
- 循环直到所有行都被读取
我希望我已经很好地解释了这个想法。正如我所说，我不知道它的表现如何，但它源于对你的例子的观察。要真正压缩它，您可以确保每个数字条目只需要尽可能多的位来计算（并且不高于）行宽（我的伪代码中的m。）
示例 A 会出现这样的结果（白色space 只是为了便于阅读）：
7 12 //dimensions
12
7 2 3
2 2 2 4 2
2 8 2
6 4 2
5 5 2
12
如果您对其进行了优化，则每个数字只需要 4 位。
我不会尝试做示例 B，但它的性能会差很多
数据压缩是一个很大的领域（你可以start here），你的问题没有确定的答案。如果我们知道如何以最佳速率压缩数据，就不会每年都有新的压缩算法 ;)
话虽这么说，你提出的是个好主意：select 从 collection 中找出最好的算法并在 header 中识别它。事实上，大多数压缩格式都使用这种方案。
回答您的问题：
什么算法：
- 使用现有格式：想到PNG, GIF, or 7zip。
- 无压缩：位图，显然，但只是为了确保我们说的是同一件事，您需要为每个元素编码 1 位（而不是 1 字节） .大多数语言都不容易访问位（因为大多数
bool/boolean 类型都存储在一个完整的字节上）。您必须使用按位运算、bitfields/bitsets 等专用语言功能或库。例如 C++，std::vector<bool> 实现了一个真正的位图（简单的 bool[] 没有）。
- 熵编码：使用比不太可能的配置更少的存储对最可能的配置进行编码的想法。
- 稀疏存储，你称之为索引，但与你暗示的相反，当有很多 1 但也有很多 0 时它很有用（只是否定结果！）。只有一个
0 或只有一个 1 的情况是对称的，应该以相同的方式处理。备用存储的 worst-case 场景是 1 和 0 一样多。
- 块编码，这意味着如果您知道它是一种可能的模式，您可以将
1111 存储在少于 4 位中。但这意味着另一个（不太可能）4 位模式将使用超过 4 位存储，因此在 selecting 您的模式时要小心。有很多方法可以做到这一点：fixed-size 或 variable-size 个单词，编码可以是静态的或 data-dependent。一些示例是：RLE, Huffman, LZ 变体（dictionary-based 您最喜欢的压缩程序中使用的算法）
- Arithmetic coding 基于相同的想法，即根据其概率为每个 symbol/block 调整存储 space，但它一次性对整个数据进行编码，而不是将其拆分在块中，这通常会导致更好的编码方案。
- 由于您的数据是 two-dimensional，因此通过 2D 块而不是 1D 块来处理它是有意义的，例如您可以编码 8x8 块。 JPEG 例如这样做。
- 数据准备：在应用你的熵编码算法（实际减少数据大小的算法）之前，应用一个双射（双向函数，不会减少数据大小）来编码您对 data-model 的了解。在您的情况下，您说您的数据代表事件，而这些事件通常是专门聚集的。有没有办法将其表示为事件列表+它们传播的方式？或者您可以使用一些 image-compression 方案，例如 Fourier transform or some kind of wavelet transform. Or you could simply use the contour matrix （当值在两个单元格之间变化时，当值不变时为零），这可能会增加矩阵的稀疏性（它在您的 例A)
极简证明：
没有普遍最优的压缩算法，因为压缩实际上取决于数据的概率分布。事实上，如果您知道您的矩阵始终相同，您甚至不需要对其进行编码。如果您知道它是两个可能的矩阵之一，只需一位就足以编码它是哪一个。
在一般情况下，Shanon 的 entropy 估计编码消息所需的理论最小位数：
min = E( -log2(P(message)) )
其中 E 是对所有可能消息的期望，P 是概率函数。但在实践中，你不知道 P，所以你能做到的最好的算法比以前最好的算法做得更好 ;)
但一般来说，您尝试压缩数据的次数越多，您的程序在 run-time 资源（CPU 周期和内存）和开发工作方面的成本就越高。
一个例子
只是为了在您的 示例 1 上付诸实践，给您灵感——即使从示例 1 开始设计是一个非常糟糕的主意，因为它几乎不会给您带来灵感代表性概率！
初始数据（我总是会省略大小 header，因为它会保持不变） -- 位图，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)
注释：通常你想存储一个header来知道块的数量（在这种情况下是5），但你可以从file/network-payload 大小。同样在这个例子中，我们只需要 3 个模式大小 (1,2,4)，所以我们可以将大小存储在两位上并将其提高到 2 的幂，使有效载荷为 40 位，但这使得方案过于专业化。此外，必须至少有一个无意义的 shape（这里有两个：000/0 和 000/1），以防 position 中没有足够的位来编码大"hole" 模式之间。例如这个 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)
我有一个大的二进制稀疏矩阵（任何单元格都可以包含 0 或 1 作为值）。有时我想拍下整个矩阵的快照。 快照必须尽可能小。
矩阵表示二维地图和发生在区域中的事件，因此它更有可能具有看起来像示例 A 的快照而不是看起来像示例 B 的快照（它们都具有相同数量的“1” ) 尽管我需要在算法中支持这两个示例。
Example A:
000000000000
000000011000
001100111100
001111111100
000000111100
000001111100
000000000000
Example B:
010010010010
001000001000
010010100100
000100101010
001000010010
010010001100
001000010000
由于数据可以从单个“1”单元格到 100% 的单元格为“1”（在非常非常落后的情况下），我认为我需要使用不止一种算法 - 并且在加载数据时使用与存储它相同的算法加载它。
例如，当只有一个单元格时，我将仅存储它的索引（以及 "index" 算法的标识符），当矩阵的 99% 为“1”时，我将其存储为位图（并且"bitmap" 算法的标识符）。
所以我得到了这样一个通用算法：
- 对于每个表示算法 - 表示矩阵
- Select最小表示
- 存储具有最小表示的数据
我的问题
- 我可以使用什么算法 - 除了存储 Index/bitmap？
- 是否有处理此问题的良好参考资料？
- 如何证明我的解决方案是最小可能的？
底线： 如何以最小的方式存储位图矩阵？
编辑 用例：我有一个稀疏矩阵，需要通过非常低的带宽介质进行传输。所以发送矩阵应该包含尽可能少的比特，假设介质两边的计算能力都很强。
您提到了一些明显的存储方式 - 1 单元格的位图和索引。通过编码 'indices' 方法的标识符和 1 单元格的数量，然后是那么多对坐标，可以很容易地扩展索引的想法。您甚至可以尝试通过按行（或列）分组进行压缩，例如
rowNumber colNumber1 colNumber2 ... -1
使用 -1 或其他一些标志值来指示行的结尾。对于只有几个条目的大型矩阵，这可以节省大量 space。您还需要存储矩阵大小。
对于示例 A，您将得到（使用 0 索引，白色 space 只是为了便于阅读）
7 12 //dimensions
1 7 8 -1
2 2 3 6 7 8 9 -1
3 2 3 4 5 6 7 8 9 -1
4 6 7 8 9 -1
5 5 6 7 8 9 -1
对于您的情况，另一种存储方式的示例可能如下所示 - 您必须进行试验，看看它在 'compressing' 信息方面的成功程度。该算法的想法来自观察，在您的 A 示例中，几乎所有行都只有一个大的 1 连接部分，被 0 包围。
假设您的矩阵可以有任何维度，第一步就是对其进行编码。所以对于 n * m 矩阵，只需存储这两个整数。
在此之后，对于每一行，以下内容如何：
- 存储左边连接0的个数。
- 存储此后连接的 1 的数量。
- 重复直到行尾。
要解码，您只需遵循如下过程：
- 对于每一行（在给定的行数中）
- 设
count为目前读取的矩阵条目数。初始化为0 - 设
next为布尔值，表示下一个数字编码的值。初始化为false. - 读下一个数字
- 将等于
next的数值插入相应的行。 - 翻转
next - 增加
count那个数字
- 将等于
- 循环直到
count == m（如果count > m出现问题）
- 设
- 循环直到所有行都被读取
我希望我已经很好地解释了这个想法。正如我所说，我不知道它的表现如何，但它源于对你的例子的观察。要真正压缩它，您可以确保每个数字条目只需要尽可能多的位来计算（并且不高于）行宽（我的伪代码中的m。）
示例 A 会出现这样的结果（白色space 只是为了便于阅读）：
7 12 //dimensions
12
7 2 3
2 2 2 4 2
2 8 2
6 4 2
5 5 2
12
如果您对其进行了优化，则每个数字只需要 4 位。
我不会尝试做示例 B，但它的性能会差很多
数据压缩是一个很大的领域（你可以start here），你的问题没有确定的答案。如果我们知道如何以最佳速率压缩数据，就不会每年都有新的压缩算法 ;)
话虽这么说，你提出的是个好主意：select 从 collection 中找出最好的算法并在 header 中识别它。事实上，大多数压缩格式都使用这种方案。
回答您的问题：
什么算法：
- 使用现有格式：想到PNG, GIF, or 7zip。
- 无压缩：位图，显然，但只是为了确保我们说的是同一件事，您需要为每个元素编码 1 位（而不是 1 字节） .大多数语言都不容易访问位（因为大多数
bool/boolean类型都存储在一个完整的字节上）。您必须使用按位运算、bitfields/bitsets等专用语言功能或库。例如C++，std::vector<bool>实现了一个真正的位图（简单的bool[]没有）。 - 熵编码：使用比不太可能的配置更少的存储对最可能的配置进行编码的想法。
- 稀疏存储，你称之为索引，但与你暗示的相反，当有很多 1 但也有很多 0 时它很有用（只是否定结果！）。只有一个
0或只有一个1的情况是对称的，应该以相同的方式处理。备用存储的 worst-case 场景是 1 和 0 一样多。 - 块编码，这意味着如果您知道它是一种可能的模式，您可以将
1111存储在少于 4 位中。但这意味着另一个（不太可能）4 位模式将使用超过 4 位存储，因此在 selecting 您的模式时要小心。有很多方法可以做到这一点：fixed-size 或 variable-size 个单词，编码可以是静态的或 data-dependent。一些示例是：RLE, Huffman, LZ 变体（dictionary-based 您最喜欢的压缩程序中使用的算法） - Arithmetic coding 基于相同的想法，即根据其概率为每个 symbol/block 调整存储 space，但它一次性对整个数据进行编码，而不是将其拆分在块中，这通常会导致更好的编码方案。
- 由于您的数据是 two-dimensional，因此通过 2D 块而不是 1D 块来处理它是有意义的，例如您可以编码 8x8 块。 JPEG 例如这样做。
- 稀疏存储，你称之为索引，但与你暗示的相反，当有很多 1 但也有很多 0 时它很有用（只是否定结果！）。只有一个
- 数据准备：在应用你的熵编码算法（实际减少数据大小的算法）之前，应用一个双射（双向函数，不会减少数据大小）来编码您对 data-model 的了解。在您的情况下，您说您的数据代表事件，而这些事件通常是专门聚集的。有没有办法将其表示为事件列表+它们传播的方式？或者您可以使用一些 image-compression 方案，例如 Fourier transform or some kind of wavelet transform. Or you could simply use the contour matrix （当值在两个单元格之间变化时，当值不变时为零），这可能会增加矩阵的稀疏性（它在您的 例A)
极简证明：
没有普遍最优的压缩算法，因为压缩实际上取决于数据的概率分布。事实上，如果您知道您的矩阵始终相同，您甚至不需要对其进行编码。如果您知道它是两个可能的矩阵之一，只需一位就足以编码它是哪一个。
在一般情况下，Shanon 的 entropy 估计编码消息所需的理论最小位数：
min = E( -log2(P(message)) )
其中 E 是对所有可能消息的期望，P 是概率函数。但在实践中，你不知道 P，所以你能做到的最好的算法比以前最好的算法做得更好 ;)
但一般来说，您尝试压缩数据的次数越多，您的程序在 run-time 资源（CPU 周期和内存）和开发工作方面的成本就越高。
一个例子
只是为了在您的 示例 1 上付诸实践，给您灵感——即使从示例 1 开始设计是一个非常糟糕的主意，因为它几乎不会给您带来灵感代表性概率！
初始数据（我总是会省略大小 header，因为它会保持不变） -- 位图，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)
注释：通常你想存储一个header来知道块的数量（在这种情况下是5），但你可以从file/network-payload 大小。同样在这个例子中，我们只需要 3 个模式大小 (1,2,4)，所以我们可以将大小存储在两位上并将其提高到 2 的幂，使有效载荷为 40 位，但这使得方案过于专业化。此外，必须至少有一个无意义的 shape（这里有两个：000/0 和 000/1），以防 position 中没有足够的位来编码大"hole" 模式之间。例如这个 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)