编码✅

编码是将信息从一种形式转换为另一种形式的过程。本章涵盖字符编码、Base64编码和数据压缩编码等核心概念。

UTF-8、ASCII、UTF-16有什么区别？

答案

核心概念

字符编码是将字符映射为数字的标准化方案，用于在计算机中存储和传输文本数据。不同编码方案在存储效率、字符支持范围和兼容性方面各有特点。

编码对比

编码格式	字符长度	支持字符	存储特点	兼容性
ASCII	7位	128个英文字符	固定长度，节省空间	广泛支持但限制大
UTF-8	1-4字节	全部Unicode字符	变长编码，向后兼容ASCII	互联网标准
UTF-16	2-4字节	全部Unicode字符	变长编码，适合亚洲字符	Windows系统常用

详细特点

ASCII（American Standard Code for Information Interchange）

• 最早的字符编码标准，1963年制定
• 7位编码，支持128个字符（0-127）
• 主要包括英文字母、数字、标点符号和控制字符
• 占用空间最少，但无法表示非英文字符

UTF-8（8-bit Unicode Transformation Format）

• 变长编码，使用1-4个字节表示字符
• 完全向后兼容ASCII（ASCII字符仍用1字节表示）
• 英文字符1字节，中文字符通常3字节
• 互联网和现代系统的主流编码

UTF-16（16-bit Unicode Transformation Format）

• 变长编码，使用2-4个字节表示字符
• 基本多语言平面字符用2字节（BMP，U+0000到U+FFFF）
• 扩展字符使用4字节（代理对机制）
• Windows系统内部广泛使用

实际应用场景

• Web开发: UTF-8是标准选择，支持国际化且兼容ASCII
• 数据库: 现代数据库默认支持UTF-8，确保多语言数据正确存储
• 文件系统: Linux/macOS使用UTF-8，Windows使用UTF-16
• API设计: 推荐使用UTF-8确保跨平台兼容性

面试官视角

该题考察候选人对底层技术的理解：

• 要点清单: 理解编码基本概念；知道主流编码特点；了解兼容性问题；有实际应用经验
• 加分项: 了解编码历史发展；能处理编码转换问题；知道性能影响；有国际化项目经验
• 常见失误: 混淆字节和字符概念；不理解变长编码；忽视兼容性问题；缺乏实践经验

延伸阅读

• Unicode标准官方文档 — Unicode编码标准
• 字符编码详解 — 经典技术文章

Base64编码原理是什么？

答案

核心概念

Base64是一种基于64个可打印字符来表示二进制数据的编码方法。它将二进制数据转换为ASCII字符串，使得二进制数据能够在文本协议中安全传输。

编码原理

1. 字符表定义：使用64个字符（A-Z, a-z, 0-9, +, /）
2. 数据分组：将原始数据按3字节（24位）分组
3. 重新分组：将24位重新分为4组，每组6位
4. 字符映射：将每个6位数值映射到Base64字符表
5. 填充处理：不足3字节的用'='字符填充

编码步骤

原始数据: "Man"
ASCII码值: 77, 97, 110
二进制: 01001101 01100001 01101110
6位分组: 010011 010110 000101 101110
十进制: 19, 22, 5, 46
Base64: T, W, F, u
结果: "TWFu"

示例实现

/**
 * Base64编码实现
 */
class Base64 {
  constructor() {
    // Base64字符表
    this.chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';
    this.charMap = {};
    
    // 构建字符映射表
    for (let i = 0; i < this.chars.length; i++) {
      this.charMap[this.chars[i]] = i;
    }
  }

  /**
   * 编码字符串为Base64
   * @param {string} str - 输入字符串
   * @returns {string} Base64编码结果
   */
  encode(str) {
    let result = '';
    let i = 0;
    
    // 将字符串转换为字节数组
    const bytes = new TextEncoder().encode(str);
    
    // 每3个字节一组进行处理
    while (i < bytes.length) {
      const a = bytes[i];
      const b = i + 1 < bytes.length ? bytes[i + 1] : 0;
      const c = i + 2 < bytes.length ? bytes[i + 2] : 0;
      
      // 合并为24位
      const bitmap = (a << 16) | (b << 8) | c;
      
      // 分割为4个6位，转换为Base64字符
      result += this.chars[(bitmap >> 18) & 63];
      result += this.chars[(bitmap >> 12) & 63];
      result += i + 1 < bytes.length ? this.chars[(bitmap >> 6) & 63] : '=';
      result += i + 2 < bytes.length ? this.chars[bitmap & 63] : '=';
      
      i += 3;
    }
    
    return result;
  }

  /**
   * 解码Base64字符串
   * @param {string} base64 - Base64编码字符串
   * @returns {string} 解码后的字符串
   */
  decode(base64) {
    // 移除填充字符
    const cleanBase64 = base64.replace(/=/g, '');
    let result = '';
    let i = 0;
    
    const bytes = [];
    
    // 每4个字符一组进行处理
    while (i < cleanBase64.length) {
      const a = this.charMap[cleanBase64[i]] || 0;
      const b = this.charMap[cleanBase64[i + 1]] || 0;
      const c = this.charMap[cleanBase64[i + 2]] || 0;
      const d = this.charMap[cleanBase64[i + 3]] || 0;
      
      // 合并为24位
      const bitmap = (a << 18) | (b << 12) | (c << 6) | d;
      
      // 分割为3个8位字节
      bytes.push((bitmap >> 16) & 255);
      if (i + 2 < cleanBase64.length) bytes.push((bitmap >> 8) & 255);
      if (i + 3 < cleanBase64.length) bytes.push(bitmap & 255);
      
      i += 4;
    }
    
    // 将字节数组转换回字符串
    return new TextDecoder().decode(new Uint8Array(bytes));
  }

  /**
   * 编码二进制数据为Base64
   * @param {Uint8Array} bytes - 二进制数据
   * @returns {string} Base64编码结果
   */
  encodeBytes(bytes) {
    let result = '';
    let i = 0;
    
    while (i < bytes.length) {
      const a = bytes[i];
      const b = i + 1 < bytes.length ? bytes[i + 1] : 0;
      const c = i + 2 < bytes.length ? bytes[i + 2] : 0;
      
      const bitmap = (a << 16) | (b << 8) | c;
      
      result += this.chars[(bitmap >> 18) & 63];
      result += this.chars[(bitmap >> 12) & 63];
      result += i + 1 < bytes.length ? this.chars[(bitmap >> 6) & 63] : '=';
      result += i + 2 < bytes.length ? this.chars[bitmap & 63] : '=';
      
      i += 3;
    }
    
    return result;
  }
}

// 创建Base64实例
const base64 = new Base64();

module.exports = { Base64, base64 };

Tests

应用场景

• 邮件传输: MIME协议中传输二进制附件
• 数据URI: 在HTML/CSS中内嵌图片和资源
• API通信: REST API中传输二进制数据
• 配置存储: 将二进制配置编码为文本格式

编码特点

• 大小增长: 编码后数据增大约33%（3字节变4字符）
• 安全传输: 只使用可打印ASCII字符，避免传输问题
• 无损编码: 可以完全还原原始二进制数据
• 标准化: RFC 4648标准，广泛支持

面试官视角

该题考察候选人对编码算法的理解：

• 要点清单: 理解编码原理和步骤；能手动实现编解码；知道应用场景；了解性能影响
• 加分项: 了解变种编码（URL安全等）；知道优化技巧；有实际项目应用；理解安全考虑
• 常见失误: 不理解6位分组原理；填充机制处理错误；忽视字节序问题；混淆编码与加密

延伸阅读

• RFC 4648 - Base64编码标准 — 官方编码标准
• MDN Base64指南 — Web开发中的Base64应用

霍夫曼编码如何实现？

答案

核心概念

霍夫曼编码是一种无损数据压缩算法，通过为出现频率高的字符分配较短的编码，为频率低的字符分配较长的编码，从而实现数据压缩。

算法原理

1. 频率统计：统计每个字符在文本中的出现频率
2. 构建优先队列：将字符按频率从小到大排序
3. 构建霍夫曼树：
   • 取出频率最小的两个节点
   • 创建新节点作为它们的父节点，频率为两者之和
   • 将新节点插入队列，重复直到只剩一个节点
4. 生成编码表：从根节点到叶节点的路径（左0右1）即为字符编码
5. 编码数据：用编码表替换原字符

算法特点

• 最优性: 在定长编码中具有最短平均长度
• 前缀性: 任何字符的编码都不是另一个字符编码的前缀
• 变长编码: 频率高的字符编码短，频率低的字符编码长
• 无损压缩: 可以完全还原原始数据

示例实现

/**
 * 霍夫曼树节点
 */
class HuffmanNode {
  constructor(char, freq, left = null, right = null) {
    this.char = char;      // 字符
    this.freq = freq;      // 频率
    this.left = left;      // 左子节点
    this.right = right;    // 右子节点
  }

  // 判断是否为叶节点
  isLeaf() {
    return this.char !== null;
  }
}

/**
 * 霍夫曼编码器
 */
class HuffmanCoder {
  /**
   * 构建霍夫曼树
   * @param {string} text - 输入文本
   * @returns {HuffmanNode} 霍夫曼树根节点
   */
  buildHuffmanTree(text) {
    if (!text || text.length === 0) {
      return null;
    }

    // 统计字符频率
    const freqMap = new Map();
    for (const char of text) {
      freqMap.set(char, (freqMap.get(char) || 0) + 1);
    }

    // 创建叶节点
    const nodes = Array.from(freqMap.entries()).map(
      ([char, freq]) => new HuffmanNode(char, freq)
    );

    // 特殊情况：只有一个字符
    if (nodes.length === 1) {
      return new HuffmanNode(null, nodes[0].freq, nodes[0], null);
    }

    // 构建霍夫曼树
    while (nodes.length > 1) {
      // 按频率排序
      nodes.sort((a, b) => a.freq - b.freq);
      
      // 取出频率最小的两个节点
      const left = nodes.shift();
      const right = nodes.shift();
      
      // 创建新的内部节点
      const newNode = new HuffmanNode(
        null, 
        left.freq + right.freq, 
        left, 
        right
      );
      
      nodes.push(newNode);
    }

    return nodes[0];
  }

  /**
   * 构建霍夫曼编码表
   * @param {HuffmanNode} root - 霍夫曼树根节点
   * @returns {Map} 字符到编码的映射
   */
  buildCodes(root) {
    if (!root) return new Map();

    const codes = new Map();

    // 特殊情况：只有一个字符
    if (root.isLeaf()) {
      codes.set(root.char, '0');
      return codes;
    }

    const traverse = (node, code) => {
      if (node.isLeaf()) {
        codes.set(node.char, code);
      } else {
        if (node.left) traverse(node.left, code + '0');
        if (node.right) traverse(node.right, code + '1');
      }
    };

    traverse(root, '');
    return codes;
  }

  /**
   * 编码文本
   * @param {string} text - 输入文本
   * @returns {Object} 包含编码结果和霍夫曼树的对象
   */
  encode(text) {
    if (!text || text.length === 0) {
      return { encoded: '', tree: null, codes: new Map() };
    }

    // 构建霍夫曼树
    const tree = this.buildHuffmanTree(text);
    
    // 构建编码表
    const codes = this.buildCodes(tree);
    
    // 编码文本
    let encoded = '';
    for (const char of text) {
      encoded += codes.get(char);
    }

    return { encoded, tree, codes };
  }

  /**
   * 解码文本
   * @param {string} encoded - 编码后的二进制字符串
   * @param {HuffmanNode} tree - 霍夫曼树
   * @returns {string} 解码后的文本
   */
  decode(encoded, tree) {
    if (!encoded || !tree) {
      return '';
    }

    let result = '';
    let current = tree;
    
    for (const bit of encoded) {
      // 根据位移动到左或右子节点
      current = bit === '0' ? current.left : current.right;
      
      // 如果到达叶节点，输出字符并回到根节点
      if (current && current.isLeaf()) {
        result += current.char;
        current = tree;
      }
    }

    return result;
  }

  /**
   * 计算压缩比
   * @param {string} original - 原文本
   * @param {string} encoded - 编码后的二进制字符串
   * @returns {Object} 压缩信息
   */
  getCompressionInfo(original, encoded) {
    const originalBits = original.length * 8; // 假设ASCII编码
    const compressedBits = encoded.length;
    const compressionRatio = (1 - compressedBits / originalBits) * 100;

    return {
      originalSize: originalBits,
      compressedSize: compressedBits,
      compressionRatio: Math.round(compressionRatio * 100) / 100
    };
  }
}

module.exports = { HuffmanNode, HuffmanCoder };

Tests

压缩效果分析

对于文本 "this is an example for huffman encoding":

• 原始大小: 39字符 × 8位 = 312位
• 霍夫曼编码: 约150-200位（压缩比30-50%）
• 效果取决于字符频率分布的不均匀程度

应用场景

• 文件压缩: DEFLATE算法（ZIP、gzip）的核心组件
• 图像压缩: JPEG格式中的熵编码步骤
• 网络传输: HTTP压缩、游戏数据压缩
• 数据存储: 数据库索引压缩、日志文件压缩

优化考虑

• 自适应霍夫曼编码: 动态更新编码表适应数据变化
• 多字符编码: 对常见字符组合进行编码
• 内存优化: 使用紧凑的树结构表示
• 并行处理: 分块处理大文件以提高性能

面试官视角

该题考察候选人对高级算法的掌握：

• 要点清单: 理解贪心算法思想；能构建霍夫曼树；掌握编解码过程；分析压缩效果
• 加分项: 了解其他压缩算法；知道实际应用场景；能优化实现；有性能分析能力
• 常见失误: 树构建逻辑错误；编码表生成错误；未处理单字符情况；不理解前缀性质

延伸阅读

• 数据压缩原理 — 斯坦福大学课程资料
• DEFLATE算法详解 — 实际压缩算法应用