---
tags: 演算法, LeetCode
disqus: HackMD
---

# 霍夫曼編碼 (Huffman coding)

## 介紹


`Huffman` 編碼是一種常用的數據壓縮算法，由 [David A. Huffman](https://en.wikipedia.org/wiki/David_A._Huffman) 在 `1952` 年發明。它通過對字符出現的頻率進行編碼，將出現頻率高的字符用較短的位元串`(Bit Strings)`表示，而出現頻率低的字符用較長的位元串`(Bit Strings)`表示，從而實現對數據的壓縮。

`Huffman` 編碼是一種基於貪心算法的編碼方法，它首先根據字符頻率構建一棵 `Huffman` 樹，然後對每個字符進行編碼。構建 `Huffman` 樹的過程中，可以使用 `Min Heap` 來維護節點，每次從 `Heap` 中取出頻率最小的兩個節點合併成一個新節點，直到 `Heap` 中只剩下一個節點，即 `Huffman` 樹的根節點。

`Huffman` 編碼採用前綴編碼`(prefix code)`方式，保證了編碼的唯一性和無歧義性。在解碼時，從 `Huffman` 樹的根節點開始遍歷，遇到 `0` 就進入左子樹，遇到 `1` 就進入右子樹，直到葉子節點，即可得到原始字符。

由於 `Huffman` 編碼採用變長編碼，可以在一定程度上減少數據存儲所需的空間，從而減少數據傳輸所需的帶寬和存儲空間。因此，`Huffman` 編碼被廣泛應用於無損數據壓縮`(Lossless compression)`領域，如圖像、音頻、視頻等。

## 霍夫曼樹建立

在建立樹之前先舉一個霍夫曼編碼的簡易範例

有一段字串要進行壓縮，假設字串編碼規則如下

| 字串 | 編碼 |
| -------- | --------
| A | 000|
| B | 001|
| C | 010|
| SPACE | 110|

我們有以下字串需對其進行壓縮

AAAABBB  C => 000000000000001001001110110010 (30bits)

我們透過先取得單個字串在字串中出現的次數，分別為
* A 出現4次
* B 出現3次
* 空白 出現2次
* C 出現1次

取得次數後對其進行排序，再從最小值的節點開始合併，如下圖所示，合併完成後再從根節點開始編碼，對字串進行壓縮。


// 壓縮後
霍夫曼編碼: AAAABBB  C => 0000101010111111110 (19bits)

統整步驟為以下:

1. 建立一個優先佇列Q，其中包含每個不同的字符。
1. 將Q中的字符按照頻率遞增的順序排序。
1. 對於所有不同的字符，進行以下操作：
* 創建一個新節點`newNode`。
* 從Q中取出頻率最小的字符，作為`newNode`的左子節點。
* 再從Q中取出頻率次小的字符，作為`newNode`的右子節點。
* 計算這兩個最小頻率的和，並將其分配給`newNode`的值。
* 將`newNode`插入`Huffman`樹中。
1. 返回根節點`rootNode`。

## 霍夫曼編碼壓縮步驟

1. 讀取待壓縮的檔案，將檔案轉化為位元串（0和1的序列）。
1. 計算每個字符出現的頻率，通常使用哈希表或數組來記錄每個字符的頻率。
1. 構建 `Huffman` 樹，將每個字符作為一個葉子節點，按照頻率從小到大逐步合併節點，構建成一棵二元樹。合併節點時，可以使用最小堆來維護節點。
1. 獲取每個字符的編碼，從 `Huffman` 樹的根節點開始，往左走記0，往右走記1，獲得每個字符的編碼，通常使用哈希表或數組來記錄每個字符的編碼。
1. 將原始資料編碼，將每個字符用對應的編碼替換，得到編碼後的位元串。
1. 將位元串分組，每組固定長度，將每組位元串轉化為一個整數。
1. 將轉化後的整數寫入壓縮檔案，並記錄最後一組位元串的長度（可能不足固定長度）。
1. 將 `Huffman` 樹的結構和最後一組位元串的長度寫入壓縮檔案中，作為解壓縮時的參考。

## 霍夫曼編碼解壓縮步驟

1. 讀取壓縮檔案，讀取 `Huffman` 樹的結構和最後一組位元串的長度。
1. 構建 `Huffman` 樹，按照壓縮過程中的結構，還原 `Huffman` 樹。
1. 讀取壓縮檔案，將壓縮後的整數還原成位元串，並將最後一組位元串的長度加入。
1. 根據 `Huffman` 樹的結構，還原原始資料。從 `Huffman` 樹的根節點開始，按照位元串的每一位，往左走記 `0`，往右走記 `1`，直到找到一個葉子節點，即為一個字符。
1. 將還原出來的字符依次寫入解壓縮檔案。

## 複雜度

### 時間複雜度

* 構建字符頻率表：需要遍歷字符串一次，時間複雜度為 $O(n)$
* 構建 `Huffman` 樹：需要將所有節點按頻率排序，時間複雜度為 $O(nlogn)$，每次取出兩個頻率最小的節點組合成一個新的節點，需要執行 `n-1` 次，因此時間複雜度為 $O(nlogn)$
* 構建編碼表：需要遍歷 `Huffman` 樹，時間複雜度為 $O(n)$
* 編碼字符串：需要遍歷字符串一次，時間複雜度為 $O(n)$

因此，總時間複雜度為 $O(nlogn)$

### 空間複雜度

* 構建字符頻率表：需要使用一個 `map` 存儲字符的頻率，空間複雜度為 $O(n)$
* 構建 `Huffman` 樹：需要使用一個優先隊列存儲所有節點，因此空間複雜度為 $O(n)$
* 構建編碼表：需要使用一個 `map` 存儲字符的編碼，空間複雜度為 $O(n)$
* 編碼字符串：需要使用一個字符串存儲編碼後的字符串，空間複雜度為 $O(n)$

因此，總空間複雜度為 $O(n)$

## 簡易實現範例

// 定義節點類別，包含字符、頻率和左右子樹節點
class Node {
  constructor(char, freq, left = null, right = null) {
    this.char = char;
    this.freq = freq;
    this.left = left;
    this.right = right;
  }
}

// 建立字符頻率
function buildFrequencyMap(str) {
  const freqMap = {};
  for (let i = 0; i < str.length; i++) {
    if (str[i] in freqMap) {
      freqMap[str[i]] += 1;
    } else {
      freqMap[str[i]] = 1;
    }
  }
  return freqMap;
}

// 建立Huffman樹
function buildHuffmanTree(freqMap) {
  const nodes = [];
  for (let char in freqMap) {
    nodes.push(new Node(char, freqMap[char]));
  }

  while (nodes.length > 1) {
    nodes.sort((a, b) => a.freq - b.freq);
    const left = nodes.shift();
    const right = nodes.shift();
    const parent = new Node('\0', left.freq + right.freq, left, right);
    nodes.push(parent);
  }

  return nodes[0];
}

// 建立Huffman編碼表
function buildHuffmanCodeMap(root) {
  const codeMap = {};

  // 遞歸方式遍歷樹節點，建立編碼表
  function traverse(node, code) {
    if (!node) {
      return;
    }
    if (node.char !== '\0') {
      codeMap[node.char] = code;
    }
    traverse(node.left, code + '0');
    traverse(node.right, code + '1');
  }

  traverse(root, '');
  return codeMap;
}

// 使用Huffman編碼表對字串進行編碼
function encode(str, codeMap) {
  let encoded = '';
  for (let i = 0; i < str.length; i++) {
    encoded += codeMap[str[i]];
  }
  return encoded;
}

// 對編碼後的字串進行解碼
function decode(encoded, root) {
  let decoded = '';
  let currNode = root;
  for (let i = 0; i < encoded.length; i++) {
    if (encoded[i] === '0') {
      currNode = currNode.left;
    } else {
      currNode = currNode.right;
    }
    if (!currNode.left && !currNode.right) {
      decoded += currNode.char;
      currNode = root;
    }
  }
  return decoded;
}

// 範例使用
const str = 'Huffman coding is a data compression algorithm.';
const freqMap = buildFrequencyMap(str);
const root = buildHuffmanTree(freqMap);
const codeMap = buildHuffmanCodeMap(root);
const encoded = encode(str, codeMap);
const decoded = decode(encoded, root);

console.log(`原始字符串: ${str}`);
console.log(`Huffman 編碼: ${encoded}`);
console.log(`解碼後字符串: ${decoded}`);