Data Compression 檔案壓縮

Lossy(失真壓縮)

• Relative / difference

  常用影音檔案上，紀錄變化量，不是每一幀的資料

• 傅立葉轉換

Lossless(非失真壓縮)

• Run-length

  依演算法，傳"指令"取代"真實行為"

  例如："接著傳100個0" 取代 "00000000....."

• Frequency- dependent

  Huffman coding - 統一全部編碼的長度很沒效率，所以把常用的符號縮短為原長度，但會衍伸一些問題

• Dictionary

  很常見的字，給一個較短的代碼，與Frequency- dependent有些許關聯，習慣上是越常出現的字 編的越短。傳送檔案時，必須連記錄代碼的code book 一起傳送過去，提供解碼。

資料傳輸

Huffman code

例：

要傳送AAABBBAABCAAAABD >16個字

若用ASCII code編碼，要傳送128個bit

其中

A 出現9次、B 出現5次、C 出現1次、D 出現1次

Huffman使用二元樹

A 0 | B 10 | C 110 | D 111

使用Huffman編碼的話，只要傳送25個bit就好了，節省許多空間，其中要考慮的是，加上傳送解碼的資訊是否有大於原本編碼的大小。

解碼方式

0001010100010110...

跟著二元樹走，看到第一個0可以直接走到A，直到碰到1時下一個數字是0可以走到B，以此類推。

Dictionary 字典壓縮法

LZM 字典壓縮法

不用將code book傳給對方。

將沒有出現過的字串，新增ASCII code 編碼，下次讀取到時，直接用新的編碼即可

(類似String pool的概念，增加上編碼)

檔案傳輸

• 檔案壓縮

  去掉redundancy(多餘的資料)

• Error detection & correction

  增加redundancy回來以防止錯誤

• Error detection: check code

  可以知道對方傳送的檔案有錯誤，但不知道錯在哪裡

• Error correcting

  可以改正錯誤

Check code - Parity bits

在傳送檔案時，每8個bit，多傳送一個bit 來讓這9個bit中1的數量為奇數個