如何在JavaScript中实现Huffman编码

Huffman编码是一种无损数据压缩算法，由David Huffman在1952年提出。它通过构建一个最小优先队列（最小堆）来生成二进制编码，使得出现频率高的字符拥有更短的编码长度，从而实现对文本数据的有效压缩。在JavaScript中实现Huffman编码，可以利用其强大的数组和对象操作能力，以及一些内置的数据结构如堆来完成。

实现步骤

1. 计算字符频率

首先，我们需要计算输入字符串中每个字符出现的次数。这可以通过遍历字符串并使用一个对象来记录每个字符的出现频率来实现。

function calculateFrequencies(input) {
    const frequencies = {};
    for (const char of input) {
        frequencies[char] = (frequencies[char] || 0) + 1;
    }
    return frequencies;
}

2. 构建Huffman树

构建Huffman树的过程涉及以下步骤：

• 初始化一个最小堆，将所有字符及其频率作为堆中的元素。
• 当堆中元素数量大于1时：
  • 弹出堆中的两个最小频率元素。
  • 创建一个新的内部节点，其频率等于这两个元素的频率之和。
  • 将新节点放入堆中。
• 重复步骤直到堆中仅剩一个元素，即根节点。

function buildHuffmanTree(frequencies) {
    const priorityQueue = new MinPriorityQueue();
    Object.entries(frequencies).forEach(([char, freq]) => {
        priorityQueue.enqueue({ char, freq });
    });

    while (priorityQueue.size() > 1) {
        let left = priorityQueue.dequeue();
        let right = priorityQueue.dequeue();
        let merged = { char: `_${left.element.char}${right.element.char}`, freq: left.element.freq + right.element.freq };
        priorityQueue.enqueue(merged);
    }

    return priorityQueue.dequeue().element;
}

3. 生成编码表

根据Huffman树，我们可以自底向上地生成每个字符的编码。这可以通过递归地访问树的路径来完成。

function generateCodeTable(node, code = '') {
    if (!node.left && !node.right) {
        codeMap[node.char] = code;
        return;
    }
    generateCodeTable(node.left, code + '0');
    generateCodeTable(node.right, code + '1');
}

function getCodeTable(huffmanTree) {
    const codeMap = {};
    generateCodeTable(huffmanTree);
    return codeMap;
}

4. 编码字符串

有了编码表后，我们可以将原始字符串转换为其Huffman编码。

function encodeString(input, codeMap) {
    let encoded = '';
    for (const char of input) {
        encoded += codeMap[char];
    }
    return encoded;
}

5. 解码字符串

解码过程与编码过程相反，需要从编码字符串中按照编码规则解析出原始字符序列。

function decodeString(encoded, huffmanTree) {
    let current = huffmanTree;
    let decoded = '';
    for (const bit of encoded) {
        current = bit === '0' ? current.left : current.right;
        if (current.left === null && current.right === null) {
            decoded += current.char;
            current = huffmanTree; // Reset to root for next character
        }
    }
    return decoded;
}

示例代码

结合上述函数，我们来实现一个完整的Huffman编码与解码功能。

function huffmanEncoding(input) {
    const frequencies = calculateFrequencies(input);
    const huffmanTree = buildHuffmanTree(frequencies);
    const codeMap = getCodeTable(huffmanTree);
    const encoded = encodeString(input, codeMap);
    return { encoded, codeMap };
}

function huffmanDecoding(encoded, huffmanTree) {
    const decoded = decodeString(encoded, huffmanTree);
    return decoded;
}

这个实现提供了基本的Huffman编码与解码功能，适用于文本数据的压缩与解压。通过调整和优化数据结构与算法，可以进一步提升性能和压缩效率。