このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
反復データの圧縮
- 圧縮はデータを小さくする。ラン長符号化(RLE)はその単純な方法の一つである。
- 同じ値が連続して繰り返される場合に効果的である。
- 可逆圧縮である——圧縮された形式から元のデータを完全に再構築できる。
「連」(Run)とは何か
- 連とは、同じ文字が繰り返されている部分である:
"aaabbc"において、"aaa"は3回繰り返しの連である。 - RLE は各連を、その文字 followed by 繰り返回数 に置き換える。
- したがって、
"aaabbc"は"a3b2c1"となり、連が長い場合は遥かに短くなる。
連のカウント
- 連を測るには、ある文字を見て、次に続く同じ文字がいくつあるか数える。
- 次の文字が異なった場合、または末尾(
'\0')に到達した時点で停止する。 - そのカウントが連の長さである。
符号化された文字列の作成
- 入力を通す。各連に対して、文字、そしてそのカウントを出力に書き込む。
- 次の連に入る前に、入力の位置を連全体を越えて進める。
- 出力文字列を
'\0'で終え、適切なC文字列とする。
English
#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を書かないでください。
探索
ランルースエンコーディング
連続する繰り返しの列を count + symbol で置き換える — 無損圧縮。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
int run_length_at(const char *s, int i)を完成させ、インデックスiから始まる文字列s[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 を書かないこと。
実行ボタンをクリックして出力を確認してください。