C++ 特殊矩阵的压缩存储算法

1. 前言

什么是特殊矩阵？

C++，一般使用二维数组存储矩阵数据。

在实际存储时，会发现矩阵中有许多值相同的数据或有许多零数据，且分布呈现出一定的规律，称这类型的矩阵为特殊矩阵。

为了节省存储空间，可以设计算法，对这类特殊矩阵进行压缩存储，让多个相同的非零数据只分配一个存储空间；对零数据不分配空间。

本文将讲解如何压缩这类特殊矩阵，以及压缩后如何保证矩阵的常规操作不受影响。

2. 压缩对称矩阵

什么是对称矩阵？

在一个n阶矩阵A中，若所有数据满足如下述特性，则可称A为对称矩阵。

• a[i][j]==a[j][i]

  i是数据在矩阵中的行号。

  j是数据在矩阵中的列号。

• 0<<i,j<<n-1

在n阶对称矩阵 a[i][j]中，当i==j(行号和列号相同)时所有元素所构建成的集合称为主对角线。

如下图所示：

对称矩阵以主对角线为分界线，把整个矩阵分成 2 个三角区域，主对角线之上的称为上三角，主对角线之下的区域称为下三角。

对称矩阵的上三角和下三角区域中的元素是相同的，以n行n列的二维数组存储时，会浪费近一半的空间，可以采压缩机制，将 二维数组中的数据压缩存储在一个一维数组中，这个过程也称为数据线性化。

线性过程时，一维数组的空间需要多大？

n阶矩阵，使用二维数组存储，理论上所需要的存储单元应该是 n²。

对称矩阵以主对角线为分界线，上三角和下三角区域中的数据是相同的。注意，主对角线上的元素是需要单独存储的，主对角线上的数据个数为 n。

真正需要的存储单元应该：(理论上所需要的存储单元-主对角线上的数据所需单元) / 2 +主对角线上的数据所需单元。

如下表达式所述：

(n²-n)/2+n=n(n+1)/2

所以，可以把n阶矩阵中的数据可以全部压缩在长度为 n(n+1)/2 的一维数组中，能节约近一半的存储空间。并且n阶矩阵和一维数组之间满足如下的位置对应关系：

i>=j 表示矩阵中的下三角区域(包含主对角线上数据)。

i<j表示矩阵中的上三角区域。

转存实现：

#include <iostream>
using namespace std;
int main(int argc, char** argv) {
	//对称矩阵
	int nums[4][4]= { {3,5,6,8},{5,4,7,9},{6,7,12,10},{8,9,10,13} };
	//一维数组，根据上述公式，一维数组长度为 4*(4+1)/2=10
	int zipNums[10]= {0};
	for(int i=0; i<4; i++) {
		for(int j=0; j<4; j++) {
			if (i>=j) {
				zipNums[ i*(i+1)/2+j]=nums[i][j];
			} else {
				zipNums[ j*(j+1)/2+i]=nums[i][j];
			}
		}
	}
	for(int i=0; i<10; i++) {
		cout<<zipNums[i]<<"/t";
	}
	return 0;
}

如上是二维数组压缩到一维数组后的结果。

3. 压缩稀疏矩阵

什么是稀疏矩阵？

如果矩阵A中的有效数据的数量远远小于矩阵实际能描述的数据的总数，则称A为稀疏矩阵。

现假设有 m行n列的矩阵，其中所保存的元素个数为 c，则稀疏因子为：e=c/(m*n)。当用二维数组存储稀疏矩阵中数据时，仅有少部分空间被利用，可以采用压缩机制来进行存储。

稀疏因子越小，表示有效数据越少。

稀疏矩阵中的非零数据的存储位置是没有规律的，在压缩存储时，除了需要记录非零数据本身外还需要记录其位置信息。所以需要一个三元组对象（i,j,a[i][j]）对数据进行唯一性确定。

3.1 三元组表

为了便于描述，压缩前的矩阵称为原稀疏矩阵，压缩后的稀疏矩阵称三元组表矩阵。

原稀疏矩阵也好，三元组表矩阵也好。只要顶着矩阵这个概念，就应该能进行矩阵相应的操作。矩阵的内置操作有很多，本文选择矩阵的转置操作来对比压缩前和压缩后的算法差异性。

什么是矩阵转置？

如有 m行n列的A 矩阵，所谓转置，指把A变成 n行m列的 B矩阵。A和B满足 A[i][j]=B[j][i]。即A的行变成B的列。如下图所示：

A稀疏矩阵转置成B稀疏矩阵的原生实现：

//原矩阵
int aArray[4][5]= {{0,5,0,1,0},{0,0,3,0,0},{0,7,0,0,0},{0,0,9,0,0}};
//转置后矩阵
int bArray[5][4];
//转置算法 
for(int row=0; row<4; row++) {
	for(int col=0; col<5; col++) {
		bArray[col][row]=aArray[row][col];
	}
}

基于原生矩阵上的转置算法，其时间复杂度为 O(m*n)，即O(n²)。

从存储角度而言，aArray矩阵和其转置后的bArray矩阵都是稀疏矩阵，使用二维数组存储会浪费大量的空间。有必要对其以三元组表的形式进行压缩存储。

本站声明：
1. iCode9 技术分享网（下文简称本站）提供的所有内容，仅供技术学习、探讨和分享；

2. 关于本站的所有留言、评论、转载及引用，纯属内容发起人的个人观点，与本站观点和立场无关；

3. 关于本站的所有言论和文字，纯属内容发起人的个人观点，与本站观点和立场无关；

4. 本站文章均是网友提供，不完全保证技术分享内容的完整性、准确性、时效性、风险性和版权归属；如您发现该文章侵犯了您的权益，可联系我们第一时间进行删除；

5. 本站为非盈利性的个人网站，所有内容不会用来进行牟利，也不会利用任何形式的广告来间接获益，纯粹是为了广大技术爱好者提供技术内容和技术思想的分享性交流网站。