[發明專利]稀疏矩陣的壓縮方法及解壓縮方法和裝置

在審

• 申請號: 202010580734.7
• 申請日: 2020-06-23
• 公開（公告）號: CN113836134A
• 公開（公告）日: 2021-12-24
• 發明（設計）人: 不公告發明人
• 申請（專利權）人: 北京希姆計算科技有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 北京中知法苑知識產權代理有限公司 11226
• 代理人: 李明;趙吉陽

本發明提供一種稀疏矩陣的壓縮方法及解壓縮方法和裝置。壓縮方法包括：建立與稀疏矩陣相對應的位圖矩陣，所述位圖矩陣與所述稀疏矩陣的維度相同，并且所述位圖矩陣中每個位元素與所述稀疏矩陣對應的元素之間存在預設的數值對應關系；對所述稀疏矩陣中非0元素依序逐個壓縮存儲；對所述位圖矩陣中所有位元素依序逐個壓縮存儲，壓縮后的所述位圖矩陣中每個位元素與壓縮前的所述稀疏矩陣中每個元素存在預設的位置對應關系。本發明的壓縮方法，不需要記錄稀疏矩陣中每一個非0元素的坐標等信息，只需要用一個等高等寬的位圖矩陣，作為恢復原始稀疏矩陣的索引即可，壓縮方法簡單，并可以有效的節省稀疏矩陣的存儲空間。

技術領域

本發明屬于稀疏矩陣技術領域，具體涉及一種稀疏矩陣的壓縮方法及解壓縮方法和裝置。

背景技術

傳統地，對稀疏矩陣進行壓縮時，稀疏矩陣中為0的元素，不予存儲，每一個非0的元素，不僅僅存儲此元素的數值，同時會存儲它在矩陣中的位置坐標。通常設置縱坐標X為矩陣行元素序號，橫坐標Y為矩陣列元素序號，將數值和坐標作為一個數據結構，以此結構為元素存儲。

顯然，在稀疏矩陣的上述壓縮過程中，壓縮后需要采取復雜的存儲方式，每一個元素還需要存儲其坐標。此外，其壓縮和解壓縮程序復雜。

發明內容

本發明旨在至少解決現有技術中存在的技術問題之一，提供一種稀疏矩陣的壓縮方法及解壓縮方法和裝置。

本發明的一個方面，提供一種稀疏矩陣的壓縮方法，包括：

建立與稀疏矩陣相對應的位圖矩陣，所述位圖矩陣與所述稀疏矩陣的維度相同，并且所述位圖矩陣中每個位元素與所述稀疏矩陣中對應的元素之間存在預設的數值對應關系；

對所述稀疏矩陣中非0元素依序逐個壓縮存儲；

對所述位圖矩陣中所有位元素依序逐個壓縮存儲，壓縮后的所述位圖矩陣中每個位元素與壓縮前的所述稀疏矩陣中每個元素存在預設的位置對應關系。

在一些可選地實施方式中，所述數值對應關系包括：

若所述稀疏矩陣的元素數值為0，則所述位圖矩陣中對應位置處的位元素數值為0；

若所述稀疏矩陣的元素數值為非0，則所述位圖矩陣中對應位置處的位元素數值為1。

在一些可選地實施方式中，所述位置對應關系包括：

壓縮后的所述位圖矩陣中每個位元素與壓縮前的所述稀疏矩陣中每個元素在位置上一一對應。

在一些可選地實施方式中，所述對所述稀疏矩陣中非0元素依序逐個壓縮存儲，包括：

對所述稀疏矩陣中非0元素逐行壓縮存儲成一維數組；或，

對所述稀疏矩陣中非0元素逐列壓縮存儲成一維數組。

在一些可選地實施方式中，所述對所述位圖矩陣中所有位元素依序逐個壓縮存儲，包括：

對所述位圖矩陣中的所有位元素逐行壓縮存儲；或，

對所述位圖矩陣中的所有位元素逐列壓縮存儲。

本發明的另一方面，提供一種稀疏矩陣的解壓縮方法，包括：

獲取與稀疏矩陣相對應的位圖矩陣，所述位圖矩陣與所述稀疏矩陣的維度相同；

根據所述位圖矩陣中位元素與所述稀疏矩陣中對應元素之間的數值對應關系，檢索出所述位圖矩陣中的各目標位元素，所述目標位元素為與所述稀疏矩陣中的各非0元素對應的所述位圖矩陣中的位元素；

根據檢索到的各所述目標位元素在所述位圖矩陣中的位置，確定壓縮前的所述稀疏矩陣中各所述非0元素的位置，解壓縮所述稀疏矩陣。