huffman coding 實作

Github link

huffman 實作我使用了幾個 data structure
1. map
2. min heap
3. tree

主要分3個階段完成huffman coding 所需要的 data structure，對於之後的encode 跟decode是很重要的
Phase 1 : read file and record the frequency of each character (unordered_map)
Phase 2 : using map to construct min heap (min heap)
Phase 3 : using min-heap to create huffman coding tree (tree)


在講 encode 前，先說明huffman的概念

Concept :

wiki link

1. 無失真壓縮
2. 常出現的字，用最少的bit來描述
3. 應用在檔案壓縮

encode algorithm :

1. construct huffman coding tree
    if there are more than 2 in min heap, we dequeue two item.
    add these two frequency and create a new node as virtual item.
    make these two item be new node's left/right child. then push back to min-heap
    go repeat until there are no more than 2
illustrated :
https://www.google.com/search?q=huffman+coding&source=lnms&tbm=isch&sa=X&ved=0ahUKEwiQ4tKOlO7iAhXIw7wKHfESDUAQ_AUIECgB&biw=1024&bih=462#imgrc=QMXyN8ycoMLfrM:

2. replace test character to huffman code

decode algorithm :

1. using huffman tree, scan all the bit from encoded file, and traverse the tree.
    when we get '0' go left child, '1' go right child, until reach leaf node, and then we know the original character.

encode 需注意的地方:

為了達到壓縮，我們要確保，寫黨時候一定是以 binary的方式寫入。
[how]
https://stackoverflow.com/questions/11249859/how-to-save-a-byte-type-char-array-data-to-a-file-in-c

git  操作筆記

如果想對已經push 的 同一筆commit 改寫，怎麼做 ?

git commit --amend 
git push -f // 強制覆寫 (危險!)