[發明專利]字典嵌套字典數據結構的稀疏矩陣壓縮存儲方法

在審

• 申請號: 202110286692.0
• 申請日: 2021-03-17
• 公開（公告）號: CN112860818A
• 公開（公告）日: 2021-05-28
• 發明（設計）人: 張然;趙麗丹;盧宇源;左文杰;陳雪乾;周明昆;泰月
• 申請（專利權）人: 吉林大學;中國科學院長春應用化學研究所
• 主分類號: G06F16/28
• 分類號: G06F16/28;G06F16/22
• 代理公司: 吉林長春新紀元專利代理有限責任公司 22100
• 代理人: 王怡敏

本發明涉及一種字典嵌套字典數據結構的稀疏矩陣壓縮存儲方法，屬于高性能計算機存儲領域。包括初始化生成字典嵌套字典類型的數據結構；輸入稀疏矩陣；判斷稀疏矩陣元素是否為零；將非零元素的行索引、列索引和值存儲在字典嵌套字典的數據存儲結構中。本發明利用字典數據存儲結構的時間復雜度和空間復雜度較優的特性，采用一種字典嵌套字典的數據存儲結構來存儲稀疏矩陣，達到占用內存少、存儲高效、處理成本低且耗時少的效果。

技術領域

本發明涉及高性能計算機存儲領域，特別涉及一種字典嵌套字典數據結構的稀疏矩陣壓縮存儲方法。

背景技術

矩陣中非零元素的個數遠遠小于矩陣元素的總數，并且非零元素的分布沒有規律，通常認為矩陣中非零元素的總數比上矩陣所有元素總數的值小于等于5％時，則稱該矩陣為稀疏矩陣。在一些工程計算中，常用到百萬級或千萬級維度的稀疏矩陣，如果將這些稀疏矩陣元素全部存儲是十分浪費計算機存儲空間的，所以考慮將稀疏矩陣進行壓縮存儲。

在一些工程問題中，會用到有限元方法，在有限元方法的組裝總體剛度矩陣的環節中，需要進行頻繁的搜索、查找和插入功能，由于以往使用的數組或鏈表數據結構的這三個功能的時間復雜度都是O(n)(n為問題的規模)，即線性時間，則組裝和存儲的時間是隨規模的增大而增大的，所以組裝和存儲大規模問題的總體剛度矩陣的過程是十分耗時的。有限元方法的總體剛度矩陣是稀疏矩陣，所以大規模問題的稀疏矩陣通常需要壓縮存儲。

目前有許多稀疏矩陣的壓縮存儲方法，如三元組順序表、行邏輯鏈接的順序表、行指針鏈表、十字鏈表、COO、CSR、CSC、LIL等方法。這些方法雖然都可以將稀疏矩陣進行壓縮存儲，但對大規模稀疏矩陣來說，仍然在存儲過程中占用大量內存。

發明內容

本發明的目的在于提供一種字典嵌套字典數據結構的稀疏矩陣壓縮存儲方法，解決了現有技術存在的上述問題。本發明的字典嵌套字典數據結構的稀疏矩陣壓縮存儲方法不僅減少了存儲稀疏矩陣所占用的內存，而且搜索、查找和插入三個功能的時間復雜度都是O(1)，用在有限元方法的總體剛度組裝過程中時，是十分省時的，這對高性能計算機存儲領域的發展是十分有利的。本發明存儲高效、處理成本低且耗時少。減少計算機存儲空間，擴大存儲稀疏矩陣的規模。包括初始化生成字典嵌套字典類型的數據結構；輸入稀疏矩陣；判斷稀疏矩陣元素是否為零；將非零元素的行索引、列索引和非零值存儲在字典嵌套字典的數據存儲結構中。本發明利用字典數據存儲結構的時間復雜度和空間復雜度較優的特性，采用一種字典嵌套字典的數據存儲結構來存儲稀疏矩陣，達到占用內存少的效果。

本發明的上述目的通過以下技術方案實現：

字典嵌套字典數據結構的稀疏矩陣壓縮存儲方法，字典是一種以鍵-值對形式存儲數據的數據結構；設稀疏矩陣表示為A＝(a_ij),i＝1,2,…,M；j＝1,2,…,N，其中，M為稀疏矩陣A的行數，N為稀疏矩陣A的列數；包括如下步驟：

步驟一、初始化生成字典嵌套字典類型的數據結構；

步驟二、讀取稀疏矩陣A的第i行第j列元素的值a_ij；

步驟三、判斷稀疏矩陣元素的值a_ij是否為0，如果不是，跳至步驟四；如果是，跳至步驟五；

步驟四、按行或者按列存儲稀疏矩陣A的非零的元素a_ij，所述按行存儲稀疏矩陣A的非零的元素a_ij，是將行索引i存儲在字典嵌套字典數據結構的外層字典的鍵中，列索引j存儲在外層字典行索引i所對應的內層字典的鍵中，非零的元素的值a_ij存儲在內層字典值中，跳至步驟五；

步驟五、判斷元素的值a_ij是否為稀疏矩陣A的最后一個元素，如果不是，則跳至步驟六；如果是，則結束；