###### tags: `Data Compression` # Modeling and Coding 資料壓縮是透過編碼的技術，來降低資料儲存時所需的空間，等到使用時，再做解壓縮 編碼技術大致分成兩種 - 等長編碼法：每個符號都用相同長度的編碼字進行編碼 - 不等長編碼法：又稱可變長度編碼，利用每個符號發生的機率，給予不同長度的編碼字 :::info 資料壓縮就是使用符號出現機率的不均等，給予不同長度的編碼字 常出現的符號給予較少的位元、不常出現則用較長的位元，以減少資料的大小 換言之，資料壓縮就是使用不等長編碼法進行 ::: 開發資料壓縮演算法可以分為兩個部分 - Modeling : 萃取資料中的冗餘，並且選擇一個適當的模型(規則)來描述這些累贅的過程 - Coding : 將模型與資料間的差異，加以編碼（通常編成二進制碼）的過程 :::info 不必對數據進行編碼，因為數據可用模型來描述，所以只要將模型編碼 ::: ## Modeling 區分成三種 - Physical Models : 能明確表達的模型 - Probability Models : 依機率猜測結果的模型 - Markov Models : 參考前面結果進行預測的模型 ==例子一== 找出一個模型來簡化資料 ^$X_n$ = n+8，n=1, 2,... numbers = 9, 11, 11, 11, 14, 13, 15, 17, 16, 17, 20, 21 $2^4$ < 21 < $2^5$ 因此需要用 5 bits 表示每一筆資料 En = $X_n$ - ^$X_n$ => 0, 1, 0, -1, 1, -1, 0, 1, -1, -1, 1, 1 總共只使用 -1, 0, 1，三個符號，因此只需要用 2 bits 表示每一個符號 ==例子二== 利用數值的關係來簡化資料 numbers = 27, 28, 29, 28, 26, 27, 29, 28, 30, 32, 34, 36, 38 後面的值與前面的值差異不大，所以紀錄起始值、差異值，之後再做運算 result = 27, 1, 1, -1, -2, 1, 2, -1, 2, 2, 2, 2, ==編碼過程的術語== - Alphabet：符號集、符號的集合 - Letter/Symbol：字母、符號、符號集合中的元素 - Coding：編碼 - Code：碼、二進制序列的集合 - Codeword：編碼字、Code裏的個別成員 ## Coding ![](https://hackmd.io/_uploads/BJj_GuCE2.png) ![](https://hackmd.io/_uploads/B1jXWXC43.png) ### Average Length (平均編碼長度) 平均編碼長度 = (每個符號的編碼位元數 x 發生機率) 的總和 例如：Code 1 => $0.5 \times 1 + 0.25 \times 1 + 0.125 \times 1 + 0.125 \times 2 = 1.125$ ### Uniquely Decodable (唯一可解碼) 表示該編碼方式在解碼時，符號可完全正確不產生混淆 - Code 1：a1、a2 使用相同的編碼字，所以不是唯一可解碼 - Code 2：若 a1 同時傳輸兩次，那解碼端無法知道該編碼字是 a1 或 a3，所以不是唯一可解碼 - Code 3：編碼字不衝突，重複傳輸也不會混淆，所以是唯一可解碼 - Code 4：解碼時遇到0，代表要開始解碼一個新的符號，所以是唯一可解碼 ### Instantaneous Code (瞬間可解碼) 表示該編碼方式在解碼時，收到任一完整的編碼字，可以立刻解碼出其對應的符號 若不是瞬間可解碼，代表需等到下一個位元出現，才有可能解碼該符號 這對應的概念是前綴碼 ==Prefix Code== ，指每個碼字，都具備「前置性質」(prefix property) 也就是在編碼中的每個碼字，都不會是其他碼字的前綴 - Code 3：任一編碼字都不是其他編碼字的前綴，所以是瞬間可解碼 - Code 4：a1 是 a2、a3、a4 的前綴，a2 是 a3、a4 的前綴，a3 是 a4 的前綴，必須等到下一位元才可解碼，所以不是瞬間可解碼 ![](https://hackmd.io/_uploads/r159zOA4h.png) ![](https://hackmd.io/_uploads/BkaPWXCVh.png) :::info 如果符合 Prefix Code，則一定是瞬間可解碼，且為最簡潔的編碼 ::: ### Entropy (熵、散度) 散度用來衡量資料的可壓縮量，在圖形中越細越尖的地方，代表散度小 $H(X) = E\ [Log_2 \dfrac{1}{P(x)}] = \sum_{x} P(x) Log_2 \dfrac{1}{P(x)} = -\sum_{x} P(x) Log_2 P(x)$ in bits $\dfrac{1}{P(x)}$ 表示事件發生所帶來的訊息量 ， $Log_2 \dfrac{1}{P(x)}$ 表示將訊息量用 2 位元編碼 \ $發生率 \times 訊息量 = 平均訊息量$ $P(x) Log_2 \dfrac{1}{P(x)}$ 平均而言，要用多少位元來編碼這個事件