---
# System prepended metadata

title: Modeling and Coding
tags: [Data Compression]

---

###### 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)}$ 平均而言，要用多少位元來編碼這個事件