Run-length encoding (compression)
ضغط البيانات المكررة
- الضغط يجعل البيانات أصغر. ترميز طول التسلسل (RLE) هو طريقة بسيطة واحدة.
- يعمل بشكل جيد عندما تتكرر نفس القيمة مرات عديدة متتالية.
- هو بدون فقدان: من الشكل المضغوط يمكنك إعادة بناء الأصل الدقيق.
ما هو "التسلسل"
- التسلسل هو سلسلة من نفس الحرف مكرر: في
"aaabbc"،"aaa"هو تسلسل بطول 3. - يقوم RLE باستبدال كل تسلسل بالحرف متبوعًا بـ كم مرة يتكرر.
- لذا يصبح
"aaabbc""a3b2c1"— أقصر بكثير عندما تكون التسلسلات طويلة.
عدّ التسلسل
- لقياس تسلسل، انظر إلى حرف، ثم عد كم عدد الأحرف نفسه التي تليه.
- توقف عندما يكون الحرف التالي مختلفًا، أو تصل إلى النهاية (
'\0'). - هذا العداد هو طول التسلسل.
بناء السلسلة المشفرة
- مرر على المدخلات. لكل تسلسل، اكتب الحرف، ثم عدده، في المخرجات.
- حرك موضع الإدخال الخاص بك بعد كامل التسلسل قبل البدء في التالي.
- أنهِ سلسلة المخرجات بـ
'\0'لتكون سلسلة C صحيحة.
#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;
}
أخطاء شائعة
- يخزن ترميز طول التسلسل قيمة ثم عددها؛ وهو مفيد فقط عندما تكون هناك تسلسلات طويلة.
- هو بدون فقدان — يتم استعادة الأصل بدقة.
الآن جرب بنفسك
- ابحث عن كل تسلسل، ثم اكتب الحرف وعدده في المخرجات.
- يُعطيك المُدْعي مصفوفة مخرجات كبيرة بما يكفي لاستيعاب النتيجة. لا تكتب
main.
ترميز المسارات
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.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 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.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 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.
اضغط تشغيل لرؤية المخرجات هنا.