此页面需较新浏览器(支持 SharedArrayBuffer)。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
压缩重复的数据
- 压缩让数据变小。行程长度编码(RLE)是一种简单的方法。
- 当同一个值连续重复很多次时,它的效果很好。
- 它是无损的:从压缩后的形式可以重建出一模一样的原始数据。
什么是“行程”
- 一个行程是同一个字符连续重复的一段:在
"aaabbc"里,"aaa"是一个长度为 3 的行程。 - RLE 把每个行程替换成那个字符,后面跟上它重复了多少次。
- 所以
"aaabbc"变成"a3b2c1"—— 行程越长,缩得越短。
数一个行程
- 要量一个行程,看一个字符,然后数后面跟着多少个相同的字符。
- 当下一个字符不同、或到了末尾(
'\0')时停止。 - 这个计数就是行程的长度。
构建编码后的字符串
- 遍历输入。对每个行程,把字符、再把它的次数写进输出。
- 在开始下一个行程之前,把输入位置移到整个行程之后。
- 用
'\0'结束输出字符串,让它成为一个合格的 C 字符串。
English
#include <stdio.h>
int main(void) {
const char *s = "aaab";
int i = 0;
char c = s[i];
int count = 0;
while (s[i] == c) { // count the first run
count++;
i++;
}
printf("%c%d\n", c, count); // a3
return 0;
}
常见错误
- 行程编码先存值再存数量;只有存在长游程时才有用。
- 它是无损的——能精确还原原始数据。
现在轮到你
- 找出每个行程,然后把字符和它的次数写进输出。
- 调用者会给你一个足够大的输出缓冲区来放结果。不要写
main。
探索
行程长度编码
Replace a run of repeats with count + symbol — lossless.
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
Complete int run_length_at(const char *s, int i) so it returns how many times the character s[i] repeats starting at index i. Do 不 write a main.
点击“运行”查看此处输出。
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
Complete void rle_encode(const char *in, char *out) so it writes the run-length encoding of in 生成 out: each run becomes the character then its count. "aaabbc" becomes "a3b2c1". End out with '\0'. Do 不 write a main.
点击“运行”查看此处输出。
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
Now undo it. Complete void rle_decode(const char *in, char *out): each character in in is followed by a single-digit count, so "a3b2c1" becomes "aaabbc". End out with '\0'. Do 不 write a main.
点击“运行”查看此处输出。