基于位图的稀疏矩阵压缩存储方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN109726314A(43)申请公布日2019.05.07(21)申请号201910003370.3(22)申请日2019.01.03(71)申请人中国人民解放军国防科技大学地址410003湖南省长沙市开福区德雅路109号(72)发明人甘新标曾瑞庚吴涛杨志辉孙泽文刘杰龚春叶李胜国杨博徐涵晏益慧(74)专利代理机构长沙中科启明知识产权代理事务所(普通合伙)43226代理人任合明(51)Int.Cl.G06F16/901(2019.01)权利要求书2页说明书5页附图3页(54)发明名称基于位图的稀疏矩阵压缩存储方法(57)摘要本发明公开了一种基于位图的稀疏矩阵压缩存储方法，目的是减少存储空间，扩大图的规模，优化采用图结构的应用程序的性能。技术方案为：仅保留存储一个或者多个顶点或边的起始位置来压缩图的邻接矩阵按行压缩存储数据结构，并使用一个额外的位图来识别顶点的边信息。具体方法包括：读取图的邻接矩阵按行压缩存储数据结构，构建改进型位数组，计算偏移量，构建位图数组，由改进型位数组和位图数组压缩存储行数组全部信息。本发明建立的位图数组可以进一步压缩图的存储空间，可以将每个非零元的表示信息大小由32bit降低至1bit；可以将图数据存储空间节约近60％，可以扩大图的应用规模，优化采用图结构的应用程序的性能。CN109726314ACN109726314A权利要求书1/2页1.一种基于位图的稀疏矩阵压缩存储方法，其特征在于仅保留存储一个或者多个顶点或边的起始位置来压缩图的邻接矩阵按行压缩存储数据结构，并使用一个额外的位图来识别顶点的边信息，具体包括以下步骤：第一步、读取图G的邻接矩阵CSR存储数据结构，即按行压缩存储数据结构，包含列数组colums和行数组rowstarts[V']，V'为正整数，V'＝NV+1，rowstarts[V']中的每一个元素为int整型量，表示对应非零元的行索引偏移；第二步、简化行数组rowstarts[V']，构建改进型位数组，具体方法如下：2.1.统计rowstarts[V']数组中不同元素的个数，记为Vb，并定义第二行数组rowstarts'[Vb]来存放这Vb个元素；2.2.将rowstarts[V']数组中Vb个不同元素依次分别表示为rowstarts'[0],rowstarts'[1],…,rowstarts'[n],…,rowstarts'[Vb-1]，n＝0,1,2,…,Vb-1；2.3.定义具有Vb个元素的改进型位数组CSR-rowstarts'[Vb]，对CSR-rowstarts'[Vb]进行赋值，将数组rowstarts'[Vb]中Vb个元素依次赋值给数组CSR-rowstarts'[Vb]；第三步、计算偏移量，具体方法如下：3.1.定义有NV个元素的偏移数组offset[NV]；3.2.定义变量j'＝0；3.3.若j'＜NV，转3.4；否则，转3.7；3.4.offset[j']＝rowstarts[j'+1]-rowstarts[j']，即计算相应的行非零元的个数；3.5.j'＝j'+1；3.6.若j'＜NV，转3.4；否则，3.7；3.7.偏移量计算完成，得到偏移数组offset[NV]；第四步、构建位图数组，由改进型位数组CSR-rowstarts'[Vb]和位图数组压缩存储行数组rowstarts[V']全部信息，具体方法如下：4.1定义有NV个元素的位图数组bitmap[NV]；bitmap[NV]中的每一个元素仅有一个bit位，用来表示两个顶点之间是否有边，1表示有边，0表示无边；4.2定义变量k＝0；4.3若k＜NV，转4.4；否则，转4.7；4.4若offset[k]≠0，转4.5；否则，转4.6；4.5bitmap[k]＝1，表示顶点之间有边，转4.7；4.6bitmap[k]＝0，表示顶点之间无边，转4.7；4.7k＝k+1；4.8若k＜NV，转4.4；否则，转4.9；4.9位图数组bitmap[NV]构建完毕，也即行数组rowstarts[V']全部信息存储完毕；第五步、结束。2.如权利要求1所述的基于位图的稀疏矩阵压缩存储方法，其特征在于2.3步对CSR-rowstarts'[Vb]进行赋值的方法是：2.3.1定义变量i'＝0；2.3.2如果i'＜Vb，转2.3.3；否则，转2.3.6；2.3.3CSR-rowstarts'[i']＝rowstarts'[i']；2CN109726314A权利要求书2/2页2.3.4i'＝i'+1；2.3.5若i'＜Vb，转2.3.3；否则，转2.3.6；2.3.6赋值完毕。3CN109726314A说明书1/5页基于位图的稀疏矩阵压缩存储方法技术领域[