稀疏矩阵存储格式

布帛矛 2019-01-13

展开全文

当运算数据数量很大且稀疏的时候，使用稀疏的数据存储格式可以节省大量的存储空间且加快计算速度。本文介绍三种比较常见的稀疏矩阵表示方式：COO（Coordinate Format坐标表示），CSR（Compressed Sparse Row行压缩），CSC（Compressed Sparse Column列压缩）。

1、COO：Coordinate Format COO格式使用行下标、列下标和数据值三元组来表示每个非零元素，所以总共需要保存非零元素个数的三倍个值

>>> import scipy
>>> import numpy as np
>>> row_idx = np.array([0,0,1,2,2,3,3,3])
>>> col_idx = np.array([0,3,1,2,3,0,1,3])
>>> values = np.array([4,2,1,5,7,6,3,8])
>>> coo_mat = scipy.sparse.coo_matrix((values, (row_idx , col_idx)),shape = (4,4)).toarray()
>>> coo_mat
array([[4, 0, 0, 2],
       [0, 1, 0, 0],
       [0, 0, 5, 7],
       [6, 3, 0, 8]])

row_idx 和col_idx 指定values 中每个数据对应的行下标和列下标。

2、 CSR：Compressed Sparse Row CSR格式的列下标向量和数据值向量与COO格式类似，在行下标表示上做了压缩。根据数据的排列规则，只需要指定在哪个数据换到下一行就行。

>>> col_idx = np.array([0,3,1,2,3,0,1,3])
>>> values = np.array([4,2,1,5,7,6,3,8])
>>> row_ptr = np.array([0,2,3,5,8])
>>> csr_mat = scipy.sparse.csr_matrix((values,col_idx, row_ptr),shape=(4,4)).toarray()
>>> csr_mat
array([[4, 0, 0, 2],
       [0, 1, 0, 0],
       [0, 0, 5, 7],
       [6, 3, 0, 8]])

把非零数据排成一列，并从0开始建立索引，row_ptr指定在哪个索引位置进行换行。例如，稀疏矩阵的第二行是1，那么就在索引2处进行切割。

3、 CSC：Compressed Sparse Column CSC格式的行下标和数据值向量与COO格式类似，在列下标上做了压缩。根据数据的排列规则，只需要指定在哪个数据换到下一列就行。

>>> values = np.array([4,6,1,3,5,2,7,8])
>>> row_idx = np.array([0,3,1,3,2,0,2,3])
>>> col_ptr = np.array([0,2,4,5,8])
>>> csc_mat = scipy.sparse.csc_matrix((values,row_idx,col_ptr),shape=(4,4)).toarray()
>>> csc_mat
array([[4, 0, 0, 2],
       [0, 1, 0, 0],
       [0, 0, 5, 7],
       [6, 3, 0, 8]])