石头狗 / 我的图书馆 / 谈谈稀疏矩阵的有效存储

分享

   

谈谈稀疏矩阵的有效存储

2009-02-04  石头狗

谈谈稀疏矩阵的有效存储

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个字节。经过在网上的一番搜索和学习后,我又发现了如下几种更加经典的好方法。

  1. 行压缩存储。如下图所示
    • 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个字节左右就够了。

  2. 稀疏分块的行压缩存储,如下图所示。

    一般的行压缩存储方式适用性广,但是当稀疏矩阵稀疏地很有规律的时候,我们还有更好的办法。比如上图,我们可以把大矩阵分隔成5×5的块,显然,只有某些块有值。左下的结构表示哪些块有值,比如(0,0)上有值,(1,2)上有值。有值的块用一个指针指向块内的数据结构。而在每块内还是用一般的行压缩方式存储。

    以上参考:

  3. QuadTree,四叉树的方法。

    Pasted from <>

    如果需要的话,它总是将空间四分。如果四分后的某个格子里还有1个以上的元素的话,则再次分裂。它可以完全表达成一棵树,每个结点上记录四个指针,指向子树的结构。

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多
    喜欢该文的人也喜欢 更多

    ×
    ×

    ¥.00

    微信或支付宝扫码支付:

    开通即同意《个图VIP服务协议》

    全部>>