数据结构重读 – 矩阵的压缩和存储

矩阵在数值运算中很常见,本节关注如何存储矩阵的元,从而使矩阵的各种运算能有效进行。

如果矩阵中有许多相同值的元素或者很多零元素。有时为了节省存储空间,可以对这类矩阵进行存储压缩,称为稀疏矩阵。更进一步的,如果稀疏矩阵的相同值或零元素分布还是有规律的,我们可以称他们为特殊矩阵

对称矩阵

例如:

1 2 4
2 3 5
4 5 6

我们可以为每一对称元分配一个存储空间,即可以将n^2个元压缩存储到n*(n+1)/2个空间中。

假设在线性(一元)数组中存储,下标是k。m[i][j]是矩阵中第i行第j列的元素,则:

当i>=j时,a[k] = m[i][j],k=i*(i-1)/2 + j -1

当i<j时,a[k] = m[i][j],k = j*(j-1)/2 +i -1

稀疏矩阵

设在m*n的矩阵中,有t个元素非零,则a=t/(m*n)称为稀疏因子,当a<=0.05,即只有不到5%的元素非零时,称为稀疏矩阵

在很多问题中,实际都是稀疏矩阵。

压缩存储可以只存储非零元,例如用一个三元组表示:(i, j, val),i和j是行、列,val是矩阵位置的元素值。

注意:在如下三元组存储中,data是从下标0开始的。但是矩阵的行、列是从1开始的!

下面是数据结构定义、初始化、打印等操作:

快速转置算法

这样的存储虽然省了不少空间,但是在一些操作如转置时算法复杂度会上升很多。因为你无法再随机访问m[i][j]了。针对这种情况,有了如下的快速转置算法。它使用两个辅助向量,nrows和frows。这里的rows都是针对转置结果矩阵T而言的。(我们假设从矩阵M转置称为矩阵T)

首先计算nrows,它表示矩阵T中每一行有多少个非空元素即三元组需要存储。实际上也就是M中列j为对应nrows下标的。于是我们扫描一遍M.data的所有元素,对应j在nrows下标中++即可。

然后计算frows,就是T矩阵每一行第一个元素应该位于T的data的哪个位置。初始的第一个frows[1] = 0。这个需要解释下,因为矩阵行列开始都是1,所以frows里面是1,但是data存储是从0开始,所以起始是0。

最后就是快速转置算法,利用上面两个向量就很简单了,直接上代码:

 

 

 

Leave a Reply

Your email address will not be published.