JavaScript 规范霍夫曼编码

         霍夫曼编码是一种无损数据压缩算法，其中数据中的每个字符都分配有可变长度的前缀代码。出现频率最低的字符获得最大代码，出现频率最高的字符获得最小代码。使用这种技术对数据进行编码非常简单且高效。但是，解码使用此技术生成的比特流效率低下。解码器（或解压缩器）需要了解所使用的编码机制，以便将编码数据解码回原始字符。 

        因此，需要将编码过程的信息与编码数据一起作为字符表及其对应代码传递给解码器。在对大量数据进行常规霍夫曼编码时，此表会占用大量内存空间，而且如果数据中存在大量唯一字符，则由于存在代码本，压缩（或编码）数据大小会增加。因此，为了使解码过程在计算上高效，同时仍保持良好的压缩率，引入了规范霍夫曼码。 

        在标准霍夫曼编码中，使用为每个符号生成的标准霍夫曼代码的位长。首先根据符号的位长按非递减顺序对符号进行排序，然后根据每个位长按字典顺序对符号进行排序。第一个符号获得一个全为零且长度与原始位长相同的代码。对于后续符号，如果符号的位长等于前一个符号的位长，则将前一个符号的代码加一并分配给当前符号。 

        否则，如果符号的位长大于前一个符号的位长，则在增加前一个符号的代码后，将零附加到该代码上，直到长度等于当前符号的位长，然后将代码分配给当前符号。 
此过程继续处理其余符号。 

以下示例说明了该过程：

考虑以下数据： 

生成的标准霍夫曼码的位长度为：  

• 步骤 1：根据位长对数据进行排序，然后根据每个位长度按字典顺序对符号进行排序。 

• 步骤 2：为第一个符号的代码分配与位长相同数量的“0”。 
  ‘c’的代码：0
  下一个符号‘a’的位长为 2 > 前一个符号‘c’的位长为 1。将前一个符号的代码增加 1 并附加 (2-1)=1 个零并将代码分配给‘a’。 
  ‘a’的代码：10
  下一个符号‘b’的位长为 3 > 前一个符号‘a’的位长为 2。将前一个符号的代码增加 1 并附加 (3-2)=1 个零并将代码分配给‘b’。 
  ‘b’的代码：110
  下一个符号‘d’的位长为 3 = 前一个符号‘b’的位长为 3。将前一个符号的代码增加 1 并将其分配给‘d’。 
  ‘d’的代码：111
• 步骤3：最终结果。  

        该方法的基本优点是，传递给解码器的编码信息可以更紧凑、更节省内存。例如，可以简单地将字符或符号的位长度传递给解码器。由于长度是连续的，因此可以轻松根据长度生成规范代码。 
有关使用 Huffman 树生成 Huffman 代码的信息，请参阅之前的文章如下：

c语言：c语言 霍夫曼编码 | 贪婪算法（Huffman Coding | Greedy Algo）_霍夫曼的贪婪c语言-CSDN博客

c++：c++ 霍夫曼编码 | 贪婪算法（Huffman Coding | Greedy Algo）_霍夫曼的贪婪算法设计核心代码-CSDN博客

c#：C# 霍夫曼编码 | 贪婪算法（Huffman Coding | Greedy Algo）-CSDN博客 

c++ STL：c++ STL 霍夫曼编码 | 贪婪算法（Huffman Coding | Greedy Algo）-CSDN博客 

java：java 霍夫曼编码 | 贪婪算法（Huffman Coding | Greedy Algo）-CSDN博客 

python：python 霍夫曼编码 | 贪婪算法（Huffman Coding | Greedy Algo）-CSDN博客 

javascript：JavaScript 霍夫曼编码 | 贪婪算法（Huffman Coding | Greedy Algo）-CSDN博客 

方法：一种简单有效的方法是为数据生成一棵哈夫曼树，并使用类似于 Java 中的 TreeMap 的数据结构来存储符号和位长，以使信息始终保持排序。然后可以使用增量和按位左移运算来获取规范代码。 

执行：

// Node class to store data and its frequency
class Node {
    constructor(char, freq) {
        this.char = char;
        this.freq = freq;
        this.left = null;
        this.right = null;
    }

    // Defining comparators less_than and equals
    lessThan(other) {
        return this.freq < other.freq;
    }

    equals(other) {
        if(other == null) {
            return false;
        }
        if(!(other instanceof Node)) {
            return false;
        }
        return this.freq == other.freq;
    }
}

// Function to generate Huffman codes
function code_gen(root, code_length, code_map) {
    if (root == null) {
        return;
    }

    if (root.left == null && root.right == null) {
        if(!code_map[code_length.length]) {
            code_map[code_length.length] = [];
        }
        code_map[code_length.length].push(root.char);
    }

    code_gen(root.left, code_length + '0', code_map);
    code_gen(root.right, code_length + '1', code_map);
}

// Main function implementing Huffman coding
function testCanonicalHC(chararr, freq) {
    // Priority queue to store heap tree
    let q = [];
    for(let i = 0; i < chararr.length; i++) {
        q.push(new Node(chararr[i], freq[i]));
    }
    q.sort((a, b) => a.lessThan(b) ? -1 : a.equals(b) ? 0 : 1);

    while (q.length > 1) {
        let left = q.shift();
        let right = q.shift();

        let merged = new Node(null, left.freq + right.freq);
        merged.left = left;
        merged.right = right;

        q.push(merged);
        q.sort((a, b) => a.lessThan(b) ? -1 : a.equals(b) ? 0 : 1);
    }

    let root = q.shift();
    let code_map = {};
    code_gen(root, "", code_map);

    // Generate Canonical Huffman codes
    let canonical_map = {};
    let c_code = 0;
    let lengths = Object.keys(code_map).sort((a, b) => a - b);
    for(let length of lengths) {
        code_map[length].sort();
        for(let char of code_map[length]) {
            canonical_map[char] = c_code.toString(2).padStart(length, '0');
            c_code += 1;
        }
        c_code <<= 1;
    }

    // Print Canonical Huffman codes
    let chars = Object.keys(canonical_map);
    chars.sort((a, b) => canonical_map[a].length - canonical_map[b].length || a.localeCompare(b));
    for(let char of chars) {
        console.log(`${char}: ${canonical_map[char]}`);
    }
}

// Driver code
let chararr = ['a', 'b', 'c', 'd'];
let freq = [10, 1, 15, 7];
testCanonicalHC(chararr, freq);

输出：
c:0
a:10
b:110
d:111