基于十字链表与三元组表的稀疏矩阵压缩存储实例研究

周张兰

摘要：十字链表和带行链接信息的三元组表是稀疏矩阵的两种压缩存储方法。十字链表为链式存储结构，带行链接信息的三元组表为顺序存储结构。在MovieLens数据集上设计了分别采用十字链表和带行链接信息的三元组表对以用户为行、项目为列、用户评分为矩阵元的稀疏矩阵进行压缩存储，并在这两种存储结构上实现用户相似度计算算法。通过测试分析和比较了两种不同的压缩存储方法在创建及相似度计算上的执行效率，并探讨了各自的特点及适用条件。

关键词关键词：稀疏矩阵；十字链表；三元组表；压缩存储

DOIDOI：10.11907/rjdk.171845

中图分类号：TP302

文献标识码：A文章编号文章编号：16727800（2017）011002204

0引言

矩阵是科学与工程计算问题中研究的数学对象。在高阶矩阵中，可能存在很多相同值或零值的矩阵元，对这些矩阵元的存储造成存储空间的浪费。因此，可以对矩阵进行压缩存储，以节省存储空间，达到提高存储利用率的目的。在算法实现中，选择的存储结构不同，执行效率也将不同。对不同矩阵存储方法的特点进行分析和比较，有助于根据不同的实际应用，有针对性地选择更为合适的存储结构，以此提高矩阵运算及其它相关操作的运行效率。

1稀疏矩阵及存储

若一个m行n列矩阵中的零元素有t个，零元素个数t与矩阵元总数m×n的比值称为稀疏因子，一般认为若稀疏因子不大于0.05，则此矩阵为稀疏矩阵。设矩阵有10行10列，即总共100个元素，若其中零元素有95个，而非零元素仅有5个，则此矩阵为稀疏矩阵。……