Data compression · 数据压缩
Why compress data
- Data takes up space to store and time to send.
- Compression makes a file smaller so it is cheaper to save and faster to share.
- There are two kinds: lossless and lossy.
为什么要压缩数据
- 数据存储需要空间,发送需要时间。
- 压缩(compression)让文件变小,这样保存更便宜、分享更快。
- 压缩有两种:无损(lossless)和有损(lossy)。
Lossless compression
- Lossless makes a file smaller but keeps every bit of the data.
- When you open the file, you get back the exact original.
- It works by finding patterns and writing them in a shorter way.
无损压缩
- 无损让文件变小,但保留数据的每一个比特。
- 当你打开文件时,你得到完全相同的原始数据。
- 它的做法是找出规律,然后用更短的方式写出来。
Original: AAAAAAAA-BBB
Shorter: 8A-3B (8 A's, then 3 B's)
Open it: AAAAAAAA-BBB (exactly the same again)
Lossy compression
- Lossy makes a file much smaller by throwing away some data.
- It drops details that people can barely see or hear.
- You cannot get the exact original back — but it is "close enough".
有损压缩
- 有损通过丢掉一些数据让文件小得多。
- 它丢掉的是人们几乎看不到或听不到的细节。
- 你无法拿回完全一样的原始数据 —— 但它"足够接近"。
Photo (large) --lossy--> Photo (small)
A few colors and fine details are gone,
but your eye hardly notices.
The trade-off: size vs quality
- Lossless keeps full quality, but the file stays larger.
- Lossy gives a much smaller file, but quality goes down a little.
- You choose based on what matters more: perfect data or small size.
取舍:大小 vs 质量
- 无损保留完整质量,但文件仍然较大。
- 有损给出小得多的文件,但质量会下降一点。
- 你根据哪个更重要来选择:完美的数据还是更小的体积。
When to use each
- Use lossless when every detail must be exact.
- Use lossy when a small drop in quality is fine and small size matters.
何时使用哪一种
- 当每个细节都必须精确时,使用无损。
- 当质量稍微下降也没关系、而且体积很重要时,使用有损。
Lossless: text, code, a .zip file, a spreadsheet
Lossy: photos (JPEG), music (MP3), video
Key idea
- Compression trades size against quality (or against work to undo it).
- Lossless = smaller and perfect; lossy = much smaller but not exact.
- Good engineers pick the right kind for the job.
核心思想
- 压缩用大小来换质量(或换还原它所需的工作)。
- 无损 = 更小且完美;有损 = 小得多但不精确。
- 优秀的工程师会为任务挑选合适的种类。
Run-length encoding
- Run-length encoding (RLE) is a simple lossless method.
- A run is a stretch of the same character repeated. RLE stores a count instead of the repeats.
- We will store each run as a pair
[character, count]inside a list.
游程编码
- 游程编码(run-length encoding, RLE)是一种简单的无损方法。
- 游程(run)是同一个字符连续重复的一段。RLE 用一个计数来代替这些重复。
- 我们会把每段游程存成一个
[字符, 计数]对,放进一个列表里。
"AAAB" -> [["A", 3], ["B", 1]] (3 个 A,然后 1 个 B)
[["A", 3], ["B", 1]] -> "AAAB" (解码还原 —— 又完全一样了)
Common mistakes
- Lossless compression can be reversed exactly; lossy throws away detail.
- More compression can mean lower quality.
常见错误
- 无损压缩能精确还原;有损压缩会丢掉细节。
- 压缩得越多,质量可能越低。
Now you try
- Build RLE yourself: an encoder, a decoder, and a length helper.
- Each task checks your function on several inputs. Press Check answer.
现在轮到你
- 自己实现 RLE:一个编码器、一个解码器,再加一个求长度的辅助函数。
- 每个任务都会用多个输入检查你的函数。按检查答案。
Lossless compression · 无损压缩
Run-length encoding replaces a run of repeats with count + symbol. · 游程编码把一串重复换成次数 + 符号。
Write encode(text) for run-length encoding. Return a list of [character, count] pairs, one per run of repeats. Example: encode("AAAB") → [['A', 3], ['B', 1]]. For the empty string return []. · 编写游程编码函数 encode(text)。返回一个 [字符, 计数] 对的列表,每段重复对应一个对。例如:encode("AAAB") → [['A', 3], ['B', 1]]。空字符串返回 []。
Click Run to see the output here. · 点击“运行”查看此处输出。
Write decode(pairs) that reverses the encoder: given a list of [character, count] pairs, rebuild the original string. Example: decode([['A', 3], ['B', 1]]) → 'AAAB'. For [] return · 回报 ''. · 编写 decode(pairs),它是编码器的逆运算:给定一个 [字符, 计数] 对的列表,重建原始字符串。例如:decode([['A', 3], ['B', 1]]) → 'AAAB'。[] 返回 ''。
Click Run to see the output here. · 点击“运行”查看此处输出。
Without decoding, write original_length(pairs) that returns how many characters the original text had — just add up the counts. Example: original_length([['A', 3], ['B', 1]]) → 4. · 不用解码,编写 original_length(pairs),返回原始文本有多少个字符 —— 把所有计数加起来即可。例如:original_length([['A', 3], ['B', 1]]) → 4。
Click Run to see the output here. · 点击“运行”查看此处输出。