algorithm - 如何有效地存储具有高度冗余值的矩阵

Question

我有一个非常大的矩阵(100M 行乘以 100M 列)，其中有很多彼此相邻的重复值。例如:

8 8 8 8 8 8 8 8 8 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 3 3 3 3 3 3 3 3 3 3 3

我想要一个数据结构/算法来尽可能紧凑地存储这些矩阵。例如，上面的矩阵应该只占用 O(1) 空间(即使矩阵被拉伸(stretch)任意大)，因为只有恒定数量的矩形区域，每个区域只有一个值。

重复发生在行和列之间，因此逐行压缩矩阵的简单方法不够好。 (这至少需要 O(num_rows) 空间来存储任何矩阵。)

矩阵的表示也需要逐行访问，这样我就可以对列向量进行矩阵乘法。

Answer 1

您可以将矩阵存储为 quadtree叶子包含单个值。将此视为值(value)的二维“运行”。