① 多維數組-矩陣的壓縮存儲- 稀疏矩陣（一）
稀疏矩陣
設矩陣A mn 中有s個非零元素 若s遠遠小於矩陣元素的總數(即s< <m×n)，則稱a為稀疏矩陣。 p=""> </m×n)，則稱a為稀疏矩陣。>
1、稀疏矩陣的壓縮存儲
為了節省存儲單元，可只存儲非零元素。由於非零元素的分布一般是沒有規律的，因此在存儲非零元素的同時，還必須存儲非零
元素所在的行號、列號，才能迅速確定一個非零元素是矩陣中的哪一個元素。稀疏矩陣的壓縮存儲會失去隨機存取功能。
其中每一個非零元素所在的行號、列號和值組成一個三元組(i，j，a ij )，並由此三元組惟一確定。
稀疏矩陣進行壓縮存儲通常有兩類方法：順序存儲和鏈式存儲。鏈式存儲方法【參見參考書目】。
2、三元組表
將表示稀疏矩陣的非零元素的三元組按行優先(或列優先)的順序排列(跳過零元素)，並依次存放在向量中，這種稀疏矩陣的順序
存儲結構稱為三元組表。
注意：
以下的討論中，均假定三元組是按行優先順序排列的。
【例】下圖(a)所示的稀疏矩陣A的三元組表表示見圖(b)
(1)三元組表的類型說明
為了運算方便，將矩陣的總行數、總列數及非零元素的總數均作為三元組表的屬性進行描述。.WINGwIT.其類型描述為：
#define MaxSize 10000 //由用戶定義
typedef int DataType; //由用戶定義
typedef struct { //三元組
int i，j;//非零元的行、列號
DataType v; //非零元的值
}TriTupleNode;
typedef struct{ //三元組表
TriTupleNode data[MaxSize]; //三元組表空間
int m,n，t; //矩陣的行數、列數及非零元個數
}TriTupleTable;
(2) 壓縮存儲結構上矩陣的轉置運算
一個m×n的矩陣A，它的轉置矩陣B是一個n×m的矩陣，且：
A[i][j]=B[j][i]，0≤i <m，0≤j<n， p=""> </m，0≤j<n，>
即A的行是B的列，A的列是B的行。
【例】下圖中的B和上圖中的A互為轉置矩陣。
①三元組表表示的矩陣轉置的思想方法
第一步：根據A矩陣的行數、列數和非零元總數確定B矩陣的列數、行數和非零元總數。
第二步：當三元組表非空(A矩陣的非零元不為0)時，根據A矩陣三元組表的結點空間data(以下簡稱為三元組表)，將A的三
元組表a->data置換為B的三元組表b->data。
②三元組表的轉置
方法一:簡單地交換a->data中i和j中的內容，得到按列優先順序存儲倒b->data;再將b->data重排成按行優先順序的三元組表。
方法二:由於A的列是B的行，因此，按a->data的列序轉置，所得到的轉置矩陣B的三元組表b->data必定是按行優先存放的。
按這種方法設計的演算法，其基本思想是：對A中的每一列col(0≤col≤a->n-1)，通過從頭至尾掃描三元組表a->data，找出所有
列號等於col的那些三元組，將它們的行號和列號互換後依次放人b->data中，即可得到B的按行優先的壓縮存貯表示。具體實現參見
【 動畫演示 】
③具體演算法：
void TransMatrix(TriTupleTable *b，TriTupleTable *a)
{//*a，*b是矩陣A、B的三元組表表示，求A轉置為B
int p，q，col;
b->m=a->n; b->n=a->m; //A和B的行列總數互換
b->t=a->t; //非零元總數
if(b->t<=0)
Error("A=0"); //A中無非零元，退出
q=0;
for(col=0;coln;col++) //對A的每一列
for(p=0;pt;p++) //掃描A的三元組表
if(a->data[p].j==col){ //找列號為col的三元組
b->data[q).i=a->data[p].j;
b->data[q].j=a->data[p].i;
b->data[q].v=a->data[p].v;
q++;
}
} //TransMatrix
④演算法分析
該演算法的時間主要耗費在col和p的二重循環上：
若A的列數為n，非零元素個數t，則執行時間為O(n×t)，即與A的列數和非零元素個數的乘積成正比。
通常用二維數組表示矩陣時，其轉置演算法的執行時間是O(m×n)，它正比於行數和列數的乘積。
由於非零元素個數一般遠遠大於行數，因此上述稀疏矩陣轉置演算法的時間大於通常的轉置演算法的時間。
lishixin/Article/program/sjjg/201311/23897
② 稀疏矩陣的存儲空間
一個稀疏矩陣中有許多元素等於零,這便於矩陣的計算和保存.如果Matlab把一個矩陣當作稀疏矩陣,那麼只需在m×3的矩陣中存儲m個非零項.第1列是行下標,第2列是列下標,第3列是非零元素值,不必保存零元素.如果存儲一個浮點數要8個位元組,存儲每個下標要4個位元組,那麼整個矩陣在內存中存儲需要1 6×m個位元組.
A = e y e ( 1 0 0 0 ) ;
得到一個1 0 0 0×1 0 0 0的單位矩陣,存儲它需要8 MB空間.如果使用命令:
B = s p e y e ( 1 0 0 0 ) ;
用一個1 0 0 0×3的矩陣來代表,每行包含有一個行下標,列下標和元素本身.只需1 6 K B的空間就可以存儲1 0 0 0×1 0 0 0的單位矩陣,它只需要滿單位矩陣的0 . 2 %存儲空間.對於許多的廣義矩陣也可這樣來作.
③ 稀疏矩陣定義以及存儲格式(COO,CSR,CSC)
網路:在矩陣中，若數值為0的元素數目遠遠多於非0元素的數目，並且非0元素分布沒有規律時，則稱該矩陣為稀疏矩陣；與之相反，若非0元素數目佔大多數時，則稱該矩陣為稠密矩陣。定義非零元素的總數比上矩陣所有元素的總數為矩陣的稠密度。 簡單來說,稀疏矩陣就是絕大部分都是0的矩陣 ,只包含很少的非零值.
比如,
上述稀疏矩陣非零元素有9個,26個零值.稀疏性是74%.
稀疏矩陣因為絕大部分都是0元素,如果我們仍然按照普通方式存儲,無疑會 浪費很多空間 ;同時如果進行運算時,0元素對最終結果也沒有幫助, 增加了許多無效計算 . 因此,我們需要設計出新的存儲方式,或者說數據結構來存儲稀疏矩陣.比較常見的有:
對於稀疏矩陣的存儲,為了達到壓縮的目的(節省存儲空間),只存儲非0元素值,但是也要保留非零元素的位置,方便恢復.所以,我們存儲時不僅存儲非零元素值,同時存儲其坐標位置(row,column). 針對這兩者的存儲,會出現不同的設計方案.這里主要介紹COO,CSR和CSC存儲格式.
我們使用三個數組row,column和data分別用來存儲非零元素坐標的row_index,col_index,以及數值.比如:
NNO:The number of nonzero.矩陣非零元素個數. 三個數組的長度都是NNO.data[i]在原稀疏矩陣中的坐標為(row[i],col[i]]).
可以發現,這種存儲方式中,row數組和column數組中有一定的重復元素.我們是否可以針對這個冗餘特性進一步進行壓縮?之後出現CSR,CSC,分別是對row數組和column數組進行了壓縮.
對COO稀疏矩陣存儲格式的三個數組中的row數組進行壓縮.其他兩個數組保持不變;三個數組分別是row_ptr,columns和data.其中columns和data數組長度均為NNO(矩陣的非零元素個數). 如何對COO的row進行壓縮?
row_ptr存儲的是每行的第一個非零元素距離稀疏矩陣第一個元素的偏移位置;
由row_ptr我們可以知道每行非零元素在data中的index范圍.第i行的非零元素為data[row_ptr[i]:row_ptr[i+1]],對data數組的切片,不包含data[row_ptr[i+1]];同時第i行非零元素的col坐標分別為columns[row_ptr[i]:row_ptr[i+1]];對data和columns的訪問相似,index是相同的.
如上圖中,第0行非零元素在data中是data[0:2],就是1,7;列坐標為columns[0:2],就是0,1,第1行非零元素為data[2:4],有兩個元素2和8,列坐標分別為columns[2:4],1和2.
方便進行行操作.
和CSR類似.只不過對列進行壓縮,row和data保持不變.
方便進行列操作.
④ 稀疏矩陣壓縮存儲：CSR/CSC (Compress Sparse Row/Column)
假設有一非對稱 矩陣A，用CSR表示需要三個向量： val , col_ind , row_ptr 。表示的意義為：
, then
, then
並約定： ，其中， 為A中非零值的個數
它的CSR表示為：
特別說明一下 row_ptr 的表示含義：
如 row_ptr[2]=3 ，表明矩陣A中第二行（從左至右）的第一個非零值是A中所有非零值的第3個； row_ptr[5]=13 ，表明矩陣A中第五行（從左至右）的第一個非零值是A中所有非零值的第13個； row_ptr[7]=20 指示A中非零值nnz的個數：nnz=20-1=19。
更新CSC的介紹 ：它的基本思想和CSR完全相同，可以看作CSR的轉置，因此這里僅對CSC進行簡單的舉例介紹。以Song Han的EIE論文為例，PE應存儲的weight矩陣為（相同顏色的對應一個PE）：
這一矩陣的採用CSC表示為：
解釋 」：和上面的CSR表示不同，這里的索引從0開始（上面的CSR舉例從1開始，當然也可以從0開始）。index對應的是非零值所在行的index，而pointer指示原始矩陣中每列非零值的數量，pointer的最後一位指示矩陣中非零值的個數。
如 pointer[1]=3 ，表明第二列之前（第一列）含三個非零值，第二列（由上至下）第一個非零值應是所有非零值中的第四個； pointer[2]=4 ，表明第三列之前有四個非零值，第三列（由上至下）第一個非零值應是所有非零值中的第五個； pointer[3] 和 pointer[4] 相等，表明第四列沒有非零值；最後， pointer[8]=13 ，表示weight矩陣中共有13個非零值。
需要注意的是，這里的Row index是相對的，即相對前一個非零值或第一行的index，上面的CSR中的Column index是絕對的。 可根據實際要求選擇絕對或相對表示。
⑤ 稀疏矩陣的壓縮存儲只需要存儲什麼
非零元素。
對於一個用二維數組存儲的稀疏矩陣Amn，如果假設存儲每個數組元素需要L個位元組，那麼存儲整個矩陣需要m*n*L個位元組。但是，這些存儲空間的大部分存放的是0元素，從而造成大量的空間浪費。為了節省存儲空間，可以只存儲其中的非0元素。
(5)稀疏矩陣存儲單元擴展閱讀
稀疏矩陣演算法的最大特點是通過只存儲和處理非零元素從而大幅度降低存儲空間需求以及計算復雜度，代價則是必須使用專門的稀疏矩陣壓縮存儲數據結構。稀疏矩陣演算法是典型的不規則演算法，計算訪存比很低，並且計算過程中的訪存軌跡與稀疏矩陣的稀疏結構相關。
⑥ 稀疏矩陣一般的壓縮存儲方法有兩種
分別是三元組和十字鏈表。
三元組是指形如（（x，y），z）的集合（這就是說，三元組是這樣的偶，其第一個射影亦是一個偶），常簡記為（x，y，z）。
三元組是計算機專業的一門公共基礎課程——數據結構里的概念。主要是用來存儲稀疏矩陣的一種壓縮方式，也叫三元組表。假設以順序存儲結構來表示三元組表（triple table），則得到稀疏矩陣的一種壓縮存儲方式，即三元組順序表，簡稱三元組表。
十字鏈表（Orthogonal List)是有向圖的另一種鏈式存儲結構。該結構可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的。用十字鏈表來存儲有向圖，可以達到高效的存取效果。同時，代碼的可讀性也會得到提升。
拓展資料：
十字鏈表（Orthogonal List)是有向圖的另一種鏈式存儲結構。可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的一種鏈表。在十字鏈表中，對應於有向圖中每一條弧都有一個結點，對應於每個定頂點也有一個結點。
十字鏈表之於有向圖，類似於鄰接表之於無向圖。
也可以理解為 將行的單鏈表和列的單鏈表結合起來存儲稀疏矩陣稱為十字鏈表， 每個節點表示一個非零元素。
三元組解釋：
1、所謂「三元組」是指圖形的幾何元素構成、圖線間的拓撲關系和尺寸約束。如果一組圖形的前二元相同而只是尺寸大小不同，則這組圖形構成一族形狀相同的系列化圖形。
2、把組成一個元素的三個數稱為三元組。一個三元組包含以下三部分的內容SDO_STARTING_OFFSET表明每個幾何元素的第一個坐標在SDO_ORDINATES數組中的存儲位置。
3、…Mt：N2）的表示稱為三元組...…Mt稱為標號，N1、N2為結點R為關系。當n≠0時，稱Li為對結點N1的修飾。t≠0時，稱Mj為對結點N2的修飾。
參考資料：網路：十字鏈表
網路：三元組
⑦ 對稀疏矩陣進行壓縮存儲的目的是什麼
對稀疏矩陣進行壓縮存儲目的是節省存儲空間。
存儲矩陣的一般方法是採用二維數組，其優點是可以隨機地訪問每一個元素，因而能夠較容易地實現矩陣的各種運算。
但對於稀疏矩陣而言，若用二維數組來表示，會重復存儲了很多個0了，浪費空間，而且要花費時間來進行零元素的無效計算。所以必須考慮對稀疏矩陣進行壓縮存儲。
(7)稀疏矩陣存儲單元擴展閱讀
優點
稀疏矩陣的計算速度更快，因為MATLAB只對非零元素進行操作，這是稀疏矩陣的一個突出的優點。假設矩陣A,B中的矩陣一樣，計算2*A需要一百萬次的浮點運算，而計算2*B只需要2000次浮點運算。
因為MATLAB不能自動創建稀疏矩陣，所以要用特殊的命令來得到稀疏矩陣。算術和邏輯運算都適用於稀疏矩陣。對於一個用二維數組存儲的稀疏矩陣Amn，如果假設存儲每個數組元素需要L個位元組，那麼存儲整個矩陣需要m*n*L個位元組。