algorithm - 存储和读取 n 维稀疏矩阵

Question

Yale format 上的维基百科页面用于存储稀疏矩阵涵盖二维矩阵，但更高维度呢？是否有像 Yale 格式(或扩展？)这样的算法可以存储 n>2 维稀疏矩阵？——我指的是一种以某种压缩方式存储的算法，因为你当然可以只存储原始矩阵。

对该主题的大多数搜索似乎都找到了特定的语言实现，这对我来说毫无用处，因为我正在搜索一种适应性强的算法。

Answer 1

我们可以想象两个极端:

• 在一种极端情况下，您假设很大一部分元素是非零的，因此您只需存储每个元素的值(不针对稀疏性进行优化)，不需要存储有关元素位置的任何额外信息，得到总大小为 mn。
• 在另一个极端，你假设一小部分元素是非零的，所以你只存储非零元素，但现在你还需要存储它们的位置(行和列)并得到总大小为 3‌x(其中 x 是非零值的数量)。

Yale 格式是这两者的折衷，其中我们假设非零元素的数量大于行数¹，但与元素总数相比较小；所以我们为每一行存储一个指针²，然后存储每个元素的值和在其行中的位置，总大小为 m + 2‌x.

多于两个维度，可以继续做同样的妥协；您只需要选择正确的维度或维度的正确组合，以便非零元素的数量小于行/超行/等的数量。

例如，对于 m×n×p 数组，索引为 (i, j, k)，你有两个折衷方案:³

• 如果预期非零元素的数量超过 mn 的一小部分，但远小于 mnp，那么对于每个 i 和 j，您可以存储指向具有 i 和 j 的元素的一维“切片”的指针。对于该切片中的每个非零元素，您存储其值及其 k，总大小为 mn + 2‌x。
• 如果预期非零元素的数量大于 m 的一小部分，但远小于 mn，则对于每个 i，您可以存储指向具有该 i 的元素的二维“切片”的指针。对于该切片中的每个非零元素，您存储其值、j 和 k，总大小为 m + 3‌< em>x.

更广泛地说，一个 d 维数组将有 d−1 个折衷选项。 . .或总共 2^d 个选项，如果您分别计算每个可能的维度选择。

---

注意事项:

1. 我在这里写“行”，但您也可以按列做同样的事情。
2. 不一定是非常严格意义上的“指针”；您可以只存储前面所有行中所有非零元素的总数。
3. 不包括您可以选择使用不同维度的事实；就像您可以在行或列上使用 Yale 格式一样，您也可以在任何维度选择上使用这些选项。