Run-length encoding (compression)
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.
"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.
Đế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.
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;
}
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.
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.
Mã hóa độ dài chuỗi
Replace a run of repeats with count + symbol — lossless.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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 không write a main.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Complete void rle_encode(const char *in, char *out) so it writes the run-length encoding of in thành out: each run becomes the character then its count. "aaabbc" becomes "a3b2c1". End out with '\0'. Do không write a main.
Nhấn Chạy để xem kết quả ở đây.
Độ khó 4/5 · 280 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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 không write a main.
Nhấn Chạy để xem kết quả ở đây.