Pengkodean panjang-lari (kompresi)
Memampatkan data berulang
- Kompresi membuat data menjadi lebih kecil. Pengkodean panjang lari (RLE) adalah salah satu cara sederhana.
- Ini bekerja baik ketika nilai yang sama berulang banyak kali secara berurutan.
- Ini tanpa kehilangan: dari bentuk yang dipadatkan Anda dapat membangun kembali aslinya persis.
Apa itu "lari"
- Sebuah lari adalah rentang karakter yang sama yang berulang: dalam
"aaabbc","aaa"adalah lari sepanjang 3. - RLE mengganti setiap lari dengan karakter diikuti oleh berapa kali ia berulang.
- Jadi
"aaabbc"menjadi"a3b2c1"— jauh lebih pendek saat lari panjang.
Menghitung lari
- Untuk mengukur lari, lihat sebuah karakter, lalu hitung berapa banyak sama karakter yang mengikutinya.
- Berhenti ketika karakter berikutnya berbeda, atau Anda mencapai akhir (
'\0'). - Hitungan itu adalah panjang lari.
Membangun string yang dikodekan
- Jelajahi input. Untuk setiap lari, tulis karakter, lalu hitungannya, ke output.
- Pindahkan posisi input Anda melewati seluruh lari sebelum memulai yang berikutnya.
- Akhiri string output dengan
'\0'agar menjadi string C yang benar.
#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;
}
Kesalahan umum
- Pengkodean panjang lari menyimpan nilai lalu hitungnya; hanya membantu jika ada lari panjang.
- Ini tanpa kehilangan — aslinya dipulihkan persis.
Sekarang Anda coba
- Temukan setiap lari, lalu tulis karakter dan hitungnya ke output.
- Pemanggil memberikan buffer output Anda cukup besar untuk menampung hasilnya. Jangan tulis
main.
Pengkodean panjang rentang
Ganti rentang pengulangan dengan jumlah + simbol — tanpa kehilangan data.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi int run_length_at(const char *s, int i) agar mengembalikan berapa kali karakter s[i] berulang mulai dari indeks i. Jangan tulis sebuah main.
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Lengkapi void rle_encode(const char *in, char *out) agar menulis pengkodean panjang-lari dari in ke out: setiap rentang menjadi karakter lalu jumlahnya. "aaabbc" menjadi "a3b2c1". Akhiri out dengan '\0'. Jangan tulis sebuah main.
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Sekarang batalkan. Lengkapi void rle_decode(const char *in, char *out): setiap karakter dalam in diikuti oleh count satu digit, sehingga "a3b2c1" menjadi "aaabbc". Akhiri out dengan '\0'. Jangan tulis main.
Klik Jalankan untuk melihat output di sini.