信息表示方式的效率差異#
- 對於同樣的信息，用不同編碼方式存儲，效率顯然不同
- 例如表示一個人的年齡，用三個字符存儲需要三字節，但用一個八位無符號整數只需一字節，節省了 2/3 的空間
- 優秀的從業者在做工程時，腦子裡一直會有一根弦，會認真考慮信息編碼的效率
二維矩陣的基本表示——方法零#
- 二維矩陣最直接的做法是用一個二維數組表示，所需存儲空間是矩陣兩個維度的乘積（M × N）
- 這種表示方法稱為「方法零」
- 如果 M 和 N 非常大，就要占用大量空間
實際應用中的大矩陣#
- 統計兩個單詞一前一後出現的頻率，英語大型字典有約 20 萬個單詞，矩陣有 400 億個元素，需要 80 GB 存儲
- 計算 PageRank 時所需要的網頁之間的鏈接矩陣，假設有 100 億個網頁，矩陣就有 1 萬億億個元素
稀疏矩陣與三元組表示#
- 現實世界裡，行和列兩個維度都很大的矩陣裡，非零元素占比極低
- 在單詞同現矩陣中，非零元素的占比不到 1%
- 在網頁鏈接的矩陣中，這個占比則小於一億分之一
- 表示稀疏矩陣比較通行的方法是只記錄非零元素
- 用一個三元組（行號、列號、元素值）的列表來表示矩陣
用三元組壓縮存儲空間的效果可以提高幾十倍、幾百倍甚至億萬倍。這才使得 Google 能夠實現 PageRank 算法。
三元組的進一步優化#
按行存儲的優化#
- 原始三元組表中行號有很多重複，可以進一步精簡
- 將三元組表拆成兩張表：
- 表一：記錄每個非零元素的列號和數值
- 表二：記錄每一行中非零元素在表一中的起始位置
- 這種方式可以將存儲空間壓縮大約 1/3
按列建索引#
- 矩陣乘法運算中需要按列來訪問非零元素，但三元組是按行存儲的
- 解決方法：建立一個列索引表，記錄矩陣每一列中非零元素索引的起始位置
- 同樣可以用類似的兩張表方式進行優化
矩陣的運算#
加法#
- 兩個矩陣的加法本質是兩個有序線性表的合併
- 用三元組存儲矩陣時，加法的時間複雜度取決於矩陣 X 和 Y 中的非零元素個數
- 比直接用二維數組進行加法（需要遍歷所有元素，包括大量零元素）要高效得多
乘法#
- 矩陣乘法中，結果矩陣 Z 的第 i 行、第 j 列的元素是矩陣 X 第 i 行和矩陣 Y 第 j 列相應元素相乘後求和
- 使用三元組時元素是按行存儲的，需要能快速按列訪問非零元素，因此需要建立列索引
為什麼不複製兩份數據？#
不按照行和列分別存儲兩個備份，原因有二：
- 同步風險：在計算機系統中，同一個數據以不同形式存兩個備份，存在難以同步的風險，特別是多人協作的軟體
- 存儲成本：矩陣的元素可能是一個體量很大的記錄（例如基因數據），沒有必要將整個矩陣儲存兩遍
動態構建矩陣#
- 在大部分應用中，矩陣中的數值都是用某種方法填入的
- 例如建立一個詞語前後同現頻率的矩陣，需要用大量文本，過程中不斷發現新組合，需要將其插入已壓縮的矩陣中
- 通常的解決方法是：在產生矩陣的過程中，採用哈希表來存儲矩陣中相應的數據項，等到整個矩陣構建完成再建立索引
圖與稀疏矩陣#
- 在計算機科學中，圖（Graph）由頂點和邊構成，一張圖其實就對應一個二維矩陣
- 現實世界裡絕大部分的圖都是稀疏的（邊的數量遠少於頂點數量的平方）
- 例如互聯網網頁之間的超鏈接構成了一張極為稀疏的巨大圖
- 自然語言處理中的二元組（Bigram）存儲也需要用到稀疏矩陣的方法
要點#
- 利用計算機處理信息時，通常原始信息的數據量總是大於計算機的存儲容量，因此需要設計好信息的存儲方式，保證信息不丟失，同時存放進有限的存儲空間裡
- 任何一個合格的計算機工程師，都應該掌握稀疏矩陣的存儲和使用方法，這是五級工程師的基本要求
- 能夠實現一個大矩陣（比如需要成百上千台服務器進行存儲和運算）是對四級或 3.5 級工程師的要求