Run-length encoding (compression) · Mã hóa độ dài chuỗi (nén)
Squeezing repeated data
- Compression makes data smaller. Run-length encoding (RLE) is one simple way.
- It works well when the same value repeats many times in a row.
- It is lossless: from the squeezed form you can rebuild the exact original.
Nén dữ liệu lặp lại
- Nén làm dữ liệu nhỏ hơn. Mã hóa độ dài chuỗi (RLE) là một cách đơn giản.
- Nó hoạt động tốt khi cùng một giá trị lặp lại nhiều lần liên tiếp.
- Nó là mất mát không: từ dạng nén bạn có thể tái tạo lại nguyên bản chính xác.
What a "run" is
- A run is a stretch of the same character repeated: in
"aaabbc","aaa"is a run of 3. - RLE replaces each run with the character followed by how many times it repeats.
- So
"aaabbc"becomes"a3b2c1"— much shorter when runs are long.
"Chuỗi" là gì
- Một chuỗi là một đoạn ký tự giống nhau được lặp lại: trong
"aaabbc","aaa"là một chuỗi 3. - RLE thay thế mỗi chuỗi bằng ký tự theo sau là số lần nó lặp lại.
- Vậy nên
"aaabbc"trở thành"a3b2c1"— ngắn hơn rất nhiều khi các chuỗi dài.
Counting a run
- To measure a run, look at a character, then count how many of the same character follow it.
- Stop when the next character is different, or you reach the end (
'\0'). - That count is the run's length.
Đếm một chuỗi
- Để đo lường một chuỗi, hãy nhìn vào một ký tự, sau đó đếm bao nhiêu ký tự giống nhau theo sau nó.
- Dừng khi ký tự tiếp theo khác, hoặc khi bạn đạt đến cuối (
'\0'). - Số đếm đó là độ dài của chuỗi.
Building the encoded string
- Walk the input. For each run, write the character, then its count, into the output.
- Move your input position past the whole run before starting the next one.
- End the output string with
'\0'so it is a proper C string.
Xây dựng chuỗi đã mã hóa
- Duyệt qua đầu vào. Với mỗi chuỗi, viết ký tự, sau đó số đếm của nó vào đầu ra.
- Di chuyển vị trí đầu vào của bạn qua toàn bộ chuỗi trước khi bắt đầu cái tiếp theo.
- Kết thúc chuỗi đầu ra với
'\0'để nó thành một chuỗi C đúng chuẩn.
#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;
}
Common mistakes
- Run-length encoding stores a value then its count; it only helps when there are long runs.
- It is lossless — the original is restored exactly.
Lỗi thường gặp
- Mã hóa độ dài chuỗi lưu một giá trị rồi số đếm của nó; nó chỉ hữu ích khi có các chuỗi dài.
- Nó là mất mát không — nguyên bản được khôi phục chính xác.
Now you try
- Find each run, then write the character and its count to the output.
- The caller gives you an output buffer big enough to hold the result. Do not write a
main.
Bây giờ bạn thử
- Tìm từng chuỗi, sau đó viết ký tự và số đếm của nó vào đầu ra.
- Người gọi đưa cho bạn một bộ đệm đầu ra đủ lớn để chứa kết quả. Đừng viết một
main.
Run-length encoding · Mã hóa độ dài chuỗi
Replace a run of repeats with count + symbol — lossless. · Thay thế chuỗi lặp lại bằng số lượng + ký tự — không mất dữ liệu.
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 not write a main. · Hoàn thành int run_length_at(const char *s, int i) để trả về số lần ký tự s[i] xuất hiện liên tiếp bắt đầu từ chỉ mục i. Không viết một main.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
Complete void rle_encode(const char *in, char *out) so it writes the run-length encoding of in into out: each run becomes the character then its count. "aaabbc" becomes "a3b2c1". End out with '\0'. Do not write a main. · Hoàn thành void rle_encode(const char *in, char *out) để ghi mã hóa độ dài chuỗi của in vào out: mỗi chuỗi lặp trở thành ký tự rồi đến số lượng của nó. "aaabbc" trở thành "a3b2c1". Kết thúc out với '\0'. Không viết một main.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.