嵌入式系统中LZString解压缩器的最小RAM预算需求

核心RAM预算的最小边界 #

要确定最小RAM需求，需拆解解压缩过程中必须的内存开销：

1. 输出缓冲区 #

如果必须完整存储解压缩后的ASCII JSON（最大2KB），这部分是固定开销，需要2048字节。若支持流式输出（比如边解压缩边写入外设/Flash），则仅需极小的临时输出缓冲区（比如几十字节，用于拼接当前解码的字符串片段），可省去这2KB开销。

2. 字典存储 #

LZString原始compress算法的解压缩依赖字典存储重复字符串的链式引用，无需存储完整字符串——每个字典条目仅需记录：

• 前一个字符串的字典索引（uint16_t，2字节，足够覆盖最大可能的条目数）
• 末尾追加的ASCII字符（uint8_t，1字节）

单条条目占用3字节，最大条目数可通过压缩数据上限反推：
压缩数据最大1KB=8192位，初始编码为9位（覆盖初始256个单字符条目），最多可容纳 8192 ÷ 9 ≈ 910 个编码。字典初始有256个条目，后续每处理一个编码新增1条，因此最大条目数为 256 + 910 - 1 = 1165。

对应字典内存开销为 1165 × 3 = 3495字节 ≈ 3.42KB。

3. 临时变量 #

包括bit流缓冲区（比如uint32_t，4字节）、剩余bit计数器（uint8_t，1字节）等，总开销不足10字节，可忽略。

最坏情况总RAM

• 需完整存储输出：2048 + 3495 ≈ 5.47KB
• 流式输出：仅需约3.42KB

C语言实现的内存边界确定方法 #

1. 静态内存规划 #

• 字典：用固定大小的结构体数组存储，数组大小按最大条目数（1200条，留少量冗余）定义，避免动态内存分配：

  typedef struct {
      uint16_t prev_idx;
      uint8_t last_char;
  } DictEntry;
  
  DictEntry dict[1200]; // 1200 × 3 = 3600字节
  

• 输出缓冲区：若需完整存储，定义uint8_t output[2048];；若流式输出，定义小缓冲区（比如uint8_t temp_buf[64];）用于拼接当前字符串。

2. 边界验证 #

• 构造极端测试用例：生成压缩数据恰好1KB，解压缩后为2KB的重复模式JSON（比如全是相同字符或重复短序列），此时字典条目数达到最大值。
• 实际运行测量：在目标嵌入式系统上运行代码，通过内存监控工具（或手动统计静态/动态内存占用）验证实际RAM使用是否符合计算值。

3. 关键优化点 #

• 摒弃哈希表：直接用数组索引映射编码与字典条目，完全避免哈希表的额外内存开销（这是C++/Python实现内存占用难以界定的核心原因）。
• 链式存储字典：无需存储完整字符串，仅通过前索引+末尾字符的方式复用已有数据，最大化内存效率。

内容的提问来源于stack exchange，提问作者fgrieu