周張?zhí)m

摘要：十字鏈表和帶行鏈接信息的三元組表是稀疏矩陣的兩種壓縮存儲方法。十字鏈表為鏈式存儲結構，帶行鏈接信息的三元組表為順序存儲結構。在MovieLens數(shù)據(jù)集上設計了分別采用十字鏈表和帶行鏈接信息的三元組表對以用戶為行、項目為列、用戶評分為矩陣元的稀疏矩陣進行壓縮存儲，并在這兩種存儲結構上實現(xiàn)用戶相似度計算算法。通過測試分析和比較了兩種不同的壓縮存儲方法在創(chuàng)建及相似度計算上的執(zhí)行效率，并探討了各自的特點及適用條件。

關鍵詞關鍵詞：稀疏矩陣；十字鏈表；三元組表；壓縮存儲

DOIDOI：10.11907/rjdk.171845

中圖分類號：TP302

文獻標識碼：A文章編號文章編號：16727800（2017）011002204

0引言

矩陣是科學與工程計算問題中研究的數(shù)學對象。在高階矩陣中，可能存在很多相同值或零值的矩陣元，對這些矩陣元的存儲造成存儲空間的浪費。因此，可以對矩陣進行壓縮存儲，以節(jié)省存儲空間，達到提高存儲利用率的目的。在算法實現(xiàn)中，選擇的存儲結構不同，執(zhí)行效率也將不同。對不同矩陣存儲方法的特點進行分析和比較，有助于根據(jù)不同的實際應用，有針對性地選擇更為合適的存儲結構，以此提高矩陣運算及其它相關操作的運行效率。

1稀疏矩陣及存儲

若一個m行n列矩陣中的零元素有t個，零元素個數(shù)t與矩陣元總數(shù)m×n的比值稱為稀疏因子，一般認為若稀疏因子不大于0.05，則此矩陣為稀疏矩陣。設矩陣有10行10列，即總共100個元素，若其中零元素有95個，而非零元素僅有5個，則此矩陣為稀疏矩陣。在存儲稀疏矩陣時，可以采用非壓縮存儲和壓縮存儲兩種方式。非壓縮存儲使用二維數(shù)組，比如，設10行10列的稀疏矩陣M的矩陣元均為整數(shù)，則可以使用二維數(shù)組存儲該矩陣M，數(shù)組的定義用C語言[1]描述如下：

int a[10][10]；

其中，a[0][0]代表稀疏矩陣M第1行第1列元素，a[i][j]代表第i+1行第j+1列元素。由于數(shù)組是從下標0開始，因此使用二維數(shù)組時下標與邏輯上的行號和列號相差1。為了操作方便，也可以從a[1][1]開始存儲第1行第1列元素，即定義為：

int a[11][11]；

這種定義方式可以使邏輯上的行、列號與二維數(shù)組的下標保持一致，采用這種方式存儲矩陣時所需存儲空間要求更大。

從操作上看，二維數(shù)組的非壓縮存儲方式按行和列存取數(shù)據(jù)元素非常方便。然而，在稀疏矩陣中，大量零元素的存儲不僅會浪費存儲空間，而且與零元素相關的運算也會在一定程度上降低計算總體效率。因此，在實際應用中，對稀疏矩陣進行壓縮存儲很有必要。壓縮存儲只存儲非零矩陣元，有順序存儲和非順序存儲兩種。其中，順序存儲可使用帶行鏈接信息的三元組表，而非順序存儲可采用十字鏈表。

2壓縮存儲

2.1三元組及表示

壓縮存儲只存儲矩陣中的非零元。在矩陣中，除了存儲非零元素的值，還要存儲該元素所在的行號和列號。三元組表示法以（行號，列號，值）形式存儲矩陣中的一個非零元素，比如，（1，1，5）表示第1行第1列元素值為5。設矩陣元素值的類型為ElemType，則存儲一個非零元三元組的結構體類型定義用C語言描述如下：

struct Triple{

int i，j；

ElemType e；

}；

三元組可存儲稀疏矩陣中所有非零元的值及其行、列號。但是，從三元組中不能得到整個稀疏矩陣行數(shù)、列數(shù)及非零元個數(shù)等信息。因此，還要對存儲整個稀疏矩陣的三元組表進行定義。帶行鏈接信息的三元組表又稱為行邏輯鏈接順序表[2]，其結構體類型定義用C語言描述如下：

struct TripleMatrix{

struct Triple *data；

int *rops；

int m，n，t；

}；

其中，以三元組形式表示的非零元存儲在數(shù)組data[]中，每行的第1個非零元在三元組表中的起始位置存放在數(shù)組rops[]中，兩個數(shù)組的存儲空間在初始化時分配。m、n、t分別代表稀疏矩陣的行數(shù)、列數(shù)和非零元個數(shù)。

2.2十字鏈表及表示

十字鏈表是稀疏矩陣的鏈式存儲結構。十字鏈表對矩陣的每一行建立一個鏈表，行鏈表的頭指針存放在其對應行的一維數(shù)組中。同樣，為矩陣的每一列建立一個鏈表，列鏈表的頭指針也存放在其對應列的一維數(shù)組中。為了實現(xiàn)十字鏈表，首先將需要存儲的非零元素封裝成一個結點。其中，結點包含5個域，除了行號、列號和值3個數(shù)據(jù)域外，還有兩個指針域，分別指向該元素所在行及所在列的下一個非零元素。設稀疏矩陣的數(shù)據(jù)元素類型為ElemType，則十字鏈表中存儲非零元素結點的結構體類型定義如下：

struct CrossLNode{

int i，j；

ElemType e；

struct CrossLNode *rownext， *colnext；

}；

其中，rownext和colnext指針分別指向該元素所在行和所在列的下一個非零元素。對整個稀疏矩陣而言，除了存儲非零元，還要記錄整個矩陣的行數(shù)、列數(shù)和非零元個數(shù)以及兩個分別存儲所有行鏈表和列鏈表頭指針的一維數(shù)組。因此，十字鏈表的結構體類型定義如下：

struct CrossLinkList{

struct CrossLNode *rowhead， *columnhead；

int m， n， t；

}；

在十字鏈表定義中，m、n、t分別代表稀疏矩陣的行數(shù)、列數(shù)和非零元素個數(shù)。rowhead和columnhead指針分別指向存儲所有行鏈表頭指針和所有列鏈表頭指針的一維數(shù)組的首地址。endprint

3實例測試

3.1數(shù)據(jù)集

協(xié)同過濾推薦[36]是一種廣泛使用的推薦方法，傳統(tǒng)的協(xié)同過濾推薦算法不依賴于推薦內(nèi)容本身，而根據(jù)用戶對項目的評分產(chǎn)生推薦。其中，用戶對項目的評分可以看作是一個以用戶為行、項目為列的矩陣，矩陣元aij表示用戶i對項目j的評分。在實際應用中，用戶有興趣并且產(chǎn)生評分的項目相對于所有項目而言極其有限。因此，用戶項目評分矩陣往往是一個稀疏矩陣。借助協(xié)同過濾推薦中常用的MovieLens[7]數(shù)據(jù)集作為數(shù)據(jù)對象，通過計算用戶相似度，分析、對比分別采用帶行鏈接信息的三元組表和十字鏈表對稀疏矩陣進行壓縮存儲時各自的執(zhí)行效率。

本文使用的MovieLens數(shù)據(jù)集中，用戶數(shù)943個、項目數(shù)1 682個。用戶評分記錄包括：用戶號、項目號、評分和時間戳。其中，訓練集有u1.base、u2.base、u3.base、u4.base和u5.base 5個數(shù)據(jù)文件，每個文件中評分記錄為80 000條，每一條評分記錄以（user_id，item_id，rating，timestamp）的形式存儲。分析此數(shù)據(jù)可以得出，以用戶對項目評分為矩陣元的矩陣稀疏因子為80 000/（943×1 682）≈0.05，即此矩陣可認為是一個稀疏矩陣。

3.2算法設計

在基于用戶的協(xié)同過濾推薦中，首先利用評分矩陣計算用戶與用戶之間的相似度，從而產(chǎn)生目標用戶的近鄰，再利用這些用戶近鄰對目標用戶未評分項目進行評分預測，最后根據(jù)預測評分的高低向目標用戶推薦。用戶相似度計算是基于用戶的協(xié)同過濾推薦算法的重要步驟，本文采用余弦相似度計算用戶之間的相似度值。為了比較帶行鏈接信息的三元組表和十字鏈表壓縮存儲效率，分別在這兩種存儲結構上設計和實現(xiàn)用戶相似度計算算法并進行了測試。

（1）帶行鏈接信息的三元組表測試算法。采用帶行鏈接信息的三元組表壓縮存儲評分矩陣并計算用戶相似度的算法步驟如下：首先，初始化TripleMatrix類型的帶行鏈接信息的三元組表M；然后，創(chuàng)建帶行鏈接信息的三元組表M。讀入評分記錄文件u1.base，將其中每一條評分記錄的行號、列號和值依次存儲到M.data中；再計算用戶之間的相似度，根據(jù)余弦相似度計算公式利用行鏈接信息M.rpos在三元組表中讀取所需用戶評分，并計算有共同評分的用戶之間的相似度值；最后，重復以上步驟分別測試u2.base、u3.base、u4.base和u5.base 4個數(shù)據(jù)文件。

（2）十字鏈表測試算法。采用十字鏈表存儲評分矩陣并計算用戶相似度的算法步驟與帶行鏈接信息的三元組表類似，但由于該方法采用鏈式存儲結構，因此在算法實現(xiàn)上主要是指針操作。首先，初始化并創(chuàng)建CrossLinkList類型的十字鏈表T；然后，讀入評分記錄文件u1.base，每讀取一條記錄，用malloc動態(tài)申請一個CrossLNode類型的節(jié)點，并存儲相應的行、列和值，同時將該結點掛到其行所在的鏈表及其列所在的鏈表中；接著，計算用戶之間的相似度，根據(jù)余弦相似度計算公式在創(chuàng)建的十字鏈表中讀取所需節(jié)點的用戶評分，并計算有共同評分的用戶之間的相似度值；最后，重復以上步驟分別測試u2.base、u3.base、u4.base和u5.base 4個數(shù)據(jù)文件。

3.3運行測試

在配置為處理器Inter（R） Core（TM） i54210，內(nèi)存4G，64位操作系統(tǒng)的電腦上使用visual C++6.0編程并運行測試。測試中，使用計時函數(shù)clock（）計算運行時間。由于在不同時刻運行程序，計算的運行時間會有所偏差，為此將每個數(shù)據(jù)文件連續(xù)運行5次，取平均值作為最終執(zhí)行時間。用訓練數(shù)據(jù)集u1至u5分別測試兩種存儲結構。其中，創(chuàng)建十字鏈表和帶行鏈接信息的三元組表所需時間如圖1所示，計算用戶相似度的運行時間如圖2所示，創(chuàng)建并計算總執(zhí)行時間如圖3所示。

3.4結果分析

由圖1可知，創(chuàng)建十字鏈表所用時間大于帶行鏈接信息的三元組表用時。分析十字鏈表創(chuàng)建過程可知，每讀入一條評分記錄，動態(tài)申請一個結點的存儲單元，不僅要將評分存儲到結點中，還需要將該節(jié)點插入到其所在行和所在列的鏈表中。相對于直接加到表尾的三元組表存儲的順序存儲而言所需時間要多。當然，由于在MovieLens數(shù)據(jù)集中，所有評分記錄已按行和列從小到大順序排序，因此當結點插入時只需要插入到所在行和列鏈表的表尾即可。但是若輸入的評分記錄沒有按行和列排序，在創(chuàng)建十字鏈表時還需要從行或列的第一個結點開始查找合適的插入位置，再實現(xiàn)節(jié)點插入。這樣所需運行時間更多，實際測試發(fā)現(xiàn)，其平均運行時間要多近3倍。若采用三元組表存儲，在創(chuàng)建時需對記錄進行按行和列排序，插入節(jié)點時還要為空出插入位置而移動元素，則所需創(chuàng)建時間會更多。

當非零元素分別以十字鏈表和三元組表存儲，采用余弦相似度計算方法計算所有用戶之間的相似度。其中，三元組表采用行邏輯連接的順序表，可按行訪問。從圖2中得到，使用十字鏈表計算相似度所需時間小于采用三元組表存儲用時。這說明，當十字鏈表和帶行鏈接信息的三元組表創(chuàng)建后，在同等條件下計算用戶相似度時，十字鏈表訪問數(shù)據(jù)元素并實現(xiàn)計算的效率要比三元組表高。從總運行時間看，十字鏈表雖然在創(chuàng)建用時比三元組表要多，但由于計算相似度所用時間少，因此總執(zhí)行時間要比三元組表少，兩者總運行時間對比如圖3所示。

將十字鏈表、帶行鏈接信息的三元組表和非壓縮的二維數(shù)組的創(chuàng)建和計算相似度的總運行時間進行比較，三者的總運行時間如表1所示?？梢钥闯?，無論是十字鏈表還是帶行鏈接信息的三元組表，在壓縮后由于去掉了大量零元素運算，因此所需運行時間均大幅減少，運行效率明顯提高。

在存儲空間方面，使用非壓縮的二維數(shù)組、壓縮的十字鏈表和帶行鏈接信息的三元組表所需存儲空間如表2所示。表中數(shù)據(jù)以943個用戶、1 682個項目，形成943行1 682列的稀疏矩陣的數(shù)據(jù)集為例，其中，評分記錄為80 000條。從表中結果可知，二維數(shù)組所需存儲空間最多，總共需要943*1 682*4=6 344 504個字節(jié)，而且必須是連續(xù)的存儲單元。十字鏈表所需存儲空間其次，其中包含存儲非零元的非連續(xù)存儲空間80 000*20=1 600 000個字節(jié)，存儲十字鏈表所有行鏈表頭指針的連續(xù)存儲空間943*4=3 772個字節(jié)和存儲所有列鏈表頭指針的連續(xù)存儲空間1 682*4=6 728個字節(jié)，即十字鏈表總存儲空間為1 610 500個字節(jié)。帶行鏈接信息的三元組表所需存儲空間最少，其中存儲矩陣非零元的連續(xù)存儲空間80 000*12=960 000個字節(jié)，存儲每行在三元組表中起始位置的連續(xù)的存儲空間943*4=3 772個字節(jié)，即總共需要963 772個字節(jié)的存儲空間。另外，在三元組表和十字鏈表中還需要存儲矩陣行數(shù)、列數(shù)和非零元個數(shù)等其它少量的輔助存儲空間。endprint

測試發(fā)現(xiàn)，無論使用十字鏈表還是帶行鏈接信息的三元組表對稀疏矩陣進行壓縮存儲，由于只需存儲非零元素，因此對存儲空間的壓縮效果明顯，尤其是帶行鏈接信息的三元組表，所需存儲空間較少。然而，由于三元組是順序存儲的，因此，存儲空間必須是連續(xù)的存儲單元。相對于帶行鏈接信息的三元組表，十字鏈表所需存儲空間更多，但所需連續(xù)存儲空間少，因為存儲非零元素的存儲空間是動態(tài)申請的，因此不必是連續(xù)的存儲單元。

從用戶相似度的運行時間上看，相比非壓縮的二維數(shù)組存儲方法，利用十字鏈表和帶行鏈接信息的三元組表壓縮存儲后計算所需運行時間較少。這是因為省略了對大量零元素的存儲，同時也就免除了大量有關零元素的運算，而這些針對零元素的運算在余弦相似度計算中并無必要。因此，經(jīng)過壓縮存儲后，對程序運行時間的提高也有很大幫助。在本例測試中，十字鏈表比帶行鏈接信息的三元組表的創(chuàng)建所用時間多，但是在計算相似度時所用時間要少，而總運行時間優(yōu)于三元組表存儲方法。這是由于十字鏈表雖然采用鏈式存儲結構，但可以按行和列訪問矩陣元，而在行邏輯鏈接的三元組順序表中，雖然每行的第一個非零元素的起始位置已存儲，也可以實現(xiàn)按行訪問，但在本例中所用時間還是比十字鏈表略多。

4結語

測試分析表明，十字鏈表和帶行鏈接信息的三元組表都可以較好地實現(xiàn)對稀疏矩陣的壓縮存儲，并且在運行時間和存儲空間上比非壓縮存儲效率均有明顯提高。在運行時間方面，若輸入數(shù)據(jù)已按行和列排序，在創(chuàng)建時只需在表尾插入，則三元組表的順序存儲結構所用創(chuàng)建時間比十字鏈表少。然而，創(chuàng)建時若輸入數(shù)據(jù)沒有經(jīng)過排序處理，則十字鏈表的結點插入需要先找到插入位置。同樣，帶行鏈接信息的三元組表需為待插入元素空出位置而移動元素，兩者在創(chuàng)建上的運行時間都將比非壓縮的二維數(shù)組多。運算時間上，本例中十字鏈表按行訪問并完成相似度計算的運行時間比帶行鏈接信息的三元組表要少。由于十字鏈表順序存儲了行鏈表和列鏈表的頭指針，相比僅按行訪問的帶行鏈接信息的三元組表，十字鏈表不僅可以按行訪問，還可以根據(jù)需要按列訪問，使用更加靈活。在存儲空間方面，三元組表的順序存儲結構所需存儲空間較少，但要求存儲單元必須連續(xù)，而且容量固定，不易擴充。十字鏈表中非零元的存儲單元是動態(tài)申請的，需要的連續(xù)存儲空間較少，同時插入、刪除操作靈活，可以很好地適應數(shù)據(jù)變化。

基于十字鏈表和三元組表的稀疏矩陣壓縮存儲特點及用戶相似度計算效率的對比與分析表明，這兩種對稀疏矩陣壓縮存儲的方法各有所長，在實際應用中可依據(jù)對數(shù)據(jù)的存儲容量和操作特點選擇更為合適的存儲結構，從而實現(xiàn)計算效率最優(yōu)化。

參考文獻參考文獻：

[1]譚浩強.C語言程序設計[M].第2版.北京：清華大學出版社，1999.

[2]嚴蔚敏，吳偉民.數(shù)據(jù)結構（C語言版）[M].北京：清華大學出版社，2007.

[3]GOLDBERG D，NICHOLS D，OKI B M，et al. Using collaborative filtering to weave an information tapestry[J]. Comm ACM，1992，35（12）：6170.

[4]KONSTAN J A，MILLER B N，MALTZ D，et al.GroupLens： applying collaborative filtering to usenet news[J]. Comm ACM，1997，40（3）：7787.

[5]LINDEN G，SMITH B，YORK J.Amazon.com recommendations： itemtoitem collaborative filtering[J]. IEEE Internet Computing，2003，7（l）：7680.

[6]SCHAFER J，KONSTAN J，RIEDLL J.Recommender systems in Ecommerce[C].Proc ACM ECommerce，1999：158166.

[7]MovieLens[EB/OL].http：//grouplens.org/datasets/.

責任編輯（責任編輯：孫娟）endprint