在用python便编写推荐相关算法时，用到了scipy中的sparse matrix来存储相似矩阵或评分数据。本文是对行压缩与列压缩ccs的总结，因为二者原理是一致的，所以只总结crs的原理。
Compressed Row Storage (CRS)
一般，我们要取矩阵中的一个值 $val$ 需要知道其行索引 $row_ind$ 和列索引$col_ind$，假设矩阵中非0值为nnz个，需要3nnz的空间存储$row_ind$、$col_ind$和$val$。CRS，顾名思义，就是对列索引$row_ind$进行了压缩。
如下所示，三个列表值索引了整个稀疏矩阵，其中行索引压缩为行指针，它存储了矩阵每一行在 $val$ 中开始的位置。
项 | 含义
:—— |:——
val | 非0值列表
col_ind | 列索引列表
row_ptr | 行指针列表
下面举一个具体的例子，假设有矩阵$A$如下：
将矩阵$A$转为CRS格式，如下(索引下标从1开始)：
可以看到 $row_ptr$明显短于另外两个列表，因为它只需要$n+1$的空间，$n$表示矩阵行数。这里解释一下$row_ind$中的值，假设$val(k)=A[i,j]$，那么$row_ptr(i) \leqslant val(k)< row_ptr(i)$。
比如，我们要取值$A[2,1]$，因为$row_ptr2=3$，$row_ptr3=6$，索引范围锁定在[3，6）之间，因为$col_ind3=1$，所以$val3=3$就是我们要取的值，可以看出get操作的时间复杂度是大于O(1)的。
但是这就是所谓的空间换时间吗？并不是。在scipy的稀疏矩阵库的使用过程中，可以感受到每种压缩方式都有各自的优缺点。行压缩和列压缩方式的矩阵算术操作效率很高，从数据结构中我们也可以看到，CRS可以很方便地锁定单行的范围。例如在计算itemcf相似矩阵的时候，需要获取用户$u$的物品列表，使用CRS的效率会非常高。
参考
scipy sparse matrix
Compressed Row Storage
Compressed Column Storage