什么是稀疏矩阵?
如果在矩阵中,多数的元素为0,称此矩阵为稀疏矩阵(sparse matrix)。假设在m x n
的矩阵中,有t个不为零的元素,令δ=t/(mxn)
,称δ
为矩阵的稀疏因子。通常认为δ<=0.05
时才称为稀疏。
稀疏矩阵压缩
与特殊矩阵的压缩不同,特殊矩阵压缩是通过将非零元的有规律的分布通过函数映射到一维数组上;稀疏矩阵的分布没有规律,除了有很多的零。
稀疏矩阵压缩的方法:
- 三元数组存储(行,列,值)
- 行指针链表(第一列为数组,用指针链接到本行下一个不为零的位置)
- 十字链表(有点复杂,不只是矩阵,有正交关系的都可以用它)
不同压缩方式的一些算法
一定意义上说算法是依托着数据格式的,稀疏矩阵的不同压缩方式的某些操作是比较好的,这里只总结了这些,一些比较简单的操作此处没有介绍。
三元组–矩阵转置
刚看到这个转置的时候感觉也是比较简单的,细想一下其实要保持有序的话可能没那么简单了。
暴力
这种是比较容易想到的,直接有序的方式进行扫描三元组,则得到的转置就是有序的。比如m x n
的矩阵,有序指的是:当转置成n x m
时,按照n
的有序的方式扫描出转置的值。再不理解下面看代码:
typedef struct {
int i,j; //该非零元的行下标i和列下标j
ElemType e; //矩阵存储的元素
} Triple;
typedef struct {
Triple data[MAXSIZE]; //非零三元组表
int mu,nu,tu; //矩阵的行数、列数、非零元个数
} TSMatrix;
Status TransposeSMatrix(TSMatrix M, TSMatrix &T) {
//采用三元组表存储表示,求稀疏矩阵M的转置矩阵T。
T.mu = M.nu;
T.nu = M.mu;
T.tu = M.tu;
if(T.tu) {
q=0;
for(col=0; col<M.nu; ++col) { //按列循环
for(p=0; p<M.tu; ++p) { //扫描整个矩阵
if(M.data[p].j == col) { //列标等于列循环的列标
T.data[q].i = M.data[p].j;
T.data[q].j = M.data[p].i;
T.data[q].e = M.data[p].e; //转置
++q;
}
}
}
}
return OK;
}
算法复杂度显而易见:O(nu*tu)
非常稀疏的话勉强可以忍,也就只能适用于tu<<mu*nu
。
三元组–快速转置
这个算法充分利用了矩阵三元组数组的随机读写的特性。在转置前求得M
的每一列中非零元的个数,进而可以求得每一列的第一个非零元在T.data
中应有的位置。
肯定是需要辅助空间的:
num[col]
:表示矩阵M中第col列中非零元的个数;cpot[col]
:表示M中第col列的第一个非零元在T.data
中的位置。 显然:cpot[1]=1
cpot[col]=cpot[col-1]+num[col-1] 2<=col<=M.nu
算法思想已经很显而易见了,如果说暴力算法是搜索非零元在T.data
中应有的位置的话,那这个算法这个位置是通过计算得到的,降低了搜索消耗的时间。
代码如下:
Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) {
//采用的依然是三元组顺序表存储表示
T.mu = M.nu;
T.nu = M.mu;
T.tu = M.tu;
if(T.tu) {
for(col=0; col<M.nu; ++col) {
num[col] = 0;
}
for(t=0; t<M.tu; ++t) {
++num[M.data[t].j]; //求M中每一列含非零元个数
}
cpot[0] = 1;
//求第col列中第一个非零元在T.data中的序号
for(col=1; col<M.nu; ++col) {
cpot[col] = cpot[col-1] + num[col-1];
}
for(p=0; p<M.tu; ++p) {
col = M.data[p].j;
q = cpot[col];
T.data[q].i = M.data[p].j;
T.data[q].j = M.data[p].i;
T.data[q].e = M.data[p].e;
++cpot[col];
}
}
return OK;
}
时间复杂度也是显而易见的:O(nu+tu)
,比暴力算法提高了不少。
三元组–排序法
这种效率并不高,依赖排序算法效率与特性。
- 如果是稳定的排序算法,则可以把
M.data
依次赋给T.data
后排序; 代码:Status SortTransposeSMatrix(TSMatrix M, TSMatrix &T) { //采用的依然是三元组顺序表存储表示 T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if(T.tu) { for(t=0; t < tu; ++t) { T.data[t].i = M.data[t].j; T.data[t].j = M.data[t].i; T.data[t].e = M.data[t].e; } sort(T); //此处的排序是稳定的排序算法,按照T.data[].i排序 } return OK; }
解释:因为
M.data
是有序的,即:在M.data
上i
是有序的,j
也是有序的,而在T.data
中按i
排序相当于在M.data
中按j
排序,由于排序算法是稳定的,则排序结果一定会有T.data
中j
也是有序的,即M.data
中i
依然有序。 时间复杂度显而易见:O(tu)+O(sort)
(O(sort)
是排序算法的时间复杂度) - 如果排序算法不稳定,则需要多次排序,效率不高,不再详述。
总结:可以看出无论排序算法多么优秀,时间复杂度依然赶不上快速转置算法的效率。
三元组的改进表示
由快速转置算法可以看出有时行位置信息很有用,比如上面的转置、矩阵乘等;所以可以将行信息也存在存储结构中:
typedef struct {
Triple data[MAXSIZE]; //同上
int rpos[MAXRC]; //各行第一个非零元的位置表
int mu,nu,tu; //同上
} RLSMatrix;
二元组顺序表
从三元组顺序表中去掉行下标得到二元组顺序表,另设一个行起始向量,其每个分量是二元组顺序表的一个下标值,指示该行中第一个非零元素在二元组顺序表中的起始位置。 代码表示如下:
typedef struct{
int j;
int e;
} DSElem;
typedef struct{
DSElem data[MAXSIZE];
int rpot[MAXROW+1]; //存储每一行在二元组中的起始位置
int mu,nu,tu;
} DSMatrix; //二元组表
其实它也只是三元组的一个变形,由于使用的是二元组存储,相对三元组存储信息少了,所以在创建的过程中需要辅助空间,而且效率也不高。
十字链表
十字链表:链表中每个非零元可用一个含5个域的节点表示,其中i、j和e这三个域和三元组表示法的含义相同,分别表示该非零元所在的行、列和非零元的值;向右域right
可以链接同一行的下一个非零元,向下域down
可以链接同一列中下一个非零元。同一行的非零元通过right
域链接成一个线性链表,同一列的非零元通过down
域也链接成一个线性链表;每个非零元既是某个行链表中的一个节点,又是某个列链表中的一个节点,这个矩阵构成了一个许多十字交叉的链表,故称这样的存储结构为十字链表。
这种存储结构在处理大量元素移动的操作时非常方便,如节点插入、删除,矩阵加等。
十字链表的代码表示:
typedef struct OLNode {
int i,j;
ElemeType e;
struct OLNode *right, *down;
} OLNode; *OLink;
typedef struct {
OLink *rhead, *chead;
int mu,nu,tu;
} CrossList;
总结自:《数据结构(C语言版)》 清华大学出版社 严蔚敏、吴伟民编著