Kuang Algorithm Engineer&Data Mining Engineer

稀疏矩阵(CSR,CSC)

2018-11-28
Kuang

在很多场景下会用到稀疏矩阵。例如推荐系统中,用户和物品之间的矩阵是非常稀疏的,大部分的矩阵元素是0。这时候如果用稠密的形式来存储矩阵,会造成很大的时间和空间的浪费。因此利用矩阵的稀疏性,可以把矩阵压缩成稀疏矩阵的表达形式。很多时候稀疏矩阵是必须的,试想如果存在上百万个用户和上千万个物品,如果用稠密矩阵存储用户购买物品次数的矩阵,正常情况下,矩阵有超过99%的元素为0,而稠密矩阵的元素个数为$10^6*10^7$个,一般的设备无法处理这种规模的矩阵。

稀疏矩阵的表达方式有很多种,例如Dictionary of key(DOK)、List of lists(LIL)、Coordinate list(COO)、Compressed sparse row(CSR,CRS or Yale format)以及Compressed sparse column(CSC or CCS)。这里主要介绍后两种。

凡事以例子说明最为直观,假设有如下矩阵

Compressed sparse row

那么CSR如何表达该矩阵呢?

首先先介绍CSR中的三个数组,A、IA、JA

A = [5,8,3,6]

A是存储矩阵所有非零元素的数组,元素顺序是行优先,即从左到右、从上往下

image-20181129145922052

IA = [0 0 2 3 4]

IA中的元素是递推得到的,IA元素的个数为行数(m)+1

IA[0] = 0

IA[1] = IA[0] + (第 i-1= 0 行非0元素的个数)

IA[2] = IA[1] + (第 i-1 =1 行非0元素的个数) 以此类推

这样,IA中的前m个元素存储的是矩阵每一行的第一个非0元在A中的下标(从0开始),第m+1个元素存储的是非0元素的个数。显而易见,第i行的非0元素是A[IA[i]] 到A[IA[i+1]-1] (例如,第0行的非零元素为A[IA[0]]~A[IA[1]-1],即A[0]~A[-1]即没有,第1行的非零元素为A[IA[0]]~A[IA[2]-1] 即A[0]~A[1])

第三个数组JA是A中每个元素的列索引

JA=[0 1 2 1]

通过A和IA,可以确定非0元素所在的行,通过JA和A可以知道每个元素所在的列。这样通过3个数组就能确定一个稀疏矩阵,显然,稀疏矩阵存储的元素远远小于稠密矩阵

Compressed sparse column

CSC和CSR类似,区别在于A数组构建是列优先,然后JA存储的是每个非0元素的行索引,当然,IA也是按照列来计算


Comments