許春榮　買買提依明·哈斯木

【摘? 要】 矩陣在數(shù)據(jù)存儲(chǔ)、機(jī)器學(xué)習(xí)、圖像處理、自然語言處理中有著廣泛的應(yīng)用。稀疏矩陣是指矩陣中非零元素的個(gè)數(shù)較少的類型。數(shù)據(jù)結(jié)構(gòu)這門課程作為高校計(jì)算機(jī)基礎(chǔ)的一門課程，主要介紹的是計(jì)算機(jī)科學(xué)中用于組織和管理數(shù)據(jù)的方法和技術(shù)，其中包括介紹稀疏矩陣的內(nèi)容。目前，一些教材在數(shù)據(jù)數(shù)組存儲(chǔ)介紹上，對稀疏矩陣這個(gè)章節(jié)內(nèi)容講解較少，僅為理論內(nèi)容，有些具體應(yīng)用沒有敘述清楚，容易使學(xué)生理解不深。為此，文章介紹具體案例，講解稀疏矩陣的存儲(chǔ)特點(diǎn)以及在計(jì)算效率上的優(yōu)越性，讓學(xué)生更好地理解稀疏矩陣，也更好地掌握數(shù)據(jù)結(jié)構(gòu)這門課的內(nèi)涵。

【關(guān)鍵詞】 數(shù)據(jù)結(jié)構(gòu)；稀疏矩陣；計(jì)算效率

數(shù)據(jù)結(jié)構(gòu)是高等學(xué)校大部分理工類專業(yè)本科學(xué)生在學(xué)校必須完成的基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)課程主要介紹的是計(jì)算機(jī)科學(xué)中用于組織和管理數(shù)據(jù)的方法和技術(shù)。它涉及存儲(chǔ)、組織、操作和檢索數(shù)據(jù)的不同數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計(jì)和分析。通過學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程，學(xué)生可以培養(yǎng)良好的問題分析與解決能力，提高程序設(shè)計(jì)和算法實(shí)現(xiàn)的效率，為進(jìn)一步學(xué)習(xí)計(jì)算機(jī)科學(xué)的相關(guān)課程打下堅(jiān)實(shí)的基礎(chǔ)。學(xué)生對該課程的掌握情況將影響到后續(xù)專業(yè)課程的學(xué)習(xí)及邏輯思維方式和程序設(shè)計(jì)思想的建立。在數(shù)據(jù)結(jié)構(gòu)中，數(shù)組的存儲(chǔ)是重要的內(nèi)容，其中包括特殊矩陣——稀疏矩陣存儲(chǔ)。

目前，一些教材在數(shù)據(jù)數(shù)組存儲(chǔ)介紹上對稀疏矩陣這個(gè)章節(jié)內(nèi)容講解較少，主要介紹稀疏矩陣的壓縮存儲(chǔ)方式，一些具體應(yīng)用沒有敘述清楚，容易使學(xué)生理解不深，為此，需要在教學(xué)中對稀疏矩陣加以介紹，適當(dāng)?shù)丶右恍┯?jì)算機(jī)案例教學(xué)，設(shè)計(jì)案例講解稀疏矩陣的概念。本研究將通過一些例題實(shí)驗(yàn)對稀疏矩陣在存儲(chǔ)和計(jì)算上進(jìn)行介紹，并和一般稠密型矩陣進(jìn)行比較，對比介紹稀疏矩陣的特點(diǎn)和優(yōu)越性。

一、稀疏矩陣

稀疏矩陣在數(shù)據(jù)存儲(chǔ)、機(jī)器學(xué)習(xí)、圖像處理、自然語言處理以及工程上有著廣泛的應(yīng)用。稀疏矩陣是指在一個(gè)二維矩陣中，絕大部分元素都是零的矩陣。與稠密矩陣（大部分元素非零）相比，稀疏矩陣的特點(diǎn)是具有較少的非零元素，占據(jù)整個(gè)矩陣的很小一部分（一般小于5%）。稀疏矩陣的應(yīng)用方面有很多，包括在線性代數(shù)上，如矩陣運(yùn)算、求解線性方程組、特征值計(jì)算等。

在圖論和網(wǎng)絡(luò)分析中，稀疏矩陣常用于表示圖結(jié)構(gòu)、網(wǎng)絡(luò)連接等。在自然語言處理中，稀疏矩陣常用于文本特征表示和文本分類任務(wù)。在圖像處理中，稀疏矩陣常用于壓縮和圖像恢復(fù)任務(wù)。例如壓縮感知技術(shù)利用稀疏矩陣表示圖像，可以實(shí)現(xiàn)高效的圖像壓縮和重建。常見的稀疏矩陣有帶型陣，塊三角，塊對角陣，單面鑲邊的帶型陣，雙面鑲邊的帶型陣等。由于稀疏矩陣它的特點(diǎn)，可以從存儲(chǔ)上對矩陣的運(yùn)算做一些描述，以便更好理解稀疏矩陣。

已有較多學(xué)者對稀疏矩陣的存儲(chǔ)進(jìn)行研究，焦點(diǎn)在于設(shè)計(jì)合適的存儲(chǔ)結(jié)構(gòu)，并在此基礎(chǔ)上進(jìn)行高效的稀疏矩陣運(yùn)算。

存儲(chǔ)矩陣的一般方法是采用二維數(shù)組，其優(yōu)點(diǎn)是可以隨機(jī)訪問每一個(gè)元素，因而能夠?qū)崿F(xiàn)矩陣的各種運(yùn)算。但對稀疏矩陣而言，會(huì)重復(fù)存儲(chǔ)多個(gè)無效元素，這浪費(fèi)了內(nèi)存空間，而且不方便查看有效數(shù)據(jù)的位置，花費(fèi)大量時(shí)間來進(jìn)行行列元素的無效計(jì)算。所以必須考慮對稀疏矩陣進(jìn)行壓縮存儲(chǔ)。稀疏矩陣的壓縮存儲(chǔ)方式有多種，主要有以下幾種：

1. COO（Coordinate）格式。COO格式使用三個(gè)數(shù)組分別存儲(chǔ)非零元素的行坐標(biāo)、列坐標(biāo)和對應(yīng)的數(shù)值。

2. CSR（Compressed Sparse Row）格式。CSR格式是常用的稀疏矩陣存儲(chǔ)壓縮格式。CSR格式使用三個(gè)數(shù)組分別存儲(chǔ)非零元素的數(shù)值、列索引和行指針。行指針數(shù)組記錄每行第一個(gè)非零元素在數(shù)值數(shù)組中的位置索引。這種格式適用于按行訪問稀疏矩陣的情況，可以高效地存儲(chǔ)和計(jì)算稀疏矩陣。

3. CSC（Compressed Sparse Column）格式。這種格式和CSR相同，只是矩陣元按列壓縮存儲(chǔ)，CSC使用三個(gè)數(shù)組分別存儲(chǔ)非零元素的數(shù)值、行索引和列指針。列指針數(shù)組記錄每列第一個(gè)非零元素在數(shù)值數(shù)組中的索引位置。這種格式適用于按列訪問稀疏矩陣的情況。

4. DOK（Dictionary of Keys）格式。DOK格式使用一個(gè)字典（鍵—值對）來存儲(chǔ)非零元素的位置和數(shù)值。字典的鍵表示元素的行列索引，值表示對應(yīng)的數(shù)值。這種格式適用于動(dòng)態(tài)稀疏矩陣或矩陣結(jié)構(gòu)頻繁變化的情況。

5. BSR（Block Compressed Sparse Row）格式。BSR格式將稀疏矩陣分為固定大小的塊，并對每個(gè)塊存儲(chǔ)非零元素的數(shù)值、列索引和塊指針。這種格式適用于擁有塊結(jié)構(gòu)的稀疏矩陣。

不同的稀疏矩陣表示形式具有不同的優(yōu)勢和適用場景。選擇合適的表示形式可以最大限度減少存儲(chǔ)空間的使用和提高矩陣操作的效率。本文主要采用第一種存儲(chǔ)方式COO（Coordinate）格式進(jìn)行存儲(chǔ)。COO使用三個(gè)數(shù)組分別存儲(chǔ)非零元素的行坐標(biāo)、列坐標(biāo)和對應(yīng)的數(shù)值，是一種三元組順序表壓縮存儲(chǔ)方式。當(dāng)一個(gè)數(shù)組中大部分元素為0，或者為同一個(gè)值的數(shù)組值，可以使用三元組順序表來保存該數(shù)組。稀疏數(shù)組的處理方法是把具有非零值的元素的行列記錄在一個(gè)三元組的順序表中，每個(gè)數(shù)據(jù)元素都是以三元組的方式組成的，即（i，j，aij），其中i表示行，j表示列，aij表示元素。利用三元組存儲(chǔ)，可以減少存儲(chǔ)空間，這樣矩陣以小規(guī)模的數(shù)組存儲(chǔ)，從而縮小程序的規(guī)模。

二、稀疏矩陣的案例設(shè)計(jì)

稀疏矩陣是一種特殊的矩陣，由于跟一般矩陣有著不同的特點(diǎn)，學(xué)生的學(xué)習(xí)理解比較淺層，為了讓學(xué)生能在學(xué)習(xí)中對稀疏矩陣有更好的理解，教師可通過設(shè)計(jì)一些案例進(jìn)行講解，讓學(xué)生理解更透徹。案例設(shè)計(jì)主要包括稀疏矩陣的存儲(chǔ)以及計(jì)算效率的特點(diǎn)介紹。

（一）稀疏矩陣的存儲(chǔ)特點(diǎn)

例1：設(shè)A為一個(gè)200*200的單位矩陣。

其稀疏程度如圖1所示。

此時(shí)A為稀疏矩陣，利用稀疏數(shù)組形式存儲(chǔ)，即利用三元組順序存儲(chǔ)，如表1。

查看兩個(gè)矩陣的存儲(chǔ)空間，原矩陣存儲(chǔ)，稀疏矩陣數(shù)組存儲(chǔ)空間大小對比如表2所示。

從結(jié)果可以看出，以稀疏矩陣三元組順序表存儲(chǔ)，存儲(chǔ)空間為4808bit，以一般矩陣形式存儲(chǔ)為320000bit，以一般矩陣存儲(chǔ)占用的空間是以三元組順序表存儲(chǔ)空間的66倍，可見，稀疏矩陣采用三元組順序表存儲(chǔ)的方法可以大大節(jié)省存儲(chǔ)空間。

（二）稀疏矩陣在計(jì)算上的特點(diǎn)

稀疏矩陣在加法、乘法上以及一些特征值的計(jì)算有著更高的效率。下文通過案例介紹。

例2：求解稀疏矩陣的特征值，A為1000*1000的矩陣，除了三條對角線為1外，其余都為0，這里對A矩陣求特征向量值，再用稀疏矩陣數(shù)組形式求解特征值。

利用Matlab編程運(yùn)算，得到運(yùn)行結(jié)果，從運(yùn)行結(jié)果可以看出，利用原矩陣和稀疏數(shù)組形式計(jì)算出來特征值一樣，而在計(jì)算時(shí)間上，一般形式矩陣計(jì)算為0.0115s，利用稀疏矩陣求解特征值為0.0115s，這說明采用稀疏數(shù)組的形式計(jì)算特征值速度也會(huì)更快，更加節(jié)省時(shí)間。稀疏矩陣在逆矩陣的求解上也具有較快的速度，如例3。

例3：設(shè)A矩陣為可逆稀疏矩陣，采用稀疏數(shù)組方式進(jìn)行求逆，并與一般形式矩陣形式求逆矩陣做對比。

利用Matlab運(yùn)算，得到運(yùn)行結(jié)果，從結(jié)果看出，若矩陣A為稀疏矩陣，采用稀疏數(shù)組形式以及一般形式矩陣，對其齊求逆矩陣，求得的解都一樣，而其求解的速度原矩陣計(jì)算時(shí)間為0.0183s，稀疏數(shù)組計(jì)算需要的時(shí)間為4.7550e-04s，用稀疏數(shù)組計(jì)算逆矩陣速度要快于一般形式矩陣求解逆矩陣，可見稀疏數(shù)組在求解上有更高的效率，還可以應(yīng)用一些數(shù)學(xué)知識(shí)求解。另外，在求解方程組時(shí)，稀疏矩陣在計(jì)算上效率也更高，如例4。

例4：設(shè)A矩陣為三對角矩陣，Ax=b；采用稀疏數(shù)組方式進(jìn)行求逆，并與一般形式矩陣求解方程組做對比。

利用Matlab運(yùn)算，得到運(yùn)行結(jié)果。從運(yùn)行結(jié)果可以看出，利用一般形式矩陣和稀疏矩陣形式計(jì)算出來方程組的解是一樣的，而在計(jì)算時(shí)間上，一般形式矩陣計(jì)算為0.0780s，利用稀疏數(shù)組求解特征值為7.0070e-04s，可見用稀疏數(shù)組的形式計(jì)求解方程組速度會(huì)更快，效率更高。

三、結(jié)語

稀疏矩陣作為一種特殊矩陣，在數(shù)學(xué)上、工程上有較好的運(yùn)用，本研究通過列舉案例介紹稀疏矩陣的存儲(chǔ)和計(jì)算，對稀疏矩陣的介紹進(jìn)一步補(bǔ)充說明，可以較好地理解稀疏矩陣的稀疏數(shù)組形式與一般矩陣形式在存儲(chǔ)上和計(jì)算上的區(qū)別。從例子的結(jié)果可以看出，稀疏矩陣數(shù)組形式在存儲(chǔ)上可以較地好降低存儲(chǔ)空間，而在計(jì)算上，包括稀疏矩陣的特征值，逆矩陣的計(jì)算以及求解方程組上都有較高的效率。通過這樣的例子，學(xué)生可以對教材中稀疏矩陣有更好的理解。由于稀疏矩陣的特點(diǎn)，在工程上，比如機(jī)器學(xué)習(xí)，圖像處理，文本分類上，如果矩陣為稀疏矩陣，那么可以采用稀疏矩陣數(shù)組形式進(jìn)行存儲(chǔ)和計(jì)算，從而減小存儲(chǔ)空間，提高處理效率。稀疏矩陣在存儲(chǔ)和計(jì)算上具有優(yōu)越的特點(diǎn)，如果是非稀疏矩陣，即矩陣在高數(shù)據(jù)密度（50%以上）下，一個(gè)完整的矩陣總是比一個(gè)稀疏的矩陣快，所以教學(xué)時(shí)要根據(jù)矩陣的具體特點(diǎn)，做相應(yīng)的處理，以更好地提高效率。

參考文獻(xiàn)：

［1］ 嚴(yán)蔚敏，李冬梅. 數(shù)據(jù)結(jié)構(gòu)（C語言版）（第2版）［M］. 北京：人民郵電出版社，2021.

［2］ 李向華，王震，高超. 面向數(shù)據(jù)結(jié)構(gòu)的“C程序設(shè)計(jì)”教學(xué)改進(jìn)策略［J］. 西南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2023，48（05）：111-115.

［3］ 曹中瀟，馮仰德，王玨，等. 基于深度學(xué)習(xí)的稀疏矩陣向量乘運(yùn)算性能預(yù)測模型［J］. 計(jì)算機(jī)工程，2022，48（02）：86-91.

［4］ 李佳佳，張秀霞，譚光明，等. 選擇稀疏矩陣乘法最優(yōu)存儲(chǔ)格式的研究［J］. 計(jì)算機(jī)研究與發(fā)展，2014，51（04）：882-894.

［5］ 張玉州. “數(shù)據(jù)結(jié)構(gòu)”課程中稀疏矩陣運(yùn)算器的實(shí)現(xiàn)［J］. 安慶師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，23（01）：98-101.

［6］ 薛紅濤，丁殿勇，李汭鋮，等. 基于分量加權(quán)重構(gòu)和稀疏NMF的輪轂電機(jī)軸承復(fù)合故障特征提取方法［J］. 機(jī)械工程學(xué)報(bào)，2023，59（09）：146-156.

［7］ 楊凡，饒雨泰. 基于雙向稀疏的多視圖子空間學(xué)習(xí)算法［J］. 計(jì)算機(jī)應(yīng)用與軟件，2023，40（06）：266-275.

［8］ 包世鵬，宋旭明，唐冕. 基于向量化的BESO方法靈敏度過濾快速算法［J］. 鐵道科學(xué)與工程學(xué)報(bào)，2023，20（05）：1810-1820.

［9］ 鄭慧敏，鄭明潔，張振寧，等. 基于低秩和一維稀疏矩陣分解的多通道SAR-GMTI方法［J］. 中國科學(xué)院大學(xué)學(xué)報(bào)，2022，39（02）：208-216.

［10］ 顧越，趙銀亮. 基于RISC-V向量指令的稀疏矩陣向量乘法實(shí)現(xiàn)與優(yōu)化［J］. 計(jì)算機(jī)工程與科學(xué)，2022，44（01）：1-8.