存储和读取 n 维稀疏矩阵

Question

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

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

Answer 1

我们可以想象两个极端：

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

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

多于两个维度，可以继续做同样的妥协；您只需要选择正确的维度或维度的正确组合，使非零元素的数量小于 rows/hyper-rows/etc.

的数量

例如，对于一个 m×n×p 数组索引为 (i, j, k), 你有两个妥协选项：³

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

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

---

备注：

1. 我这里写的是"rows"，不过你也可以这样写column-wise
2. 严格意义上不一定是"pointer"；您可以只存储前面所有行中所有非零元素的总数。
3. 不包括您可以选择使用不同维度的事实；就像您可以在行或列上使用 Yale 格式一样，您可以在任何维度上使用这些选项。