具有运行的稀疏二进制矩阵的最优 space-高效存储方案

Question

在为 C 中的快速动态时间规整实现 "search window" 的上下文中，我需要构建一个结构来表示具有非常特殊结构的稀疏二进制矩阵。

这个矩阵有一些很强的结构约束：具体来说，每行只有一个 "run" 非零数据，尽管运行是可变长度的。起始单元格的列索引和结束单元格的列索引的值随着行的增加而单调增加：

示例有效矩阵（* = 已填充，. = 未填充）

  0 1 2 3 4 5
0 * * * . . .
1 . * * * . .
2 . * * * . .
3 . . * * * *
4 . . * * * *


  0 1 2 3 4 5
0 * * * * . .
1 . * * * * .
2 . . * * * .
3 . . . . * *
4 . . . . . *

示例无效矩阵：

  0 1 2 3 4 5
0 * * * . * * <-- more than one continuous run
1 . * * * . .
2 . * * * . .
3 . . * * * *
4 . . * * * *

  0 1 2 3 4 5
0 * * * . . .
1 . * * * . .
2 . * * * . .
3 * * * * * * <-- start index not monotonically increasing
4 . . * * * *


  0 1 2 3 4 5
0 * * * . . .
1 . * * * * .
2 . * * * . . <-- end index not monotonically increasing
3 . . * * * *
4 . . * * * *

这些稀疏矩阵主要分布在对角线上，但它们不是正方形，所以我不知道是否应该使用"jagged diagonal storage"。

我目前的方法是为每一行存储（开始，结束）列索引：即

  0 1 2 3 4 5
0 * * * . . .
1 . * * * . .
2 . * * * . .
3 . . * * * *
4 . . * * * *

（逻辑上）存储为

(0, 0) --> (0, 2)
(1, 1) --> (1, 3)
(2, 1) --> (2, 3)
(3, 2) --> (3, 5) 
(4, 2) --> (4, 5)

（尽管这些在内部存储为混乱的索引，即）

(0 * num_cols + 0) --> (0 * num_cols + 2)
(1 * num_cols + 1) --> (1 * num_cols + 3)

所以最终的结构看起来像

[0, 2, 7, 9, 13, 15, 20, 23, 26, 29]

然后，这个结构像

一样被delta编码

[first_value, offset_1, offset_2, ...]
[0, 2, 5, 2, 4, 2, 5, 3, 3, 3]

因为这些增量值很小且为正，我们可以利用将它们打包成某种 VARINT 结构。

第一个问题：这些矩阵有一个众所周知的名字吗？似乎在文献中找不到太多。

第二个问题：这种存储方案是否利用了矩阵的所有强特性？我可以滥用约束以某种方式存储更少的数据吗？

我已经阅读了一些描述一般稀疏矩阵的稀疏矩阵存储的文档，但令我印象深刻的是，这种特殊情况的结构可能有一种特殊情况的最佳存储/编码方案。

Answer 1

我认为你考虑绝对索引值（然后使用增量编码）的方法已经产生了很好的结果，但它没有利用单调递增的 start/end-index 约束。

考虑存储结构 - 相对于绝对开始和结束索引 - 只有开始和结束索引的增量应该 - 平均 - 产生范围更小（因此表示更短）的数字。

将您的第一个示例翻译成此结构如下所示：

(0/2) - (1/1)(0/0)(1/2)(0/0)

其中第一对 (0/2) 代表绝对 start/end - 索引，其他对代表每行开始和结束的增量。由于这些数字使用较小的范围，可变长度整数编码应该产生更好的压缩。

例如，考虑以下（简单的）整数编码：

0 .. 00
1 .. 01
2 .. 100
3 .. 101
4 .. 1100
5 .. 1101
6 and higher: 111 + 16 bit integer

使用这种编码，第一个样本转换为以下包含 22 位的位流：

00 100 01 01 00 00 01 100 00 00

增量越小，这种方法越有效；当按行考虑增量时，如果矩阵的行数多于列数，则应该是这种情况。

只是优化列多于行的矩阵的想法：可以考虑按列使用相同的存储方法；我认为（但没有数学证明）单次运行的行单调递增也意味着单次运行的列单调递增。

具有运行的稀疏二进制矩阵的最优 space-高效存储方案

Optimal space-efficient storage scheme for Sparse Binary Matrix with runs

c

sparse-matrix