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

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN109740023A(43)申请公布日2019.05.10(21)申请号201910003397.2(22)申请日2019.01.03(71)申请人中国人民解放军国防科技大学地址410003湖南省长沙市开福区德雅路109号(72)发明人甘新标曾瑞庚吴涛杨志辉孙泽文刘杰龚春叶李胜国杨博徐涵(74)专利代理机构长沙中科启明知识产权代理事务所(普通合伙)43226代理人任合明(51)Int.Cl.G06F16/901(2019.01)权利要求书3页说明书8页附图2页(54)发明名称基于双向位图的稀疏矩阵压缩存储方法(57)摘要本发明公开了一种双向位图的稀疏矩阵压缩存储方法，目的是减少存储空间。技术方案为：仅保留存储一个或者多个顶点或边的起始位置来压缩图的邻接矩阵按行压缩存储数据结构，在行列两个方向使用位图数组来辅助识别顶点的边信息。具体方法包括：读取图的邻接矩阵按行压缩存储数据结构；构建改进型位数组；计算偏移量；构建行方向位图数组，由改进型位数组和行方向位图数组压缩存储行数组；计算列数组连续片段长度并构建连续片段二元组集合；构建简化列数组和列方向位图数组，由简化列数组和列方向位图数组压缩存储列数组。可以将图数据存储空间在行方向位图数组的基础上进一步压缩，极大规模扩大图的应用规模，优化采用图结构的应用程序的性能。CN109740023ACN109740023A权利要求书1/3页1.一种基于双向位图的稀疏矩阵压缩存储方法，其特征在于仅保留存储一个或者多个顶点或边的起始位置来压缩图的邻接矩阵按行压缩存储数据结构，分别在行列两个方向使用位图数组来辅助识别顶点的边信息，具体包括以下步骤：第一步、读取图G的邻接矩阵CSR存储数据结构，即按行压缩存储数据结构，包含列数组colums[V”]和行数组rowstarts[V']，V'，V”均为正整数，V'＝NV+1，V”为非零元的个数，rowstarts[V']中的每一个元素为int整型量，表示对应非零元的行索引偏移，列数组colums[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个元素的行方向位图数组row-bitmap[NV]；row-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位图数组row-bitmap[NV]构建完毕；第五步、计算列数组colums[V”]连续片段长度并构建连续片段二元组集合，方法是：5.1.定义二元组集合F中存放形如＜colums,len＞的二元组，＜colums,len＞表示每个连续片段列位置编号colums连续出现了len次，len≥1，colums是连续片段列位置编号，len是colums连续出现的次数，且len，colums均为正整数；5.2.定义循环变量m＝0，令len＝1；2CN1097400