JavaScript贪心算法_霍夫曼编码实现

// 构建霍夫曼树 function buildHuffmanTree(text) { // 统计频率 const freqMap = {}; for (let ch of text) { freqMap[ch] = (freqMap[ch] || 0) + 1; }

// 构建最小堆（用数组模拟） let heap = Object.keys(freqMap).map(ch => Node(ch, freqMap[ch]) );

// 最小堆排序函数（简单实现） const heapify = () => { heap.sort((a, b) => a.freq - b.freq); };

heapify();

AutoGLM沉思

智谱AI推出的具备深度研究和自主执行能力的AI智能体

129

查看详情

// 合并节点 while (heap.length > 1) { const left = heap.shift(); // 最小 const right = heap.shift(); // 次小 const merged = Node(null, left.freq + right.freq, left, right); heap.push(merged); heapify(); }

return heap[0]; // 返回根节点 }

// 生成编码表 function generateCodes(root) { const codes = {}; function traverse(node, code) { if (!node) return; if (node.char !== null) { codes[node.char] = code || "0"; // 单字符情况 } else { traverse(node.left, code + "0"); traverse(node.right, code + "1"); } } traverse(root, ""); return codes; }

// 编码字符串 function huffmanEncode(text) { if (!text) return { encoded: "", codes: {}, tree: null };

const root = buildHuffmanTree(text); const codes = generateCodes(root); const encoded = text.split("").map(ch => codes[ch]).join(""); return { encoded, codes, tree: root }; }

// 解码（可选实现） function huffmanDecode(encoded, root) { if (!encoded || !root) return ""; let result = ""; let current = root; for (let bit of encoded) { current = bit === "0" ? current.left : current.right; if (current.char !== null) { result += current.char; current = root; } } return result; }

console.log("原始文本:", text); console.log("编码表:", codes); console.log("编码结果:", encoded); console.log("原长度:", text.length 8); // 假设ASCII console.log("编码长度:", encoded.length); console.log("压缩率:", ((text.length 8 - encoded.length) / (text.length * 8)).toFixed(2));