最近一段時(shí)間在工作中需要處理稀疏矩陣,，遇到如何有效存儲(chǔ)的問題。所謂稀疏矩陣是指這樣一個(gè)矩陣,，0元素（或者某種占絕對優(yōu)勢的元素）占了絕大多數(shù),。稀疏矩陣的應(yīng)用非常之廣，比如處理圖像（有大量單一顏色）,、用向量空間模型來表示文檔,、表達(dá)兩個(gè)變量之間的兩兩關(guān)系。存儲(chǔ)這樣的矩陣,，直接用一個(gè)二維數(shù)組顯然是不經(jīng)濟(jì)的,。

如果只是簡單想一想，可能會(huì)得到如下的解法,。

• 稀疏矩陣最常用的操作,，也是我當(dāng)前唯一用到的操作，就是根據(jù)橫縱坐標(biāo)查詢某位置元素的值,。于是我用std::map實(shí)現(xiàn),，key是一個(gè)std::pair (x,y)，value是用模板定義的矩陣元素的類型,。但是很快發(fā)現(xiàn),，當(dāng)矩陣規(guī)模增加之后，內(nèi)存使用迅速膨脹,?？磥恚瑂td::map的內(nèi)存使用不合乎要求,。
• 于是我決定用Vector加排序來實(shí)現(xiàn),。我把坐標(biāo)和對應(yīng)值封裝了一個(gè)結(jié)構(gòu)體，還是用坐標(biāo)作為key,。每次將這個(gè)結(jié)構(gòu)壓入vector中,。全部數(shù)據(jù)都存入后再對這個(gè)vector排序。排序的準(zhǔn)則是自定義的坐標(biāo)比較函數(shù),。當(dāng)使用的時(shí)候，可以利用下面的二分查找來實(shí)現(xiàn),，如,，

  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;
      }
      }

使用了這一方法后，內(nèi)存的使用降了下來,。但是,，這是最優(yōu)的方法嗎,？顯然還不是。在這里,，除了所有的非零元素必須存儲(chǔ)外,，對于每個(gè)非零元素，我們存了兩個(gè)坐標(biāo),，兩個(gè)32bit int也就是8個(gè)字節(jié),。經(jīng)過在網(wǎng)上的一番搜索和學(xué)習(xí)后，我又發(fā)現(xiàn)了如下幾種更加經(jīng)典的好方法,。

1. 行壓縮存儲(chǔ),。如下圖所示
   • AN (Array of Non-zero elements, 猜的，下同）：用來記錄所有的非零元素,，這個(gè)是省不掉的,。
   • AJ (Array of j, j一般用來指縱坐標(biāo)，即列索引）：用來記錄在每一行上,，哪些列出現(xiàn)了非平凡值,。比如第一行的6,9,4，它們出現(xiàn)在列1,3,6上,，以此類推,。
   • AI (Array of i)：它用來記錄每一行上第一個(gè)元素的編號，如果我們按從左到右從上到下的順序給非零元素編號的話,。比如,， 第一行有三個(gè)元素，第4號元素是第二行的第一個(gè),，第5號元素是第三行的第一個(gè),，等等。

   

   上面那個(gè)矩陣是我們要存儲(chǔ)的稀疏矩陣,。我們用如下三個(gè)vector來表示它,，

   在查詢的時(shí)候，假設(shè)要找(x,y),，從AI開始,，找到要查的那行在AJ中的起止，即[AI[x], AI[x+1]),。再看看,，y是否在AJ的這個(gè)范圍中出現(xiàn)。如果沒有,，那么要找的值就是一個(gè)零元素,，否則從AN中取出對應(yīng)元素即可。注意到,，AN,，AJ是等長的大數(shù)組,，AI是一個(gè)可以忽略的小數(shù)組。使用這種方法,，每個(gè)非零元素多存4個(gè)字節(jié)左右就夠了,。

2. 稀疏分塊的行壓縮存儲(chǔ)，如下圖所示,。

   

   一般的行壓縮存儲(chǔ)方式適用性廣,，但是當(dāng)稀疏矩陣稀疏地很有規(guī)律的時(shí)候，我們還有更好的辦法,。比如上圖,，我們可以把大矩陣分隔成5×5的塊，顯然,，只有某些塊有值,。左下的結(jié)構(gòu)表示哪些塊有值，比如(0,0)上有值,，(1,2)上有值,。有值的塊用一個(gè)指針指向塊內(nèi)的數(shù)據(jù)結(jié)構(gòu)。而在每塊內(nèi)還是用一般的行壓縮方式存儲(chǔ),。

   以上參考：http://ce.et./publicationfiles/1106_547_smailbegovic.pdf

3. QuadTree,，四叉樹的方法。

   

   Pasted from <http://en./wiki/Image:Point_quadtree.svg>

   如果需要的話,，它總是將空間四分,。如果四分后的某個(gè)格子里還有1個(gè)以上的元素的話，則再次分裂,。它可以完全表達(dá)成一棵樹,，每個(gè)結(jié)點(diǎn)上記錄四個(gè)指針，指向子樹的結(jié)構(gòu),。