Huffman 压缩：从字符频率到最优前缀码

// 运行环境：Node.js 14+
// 保存为 aj-l15.js，执行：node aj-l15.js
class Huffman {
  constructor(text) {
    // 1) 统计频率
    const freq = {}
    for (const ch of text) freq[ch] = (freq[ch] || 0) + 1
    // 2) 建树：最小堆取两个最小频率节点合并
    let nodes = Object.entries(freq).map(([ch, f]) => ({ ch, f, left: null, right: null }))
    while (nodes.length > 1) {
      nodes.sort((a, b) => a.f - b.f)
      const l = nodes.shift(), r = nodes.shift()
      nodes.push({ ch: null, f: l.f + r.f, left: l, right: r })
    }
    this.root = nodes[0]
    // 3) 生成编码表（遍历树）
    this.code = {}
    const walk = (n, prefix) => {
      if (n.ch !== null) { this.code[n.ch] = prefix || '0'; return }
      walk(n.left, prefix + '0'); walk(n.right, prefix + '1')
    }
    walk(this.root, '')
  }
  encode(text) { return text.split('').map(ch => this.code[ch]).join('') }
  decode(bits) {
    let cur = this.root, out = ''
    for (const b of bits) {
      cur = b === '0' ? cur.left : cur.right
      if (cur.ch !== null) { out += cur.ch; cur = this.root }
    }
    return out
  }
}

// 调用示例
const h = new Huffman('abracadabra')
const code = h.encode('abracadabra')
console.log('编码表:', h.code)             // a:0 b:10 ...（高频更短）
console.log('编码:', code)
console.log('解码:', h.decode(code))        // abracadabra