一种对稀疏矩阵进行压缩和查询的方法及系统

摘要

本发明涉及一种对稀疏矩阵进行压缩和查询的方法及系统。该方法对k²-tree方法进行了改进：一是rank操作的改变，二是对于一般矩阵和非零一矩阵的处理。首先对待处理的稀疏矩阵进行预处理，得到单元值为0或1且为方阵的稀疏矩阵A；然后采用k²-tree算法得到数组T(tree)和L(leaves)，根据T(tree)中的信息对Rank数组间隔固定位数进行存储，得出Rank(tree)，并根据L(leaves)和对应的原稀疏矩阵得到V(leaves)和rank(leaves)值，输入查询单元的坐标后，可查询得出稀疏矩阵A中存储的数值。本发明可以有效地压缩稀疏矩阵，使查询速度更快，存储空间更节省。

主权项

一种对稀疏矩阵进行压缩和查询的方法，其特征在于，包括如下步骤：1)对待处理的稀疏矩阵进行预处理，得到单元值为0或1且为方阵的稀疏矩阵A，设其规模行高为n，并设定稀疏矩阵A的分块大小k；2)根据分块大小k、稀疏矩阵A及其规模行高n，采用k²‑tree算法得到数组T(tree)和L(leaves)；3)根据T(tree)中的信息对Rank数组间隔固定位数进行存储，得出Rank(tree)，并根据L(leaves)和对应的原稀疏矩阵得到V(leaves)和rank(leaves)值，其中V(leaves)顺序存储L(leaves)中1对应的原稀疏矩阵的真实数据，rank(leaves)存储L(leaves)中当前位置m之前1的个数；4)输入查询单元的坐标，根据该坐标以及T(tree)、L(leaves)、Rank(tree)、V(leaves)和rank(leaves)，查询得出稀疏矩阵A中存储的数值。