{%hackmd @yW7HKRexRASTmH3kBDXQpQ/dark_theme2 %}
<style>
html, body{
background-color: #333;
color: #ddd;
}
</style>
## 無失真壓縮
無失真壓縮指得是壓縮後的資料經過解壓縮也能還原成原本的資料。

Huffman compression是一種無失真壓縮的方法。

## Huffman encoding
每個字元(character) 如 'A', 'B' ,'C'..., 在檔案中皆是以1 byte儲存的。當資料一但變大，資料的儲存就會變得很不容易，因為需要更多的儲存空間。

而藉由Huffman encoding，可以將資料編碼成variable-length codes， 像是: 'A' -> 00 , 'B' -> 1110 , 'C' -> 010。

那麼將ABCABC (6 byte)的資料，就可以轉成001110010001110010 (18 bits)的資料。

Huffman algorithm 是根據資料頻率決定資料如何編碼的。
另外，Huffman encoding是一種無前綴碼(prefix-free code)，即某個編碼不會是另一個編碼的前綴。 例如00是001的前綴。

每個資料的編碼藉由Huffman tree形成，通常往左走是0，往右走是1。

Huffman Algorithm step:
1. 先知道出現的資料跟其頻率
2. 每次取出兩個最小的頻率跟資料，用一個新節點連接這兩個節點 (此節點之後也要考慮)
3. 重複2，直到剩下一個節點為止

## Huffman compression
1. 建立Huffman tree
2. 寫入編碼表及壓縮資料
(這樣就是壓縮)
3. 讀壓縮檔
4. 讀出編碼表，重建Huffman tree
5. 讀出資料，重建原始資料
(解壓縮)

## Code

### Huffman Node
Huffman tree -節點的設計 (可依照需求更動)

typedef long long int LONG;
struct HuffmanNode{
    unsigned char value;
    LONG frequency;
    HuffmanNode* left;
    HuffmanNode* right;
};

### STL-map
好用的STL-map，我用它來記錄資料跟其頻率
(用起來有點像陣列(array))

// 宣告
map<char, LONG> data_frequency;

插入資料可以用 insert() 或 array形式 如: data_frequency['A'] = 1;

尋找該資料是否存在，可用find()

### STL-Priority queue
有優先順序的Queue，資料預設由大到小排序，即優先權高的資料會先被取出。
是Queue的一種，也支援Push(),Pop(),Top()

priority queue宣告時可接受三種參數
1. Type of element (資料型態)
2. container (用來儲存資料)
3. Compare (決定了資料排序順序)
> comp(a,b) return true if we want to order b prior to a.

宣告:

// 簡單的宣告可以只用
priority_queue <int> pq;

// 在這裡我們用
priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;

可以重新寫一個Compare 來更符合我們的使用
* Comparator Classes are used to compare the objects of user-defined classes.

// 比較器用於priority_queue
struct Compare {
    bool operator()(const HuffmanNode* left, const HuffmanNode* right) const {
        if (left->frequency == right->frequency) // same frequency，照字典序
            return left->value >= right->value;

        return left->frequency > right->frequency;
    }
};

[why extra const?](https://stackoverflow.com/questions/71535955/why-custom-comparator-for-set-in-c-requires-extra-const-keyword)

### traversal the tree
通常都用recursion的方式，藉由跑遍每一個藉由跑遍每個Node得到對應的編碼

void generateCodes()
{
    if (root == nullptr) {
        return;
    }
    
    generateCodes(root->left, code + "0", codes);
    generateCodes(root->right, code + "1", codes);
}

### 檔案操作
我覺得用C的寫法比較好寫，就採用C了

宣告:

// read binary file
FILE* fp = fopen(filename, "rb");

// write binary file
FILE* fp = fopen(filename, "wb");

資料處理:

char ch;
// read from binary file
fread(&ch , sizeof(ch), 1, fp);

// write from binary file
fwrite(&ch , sizeof(ch), 1, fp);

> ptr: 資料要存放的地方 pointer
> size: 要讀取的每一個元素大小(bytes)
> count: 要讀取的元素數量
> stream: 指向 FILE 物件的指標

### 寫檔
==**以Binary模式寫檔**==

#### Frequency Table
因為要把編碼表寫進去，所以需要一個long long int(8 bytes) 來儲存編碼表的大小，在利用一個int(4 bytes)存實際為編碼資料的bits數量，1 byte存字元，之後存編碼資料。

大概會長這樣

// 有排版過，實際上是連續存在一起
Table size
2 'A' 00
3 'B' 010

但是有一個問題， 'A'的編碼 00 是以 000000000(1 byte = 8 bits)寫進去的，我們還需要為編碼資料做處理。

#### compressed data
需要把原本的檔案大小也一併寫進去，這樣才能恰好還原回來。

將資料經過編碼以後，一樣需要轉成bytes，不足8 bits則補0，在寫進去。

### 讀檔
==**以Binary模式讀檔**==

讀檔就簡單了，先照原本儲存的方式一一取出來，得到編碼表(std::map 儲存)。

之後藉由編碼表重建Huffman tree
1. 先建立一個新root
2. 照著編碼表，一直新增節點
ex: 'A' 00， 往左走兩步(沒有就新增節點)，走完之後將'A'放入

最後，根據讀出的檔案大小，編碼資料則利用重建的Huffman tree來解壓縮。

## GUI (非必要)
起初是想要用成視窗操作(GUI)的樣子，但我覺得有點難搞 (好吧 修行不夠)。

使用tkinter。

# 一般常見的Code
import tkinter as tk

window = tk.Tk() # GUI 必須的
window.title('...') # 視窗標題
window.geometry('800x1200') # 視窗大小

window.mainloop() # 除非關掉，不然會一直執行

設計流程:
* 一個按鈕可查看檔案- 分為圖片檔跟文字檔
* 一個輸入框可輸入指令
操作範例：
huffman –c –i infile –o outfile
(進行壓縮，infile為輸入檔案，outfile為輸出檔案)
huffman –u –i infile –o outfile
(進行解壓縮，infile為輸入檔案，outfile為輸出檔案)
* 最後是執行指令的按鈕

# Button
btn = tk.Button(text='要顯示的文字', command=要執行的function, font=按鈕格式)
btn.pack() # 按鈕才會顯示在視窗上

# Entry
en =tk.Entry() # 輸入視窗
en.pack()

# 創建一個 Text 元件用於顯示文字內容
text_area = tk.Text(window)
text_area.pack()

# 創建一個標籤用於顯示圖片
canvas = tk.Canvas(window, width = 350, height = 350)  
canvas.pack()