实现稀疏矩阵存储

1. 稀疏矩阵稀疏矩阵的计算机存储

在计算机存储中，稀疏矩阵的特性使其在处理大量元素为零的情况时显得尤为高效。当Matlab将矩阵视为稀疏矩阵时，存储策略发生了改变。通常，矩阵的存储仅需关注非零元素，而非全矩阵。具体来说，这种存储方式采用一个m×3的矩阵，其中第1列存储行下标，第2列存储列下标，第3列则是非零元素的值。每个非零元素占用8个字节（相当于高斯节），而下标则需要4个字节。因此，对于一个包含m个非零元素的矩阵，总的内存占用为16字节乘以m。

以矩阵A为例，其元素为(1,0,0,0)，形成一个1×1的单位矩阵，常规存储需要8兆字节（Mb）。然而，如果使用`sparse`命令，我们可以将其表示为一个1×3的矩阵，每行仅包含一个元素的行下标、列下标和值。这样，存储这个单位矩阵只需16千字节（Kb），相比于常规存储，节省的空间达到了99.8%。这种方法同样适用于许多具有大量零元素的广义矩阵，极大地节省了存储空间。

(1)实现稀疏矩阵存储扩展阅读

如果在矩阵中，多数的元素为0，称此矩阵为稀疏矩阵（sparse matrix）。

2. 特殊矩阵的压缩存储（稀疏矩阵的链式存储）

在计算机科学领域，特殊矩阵的存储是一个重要话题，尤其是对于稀疏矩阵。稀疏矩阵的特点是其中大部分元素为零，因此传统的二维数组存储方式会浪费大量的存储空间。针对这一问题，我们可以采用压缩存储方式，尤其是链式存储，以提高存储效率。

一、参数解释

在压缩存储稀疏矩阵时，我们主要关注三个参数：非零元素的数量、矩阵的行数和列数。通过这些参数，我们可以构建一个紧凑的存储结构，仅存储非零元素的位置和值。

二、逻辑结构

逻辑上，我们可以将稀疏矩阵表示为一个链表结构。每个节点代表矩阵中的一个非零元素，包含元素的位置（行和列）和值。链表的头节点通常包含矩阵的行数和列数。通过这种方式，我们有效地压缩了存储空间，因为只存储了非零元素的信息。

三、代码实现

实现代码时，首先定义一个节点类，包含元素的位置（行和列）和值。接着构建一个链表，用于存储所有非零元素。在插入元素时，检查该元素是否已存在于链表中，以避免重复存储。最后，可以通过遍历链表，以二维数组的形式输出矩阵。

四、总结

压缩存储，特别是链式存储，对于稀疏矩阵是非常有效的解决方案。它不仅节省了存储空间，还简化了矩阵的读取和操作。通过合理设计，我们能够以较低的时间复杂度实现矩阵的高效操作。

五、课程链接

如果您想了解更多关于数据结构与算法的知识，特别是特殊矩阵的压缩存储，可以访问以下链接：数据结构与算法基础（青岛大学-王卓）_哔哩哔哩_bilibili

3. 稀疏矩阵定义以及存储格式(COO,CSR,CSC)

网络:在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。 简单来说,稀疏矩阵就是绝大部分都是0的矩阵 ,只包含很少的非零值.

比如,

上述稀疏矩阵非零元素有9个,26个零值.稀疏性是74%.

稀疏矩阵因为绝大部分都是0元素,如果我们仍然按照普通方式存储,无疑会 浪费很多空间 ;同时如果进行运算时,0元素对最终结果也没有帮助, 增加了许多无效计算 . 因此,我们需要设计出新的存储方式,或者说数据结构来存储稀疏矩阵.比较常见的有:

对于稀疏矩阵的存储,为了达到压缩的目的(节省存储空间),只存储非0元素值,但是也要保留非零元素的位置,方便恢复.所以,我们存储时不仅存储非零元素值,同时存储其坐标位置(row,column). 针对这两者的存储,会出现不同的设计方案.这里主要介绍COO,CSR和CSC存储格式.

我们使用三个数组row,column和data分别用来存储非零元素坐标的row_index,col_index,以及数值.比如:

NNO:The number of nonzero.矩阵非零元素个数. 三个数组的长度都是NNO.data[i]在原稀疏矩阵中的坐标为(row[i],col[i]]).

可以发现,这种存储方式中,row数组和column数组中有一定的重复元素.我们是否可以针对这个冗余特性进一步进行压缩?之后出现CSR,CSC,分别是对row数组和column数组进行了压缩.

对COO稀疏矩阵存储格式的三个数组中的row数组进行压缩.其他两个数组保持不变;三个数组分别是row_ptr,columns和data.其中columns和data数组长度均为NNO(矩阵的非零元素个数). 如何对COO的row进行压缩?

row_ptr存储的是每行的第一个非零元素距离稀疏矩阵第一个元素的偏移位置;

由row_ptr我们可以知道每行非零元素在data中的index范围.第i行的非零元素为data[row_ptr[i]:row_ptr[i+1]],对data数组的切片,不包含data[row_ptr[i+1]];同时第i行非零元素的col坐标分别为columns[row_ptr[i]:row_ptr[i+1]];对data和columns的访问相似,index是相同的.

如上图中,第0行非零元素在data中是data[0:2],就是1,7;列坐标为columns[0:2],就是0,1,第1行非零元素为data[2:4],有两个元素2和8,列坐标分别为columns[2:4],1和2.

方便进行行操作.

和CSR类似.只不过对列进行压缩,row和data保持不变.

方便进行列操作.

4. 稀疏矩阵的压缩存储方式有

顺序存储、三元组表和十字链表。
1、顺序存储：将矩阵按照行号顺序依次存储，每一行的非零元素按照列号顺序依次存储。这种方式适用于行数较少，且行内非零元素分布较为均匀的稀疏矩阵。
2、三元组表：这是一种更为紧凑的存储方式，使用三个数组分别存储非零元素的行号、列号和值。假设矩阵中有m行n列，非零元素个数为nz，则三个数组的长度分别为mz、nz和nz。这种方式适用于行数较多，且行内非零元素分布不均匀的稀疏矩阵。
3、十字链表：这是一种链式存储方式，通过链表结构将每一行的非零元素连接起来，同时记录其列号和值。这种方式适用于需要频繁进行插入和删除操作的稀疏矩阵。