筆記 - Huffman Encoding & Minimal Spanning Tree

Posted on In

本篇為 資料結構與演算法 學習筆記，主題為 Tree 的兩種應用。

Huffman Encoding

Concepts

  1. 常用在資料壓縮的演算法(Lossless compression)
  2. 出現次數多的字母 => 用較少的bits儲存他；
    出現次數較少的字母 => 用較多的bits儲存他

Huffman Tree

從次數較少開始，相加變成parent node

插入並維持sorted狀態

Ref: Huffman Tree Generator

Compression

  1. 讀取檔案，計算字母出現的頻率
  2. 頻率數字排序
  3. 將頻率數字做成Huffman Tree (可使用PQ)
  4. 左邊edge放0, 右邊edge放1，得到節點的encode
  5. 再次讀取檔案，將字母換成Huffman encodes

Decompression

  1. Huffman code與其對照的字母，對應關係儲存在hash table中
  2. 讀取壓縮的檔案內容，將每個byte轉成8 bits儲存在bitArray中
  3. 讀取bitArray，使用left and right algorism將encode轉換回字母

Minimal Spanning Tree

Concepts

  1. Spanning tree: 將一個graph移除某些edges，保持原來的nodes，使其形成一個tree，此時tree稱之為spanning tree
  2. Spanning tree是原本的graph的子集合（subset），包含原本的所有nodes都有連結在一起。一個graph可能會有好幾種可能的spanning tree。
  3. Minimal spanning tree（MST, 最小生成樹）：指將所有edge的weight加起來最小的spanning tree。

Prim’s Algorithm

找出MST的演算法

  1. 可以從任意node開始，最後都會找到一樣的MST
  2. 紀錄已經拜訪過的nodes => 紀錄此node是否被拜訪過
  3. 紀錄要放進MST的edges（做成MST edge list - array）
  4. 找出：weight最小，且不會形成loop的edge（當edge兩端nodes都是拜訪過的，就會形成loop）
  5. 當所有smallest edges都會形成loop時結束

Code前要先做出graph，再寫出Prim’s AL找出MST

Repl

Kruskal’s Algorithm

也是找出MST的演算法，與Prim’s algorithm同樣被歸類為”Greedy Algorithm”

  1. 列出所有edges
  2. 從weight最小的開始，排除會形成loop的edge，放入MST edge list中

會得到相同的MST。時間複雜度O(n logn)

Application of MST

  1. 線路路網設計，街道為edges，十字路口為nodes。MST找出最小佈線成本。
  2. IC板設計