Run-length encoding
C Programming Lesson 22 2:19 English narration · English + 中文 subtitles burned in
Chapters
Transcript
Compression makes data smaller, and run-length encoding is the simplest method there is.
压缩让数据变小，而游程编码是其中最简单的一种方法。
It looks for runs — stretches where the same character repeats.
它寻找的是“游程”——同一个字符连续重复的一段。
Take the word a-a-a-b-b-c.
看这个字符串 aaabbc。
There are three runs in it: three, then two, then one.
它里面有三段：3 个、然后 2 个、然后 1 个。
The encoding writes each run as the character, then how many times it repeats.
编码把每一段写成“这个字符，加上它重复了多少次”。
So that becomes a3 b2 c1.
于是它变成了 a3b2c1。
The first task is one run on its own: given a position, how long is the run that starts there?
第一道题只处理一段： 给定一个位置，从那里开始的这一段有多长？
Remember the character at that spot, then walk forward and count how many match it.
记住那个位置上的字符，然后往前走，数有多少个和它相同。
Two things stop you: a different character, or the end of the string.
有两件事会让你停下：遇到不同的字符，或者到了字符串的末尾。
Miss that second one and the loop walks straight past the zero byte into memory that is not yours.
漏掉第二个，循环就会径直越过那个 0 字节， 走进不属于你的内存里。
The second task encodes the whole string, and it is a loop over runs, not over characters.
第二道题要编码整个字符串， 而它是一个按“段”走的循环，不是按字符走的循环。
For each run, write the character and the count into the output.
对每一段，把字符和个数写进输出里。
Then move your input position forward past the whole run.
然后把输入位置往前挪，跳过整整一段。
Finish with a zero byte, so the output is a proper C string.
最后补一个 0 字节，让输出是一个合格的 C 字符串。
And here is the bug everyone writes once: step forward by one instead, and you start counting the same run again from its middle.
下面是每个人都会写错一次的 bug： 如果你只往前挪一格， 你就会从这一段的中间开始，把同一段重新数一遍。
It is worth being honest about when this helps.
值得如实说明它什么时候有用。
On data with long runs — a scanned page that is mostly white, a cartoon image with flat colour — it wins easily.
在有很长重复段的数据上—— 一张几乎全是白色的扫描页，一张色块平整的卡通图——它轻松取胜。
On data where nothing repeats, every single character becomes a character and a one, so the output is twice the size of the input.
而在完全没有重复的数据上， 每一个字符都变成“一个字符加一个 1”， 输出就是输入的两倍大。
Either way nothing is lost: decoding rebuilds the original exactly, which is what lossless means.
但无论哪种情况，信息都没有丢失： 解码能把原文一模一样地还原出来，这就是“无损”的含义。
Four things to take with you.
带走四点。
One: a run is one character repeated in a row.
第一：一段游程就是同一个字符连续重复。
Two: encode it as the character, then its count.
第二：把它编码成“字符，加上它的个数”。
Three: skip past the whole run before the next one.
第三：进入下一段之前，要跳过整整一段。
Four: with no runs at all, the output is bigger, not smaller.
第四：完全没有重复时，输出会变大，而不是变小。
Now do both tasks — the first one is the counting loop the second one needs.
现在两道题都做一下—— 第一题正是第二题要用到的那个计数循环。