最近一段时间在工作中需要处理稀疏矩阵，遇到如何有效存储的问题。所谓稀疏矩阵是指这样一个矩阵，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号元素是第三行的第一个，等等。
- 稀疏分块的行压缩存储，如下图所示。
一般的行压缩存储方式适用性广，但是当稀疏矩阵稀疏地很有规律的时候，我们还有更好的办法。比如上图，我们可以把大矩阵分隔成5×5的块，显然，只有某些块有值。左下的结构表示哪些块有值，比如(0,0)上有值，(1,2)上有值。有值的块用一个指针指向块内的数据结构。而在每块内还是用一般的行压缩方式存储。
以上参考：http://ce.et.tudelft.nl/publicationfiles/1106_547_smailbegovic.pdf
- QuadTree，四叉树的方法。
Pasted from <http://en.wikipedia.org/wiki/Image:Point_quadtree.svg>
如果需要的话，它总是将空间四分。如果四分后的某个格子里还有1个以上的元素的话，则再次分裂。它可以完全表达成一棵树，每个结点上记录四个指针，指向子树的结构。
上面那个矩阵是我们要存储的稀疏矩阵。我们用如下三个vector来表示它，
在查询的时候，假设要找(x,y)，从AI开始，找到要查的那行在AJ中的起止，即[AI[x], AI[x+1])。再看看，y是否在AJ的这个范围中出现。如果没有，那么要找的值就是一个零元素，否则从AN中取出对应元素即可。注意到，AN，AJ是等长的大数组，AI是一个可以忽略的小数组。使用这种方法，每个非零元素多存4个字节左右就够了。
