最近一段時間在工作中需要處理稀疏矩陣，遇到如何有效存儲的問題。所謂稀疏矩陣是指這樣一個矩陣，0元素（或者某種占絕對優(yōu)勢的元素）占了絕大多數(shù)。稀疏矩陣的應用非常之廣，比如處理圖像（有大量單一顏色）、用向量空間模型來表示文檔、表達兩個變量之間的兩兩關系。存儲這樣的矩陣，直接用一個二維數(shù)組顯然是不經(jīng)濟的。
如果只是簡單想一想，可能會得到如下的解法。
- 稀疏矩陣最常用的操作，也是我當前唯一用到的操作，就是根據(jù)橫縱坐標查詢某位置元素的值。于是我用std::map實現(xiàn)，key是一個std::pair (x,y)，value是用模板定義的矩陣元素的類型。但是很快發(fā)現(xiàn)，當矩陣規(guī)模增加之后，內(nèi)存使用迅速膨脹?？磥恚瑂td::map的內(nèi)存使用不合乎要求。
- 于是我決定用Vector加排序來實現(xiàn)。我把坐標和對應值封裝了一個結構體，還是用坐標作為key。每次將這個結構壓入vector中。全部數(shù)據(jù)都存入后再對這個vector排序。排序的準則是自定義的坐標比較函數(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)的方法嗎？顯然還不是。在這里，除了所有的非零元素必須存儲外，對于每個非零元素，我們存了兩個坐標，兩個32bit int也就是8個字節(jié)。經(jīng)過在網(wǎng)上的一番搜索和學習后，我又發(fā)現(xiàn)了如下幾種更加經(jīng)典的好方法。
- 行壓縮存儲。如下圖所示
- AN (Array of Non-zero elements, 猜的，下同）：用來記錄所有的非零元素，這個是省不掉的。
- AJ (Array of j, j一般用來指縱坐標，即列索引）：用來記錄在每一行上，哪些列出現(xiàn)了非平凡值。比如第一行的6,9,4，它們出現(xiàn)在列1,3,6上，以此類推。
- AI (Array of i)：它用來記錄每一行上第一個元素的編號，如果我們按從左到右從上到下的順序給非零元素編號的話。比如， 第一行有三個元素，第4號元素是第二行的第一個，第5號元素是第三行的第一個，等等。
- 稀疏分塊的行壓縮存儲，如下圖所示。
一般的行壓縮存儲方式適用性廣，但是當稀疏矩陣稀疏地很有規(guī)律的時候，我們還有更好的辦法。比如上圖，我們可以把大矩陣分隔成5×5的塊，顯然，只有某些塊有值。左下的結構表示哪些塊有值，比如(0,0)上有值，(1,2)上有值。有值的塊用一個指針指向塊內(nèi)的數(shù)據(jù)結構。而在每塊內(nèi)還是用一般的行壓縮方式存儲。
以上參考：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的這個范圍中出現(xiàn)。如果沒有，那么要找的值就是一個零元素，否則從AN中取出對應元素即可。注意到，AN，AJ是等長的大數(shù)組，AI是一個可以忽略的小數(shù)組。使用這種方法，每個非零元素多存4個字節(jié)左右就夠了。
