Run-length encoding (compression)
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · このページには最新のブラウザ（SharedArrayBuffer対応）が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
English
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）はその単純な方法の一つである。
- 同じ値が連続して繰り返される場合に効果的である。
- 可逆圧縮である——圧縮された形式から元のデータを完全に再構築できる。
English
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.
日本語
「連」（Run）とは何か
- 連とは、同じ文字が繰り返されている部分である：
"aaabbc"において、"aaa"は3回繰り返しの連である。 - RLE は各連を、その文字 followed by 繰り返回数 に置き換える。
- したがって、
"aaabbc"は"a3b2c1"となり、連が長い場合は遥かに短くなる。
English
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'）に到達した時点で停止する。 - そのカウントが連の長さである。
English
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;
}
English
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.
日本語
よくあるミス
- ラン長符号化は値とそのカウントを格納し、長い連がある場合にのみ有効である。
- 可逆圧縮である——元データが正確に復元される。
English
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を書かないでください。
Explore · 探索
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.
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.
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。