1. 壓縮演算法可歸為兩類

1.1. 統計壓縮（即VLC）

1.2. 字典壓縮（如LZ78）

1.3. 從不同的角度利用了給定資料流中存在的統計冗余資訊

2. 背景關系變換

2.1. contextual transform

2.2. 給定一組相鄰的符號集，對它們進行某種方式的變換使其更容易壓縮

3. 行程編碼

3.1. run-length encoding，RLE

3.2. 過去40多年來看似很簡單、實則很高效的編碼技術

3.3. 單字符背景關系模型

3.3.1. 對任何給定的符號，在編碼時我們都只考慮它的前一個符號

3.3.1.1. 如果這兩個符號是相同的，那么行程繼續

3.3.1.2. 如果不相同，那么當前行程終止

3.4. 主要針對的是連續出現的相同符號聚類的現象，它會用包含符號值及其重復出現次數的元組，來替換某個符號一段連續的“行程”（run）

3.5. 將最短碼字分配給最大的值（因為它表示的是最長的行程）

3.5.1. 如果我們從絕對值的角度理解每個行程的開始，那么長度值表示的是資料流中符號變化之間的距離

3.6. 最適用于大多數符號都連續重復出現的資料集

3.6.1. 如果要處理的資料集沒有這樣的性質，那么RLE演算法并不適用

3.6.2. 會將最短的編碼分配給那些連續重復出現的符號

3.7. 示例

3.7.1. AAAABBBBBBBBCCCCCCCC

3.7.2. [A,4][B,8][C,8]

3.8. 編碼作業就是找到一個符號并向前掃描看看其行程有多長

3.9. 解碼作業則相反，給定某個符號值及其長度值的二元組，只需要將正確個數的符號添加到輸出流之后就行了

3.10. 短行程是RLE作為一種演算法面臨的大問題

3.10.1. 存盤短行程的開銷極大地影響了資料壓縮后的大小

3.11. 資料流中交錯出現字面值是會出問題的

3.11.1. 在資料集中增加一個二進制位流，來表示某個給定的符號流中各個符號是否連續重復出現

3.12. 對干擾符號十分敏感

4. 從壓縮角度來說，數值型資料算是最令人討厭的資料型別之一

4.1. GPS的坐標資訊

4.2. 搜索引擎的倒排索引資訊

4.3. 回傳的用戶ID

4.4. 因為大多數時候，我們找不到可以利用的統計資訊

5. 增量編碼

5.1. delta coding

5.2. 將一組資料轉換為各個相鄰資料之間的相對差值（即增量）的程序

5.3. 思想

5.3.1. 給定一組資料，相關的或相似的資料往往會集中在一起，如果這樣，有了兩個相鄰值之間的差，就可以用其中一個值以及該差值來表示另外一個值

5.3.2. 它依靠的是相鄰性

5.4. 在數值型資料這樣普遍而其熵值又如此偏高的情況下，增量編碼提供了一種不依靠統計的轉換

5.5. 目的就是縮小資料集的變化范圍

5.5.1. 為了減少表示資料集中的每個值所需要的二進制位數

5.5.2. 當相鄰數值之間的差相對較小時，增量編碼最有效

5.5.3. 如果差值變大，情況就會變糟

5.6. 最適用于處理時間序列資料以及音頻和影像資料這類多媒體資料

5.6.1. 比如每10秒檢測一次溫度的傳感器所產生的資料

5.6.2. 這類資料中鄰近的資料之間存在著時間上的關聯

5.7. 減法增量編碼演算法的問題是，結果中可能會出現負數，進而產生各種問題

5.7.1. 負數不僅在存盤的時候需要額外的二進制位，此外還可能會增大資料的變化范圍

5.8. 如果增量編碼能做到以下兩點，那么我們就可以認為它生成的資料更容易壓縮

5.8.1. 將資料集中的最大值變小，因此縮小了數值的變化范圍

5.8.2. 生成了許多重復值，可以讓統計壓縮的效率更高

6. XOR增量編碼

6.1. 通過使用按位異或運算（bitwise exclusive OR，XOR）代替減法運算

6.2. 完全繞開了負數出現的問題，因為整數之間的XOR根本不可能產生負數

7. 參照系增量編碼

7.1. 參照系方法通過讓其他數減去最小的數

7.2. “參照系”（frame of reference，FOR）中那個“參照數”（frame）的選取，與將轉換恰當地應用到資料集上有關

7.2.1. 因此需要將資料集細分為更小的資料組

7.3. FOR最初的設計目的是，盡可能地將更多數值匹配到單個整數的空間之內（通常是32位或者128位的整數

7.3.1. 使數值在運行時更容易處理（因為計算機處理經過位元組對齊，是 2的冪的那些數值會更容易），同時還可以將它當作一種漂亮的記憶體壓縮表示

7.3.2. 提供了一種非常簡單的壓縮方法，將 10個整數壓縮到32個二進制位的空間內，這樣的壓縮效果可以說很好了，其結果是產生了一種性能很強的方法，可以在一秒內解碼數十億個整數值，代價則是那些沒有充分利用空間的整數需要額外的開銷

7.4. 修正的參照系增量編碼

7.4.1. Patched Frame of Reference Delta Coding，PFOR

7.4.2. Zukowski等人提出

8. 前移編碼

8.1. move-to-front coding，MTF

8.2. 最簡單的動態統計轉換形式之一

8.3. 資料的排列次序中包含著一些有助于編碼未來符號的資訊

8.4. MTF是區域自適應的

8.4.1. 會根據輸入流中區域區域符號的出現頻次進行調整

8.4.2. 符號在短時間內重復出現時，MTF會重新分配一個較小的值

8.5. 對干擾符號這類問題不敏感

8.6. 問題

8.6.1. 一些搗亂的符號會打亂前面存在的符號流

8.6.1.1. 真實資料中普遍存在

8.7. 解決方法

8.7.1. 不是一讀到某個符號就將它移到最前面，而是采取一些探索式方法慢慢地將它移到最前面

9. 伯羅斯–惠勒變換

9.1. Burrows-Wheeler transform，BWT

9.1.1. 1994年

9.1.2. Burrows與Wheeler合作

9.2. 作業原理

9.2.1. 通過打亂資料流次序來讓重復的子串聚集在一起

9.2.2. 這一操作本身不能壓縮資料，卻可以為后續的壓縮系統提供轉換好的資料流，方便壓縮

9.3. 順序很重要

9.3.1. 熵作為度量單位，它的一個問題是沒有考慮符號之間的順序

9.3.1.1. 事實上符號之間的順序很重要

9.3.2. 通過轉換資料流中符號之間的順序，可以讓資料流更容易壓縮

9.3.3. 在對資料排序后，如果沒有更多額外的資訊指明它是如何變化的，我們無法讓資料重新回到未排序的狀態

9.3.4. 字典序排列

9.3.4.1. lexicographical permutation

9.3.4.2. BWT會打亂資料流中符號的順序，并試圖讓相同的符號簇彼此靠近

9.3.4.3. 找出原始資料集的一種排列，根據其順序，該排列可能更容易壓縮

9.3.5. 通過BWT，在編碼與解碼時無須增加太多的額外資訊

9.4. 示例

9.4.1. BANANA

9.4.2. 在接下來的每一行，我們都會對該字串進行一次回圈右移一位操作

9.4.3. BANANA

ABANAN
NABANA
ANABAN
NANABA
ANANAB
BANANA

9.4.4. 對表中的每一行按字典順序排序

9.4.5. ABANAN

ANABAN
ANANAB
BANANA
NABANA
NANABA

9.4.6. 每個字串的最后一個字符，從上到下

9.4.7. NNBAAA

9.4.7.1. 與BANANA相比更好地將相同的字符聚集在了一起

9.4.8. 0  ABANAN

1  ANABAN
2  ANANAB
3  BANANA
4  NABANA
5  NANABA

9.4.9. 行索引3就是源字串

9.5. 最引人注目的特點在于只需要極小的資料開銷，它所進行的變換操作就是可逆的（reversible）

9.6. 對DNA來說是一種理想的變換，可以使其更容易壓縮、查詢和檢索

9.7. 具體實作

9.7.1. 將整個檔案分為許多1 MB大小的資料塊，然后在每個資料塊上分別應用該演算法

9.8. 最常見的用法

9.8.1. 將BWT的輸出作為MTF的輸入，經過處理后接著用統計編碼演算法處理

9.8.1.1. BZIP2的內部作業原理

標籤：其他

上一篇：LGV引理

下一篇：返回列表