16. 字符串压缩与解压：从‘aaabbbcc’到‘a3b3c2’

字符串压缩和解压，听起来挺唬人，其实说白了就是「数数」。把连续重复的字符，换成「字符+重复次数」的格式。反过来，再把这种格式还原成原始字符串。

我在做嵌入式项目时，经常要传输一些传感器状态字符串。比如温度传感器连续上报了 100 次「25.5」，如果原样发送，数据量不小。用这种简单的游程编码（Run-Length Encoding，简称 RLE）压缩一下，能省不少带宽。嗯，虽然它不算最高效的压缩算法，但胜在简单、无专利、实现起来快。

16.1 压缩算法：核心思路

压缩的逻辑其实就三步：

  1. 遍历字符串，记录当前字符。
  2. 数一数这个字符连续出现了几次。
  3. 把字符和次数拼到结果字符串里。

举个例子："aaabbbcc" → 遍历到 'a'，连续 3 次 → 输出 "a3"；接着 'b' 连续 3 次 → 输出 "b3"；最后 'c' 连续 2 次 → 输出 "c2"。最终得到 "a3b3c2"。

你想想看，如果字符串是 "abc"，每个字符只出现一次，压缩后变成 "a1b1c1"，反而更长了。所以这种算法只适合「连续重复字符较多」的场景。

适用场景提醒： 游程编码适合图像数据、传感器日志、简单配置文件等有大量连续重复内容的场景。对于随机字符串，压缩率可能为负。

16.2 压缩的 C 语言实现

直接上代码。我个人习惯用 while 循环配合双指针，一个指针遍历原字符串，另一个指针记录结果位置。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void compress(const char *input, char *output) {
    int i = 0, j = 0;
    int len = strlen(input);

    while (i < len) {
        char current = input[i];
        int count = 1;

        // 数连续重复的字符
        while (i + count < len && input[i + count] == current) {
            count++;
        }

        // 写入字符
        output[j++] = current;

        // 写入次数（处理多位数的情况）
        char countStr[10];
        sprintf(countStr, "%d", count);
        for (int k = 0; countStr[k] != '\0'; k++) {
            output[j++] = countStr[k];
        }

        i += count;
    }

    output[j] = '\0';
}

int main() {
    char src[] = "aaabbbcc";
    char dest[100];
    compress(src, dest);
    printf("压缩前: %s\n", src);
    printf("压缩后: %s\n", dest);
    return 0;
}

这里有个细节：次数可能超过 9，比如 "aaaaaaaaaa"（10 个 a），压缩后是 "a10"。所以不能简单用 output[j++] = count + '0'，得用 sprintf 转成字符串再逐字符写入。我曾经在这个地方踩过坑，直接转字符导致 10 被写成了 ':'（ASCII 码问题），调试了半天才发现。

16.3 解压算法：核心思路

解压就是压缩的逆过程：

  1. 遍历压缩后的字符串。
  2. 遇到一个字符，就往后读数字，直到数字结束。
  3. 把这个字符重复数字指定的次数，写入结果。

比如 "a3b3c2" → 读到 'a'，接着读数字 "3" → 输出 "aaa"；然后 'b' 和 "3" → 输出 "bbb"；最后 'c' 和 "2" → 输出 "cc"。还原成 "aaabbbcc"。

注意： 解压时，数字可能有多位（如 "a12"）。必须完整读取数字字符串，再转换成整数。不能只读一位就停。

16.4 解压的 C 语言实现

void decompress(const char *input, char *output) {
    int i = 0, j = 0;
    int len = strlen(input);

    while (i < len) {
        char current = input[i++];  // 读取字符

        // 读取数字部分（可能多位）
        int count = 0;
        while (i < len && input[i] >= '0' && input[i] <= '9') {
            count = count * 10 + (input[i] - '0');
            i++;
        }

        // 重复写入字符
        for (int k = 0; k < count; k++) {
            output[j++] = current;
        }
    }

    output[j] = '\0';
}

int main() {
    char compressed[] = "a3b3c2";
    char original[100];
    decompress(compressed, original);
    printf("压缩串: %s\n", compressed);
    printf("解压后: %s\n", original);
    return 0;
}

你看，解压的代码比压缩还短一些。核心就是那个 while 循环读数字：count = count * 10 + (input[i] - '0')。这个技巧在处理多位数字时非常实用。

16.5 知识体系流程图

下面这张图把压缩和解压的完整流程串起来了。我建议你多看几遍，理解每一步的输入输出。

字符串压缩与解压流程 压缩流程 输入: 原始字符串 "aaabbbcc" 遍历字符，统计连续重复次数 输出: "a3b3c2" 解压流程 输入: 压缩串 "a3b3c2" 读取字符，解析数字次数 输出: "aaabbbcc" 互为逆操作 ⚠️ 注意：数字可能有多位（如 "a12"），需完整解析 ⚠️ 压缩率：连续重复越多，压缩效果越好

16.6 避坑指南与经验总结

做这个功能时，有几个地方特别容易出问题。我把自己踩过的坑列出来，你写代码时多留个心眼。

  • 数字解析不完整： 我曾经写解压时，只读了数字的第一位。结果 "a12" 被解析成重复 1 次，后面 "2" 被当成下一个字符处理。输出完全乱套。记住，一定要用循环读完所有数字位。
  • 缓冲区溢出： 压缩后的字符串可能比原串长（比如 "abc" → "a1b1c1"）。输出缓冲区要预留足够空间。我一般开原串长度的 2 倍，或者用动态内存。
  • 空字符串处理： 如果输入是空串，压缩和解压都应该直接返回空串。别让代码在 while 循环里死掉。
  • 数字 0 的情况： 理论上压缩时不会出现次数 0，但解压时如果遇到 "a0"，应该输出空。虽然正常压缩不会产生这种数据，但防御性编程总没错。

小技巧： 如果你不确定压缩后的字符串长度，可以用 malloc 动态分配内存，用完后 free 掉。或者先遍历一遍原串，估算最大可能长度（最坏情况是每个字符都不同，长度翻倍）。

16.7 扩展思考

这种简单的游程编码，其实在很多地方都能见到。比如：

  • BMP 图像格式： 早期 Windows 位图就用 RLE 压缩。
  • 传真机： 传真图像本质上是黑白二值图，连续黑白像素非常多，RLE 压缩率很高。
  • 日志系统： 我在项目中用 RLE 压缩过设备状态日志，压缩率能达到 60% 以上。

不过它也有局限。如果字符串是 "abcdefghij"，每个字符都不重复，压缩后反而膨胀到 20 个字符。所以实际使用时，最好先判断一下「连续重复字符的比例」，再决定要不要压缩。

嗯，字符串压缩和解压就讲到这里。代码不长，但细节不少。你动手写一遍，跑几个测试用例，很快就能掌握。

← 上一章 📖 返回目录 下一章 →