קידוד אורך רצף (דחיסה)
צפיפת נתונים חוזרים
- צפיפות הופכת נתונים לקטנים יותר. העתקה באורך ריצה (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;
}
טעויות נפוצות
- ממחושק אורך-רצף (Run-length encoding) מאחסן ערך ולאחר מכן את הספירה שלו; הוא מועיל רק כאשר ישנם רצפים ארוכים.
- זהו קידוד לא אבוד — המקור משוחזר בדיוק.
כעת תנסו בעצמכם
- מצא כל רצף, ולאחר מכן כתוב את התווית ואת הספירה שלה לתוצאה.
- The caller gives you an output buffer big enough to hold the result. Do not write a
main.
אנכוד רצפים
החלף רצף חזרות ב-מספר + סימן — ללא איבוד נתונים.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
שלים int run_length_at(const char *s, int i) כך שיחזיר כמה פעמים התווית s[i] חוזרת החל מאינדקס i. אל תכתוב main.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
שלים void rle_encode(const char *in, char *out) כדי שייכתוב את קידוד אורך הרצף של in לתוך out: כל רצף הופך לתווית ולאחריה המספר שלה. "aaabbc" הופך ל-"a3b2c1". סיים out עם '\0'. אל תכתוב main.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
עכשיו ביטל זאת. השלם את void rle_decode(const char *in, char *out): כל תווית ב-in מלווה בספירת דיגיט אחת, כך ש"a3b2c1" הופך ל"aaabbc". סיים את out עם '\0'. אל תכתוב main.
לחץ על הרץ כדי לראות את התוצא כאן.