霍夫曼編碼 (Huffman coding)

介紹

Huffman 編碼是一種常用的數據壓縮算法，由 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，其中包含每個不同的字符。
2. 將Q中的字符按照頻率遞增的順序排序。
3. 對於所有不同的字符，進行以下操作：
   • 創建一個新節點newNode。
   • 從Q中取出頻率最小的字符，作為newNode的左子節點。
   • 再從Q中取出頻率次小的字符，作為newNode的右子節點。
   • 計算這兩個最小頻率的和，並將其分配給newNode的值。
   • 將newNode插入Huffman樹中。
4. 返回根節點rootNode。

霍夫曼編碼壓縮步驟

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

霍夫曼編碼解壓縮步驟

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

複雜度

時間複雜度

• 構建字符頻率表：需要遍歷字符串一次，時間複雜度為
  $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}`);