C++實現特殊矩陣的壓縮存儲算法
1. 前言
什么是特殊矩陣？
C++，一般使用二維數組存儲矩陣數據。
在實際存儲時，會發(fā)現矩陣中有許多值相同的數據或有許多零數據，且分布呈現出一定的規(guī)律，稱這類型的矩陣為特殊矩陣。
為了節(jié)省存儲空間，可以設計算法，對這類特殊矩陣進行壓縮存儲，讓多個相同的非零數據只分配一個存儲空間；對零數據不分配空間。
本文將講解如何壓縮這類特殊矩陣，以及壓縮后如何保證矩陣的常規(guī)操作不受影響。
2. 壓縮對稱矩陣
什么是對稱矩陣？
在一個n階矩陣A中，若所有數據滿足如下述特性，則可稱A為對稱矩陣。
a[i][j]==a[j][i]
i是數據在矩陣中的行號。
j是數據在矩陣中的列號。
0<<i,j<<n-1
在n階對稱矩陣 a[i][j]中，當i==j(行號和列號相同)時所有元素所構建成的集合稱為主對角線。
如下圖所示：
對稱矩陣以主對角線為分界線，把整個矩陣分成 2 個三角區(qū)域，主對角線之上的稱為上三角，主對角線之下的區(qū)域稱為下三角。
對稱矩陣的上三角和下三角區(qū)域中的元素是相同的，以n行n列的二維數組存儲時，會浪費近一半的空間，可以采壓縮機制，將 二維數組中的數據壓縮存儲在一個一維數組中，這個過程也稱為數據線性化。
線性過程時，一維數組的空間需要多大？
n階矩陣，使用二維數組存儲，理論上所需要的存儲單元應該是 n2。
對稱矩陣以主對角線為分界線，上三角和下三角區(qū)域中的數據是相同的。注意，主對角線上的元素是需要單獨存儲的，主對角線上的數據個數為 n。
真正需要的存儲單元應該：(理論上所需要的存儲單元-主對角線上的數據所需單元) / 2 +主對角線上的數據所需單元。
如下表達式所述：
(n2-n)/2+n=n(n+1)/2
所以，可以把n階矩陣中的數據可以全部壓縮在長度為 n(n+1)/2 的一維數組中，能節(jié)約近一半的存儲空間。并且n階矩陣和一維數組之間滿足如下的位置對應關系：
i>=j 表示矩陣中的下三角區(qū)域(包含主對角線上數據)。
i<j表示矩陣中的上三角區(qū)域。
轉存實現：
#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)。當用二維數組存儲稀疏矩陣中數據時，僅有少部分空間被利用，可以采用壓縮機制來進行存儲。
稀疏因子越小，表示有效數據越少。
稀疏矩陣中的非零數據的存儲位置是沒有規(guī)律的，在壓縮存儲時，除了需要記錄非零數據本身外還需要記錄其位置信息。所以需要一個三元組對象（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(n2)。
從存儲角度而言，aArray矩陣和其轉置后的bArray矩陣都是稀疏矩陣，使用二維數組存儲會浪費大量的空間。有必要對其以三元組表的形式進行壓縮存儲。
三元組表是一個一維數組，因其中的每一個存儲位置需要存儲原稀疏矩陣中非零數據的3 個信息（行，列，值）。三元組表名由此而來，也就是說數組中存儲的是對象。
先來一個圖示，直觀上了解一下A稀疏矩陣壓縮前后的差異性。
壓縮算法實現：
#include <iostream>
using namespace std;
typedef int DataType;
#define maxSize 100
//三元組結構
struct Node {
//行號
int row=-1;
//列號
int col=-1;
//非零元素的值
DataType val=0;
} ;
//維護三元組表的類
class Matrix {
private:
//位置編號
int idx=0;
//壓縮前稀疏矩陣的行數
int rows;
//壓縮前稀疏矩陣的列數
int cols;
//原稀疏矩陣中非零數據的個數
int terms;
//壓縮存儲的一維數組，初始化
Node node;
Node data[maxSize]= {node};
public:
//構造函數
Matrix(int row,int col) {
this->rows=row;
this->cols=col;
this->terms=0;
}
//存儲三元結點
void setData(int row ,int col,int val) {
Node n;
n.row=row;
n.col=col;
n.val=val;
this->data[idx++]=n;
//記錄非零數據的數量
this->terms++;
}
//重載上面函數
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++;
}
//顯示三無組表中的數據
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;
}
}
//基于三元組表的轉置算法
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}};
//實例化
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]);
}
}
}
matrix.showInfo();
return 0;
}
代碼執(zhí)行后的結果和直觀圖示結果一致：
壓縮之后，則要思考，如何在A三元組表的基礎上直接實現矩陣的轉置?；蛘哒f ，轉置后的矩陣還是使用三元組表方式描述。
先從直觀上了解一下，轉置后的B矩稀疏陣的三元組表的結構應該是什么樣子。
是否可以通過直接交換A的三元組表中行和列位置中的值？至于可不可以，可以先用演示圖推演一下：
從圖示可知，如果僅是交換A三元組表的行和列位置后得到的新三元組表并不和前面所推演出現的B三元組表一致。
如果仔細觀察，可發(fā)現得到的新三元組表的是對原B稀疏表以列優(yōu)先遍歷后的結果。
B稀疏矩陣的三元組表顯然應該是以行優(yōu)先遍歷的結果。
3.2 以列優(yōu)先搜索
經過轉置后，A稀疏矩陣的行會變成B稀疏矩陣的列，也可以說A的列變成B的行。如果在A中以列優(yōu)先搜索，則相當于在B中以行優(yōu)先進行搜索?？衫眠@個簡單而又令人興奮的道理實現基于三元組表的轉置。
Matrix Matrix::transMatrix(){
//轉置后的三元組表對象
Matrix bMatrix(this->cols,this->rows);
//對原稀疏矩陣以列優(yōu)先搜索
for(int c=0;c<this->cols;c++){
//在對應的三元組表上查找此列上是否有非零數據
for(int j=0;j<this->terms;j++ ){
if(this->data[j].col==c){
//如果此列上有數據，則轉置并保存
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}};
//實例化壓縮矩陣
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 稀疏矩陣壓縮后的結果："<<endl;
matrix.showInfo();
cout<<"在A的三元組表的基礎上轉置后的結果："<<endl;
Matrix bMatrix= matrix.transMatrix();
bMatrix.showInfo();
return 0;
}
輸出結果：
代碼執(zhí)行后輸出的結果，和前文推演出來的結果是一樣的。
前文可知，基于原生稀疏矩陣上的轉置時間復雜度為 O(m*n)?；谌M表的 時間復雜度=稀疏矩陣的列數乘以稀疏矩陣中非零數據的個數。當稀疏矩陣中的元素個數為n*m時，則上述的時間復雜度會變成 O（m*n2）。
3.3 找出存儲位置
上述算法適合于當稀疏因子較小時，當矩陣中的非零數據較多時，時間復雜度會較高?？梢栽谏鲜隽袃?yōu)先搜索的算法基礎上進行優(yōu)化。
其核心思路如下所述：
- 在原A稀疏矩陣中按列優(yōu)先進行搜索。
- 統(tǒng)計每一列中非零數據的個數。
- 記錄每一列中第一個非零數據在
B三元組表中的位置。
對A稀疏矩陣按列遍歷時，可以發(fā)現，掃描時，數據出現的順序和其在B三元組表中的存儲順序是一致的。
如果在遍歷時，能記錄每列非零數據在B三元組表中應該存儲的位置，則可以實現A三元組表中的數據直接以轉置要求存儲在B三元組表中。
重寫上述的轉置函數。
Matrix Matrix::transMatrix() {
//保存轉置后數據的壓縮矩陣
Matrix bMatrix(this->cols,this->rows);
//初始化數組，用來保存A稀疏矩陣中第一列中非零數據的個數
int counts[this->cols]= {0};
//計算每一列中非零數據個數
for(int i=0; i<this->terms; i++)
counts[this->data[i].col]++;
//初始化數組，用來保存A稀疏矩陣每列中非零數據在B三元組表中的起始位置
int position[this->cols]= {0};
for(int i=1;i<this->cols;i++ ){
//上一列的起始位置加上上一列非零數據的個數
position[i]=position[i-1]+counts[i-1];
}
//轉置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三元組中的起始存儲位置
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}};
//實例化壓縮矩陣
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 稀疏矩陣壓縮后的結果："<<endl;
matrix.showInfo();
cout<<"在A的三元組表的基礎上轉置后的結果："<<endl;
Matrix bMatrix= matrix.transMatrix();
bMatrix.showInfo();
return 0;
}
輸出結果：
上述 2 種轉置算法，其本質是一樣的，第一種方案更容易理解，第二種方案在第一種方案的基礎上用空間換取了時間上性能的提升。
4. 總結
使用二維數組存儲矩陣中數據時，如果矩陣中的有效數據較小時，可以采用壓縮的方式對其進行存儲。
本文著重講解如何使用三元組表方式壓縮存儲稀疏矩陣。轉存過程并不難，難點在于轉存為三元組表后，如何在三元組表的基礎上正常進行矩陣相關操作。
以上就是C++實現特殊矩陣的壓縮存儲算法的詳細內容，更多關于C++矩陣壓縮存儲的資料請關注腳本之家其它相關文章！
相關文章
AVL樹是高度平衡的而二叉樹,它的特點是AVL樹中任何節(jié)點的兩個子樹的高度最大差別為1,本文主要給大家介紹了C++如何實現AVL樹,需要的朋友可以參考下2022-06-06
這篇文章主要為大家介紹了C語言中數組的使用，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-12-12
全網最接地氣的C語言野指針介紹，此處對于野指針與空指針知識點做一些簡要的介紹，作者實屬初學，寫博客也是作者學習的一個過程，難免文章中有內容理解不到位或者有不當之處，還請朋友們不吝指正，希望大家多多給予支持，贈人玫瑰，手有余香2021-11-11
這篇文章主要為大家詳細介紹了C++?vector的簡單實現，使用數據庫，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
本文主要介紹了vscode終端中打不開conda虛擬包管理的解決,文中通過圖文介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-09-09
這篇文章主要為大家詳細介紹了OpenCV實現人臉檢測功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
這篇文章主要為大家詳細介紹了OpenCV實現人臉檢測的相關資料，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章給大家介紹了使用C/C++讀取matlab中.mat格式數據的操作,文中通過圖文結合的方式介紹的非常詳細,對大家的學習或工作有一定的幫助,需要的朋友可以參考下2023-12-12
C++是不支持根據類名動態(tài)地生成對象的,比如從一個文本文件中讀取類名然后構造一個對象.主要原因是沒有豐富的動態(tài)元信息，沒有單根類庫。那么下面這篇文章就來給大家介紹C++是如何動態(tài)的生成對象，有需要的朋友們可以參考借鑒。2017-02-02
這篇文章主要介紹了關于C語言文件操作方法的相關資料,小編覺得這篇文章寫的還不錯，需要的朋友可以參考下，希望能夠給你帶來幫助2021-11-11