[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇

章節連結

課程相關資訊
內容
程式碼
系列文章

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

本篇範圍：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/

class HuffmanNode {
    constructor(ch, frequency, left, right) {
        this.ch = ch;
        this.frequency = frequency;
        this.left = left;
        this.right = right;
    }  
}

class HuffmanCoding {
    getCode(input) {
        const freqMap = this.buildFrequencyMap(input); 
        const nodeQueue = this.sortByFrequence(freqMap);
        this.root = this.buildTree(nodeQueue);
        const codeMap = this.createHuffmanCode(this.root);
        return codeMap;
    }

    buildFrequencyMap(input) {
        const map = new Map();
        for (let i = 0; i < input.length; i++) {
            const ch = input.charAt(i);
            if (!map.has(ch)) {
                map.set(ch, 1);
            } else {
                let val = map.get(ch);
                map.set(ch, ++val);
            }
        }
        return map;
    }

    sortByFrequence(map) {
        const queue = [];
        for (const entry of map.entries()) {
            queue.push(new HuffmanNode(entry[0], entry[1], null, null));
        }
        queue.sort((a, b) => a.frequency - b.frequency);
        return queue;
    }

    buildTree(nodeQueue) {
        while (nodeQueue.length > 1) {
            const node1 = nodeQueue.shift();
            const node2 = nodeQueue.shift();
            const node = new HuffmanNode('', node1.frequency + node2.frequency, node1, node2);
            nodeQueue.push(node);
        }
        return nodeQueue.shift();
    }

    createHuffmanCode(node) {
        const map = new Map();
        this.createCodeRec(node, map, "");
        return map;
    }

    createCodeRec(node, map, s) {
        if (node.left == null && node.right == null) {
            map.set(node.ch, s);
            return;
        }    
        this.createCodeRec(node.left, map, s + '0');
        this.createCodeRec(node.right, map, s + '1');
    }

    encode(codeMap, input) {
        let s = "";
        for (let i = 0; i < input.length; i++) {
            s += codeMap.get(input.charAt(i));
        }
        return s;
    }

    decode(coded) {
        let s = "";
        let curr = this.root;
        for (let i = 0; i < coded.length; i++) {
            curr = coded.charAt(i) === '1' ? curr.right : curr.left;
            if (curr.left == null && curr.right == null) {
                s += curr.ch;
                curr = this.root;
            }
        }
        return s;
    }
}

const input = "AAAAAABBCCDDEEFFFFF";
const huffman = new HuffmanCoding();       
const codeMap = huffman.getCode(input);
console.log(codeMap);
const encoded = huffman.encode(codeMap, input);
console.log("encoding string: " + encoded); 
const decode = huffman.decode(encoded);
console.log("decoding string: " + decode);