稀疏矩阵的存储方法（DOK、LIL、COO、CSR, CRS）

存储稀疏矩阵

经常用二维数组来存储矩阵。 用数组的$a_{i,j}$可以用索引值$i$和$j$访问。通常，$i$是 行索引，从上往下编号，$j$是列索引，从左到右进行编号。对于$m\times n$的矩阵，用这种格式存储需要的内存和$m\times n$成比例。

对于稀疏矩阵，如果只存储非零的数据，可以极大的节约内存。根据非零数据的数量和分布情况，有不同的数据结构可以使用。需要权衡的是访问单个元素时会比较复杂，并且需要额外的数据结构。

这些数据结构主要分为两组：

• ˙支持高效修改的，如关键字字典DOK（Dictionary of keys）、LIL（List of List）或COO（Coordinate List）。它们通常用于构造矩阵。
• 支持高效访问和矩阵操作的那些，例如CSR（压缩稀疏行）或CSC（压缩稀疏列）。

关键字词典（DOK）

DOK由一个将（行、列）作为关键字映射到元素值的字典组成。字典中缺少的元素将被视为零。这种格式有利于按随机顺序递增地构造稀疏矩阵，但不利于按字典顺序迭代非零值。通常用这种格式构造一个矩阵，然后转换成另一种更有效的格式进行处理。

嵌套列表（LIL – List of List）

LIL每行存储一个列表，每个条目包含列索引和值。通常，这些条目按列索引进行排序，以便更快地查找。这是另一种适合增量矩阵构造的格式。

坐标列表（COO）

COO存储（行、列、值）元组的列表。理想情况下，条目首先按行索引排序，然后按列索引排序，以提高随机访问时间。这是另一种适合增量矩阵构造的格式。

压缩稀疏行（CSR、CRS或耶鲁格式）

压缩稀疏行（CSR）或压缩行存储（CRS）或Yale格式表示由三个（一维）数组组成的矩阵M，这些数组分别包含非零值、行的范围和列索引。它类似于COO，但压缩行索引，因此得名。这种格式允许快速行访问和矩阵向量乘法（Mx）。CSR格式至少从20世纪60年代中期开始使用，第一次完整的描述出现在1967年

CSR格式使用三个（一维）数组（V，COL_INDEX，row_INDEX）以行的形式存储稀疏m×n矩阵m。设NNZ表示M中非零项的数量（注意，此处应使用从零开始的索引）

• 数组V和COL_INDEX的长度为NNZ，分别包含这些值的非零值和列索引。
• 数组ROW_INDEX在矩阵中每行有一个元素，并在给定行开始的地方将索引编码为V。（它可能包含一个设置为NNZ的额外结束元素）。

例如，矩阵

$$\left(\begin{array}{cccc}0& 0& 0& 0\\ 5& 8& 0& 0\\ 0& 0& 3& 0\\ 0& 6& 0& 0\end{array}\right)$$
是具有4个非零元素的4×4矩阵，因此

V=[5 8 3 6]
COL_INDEX=[0 1 2 1]
ROW_INDEX=[0 0 2 3 4]

假设是索引是从0开始的语言。
要提取行，我们首先定义：

row_start=ROW_INDEX[row]
row_end=ROW_INDEX[row+1]

然后我们从V和COL_INDEX中提取切片，从row_start到row_end。

为了访问这个矩阵的行1（第二行），我们设置row_start=0和row_end=2。然后我们将切片V[0:2]=[5，8]和COL_INDEX[0:2]=[0，1]。我们现在知道，在第1行的第0列和第1列有两个元素，值分别为5和8。

在这种情况下，CSR表示用了13个条目，而原始矩阵中只有16个条目。只有当$NNZ<（m（n-1)–1)/2$时，CSR格式才会节约内存。另一个例子，矩阵

$$\left(\begin{array}{cccccc}10& 20& 0& 0& 0& 0\\ 30& 0& 40& 0& 0& 0\\ 0& 0& 50& 60& 70& 0\\ 0& 0& 0& 0& 0& 80\end{array}\right)$$
是一个有8个非零元素的4×6矩阵（24个元素），所以

   V         = [ 10 20 30 40 50 60 70 80 ]
   COL_INDEX = [  0  1  1  3  2  3  4  5 ]   
   ROW_INDEX = [  0  2  4  7  8 ]

整个存储为21个条目。

ROW_INDEX将数组V拆分成行：（10，20）（30，40）（50，60，70）（80）；

列索引确定这些值的列：（10，20，…）（0，30，0，40，…）（0，0，50，60，70，0）（0，0，0，0，0，80）。
注意，在这种格式中，ROW_INDEX的第一个值始终为零，最后一个值始终为NNZ，因此它们在某种意义上是冗余的（尽管在需要显式存储数组长度的编程语言中，NNZ不会是冗余的）。尽管如此，这确实避免了在计算每一行的长度时处理异常情况的需要，因为这保证了公式$ro{w}_{I}NDEX[i+1]-ro{w}_{I}NDEX[i]$对任何一行i都有效。此外，对于足够大的矩阵来说，此冗余存储的内存成本是微不足道的。

耶鲁稀疏矩阵格式（新版或旧版）是CSR方案的实例。旧的Yale格式与上面描述的完全一样，有三个数组；新的格式将ROW_INDEX和COL_INDEX组合成一个数组，并分别处理矩阵的对角线。

对于逻辑邻接矩阵，可以省略数据数组，因为行数组中的元素的存在足以建模二元邻接关系。

它被称为耶鲁格式，可能因为它是在1977年耶鲁大学计算机科学系的耶鲁稀疏矩阵包报告中提出的。

压缩稀疏列（CSC或CCS）

CSC与CSR类似，不同之处在于首先按列读取值，为每个值存储一个行索引，并存储列指针。例如，CSC是（val，row_ind，col_ptr），其中val是矩阵的（从上到下，然后从左到右）非零值的数组；row_ind是对应于这些值的行索引；col_ptr是每列开始的val索引的列表。该名称基于列索引信息相对于COO格式进行压缩的事实。一种通常使用另一种格式（LIL、DOK、COO）进行构建。这种格式对于算术运算、列切片和矩阵向量积是有效的。见scipy.sparse.csc_矩阵. 这是在MATLAB中指定稀疏矩阵的传统格式（通过稀疏函数）。

参考文献
https://en.wikipedia.org/wiki/Sparse_matrix