Run-length encoding (compression)
การบีบอัดข้อมูลซ้ำซ้อน
- Compression ทำให้ข้อมูลเล็กลง Run-length encoding (RLE) เป็นวิธีง่ายๆ หนึ่งวิธี
- มันทำงานได้ดีเมื่อมีค่าเดียวกันซ้ำกันหลายครั้งติดต่อกัน
- มันคือ lossless: จากรูปแบบที่บีบอัดแล้วคุณสามารถสร้างต้นฉบับเดิมออกมาได้พอดี
"run" คืออะไร
- Run คือช่วงของ character เดียวกันซ้ำ: ใน
"aaabbc","aaa"เป็น run จำนวน 3 ครั้ง - RLE แทนที่แต่ละ run ด้วย character ตามด้วย จำนวนครั้งที่ซ้ำ
- ดังนั้น
"aaabbc"จะกลายเป็น"a3b2c1"— สั้นลงมากเมื่อ runs ยาว
นับ run
- ในการวัด run ให้มองที่ character ก่อน แล้วนับว่ามี same character ตามมาอีกกี่ตัว
- หยุดเมื่อ character ถัดไปต่างกัน หรือคุณถึงจุดจบ (
'\0') - ค่านี้คือความยาวของ run
สร้าง string ที่เข้ารหัส
- เดินผ่าน input สำหรับแต่ละ run เขียน character, แล้วตามด้วย count, ลงใน output
- เคลื่อนตำแหน่ง input ของคุณ พ้น ทั้ง run ก่อนเริ่ม run ถัดไป
- ทิ้ง output string ด้วย
'\0'เพื่อให้เป็น C string ที่ถูกต้อง
#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;
}
ข้อผิดพลาดที่พบบ่อย
- Run-length encoding เก็บค่าแล้วตามด้วย count; มันมีประโยชน์ก็ต่อเมื่อมี long runs เท่านั้น
- มัน lossless — ต้นฉบับจะถูกคืนกลับมาอย่างสมบูรณ์
ลองดูเลย
- หาแต่ละ run แล้วเขียน character และ count ของมันลงใน output
- ผู้เรียกมอบ output buffer ที่ใหญ่พอที่จะเก็บผลลัพธ์ อย่า เขียน
main
Run-length encoding
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.
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 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.
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 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.
คลิก Run เพื่อดูผลลัพธ์ที่นี่