Run-length encoding (compression) · Кодирование длин серий (сжатие)
Squeezing repeated data
- Compression makes data smaller. Run-length encoding (RLE) is one simple way.
- It works well when the same value repeats many times in a row.
- It is lossless: from the squeezed form you can rebuild the exact original.
Сжатие повторяющихся данных
- Сжатие делает данные меньше. Кодирование длин серий (RLE) — один из простых способов.
- Оно хорошо работает, когда одно и то же значение повторяется много раз подряд.
- Оно без потерь: из сжатой формы можно восстановить точный оригинал.
What a "run" is
- A run is a stretch of the same character repeated: in
"aaabbc","aaa"is a run of 3. - RLE replaces each run with the character followed by how many times it repeats.
- So
"aaabbc"becomes"a3b2c1"— much shorter when runs are long.
Что такое «серия»
- Серия — это последовательность одинаковых символов: в строке
"aaabbc"символ"aaa"образует серию длины 3. - RLE заменяет каждую серию символом, за которым следует количество повторений.
- Так строка
"aaabbc"превращается в"a3b2c1"— гораздо короче, если серии длинные.
Counting a run
- To measure a run, look at a character, then count how many of the same character follow it.
- Stop when the next character is different, or you reach the end (
'\0'). - That count is the run's length.
Подсчет серии
- Чтобы измерить серию, посмотрите на символ, затем посчитайте, сколько таких же символов следуют за ним.
- Остановитесь, когда следующий символ отличается, или вы достигнете конца (
'\0'). - Это количество и есть длина серии.
Building the encoded string
- Walk the input. For each run, write the character, then its count, into the output.
- Move your input position past the whole run before starting the next one.
- End the output string with
'\0'so it is a proper C string.
Создание закодированной строки
- Пройдите входные данные. Для каждой серии запишите символ, затем его количество, в выходную строку.
- Переместите позицию входа за всю серию перед началом следующей.
- Завершите выходную строку символом
'\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;
}
Common mistakes
- Run-length encoding stores a value then its count; it only helps when there are long runs.
- It is lossless — the original is restored exactly.
Распространенные ошибки
- Кодирование длин серий сохраняет значение, затем его количество; оно полезно только при наличии длинных серий.
- Оно без потерь — оригинал восстанавливается точно.
Now you try
- Find each run, then write the character and its count to the output.
- The caller gives you an output buffer big enough to hold the result. Do not write a
main.
Теперь попробуйте сами
- Найдите каждую серию, затем запишите символ и его количество в выходную строку.
- Вызывающий код выделяет буфер вывода достаточного размера для результата. Не записывайте туда
main.
Run-length encoding · Кодирование длин серий
Replace a run of repeats with count + symbol — lossless. · Замените серию повторений на количество + символ — без потерь.
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 not write a main. · Завершите блок int run_length_at(const char *s, int i) так, чтобы он возвращал количество повторений символа ⟨s[i]⟩, начиная с индекса ⟨i⟩. Не пишите код для main.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Complete void rle_encode(const char *in, char *out) so it writes the run-length encoding of in into out: each run becomes the character then its count. "aaabbc" becomes "a3b2c1". End out with '\0'. Do not write a main. · Заполните void rle_encode(const char *in, char *out) так, чтобы оно записывало кодирование длин серий для in в out: каждая серия становится символом, а затем её количеством. "aaabbc" превращается в "a3b2c1". Завершите out с помощью '\0'. Не пишите не main.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.