C++實(shí)現(xiàn)特殊矩陣的壓縮存儲(chǔ)算法

更新時(shí)間：2022年08月16日 08:38:21 作者：一枚大果殼

在實(shí)際存儲(chǔ)時(shí)，會(huì)發(fā)現(xiàn)矩陣中有許多值相同的數(shù)據(jù)或有許多零數(shù)據(jù)，且分布呈現(xiàn)出一定的規(guī)律，稱這類型的矩陣為特殊矩陣。本文將利用C++實(shí)現(xiàn)特殊矩陣的壓縮存儲(chǔ)，感興趣的可以了解一下

1. 前言

什么是特殊矩陣？

C++，一般使用二維數(shù)組存儲(chǔ)矩陣數(shù)據(jù)。

在實(shí)際存儲(chǔ)時(shí)，會(huì)發(fā)現(xiàn)矩陣中有許多值相同的數(shù)據(jù)或有許多零數(shù)據(jù)，且分布呈現(xiàn)出一定的規(guī)律，稱這類型的矩陣為特殊矩陣。

為了節(jié)省存儲(chǔ)空間，可以設(shè)計(jì)算法，對這類特殊矩陣進(jìn)行壓縮存儲(chǔ)，讓多個(gè)相同的非零數(shù)據(jù)只分配一個(gè)存儲(chǔ)空間；對零數(shù)據(jù)不分配空間。

本文將講解如何壓縮這類特殊矩陣，以及壓縮后如何保證矩陣的常規(guī)操作不受影響。

2. 壓縮對稱矩陣

什么是對稱矩陣？

在一個(gè)n階矩陣A中，若所有數(shù)據(jù)滿足如下述特性，則可稱A為對稱矩陣。

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

i是數(shù)據(jù)在矩陣中的行號(hào)。

j是數(shù)據(jù)在矩陣中的列號(hào)。

0<<i,j<<n-1

在n階對稱矩陣 a[i][j]中，當(dāng)i==j(行號(hào)和列號(hào)相同)時(shí)所有元素所構(gòu)建成的集合稱為主對角線。

如下圖所示：

對稱矩陣以主對角線為分界線，把整個(gè)矩陣分成 2 個(gè)三角區(qū)域，主對角線之上的稱為上三角，主對角線之下的區(qū)域稱為下三角。

對稱矩陣的上三角和下三角區(qū)域中的元素是相同的，以n行n列的二維數(shù)組存儲(chǔ)時(shí)，會(huì)浪費(fèi)近一半的空間，可以采壓縮機(jī)制，將二維數(shù)組中的數(shù)據(jù)壓縮存儲(chǔ)在一個(gè)一維數(shù)組中，這個(gè)過程也稱為數(shù)據(jù)線性化。

線性過程時(shí)，一維數(shù)組的空間需要多大？

n階矩陣，使用二維數(shù)組存儲(chǔ)，理論上所需要的存儲(chǔ)單元應(yīng)該是 n2。

對稱矩陣以主對角線為分界線，上三角和下三角區(qū)域中的數(shù)據(jù)是相同的。注意，主對角線上的元素是需要單獨(dú)存儲(chǔ)的，主對角線上的數(shù)據(jù)個(gè)數(shù)為 n。

真正需要的存儲(chǔ)單元應(yīng)該：(理論上所需要的存儲(chǔ)單元-主對角線上的數(shù)據(jù)所需單元) / 2 +主對角線上的數(shù)據(jù)所需單元。

如下表達(dá)式所述：

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

所以，可以把n階矩陣中的數(shù)據(jù)可以全部壓縮在長度為 n(n+1)/2 的一維數(shù)組中，能節(jié)約近一半的存儲(chǔ)空間。并且n階矩陣和一維數(shù)組之間滿足如下的位置對應(yīng)關(guān)系：

i>=j 表示矩陣中的下三角區(qū)域(包含主對角線上數(shù)據(jù))。

i<j表示矩陣中的上三角區(qū)域。

轉(zhuǎn)存實(shí)現(xiàn)：

#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} };
	//一維數(shù)組，根據(jù)上述公式，一維數(shù)組長度為 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;
}

如上是二維數(shù)組壓縮到一維數(shù)組后的結(jié)果。

3. 壓縮稀疏矩陣

什么是稀疏矩陣？

如果矩陣A中的有效數(shù)據(jù)的數(shù)量遠(yuǎn)遠(yuǎn)小于矩陣實(shí)際能描述的數(shù)據(jù)的總數(shù)，則稱A為稀疏矩陣。

現(xiàn)假設(shè)有 m行n列的矩陣，其中所保存的元素個(gè)數(shù)為 c，則稀疏因子為：e=c/(m*n)。當(dāng)用二維數(shù)組存儲(chǔ)稀疏矩陣中數(shù)據(jù)時(shí)，僅有少部分空間被利用，可以采用壓縮機(jī)制來進(jìn)行存儲(chǔ)。

稀疏因子越小，表示有效數(shù)據(jù)越少。

稀疏矩陣中的非零數(shù)據(jù)的存儲(chǔ)位置是沒有規(guī)律的，在壓縮存儲(chǔ)時(shí)，除了需要記錄非零數(shù)據(jù)本身外還需要記錄其位置信息。所以需要一個(gè)三元組對象（i,j,a[i][j]）對數(shù)據(jù)進(jìn)行唯一性確定。

3.1 三元組表

為了便于描述，壓縮前的矩陣稱為原稀疏矩陣，壓縮后的稀疏矩陣稱三元組表矩陣。

原稀疏矩陣也好，三元組表矩陣也好。只要頂著矩陣這個(gè)概念，就應(yīng)該能進(jìn)行矩陣相應(yīng)的操作。矩陣的內(nèi)置操作有很多，本文選擇矩陣的轉(zhuǎn)置操作來對比壓縮前和壓縮后的算法差異性。

什么是矩陣轉(zhuǎn)置？

如有 m行n列的A 矩陣，所謂轉(zhuǎn)置，指把A變成 n行m列的 B矩陣。A和B滿足 A[i][j]=B[j][i]。即A的行變成B的列。如下圖所示：

A稀疏矩陣轉(zhuǎn)置成B稀疏矩陣的原生實(shí)現(xiàn)：

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

基于原生矩陣上的轉(zhuǎn)置算法，其時(shí)間復(fù)雜度為 O(m*n)，即O(n2)。

從存儲(chǔ)角度而言，aArray矩陣和其轉(zhuǎn)置后的bArray矩陣都是稀疏矩陣，使用二維數(shù)組存儲(chǔ)會(huì)浪費(fèi)大量的空間。有必要對其以三元組表的形式進(jìn)行壓縮存儲(chǔ)。

三元組表是一個(gè)一維數(shù)組，因其中的每一個(gè)存儲(chǔ)位置需要存儲(chǔ)原稀疏矩陣中非零數(shù)據(jù)的3 個(gè)信息（行，列，值）。三元組表名由此而來，也就是說數(shù)組中存儲(chǔ)的是對象。

先來一個(gè)圖示，直觀上了解一下A稀疏矩陣壓縮前后的差異性。

壓縮算法實(shí)現(xiàn)：

#include <iostream>
using namespace std;
typedef int DataType;
#define maxSize 100
//三元組結(jié)構(gòu)
struct Node {
	//行號(hào)
	int row=-1;
	//列號(hào)
	int col=-1;
	//非零元素的值
	DataType val=0;
} ;

//維護(hù)三元組表的類
class Matrix {
	private:
		//位置編號(hào)
		int idx=0;
		//壓縮前稀疏矩陣的行數(shù)
		int rows;
		//壓縮前稀疏矩陣的列數(shù)
		int cols;
		//原稀疏矩陣中非零數(shù)據(jù)的個(gè)數(shù)
		int terms;
		//壓縮存儲(chǔ)的一維數(shù)組，初始化
		Node node;
		Node data[maxSize]= {node};
	public:
		//構(gòu)造函數(shù)
		Matrix(int row,int col) {
			this->rows=row;
			this->cols=col;
             this->terms=0;
		}
		//存儲(chǔ)三元結(jié)點(diǎn)
		void setData(int row ,int col,int val) {
			Node n;
			n.row=row;
			n.col=col;
			n.val=val;
			this->data[idx++]=n;
             //記錄非零數(shù)據(jù)的數(shù)量
             this->terms++;
		}
        //重載上面函數(shù)
    	void setData(int index,int row ,int col,int val) {
			Node n;
			n.row=row;
			n.col=col;
			n.val=val;
			this->data[index]=n;
			this->terms++;
		}
		//顯示三無組表中的數(shù)據(jù)
		void showInfo() {
			for(int i=0; i<maxSize; i++ ) {
				if(data[i].val==0)break;
				cout<<data[i].row<<"\t"<<data[i].col<<"\t"<<data[i].val<<endl;
			}
		}
		//基于三元組表的轉(zhuǎn)置算法
		Matrix transMatrix();
};

int main(int argc, char** argv) {
	//原稀疏矩陣
	int aArray[4][5]= {{0,5,0,1,0},{0,0,3,0,0},{0,7,0,0,0},{0,0,9,0,0}};
	//實(shí)例化
	Matrix matrix(4,5);
	//壓縮矩陣
	for(int row=0; row<4; row++) {
		for(int col=0; col<5; col++) {
			if (aArray[row][col]!=0) {
                 //轉(zhuǎn)存至三元組表中
				matrix.setData(row,col,aArray[row][col]);
			}
		}
	}
	matrix.showInfo();
	return 0;
}

代碼執(zhí)行后的結(jié)果和直觀圖示結(jié)果一致：

壓縮之后，則要思考，如何在A三元組表的基礎(chǔ)上直接實(shí)現(xiàn)矩陣的轉(zhuǎn)置?；蛘哒f ，轉(zhuǎn)置后的矩陣還是使用三元組表方式描述。

先從直觀上了解一下，轉(zhuǎn)置后的B矩稀疏陣的三元組表的結(jié)構(gòu)應(yīng)該是什么樣子。

是否可以通過直接交換A的三元組表中行和列位置中的值？至于可不可以，可以先用演示圖推演一下：

從圖示可知，如果僅是交換A三元組表的行和列位置后得到的新三元組表并不和前面所推演出現(xiàn)的B三元組表一致。

如果仔細(xì)觀察，可發(fā)現(xiàn)得到的新三元組表的是對原B稀疏表以列優(yōu)先遍歷后的結(jié)果。

B稀疏矩陣的三元組表顯然應(yīng)該是以行優(yōu)先遍歷的結(jié)果。

3.2 以列優(yōu)先搜索

經(jīng)過轉(zhuǎn)置后，A稀疏矩陣的行會(huì)變成B稀疏矩陣的列，也可以說A的列變成B的行。如果在A中以列優(yōu)先搜索，則相當(dāng)于在B中以行優(yōu)先進(jìn)行搜索?？衫眠@個(gè)簡單而又令人興奮的道理實(shí)現(xiàn)基于三元組表的轉(zhuǎn)置。

Matrix Matrix::transMatrix(){
	//轉(zhuǎn)置后的三元組表對象
	Matrix bMatrix(this->cols,this->rows);
	//對原稀疏矩陣以列優(yōu)先搜索
	for(int c=0;c<this->cols;c++){
		//在對應(yīng)的三元組表上查找此列上是否有非零數(shù)據(jù)
	 	for(int j=0;j<this->terms;j++ ){
	 		if(this->data[j].col==c){
	 			//如果此列上有數(shù)據(jù)，則轉(zhuǎn)置并保存
				bMatrix.setData(this->data[j].col,this->data[j].row,this->data[j].val);  
			 }
		 } 
	}
	return  bMatrix;
}

測試代碼：

int main(int argc, char** argv) {
//原稀疏矩陣
int aArray[4][5]= {{0,5,0,1,0},{0,0,3,0,0},{0,7,0,0,0},{0,0,9,0,0}};
//實(shí)例化壓縮矩陣
Matrix matrix(4,5);
//壓縮矩陣
for(int row=0; row<4; row++) {
	for(int col=0; col<5; col++) {
		if (aArray[row][col]!=0) {
			matrix.setData(row,col,aArray[row][col]);
		}
	}
}
cout<<"顯示 A 稀疏矩陣壓縮后的結(jié)果："<<endl; 
matrix.showInfo();
cout<<"在A的三元組表的基礎(chǔ)上轉(zhuǎn)置后的結(jié)果："<<endl;
Matrix bMatrix= matrix.transMatrix();
bMatrix.showInfo(); 	 
return 0;
}

輸出結(jié)果：

代碼執(zhí)行后輸出的結(jié)果，和前文推演出來的結(jié)果是一樣的。

前文可知，基于原生稀疏矩陣上的轉(zhuǎn)置時(shí)間復(fù)雜度為 O(m*n)?；谌M表的時(shí)間復(fù)雜度=稀疏矩陣的列數(shù)乘以稀疏矩陣中非零數(shù)據(jù)的個(gè)數(shù)。當(dāng)稀疏矩陣中的元素個(gè)數(shù)為n*m時(shí)，則上述的時(shí)間復(fù)雜度會(huì)變成 O（m*n2）。

3.3 找出存儲(chǔ)位置

上述算法適合于當(dāng)稀疏因子較小時(shí)，當(dāng)矩陣中的非零數(shù)據(jù)較多時(shí)，時(shí)間復(fù)雜度會(huì)較高。可以在上述列優(yōu)先搜索的算法基礎(chǔ)上進(jìn)行優(yōu)化。

其核心思路如下所述：

在原A稀疏矩陣中按列優(yōu)先進(jìn)行搜索。
統(tǒng)計(jì)每一列中非零數(shù)據(jù)的個(gè)數(shù)。
記錄每一列中第一個(gè)非零數(shù)據(jù)在B三元組表中的位置。

對A稀疏矩陣按列遍歷時(shí)，可以發(fā)現(xiàn)，掃描時(shí)，數(shù)據(jù)出現(xiàn)的順序和其在B三元組表中的存儲(chǔ)順序是一致的。

如果在遍歷時(shí)，能記錄每列非零數(shù)據(jù)在B三元組表中應(yīng)該存儲(chǔ)的位置，則可以實(shí)現(xiàn)A三元組表中的數(shù)據(jù)直接以轉(zhuǎn)置要求存儲(chǔ)在B三元組表中。

重寫上述的轉(zhuǎn)置函數(shù)。

Matrix Matrix::transMatrix() {
	//保存轉(zhuǎn)置后數(shù)據(jù)的壓縮矩陣
	Matrix bMatrix(this->cols,this->rows);
	//初始化數(shù)組，用來保存A稀疏矩陣中第一列中非零數(shù)據(jù)的個(gè)數(shù)
	int counts[this->cols]= {0};
	//計(jì)算每一列中非零數(shù)據(jù)個(gè)數(shù)
	for(int i=0; i<this->terms; i++)
		counts[this->data[i].col]++;
	//初始化數(shù)組，用來保存A稀疏矩陣每列中非零數(shù)據(jù)在B三元組表中的起始位置
	int position[this->cols]= {0};	
	for(int i=1;i<this->cols;i++ ){
        //上一列的起始位置加上上一列非零數(shù)據(jù)的個(gè)數(shù)
		position[i]=position[i-1]+counts[i-1];
	}
    //轉(zhuǎn)置A三元組表
    for(int i=0;i<this->terms;i++){ 
    	int col=this->data[i].col;
    	int row=this->data[i].row;
    	int val=this->data[i].val;
    	//找到在B三元組中的起始存儲(chǔ)位置
		int pos=position[col];
		bMatrix.setData(pos,col,row,val);
		position[col]++;	
	} 
	return  bMatrix;
}

測試代碼不需要任何變化：

int main(int argc, char** argv) {
	//原稀疏矩陣
	int aArray[4][5]= {{0,5,0,1,0},{0,0,3,0,0},{0,7,0,0,0},{0,0,9,0,0}};
	//實(shí)例化壓縮矩陣
	Matrix matrix(4,5);
	//壓縮矩陣
	for(int row=0; row<4; row++) {
		for(int col=0; col<5; col++) {
			if (aArray[row][col]!=0) {
				matrix.setData(row,col,aArray[row][col]);
			}
		}
	}
	cout<<"顯示 A 稀疏矩陣壓縮后的結(jié)果："<<endl;
	matrix.showInfo();
	cout<<"在A的三元組表的基礎(chǔ)上轉(zhuǎn)置后的結(jié)果："<<endl;
	Matrix bMatrix= matrix.transMatrix();
	bMatrix.showInfo();
	return 0;
}

輸出結(jié)果：