ランレングス符号化
モノクロ画像であるFAX (死語?) を転送する際のデータ圧縮に活用する
以下のような画像を送るとする
□□□□□□■■□□□□□□
□□□□■□□□□■□□□□
□□□■□□□□□□■□□□
□□□□■□□□□■□□□□
□□□□□□■■□□□□□□
□を0、■を1として圧縮せずに表現すると 14 x 5 = 70ビット
00000011000000
00001000010000
00010000001000
00001000010000
00000011000000
ランレングス符合にすると… 63ビット
110 010 110
010 001 100 001 100
011 001 110 001 011
010 001 100 001 100
110 010 110
補足説明:
なお例題の解説には曖昧さが…
例題では「3桁ずつ」で切っているが、1が8回以上続いたらどう表現する? (3桁では表現できない)
例題では「どの0,1の連続も最大で7回以内に収まる」という仮定のもと、便宜上3桁としている
8回続く1を 111000001と表現することも出来るが、圧縮にはならない
1が8回 = 1が7回 + 0が0回 + 1が1回 → 111000001
データ量むしろ増えるやん
要は 1が7回、0が0回、1が1回という冗長な表現
https://gyazo.com/8b97dbc2a1a17aba53d20a3455cdb461
黒黒黒黒黒黒黒黒黒黒白白白白白白白白白白黒黒黒黒黒黒黒黒黒黒黒黒黒黒黒黒黒黒黒黒の場合
黒が10回、白が10回、黒が20回
白が0回 … 2進数表記 0 → 0桁 → 「0-2回の1: - 」「区切り:0」「白が0回 00」
※読み取り時、「0が登場するまでの1の個数+2桁を読み取る」というルールのため、便宜上0を2つ付記
黒が10回 … 2進数表記1010 → 4桁 → 「4-2回の1:11」 「区切り:0」 「黒が10回:1010」
白が10回 … 2進数表記1010 → 4桁 → 「4-2回の1:11」「区切り: 0」 「白が10回:1010」
黒が20回 … 2進数表記10100 → 5桁 → 「5-2回の1:111」「 区切り:0」 「黒が20回:10100」
答えは「00011010101101010111010100」 ※40bit → 26bitに圧縮
解読するには以下を繰り返すだけで良い
前提:白の数から宣言する
先頭から「0が出るまで読み取り」
それまでに発見できた1の個数 + 2桁 を0のあとから読み取る
読み取った数字の回数だけ白(or黒)を並べる
例
0が現れるまで1が0回→+2して2桁読み取り → 00 → 白は0回
0が現れるまで1が2回→+2して4桁読み取り → 1010 → 黒が10回
0が現れるまで1が2回→+2して4桁読み取り → 1010 → 白が10回
0が現れるまで1が3回→+2して5桁読み取り → 10100 → 黒が20回