我有一个非常大的矩阵（100M 行 x 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) 空间（即使矩阵被拉伸到任意大），因为只有恒定数量的矩形区域，每个区域只有一个值。
重复发生在行和下列中，因此逐行压缩矩阵的简单方法还不够好。（这将需要最少 O(num_rows) 空间来存储任何矩阵。）
矩阵的表示也需要逐行访问，以便我可以对列向量进行矩阵乘法。
您可以将矩阵存储为四叉树，其中的叶子包含单个值。将此视为价值的二维“运行”。
现在是我的首选方法。
好的，正如我在之前的答案中提到的，矩阵 A 中每一列中具有相同条目的行将乘以矩阵 AB 中的相同结果。如果我们能保持这种关系，那么理论上我们可以显着加快计算速度（分析器是你的朋友）。
在这种方法中，我们维护矩阵的行*列结构。
每一行都使用任何可以足够快地解压缩而不会过多影响乘法速度的方法进行压缩。RLE 可能就足够了。
我们现在有一个压缩行列表。
我们使用熵编码方法（如 Shannon-Fano、Huffman 或算术编码），但我们不使用此压缩行中的数据，我们使用它来压缩行集。我们用它来编码行的相对频率。即我们对待一行的方式与标准熵编码对待一个字符/字节的方式相同。
在此示例中， RLE 压缩一行，而 Huffman 压缩整个行集。
因此，例如，给定以下矩阵（以行号为前缀，Huffman 用于便于解释）
0 | 8 8 8 8 8 8 8 8 8 8 8 8 8 |
1 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
2 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
3 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
4 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
5 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
6 | 8 8 8 8 8 8 8 8 8 8 8 8 8 |
7 | 8 8 3 3 3 3 3 3 3 3 3 3 3 |
运行长度编码
0 | 8{13} |
1 | 8{1} 4{1} 8{2} 1{5} 8{4} |
2 | 8{1} 4{1} 8{2} 1{5} 8{4} |
3 | 8{1} 4{1} 8{2} 1{5} 8{4} |
4 | 8{1} 4{1} 8{2} 1{5} 8{4} |
5 | 8{1} 4{1} 8{2} 1{5} 8{4} |
6 | 8{13} |
7 | 8{2} 3{11} |
因此，0 和 6 出现两次，1 – 5 出现 5 次。7只有一次。
频率表
A: 5 (1-5) | 8{1} 4{1} 8{2} 1{5} 8{4} |
B: 2 (0,6) | 8{13} |
C: 1 7 | 8{2} 3{11} |
霍夫曼树
0|1
/ \
A 0|1
/ \
B C
因此，在这种情况下，对第 1-5 行进行编码需要一位（对于每一行），对第 0、6 和 7 行进行编码需要 2 位。
（如果运行时间超过几个字节，那么在执行 RLE 时建立的散列上执行频率计数）。
您存储 Huffman 树、唯一字符串和行编码比特流。
Huffman 的好处是它有一个独特的前缀属性，所以你总是知道什么时候完成。因此，给定位串10000001011，您可以从存储的唯一字符串和树中重建矩阵 A。编码的比特流告诉您行出现的顺序。
您可能想研究自适应霍夫曼编码或其算术对应物。
看到 A 中具有相同列条目的行在向量 B 上乘以 AB 中的相同结果，您可以缓存结果并使用它而不是再次计算它（如果可以的话，避免 100M*100M 乘法总是好的）。
更多信息的链接：
一个对比
未压缩
0 1 2 3 4 5 6 7
=================================
0 | 3 3 3 3 3 3 3 3 |
|-------+ +-------|
1 | 4 4 | 3 3 3 3 | 4 4 |
| +-----------+---+ |
2 | 4 4 | 5 5 5 | 1 | 4 4 |
| | | | |
3 | 4 4 | 5 5 5 | 1 | 4 4 |
|---+---| | | |
4 | 5 | 0 | 5 5 5 | 1 | 4 4 |
| | +---+-------+---+-------|
5 | 5 | 0 0 | 2 2 2 2 2 |
| | | |
6 | 5 | 0 0 | 2 2 2 2 2 |
| | +-------------------|
7 | 5 | 0 0 0 0 0 0 0 |
=================================
= 64 字节
四叉树
0 1 2 3 4 5 6 7
=================================
0 | 3 | 3 | | | 3 | 3 |
|---+---| 3 | 3 |---+---|
1 | 4 | 4 | | | 4 | 4 |
|-------+-------|-------+-------|
2 | | | 5 | 1 | |
| 4 | 5 |---+---| 4 |
3 | | | 5 | 1 | |
|---------------+---------------|
4 | 5 | 0 | 5 | 5 | 5 | 1 | 4 | 4 |
|---+---|---+---|---+---|---+---|
5 | 5 | 0 | 0 | 2 | 2 | 2 | 2 | 2 |
|-------+-------|-------+-------|
6 | 5 | 0 | 0 | 2 | 2 | 2 | 2 | 2 |
|---+---+---+---|---+---+---+---|
7 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
=================================
0 +- 0 +- 0 -> 3
| +- 1 -> 3
| +- 2 -> 4
| +- 3 -> 4
+- 1 -> 3
+- 2 -> 4
+- 3 -> 5
1 +- 0 -> 3
+- 1 +- 0 -> 3
| +- 1 -> 3
| +- 2 -> 4
| +- 3 -> 4
+- 2 +- 0 -> 5
| +- 1 -> 1
| +- 2 -> 5
| +- 3 -> 1
+- 3 -> 4
2 +- 0 +- 0 -> 5
| +- 1 -> 0
| +- 2 -> 5
| +- 3 -> 0
+- 1 +- 0 -> 5
| +- 1 -> 5
| +- 2 -> 0
| +- 3 -> 2
+- 2 +- 0 -> 5
| +- 1 -> 0
| +- 2 -> 5
| +- 3 -> 0
+- 3 +- 0 -> 0
+- 1 -> 2
+- 2 -> 0
+- 3 -> 0
3 +- 0 +- 0 -> 5
| +- 1 -> 1
| +- 2 -> 2
| +- 3 -> 2
+- 1 +- 0 -> 4
| +- 1 -> 4
| +- 2 -> 2
| +- 3 -> 2
+- 2 +- 0 -> 2
| +- 1 -> 2
| +- 2 -> 0
| +- 3 -> 0
+- 3 +- 0 -> 2
+- 1 -> 2
+- 2 -> 0
+- 3 -> 0
((1*4) + 3) + ((2*4) + 2) + (4 * 8) = 49 leaf nodes
49 * (2 + 1) = 147 (2 * 8 bit indexer, 1 byte data)
+ 14 inner nodes -> 2 * 14 bytes (2 * 8 bit indexers)
= 175 Bytes
区域哈希
0 1 2 3 4 5 6 7
=================================
0 | 3 3 3 3 3 3 3 3 |
|-------+---------------+-------|
1 | 4 4 | 3 3 3 3 | 4 4 |
| +-----------+---+ |
2 | 4 4 | 5 5 5 | 1 | 4 4 |
| | | | |
3 | 4 4 | 5 5 5 | 1 | 4 4 |
|---+---| | | |
4 | 5 | 0 | 5 5 5 | 1 | 4 4 |
| + - +---+-------+---+-------|
5 | 5 | 0 0 | 2 2 2 2 2 |
| | | |
6 | 5 | 0 0 | 2 2 2 2 2 |
| +-------+-------------------|
7 | 5 | 0 0 0 0 0 0 0 |
=================================
0: (4,1; 4,1), (5,1; 6,2), (7,1; 7,7) | 3
1: (2,5; 4,5) | 1
2: (5,3; 6,7) | 1
3: (0,0; 0,7), (1,2; 1,5) | 2
4: (1,0; 3,1), (1,6; 4,7) | 2
5: (2,2; 4,4), (4,0; 7,0) | 2
区域：（3 + 1 + 1 + 2 + 2 + 2）* 5 = 55 字节{4 字节矩形，1 字节数据）
{查找表是一个排序数组，所以它不需要额外的存储空间}。
霍夫曼编码的 RLE
0 | 3 {8} | 1
1 | 4 {2} | 3 {4} | 4 {2} | 2
2,3 | 4 {2} | 5 {3} | 1 {1} | 4 {2} | 4
4 | 5 {1} | 0 {1} | 5 {3} | 1 {1} | 4 {2} | 5
5,6 | 5 {1} | 0 {2} | 2 {5} | 3
7 | 5 {1} | 0 {7} | 2
RLE Data: (1 + 3+ 4 + 5 + 3 + 2) * 2 = 36
Bit Stream: 20 bits packed into 3 bytes = 3
Huffman Tree: 10 nodes * 3 = 30
= 69 Bytes
一个巨大的 RLE 流
3{8};4{2};3{4};4{4};5{3};1{1};4{4};5{3};1{1};4{2};5{1};0{1};
5{3};1{1};4{2};5{1};0{2};2{5};5{1};0{2};2{5};5{1};0{7}
= 2 * 23 = 46 Bytes
一个使用公共前缀折叠编码的巨型 RLE 流
3{8};
4{2};3{4};
4{4};5{3};1{1};
4{4};5{3};
1{1};4{2};5{1};0{1};5{3};
1{1};4{2};5{1};0{2};2{5};
5{1};0{2};2{5};
5{1};0{7}
0 + 0 -> 3{8};4{2};3{4};
+ 1 -> 4{4};5{3};1{1};
1 + 0 -> 4{2};5{1} + 0 -> 0{1};5{3};1{1};
| + 1 -> 0{2}
|
+ 1 -> 2{5};5{1} + 0 -> 0{2};
+ 1 -> 0{7}
3{8};4{2};3{4} | 00
4{4};5{3};1{1} | 01
4{4};5{3};1{1} | 01
4{2};5{1};0{1};5{3};1{1} | 100
4{2};5{1};0{2} | 101
2{5};5{1};0{2} | 110
2{5};5{1};0{7} | 111
Bit stream: 000101100101110111
RLE Data: 16 * 2 = 32
Tree: : 5 * 2 = 10
Bit stream: 18 bits in 3 bytes = 3
= 45 bytes
如果您的数据确实是有规律的，那么您可能会受益于以结构化格式存储它；例如，您的示例矩阵可能存储为以下“填充矩形”指令列表：
(0,0)-(13,7) = 8
(4,1)-(8,5) = 1
（然后要查找特定单元格的值，您将向后遍历列表，直到找到包含该单元格的矩形）
正如 Ira Baxter 建议的那样，您可以将矩阵存储为四叉树，其中的叶子包含单个值。
最简单的方法是让四叉树的每个节点覆盖一个 2^nx 2^n 的区域，并且每个非叶节点指向它的 4 个大小为 2^(n-1) x 2^(n- 1）。
使用允许不规则细分的自适应四叉树可能会获得更好的压缩。然后每个非叶节点存储切点 (B,G) 并指向其 4 个子节点。例如，如果某个非叶子节点覆盖了从左上角 (A,F) 到右下角 (C,H) 的区域，那么它的 4 个子节点覆盖区域 (A,F) 到 ( B-1, G-1) (A,G) 到 (B-1, H) (B,F) 到 (C,G-1) (B,G) 到 (C,H)。
您将尝试为每个非叶节点选择 (B,G) 切点，使其与数据中的一些实际划分对齐。
例如，假设您有一个矩阵，中间有一个小正方形，在其他地方填充了 9 和 0。
使用简单的二次幂四叉树，您最终将得到至少 21 个节点：5 个非叶节点、4 个 9 的叶节点和 12 个零的叶节点。（如果居中的小方块与左边缘和上边缘的距离不是精确的二次方，并且本身不是精确的二次方，那么您将获得更多节点）。
对于自适应四叉树，如果您足够聪明，可以在该正方形的左上角为根节点选择切点，那么对于根的右下子节点，您可以在右下角选择一个切点对于正方形，您可以用 9 个节点表示整个矩阵：2 个非叶节点，1 个叶节点代表 9，6 个叶节点代表 0。
你知道....区间树吗？
区间树是一种有效存储区间，然后查询它们的方法。泛化是Range Tree，它可以适应任何维度。
在这里，您可以有效地描述您的矩形并为其附加值。当然，矩形可以重叠，这将使其高效。
0,0-n,n --> 8
4,4-7,7 --> 1
8,8-8,n --> 3
然后，当查询一个特定位置的值时，会返回一个包含几个矩形的列表，需要确定最里面的一个：这就是该位置的值。
您对大小为 100M x 100M 的矩阵的 O(1) 空间的描述令人困惑。当你有一个有限矩阵时，你的大小是一个常数（除非生成矩阵的程序没有改变它）。因此，即使将其乘以标量，存储所需的空间量也是一个常数。读取和写入矩阵的时间绝对不会是 O(1)。
稀疏矩阵是我能想到的减少存储这样一个矩阵所需的空间量。您可以将此稀疏矩阵写入文件并将其存储为 tar.gz，这将进一步压缩数据。
我确实有一个问题 100M 中的 M 表示什么？这是否意味着兆字节/百万？如果是，则此矩阵大小将为 100 x 10^6 x 100 x 10^6 字节 = 10^16 / 10^6 MB = 10^10/10^6 TB = 10^4 TB！！！你用的是什么机器？
最简单的方法是在一个维度上使用游程编码，而不用担心另一个维度。
（如果数据集不是那么大，将其解释为图像并使用标准的无损图像压缩方法也将非常简单 - 但由于您必须努力使算法在稀疏矩阵上工作，它不会最终不会那么简单。）
另一种简单的方法是尝试矩形泛光填充——从右上角的像素开始，将其增加到最大的矩形（宽度优先）；然后将所有这些像素标记为“完成”并获取右上角最剩余的像素，重复直到完成。（您可能希望将这些矩形存储在某种 BSP 或四叉树中。）
一种高效的技术——不是最优的，但可能已经足够好了——是使用二进制空间划分树，其中“空间”不是在空间上而是通过变化的数量来衡量的。您将递归切割，以便在左侧和右侧（或顶部和底部 - 大概您希望保持正方形）具有相同数量的更改，并且随着您的尺寸变小，您可以切割尽可能多的尽可能地改变。最终，您将切割两个彼此分开的矩形，每个矩形都有相同的数字；然后停下来。（x 和 y 中的 RLE 编码会很快告诉您变化点在哪里。）
我不知道为什么这个问题是社区维基，但事实如此。
我将假设您有一个线性代数应用程序，并且您的矩阵具有矩形冗余类型。如果是这样，那么您可以做一些比四叉树更好的事情，并且比将矩阵切割成矩形更干净（这通常是正确的想法）。
让 M 是你的矩阵，让 v 是你想乘以 M 的向量，让 A 是特殊矩阵
A = [1 -1 0 0 0]
[0 1 -1 0 0]
[0 0 1 -1 0]
[0 0 0 1 -1]
[0 0 0 0 1]
您还需要 A 的逆矩阵，我将其称为 B：
B = [1 1 1 1 1]
[0 1 1 1 1]
[0 0 1 1 1]
[0 0 0 1 1]
[0 0 0 0 1]
将向量 v 乘以 A 既快速又简单：您只需获取 v 的连续元素对的差异。将向量 v 乘以 B 也快速简单：Bv 的条目是 v 的元素的部分和。然后你想用方程
Mv = B AMA B v
矩阵 AMA 是稀疏的：在中间，每个条目是 M 的 4 个条目的交替总和，构成 2 x 2 正方形。您必须在 M 中的一个矩形的角处，才能使这个交替和为非零。由于 AMA 是稀疏的，因此您可以将其非零条目存储在关联数组中，并使用稀疏矩阵乘法将其应用于向量。
您可能想看看GIF 格式及其压缩算法。只需将您的矩阵视为位图...
上述许多解决方案都很好。
如果您正在处理文件，请考虑使用面向文件的压缩工具，例如 compress、bzip、zip、bzip2 和朋友。它们工作得很好，尤其是在数据包含冗余 ASCII 字符的情况下。使用外部压缩工具可以消除代码内部的问题和挑战，并将压缩二进制和 ASCII 数据。
在您的示例中，您正在显示一个字符编号。数字 0-9 可以用较小的四位编码模式表示。您可以使用字节中的附加位作为计数。四位为您提供了额外的代码以逃避额外的...但是有一个警告可以追溯到旧的 Y2K 错误，其中两个字符被使用了一年。偏移量的字节编码将给出 255 年，而相同的两个字节将跨越所有书面历史，然后是一些。
让我检查一下我的假设，如果只是为了指导我对问题的思考：
人们可以尝试各种巧妙的方案来检测矩形或自相似性等，但这最终会损害乘法时的性能。我提出了2个相对简单的解决方案。
我将不得不向后工作一点，所以请耐心等待。
如果数据主要偏向于水平重复，那么以下可能会很好。
想想将矩阵展平成一个数组（这实际上是它存储在内存中的方式）。例如
A
| w0 w1 w2 |
| x0 x1 x2 |
| y0 y1 y2 |
| z0 z1 z2 |
变成
A’
| w0 w1 w2 x0 x1 x2 y0 y1 y2 z0 z1 z2 |
我们可以使用任何索引[i,j] = i * j.
因此，当我们进行乘法运算时，我们使用 k = [0..m*n-1] 遍历“矩阵”数组 A' 并使用 (k mod n) 索引向量 B 并使用 (k div 索引向量 AB n)。“div”是整数除法。
所以，例如，A[10] = z1。 10 mod 3 = 1和10 div 3 = 3 A[3,1] = z1.
现在，继续压缩。我们进行正常运行的运行长度编码 (RLE)，但针对的是 A'，而不是 A。使用平面阵列会有更长的重复序列，因此压缩效果更好。然后在对运行进行编码之后，我们执行另一个过程，我们提取公共子字符串。我们可以进行某种形式的字典压缩，或者将运行数据处理成某种形式的空间优化图，例如基数树/后缀树或您自己创建的合并顶部和尾部的设备。该图应具有数据中所有唯一字符串的表示形式。您可以选择任意数量的方法将流分解为字符串：匹配前缀、长度或其他内容（最适合您的图形），但在运行边界上进行，而不是字节，否则您的解码将变得更加复杂。
我将使用比特流和Patricia trie作为示例，因为它最简单，但您可以使用其他东西（每个状态的更多比特会改变更好的合并等。查找Stefan Nilsson的论文）。
为了压缩运行数据，我们针对图表构建了一个哈希表。该表将字符串映射到位序列。您可以通过遍历图形并将每个左分支编码为 0 并将右分支编码为 1（任意选择）来做到这一点。
处理运行数据并建立一个位字符串，直到在哈希表中得到匹配，输出位并清除字符串（位不会在字节边界上，因此您可能需要缓冲直到获得一个长序列足够写出来）。冲洗并重复，直到您处理完完整的运行数据流。您存储图形和比特流。比特流编码字符串，而不是字节。
如果您反转该过程，使用比特流遍历图形，直到您到达叶/终端节点，您将返回原始运行数据，您可以对其进行动态解码以生成与向量 B 相乘的整数流得到AB。每次运行用完时，您都会读取下一位并查找其相应的字符串。我们不关心我们没有随机访问 A，因为我们只需要在 B 中（B 可以是范围/间隔压缩但不需要）。
因此，即使 RLE 偏向于水平运行，我们仍然可以获得良好的垂直压缩，因为常见的字符串只存储一次。
我将在单独的答案中解释另一种方法，因为它变得太长了，但是由于矩阵 A 中的重复行乘以 AB 中的相同结果，该方法实际上可以加快计算速度。
对于您显示的矩阵，我没有具体的答案。在有限元分析 (FEA) 中，您拥有包含冗余数据的矩阵。在我的研究生项目中实施 FEA 包时，我使用了天际线存储方法。
一些链接：
首先要尝试的始终是现有的库和解决方案。让自定义格式与您最终想要的所有操作一起工作需要做很多工作。稀疏矩阵是一个老问题，所以一定要阅读现有的东西。
假设您找不到合适的东西，我会推荐一种基于行的格式。不要试图对超级紧凑的表示过于花哨，你最终会为代码中的每一个小操作和错误带来大量的处理。而是尝试分别压缩每一行。您知道您将不得不扫描每一行以进行矩阵向量乘法，让自己的生活变得轻松。
我将从运行长度编码开始，先看看它是如何工作的。一旦它起作用，请尝试添加一些技巧，例如对上一行的部分的引用。因此，一行可能被编码为：126 个零，8 个 1，直接从上面的行复制的 1000 个条目，32 个零。对于您给定的示例，这似乎非常有效。
好的，您需要一种压缩算法，在数据高度冗余时尝试RLE （运行长度编码）它的工作非常好。