[筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 42

重念一次早該補起來的「資料結構與演算法」。這篇筆記 Huffmann Encoding。

notes-theideaofalgorithm-javascript-1


課程相關資訊

[連結]:https://hiskio.com/courses/572/lectures/29884

本篇範圍:Chapter 9

請注意:本系列文章為個人對應課程的消化吸收後,所整理出來的內容。換言之,並不一定會包含全部的課程內容,也有可能會添加其他資源來說明。


內容

以下內容由 ChatGPT 生成:

Huffman 編碼是一種被廣泛應用於數據壓縮的方法,它依據字符出現頻率來分配不等長的編碼。出現頻率高的字符使用較短的編碼,出現頻率低的字符則使用較長的編碼,從而達到壓縮數據的目的。

1. 建立字符頻率表(buildFrequencyMap 方法)
此步驟遍歷輸入字符串,統計每個字符的出現次數,並將結果儲存於一個 Map 中。這樣做是為了確定每個字符的重要性,依此來決定其在 Huffman 樹中的位置。
計算複雜度:時間複雜度為 O(s),空間複雜度為 O(m),其中 s 是輸入字符串的長度,m 是不同字符的數量。
2. 按頻率排序並建立節點隊列(sortByFrequence 方法)
將頻率表中的數據轉換成 HuffmanNode 節點,然後將這些節點按照頻率從低到高排序。這是為了之後構建 Huffman 樹時可以從最低頻率的節點開始組合。
計算複雜度:時間複雜度為 O(m log m),空間複雜度為 O(m)。
3. 建立 Huffman 樹(buildTree 方法)
使用先前排序的節點隊列來建立 Huffman 樹。方法是反覆將頻率最低的兩個節點結合成一個新節點,新節點的頻率是兩個子節點的頻率之和,直到隊列中只剩下一個節點,這個節點成為樹的根節點。
計算複雜度:時間複雜度為 O(m),空間複雜度為 O(n),其中 n 是樹中節點的總數,理論上 n=2m-1。
4. 創建 Huffman 編碼表(createHuffmanCode 方法)
這一步驟通過前序遍歷 Huffman 樹來生成每個字符的編碼,並儲存在 Map 中。遍歷到葉節點時記錄從根節點到該葉節點的路徑(左子樹記為 ‘0’,右子樹記為 ‘1’)。
計算複雜度:時間複雜度為 O(n),空間複雜度為 O(m+n)。
5. 使用 Huffman 編碼表進行編碼和解碼
編碼(encode 方法):根據編碼表將輸入字符串轉換成一串由 ‘0’ 和 ‘1’ 組成的編碼字符串。
解碼(decode 方法):逆向操作,從編碼字符串出發,根據 ‘0’ 和 ‘1’ 的序列在 Huffman 樹中尋找對應的字符。


程式碼

參考來源:https://www.lavivienpost.com/huffman-coding-and-decoding/


系列文章

  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 9
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 8
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 7
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 6
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 5
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 48
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 47
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 46
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 45
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 44
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 43
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 41
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 40
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 4
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 39
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 38
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 37
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 36
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 35
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 34
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 33
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 32
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 31
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 30
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 3
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 29
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 28
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 27
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 26
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 25
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 24
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 23
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 22
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 21
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 20
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 2
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 19
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 18
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 17
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 16
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 15
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 14
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 13
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 12
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 11
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 10
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 1
  • 按讚加入粉絲團

    延伸閱讀