神马文学网谈谈稀疏矩阵的有效存储
来源：百度文库 编辑：神马文学网 时间：2024/10/02 16:46:35
2008年1月24日
评论发表评论
最近一段时间在工作中需要处理稀疏矩阵，遇到如何有效存储的问题。所谓稀疏矩阵是指这样一个矩阵，0元素（或者某种占绝对优势的元素）占了绝大多数。稀疏矩阵的应用非常之广，比如处理图像（有大量单一颜色）、用向量空间模型来表示文档、表达两个变量之间的两两关系。存储这样的矩阵，直接用一个二维数组显然是不经济的。
如果只是简单想一想，可能会得到如下的解法。
稀疏矩阵最常用的操作，也是我当前唯一用到的操作，就是根据横纵坐标查询某位置元素的值。于是我用std::map实现，key是一个std::pair (x,y)，value是用模板定义的矩阵元素的类型。但是很快发现，当矩阵规模增加之后，内存使用迅速膨胀。看来，std::map的内存使用不合乎要求。 于是我决定用Vector加排序来实现。我把坐标和对应值封装了一个结构体，还是用坐标作为key。每次将这个结构压入vector中。全部数据都存入后再对这个vector排序。排序的准则是自定义的坐标比较函数。当使用的时候，可以利用下面的二分查找来实现，如， bool find(const KT& k, VT& v) { // use binary search to locate the item std::vector::const_iterator it( std::lower_bound( this->data.begin(), this->data.end(), key_value_t(k, 0), key_value_t_less())); if (it != this->data.end() && it->key == k) { v = it->value; return true; } else { return false; } }
使用了这一方法后，内存的使用降了下来。但是，这是最优的方法吗？显然还不是。在这里，除了所有的非零元素必须存储外，对于每个非零元素，我们存了两个坐标，两个32bit int也就是8个字节。经过在网上的一番搜索和学习后，我又发现了如下几种更加经典的好方法。
行压缩存储。如下图所示 AN (Array of Non-zero elements, 猜的，下同）：用来记录所有的非零元素，这个是省不掉的。 AJ (Array of j, j一般用来指纵坐标，即列索引）：用来记录在每一行上，哪些列出现了非平凡值。比如第一行的6,9,4，它们出现在列1,3,6上，以此类推。 AI (Array of i)：它用来记录每一行上第一个元素的编号，如果我们按从左到右从上到下的顺序给非零元素编号的话。比如， 第一行有三个元素，第4号元素是第二行的第一个，第5号元素是第三行的第一个，等等。
上面那个矩阵是我们要存储的稀疏矩阵。我们用如下三个vector来表示它，
在查询的时候，假设要找(x,y)，从AI开始，找到要查的那行在AJ中的起止，即[AI[x], AI[x+1])。再看看，y是否在AJ的这个范围中出现。如果没有，那么要找的值就是一个零元素，否则从AN中取出对应元素即可。注意到，AN，AJ是等长的大数组，AI是一个可以忽略的小数组。使用这种方法，每个非零元素多存4个字节左右就够了。
稀疏分块的行压缩存储，如下图所示。
一般的行压缩存储方式适用性广，但是当稀疏矩阵稀疏地很有规律的时候，我们还有更好的办法。比如上图，我们可以把大矩阵分隔成5×5的块，显然，只有某些块有值。左下的结构表示哪些块有值，比如(0,0)上有值，(1,2)上有值。有值的块用一个指针指向块内的数据结构。而在每块内还是用一般的行压缩方式存储。
以上参考：http://ce.et.tudelft.nl/publicationfiles/1106_547_smailbegovic.pdf
QuadTree，四叉树的方法。
Pasted from
如果需要的话，它总是将空间四分。如果四分后的某个格子里还有1个以上的元素的话，则再次分裂。它可以完全表达成一棵树，每个结点上记录四个指针，指向子树的结构。
评论发表评论
最近一段时间在工作中需要处理稀疏矩阵，遇到如何有效存储的问题。所谓稀疏矩阵是指这样一个矩阵，0元素（或者某种占绝对优势的元素）占了绝大多数。稀疏矩阵的应用非常之广，比如处理图像（有大量单一颜色）、用向量空间模型来表示文档、表达两个变量之间的两两关系。存储这样的矩阵，直接用一个二维数组显然是不经济的。
如果只是简单想一想，可能会得到如下的解法。
稀疏矩阵最常用的操作，也是我当前唯一用到的操作，就是根据横纵坐标查询某位置元素的值。于是我用std::map实现，key是一个std::pair (x,y)，value是用模板定义的矩阵元素的类型。但是很快发现，当矩阵规模增加之后，内存使用迅速膨胀。看来，std::map的内存使用不合乎要求。 于是我决定用Vector加排序来实现。我把坐标和对应值封装了一个结构体，还是用坐标作为key。每次将这个结构压入vector中。全部数据都存入后再对这个vector排序。排序的准则是自定义的坐标比较函数。当使用的时候，可以利用下面的二分查找来实现，如， bool find(const KT& k, VT& v) { // use binary search to locate the item std::vector::const_iterator it( std::lower_bound( this->data.begin(), this->data.end(), key_value_t(k, 0), key_value_t_less())); if (it != this->data.end() && it->key == k) { v = it->value; return true; } else { return false; } }
使用了这一方法后，内存的使用降了下来。但是，这是最优的方法吗？显然还不是。在这里，除了所有的非零元素必须存储外，对于每个非零元素，我们存了两个坐标，两个32bit int也就是8个字节。经过在网上的一番搜索和学习后，我又发现了如下几种更加经典的好方法。
行压缩存储。如下图所示 AN (Array of Non-zero elements, 猜的，下同）：用来记录所有的非零元素，这个是省不掉的。 AJ (Array of j, j一般用来指纵坐标，即列索引）：用来记录在每一行上，哪些列出现了非平凡值。比如第一行的6,9,4，它们出现在列1,3,6上，以此类推。 AI (Array of i)：它用来记录每一行上第一个元素的编号，如果我们按从左到右从上到下的顺序给非零元素编号的话。比如， 第一行有三个元素，第4号元素是第二行的第一个，第5号元素是第三行的第一个，等等。
上面那个矩阵是我们要存储的稀疏矩阵。我们用如下三个vector来表示它，
在查询的时候，假设要找(x,y)，从AI开始，找到要查的那行在AJ中的起止，即[AI[x], AI[x+1])。再看看，y是否在AJ的这个范围中出现。如果没有，那么要找的值就是一个零元素，否则从AN中取出对应元素即可。注意到，AN，AJ是等长的大数组，AI是一个可以忽略的小数组。使用这种方法，每个非零元素多存4个字节左右就够了。
稀疏分块的行压缩存储，如下图所示。
一般的行压缩存储方式适用性广，但是当稀疏矩阵稀疏地很有规律的时候，我们还有更好的办法。比如上图，我们可以把大矩阵分隔成5×5的块，显然，只有某些块有值。左下的结构表示哪些块有值，比如(0,0)上有值，(1,2)上有值。有值的块用一个指针指向块内的数据结构。而在每块内还是用一般的行压缩方式存储。
以上参考：http://ce.et.tudelft.nl/publicationfiles/1106_547_smailbegovic.pdf
QuadTree，四叉树的方法。
Pasted from
如果需要的话，它总是将空间四分。如果四分后的某个格子里还有1个以上的元素的话，则再次分裂。它可以完全表达成一棵树，每个结点上记录四个指针，指向子树的结构。
谈谈稀疏矩阵的有效存储
谈谈网络数字矩阵VS模拟矩阵
治眉毛稀疏的方法
测量骨质稀疏的方法
测量骨质稀疏的方法
谈谈有效数字
谈谈有效数字
谈谈如何有效沟通。
谈谈有效教学
矩阵制度的弊端
谈谈如何有效开展物理教研组的校本教研活动
谈谈有效课堂教学必须处理好的四个关系
谈谈有效课堂教学必须处理好的四个关系
基于非常稀疏随机投影的图像重建方法
谈谈有效教学理论 hao
谈谈有效教学理论2
谈谈有效教学理论1
陈一舟的Web2.0矩阵
[宽频]有效挖掘企业信息资源价值的途径与方法_DOSTOR.com_存储在线 | 信息创造...
[宽频]有效挖掘企业信息资源价值的途径与方法_DOSTOR.com_存储在线 | 信息创造...
增强抵抗力，多少维C才有效--谈谈维生素C的合理补充
谈谈笛卡尔的《谈谈方法》
变量的存储类型
蔬菜的存储