問85
頻出度★☆☆
図を画素で表す手法を考える。図1の場合，3×3個の画素を左上から1行ずつ右方向へ1画素ずつ読み取り，黒なら B，白なら W と書くと“BWBBBBBWB”(9文字)となる。次に，B や W が n 文字連続する場合を“Bn”，“Wn”と表す(n は2以上の整数)と，図1は“BWB5WB”(6文字)と表現でき，このときの圧縮率を 6/9=66.7% であると定義する。図2の5×5の図形について同じ手法で表現すると，圧縮率は何%か。
平成22年度 秋期 ITパスポート試験 問85
テクノロジ系情報メディア › マルチメディア技術
この問題の解説と、これまでの解答の記録です。
解説
問 85
不正解ア
48.0% は 100−52 で求まる値、つまり圧縮によって「減った分」の割合である。本問は図1の例で 6÷9 = 66.7% と示しているとおり、圧縮率を圧縮後の文字数÷圧縮前の文字数と定義している。減少率 (削減できた割合) ではないので、13文字÷25文字 = 52.0% がそのまま答えになる。定義を取り違えて残りを答えると ア を選んでしまう。
- イ
正解 正解は イ (52.0%)。まず図2の25個の画素を、問題文どおり左上から1行ずつ右方向へ読み取る。1行目は5個すべて黒で BBBBB、2行目は左端だけ黒で BWWWW、3行目は左から4個が黒で BBBBW、4行目と5行目はどちらも BWWWW。つなげると BBBBBBWWWWBBBBWBWWWWBWWWW の25文字になる。ここで最大の要点は、連続の数え方が行の切れ目で途切れないことである。1行目の黒5個と2行目の先頭の黒1個がつながるので、先頭は黒が6個連続する。連ごとに区切ると B が6個、W が4個、B が4個、W が1個、B が1個、W が4個、B が1個、W が4個の8つの連になる。2文字以上続く連だけが「B6」「W4」のような2文字表記に置き換わり、1文字しかない連は置き換えずそのまま1文字と数える (n は2以上の整数と定義されているため)。したがって圧縮後は 2+2+2+1+1+2+1+2 = 13文字。圧縮率は問題文の定義どおり圧縮後÷圧縮前なので 13÷25 = 0.52、すなわち 52.0% となる。
不正解ウ
76.0% は 19÷25 に当たる値で、読み取り順を取り違えたときに出る。例えば左上から1列ずつ下方向へ縦に読むと BBBBB / BWBWW / BWBWW / BWBWW / BWWWW となり、黒と白が1個ずつ交互に現れる箇所が増えて置き換えられない1文字の連が多発し、圧縮後が19文字になってしまう。問題文は1行ずつ右方向へと走査順を指定しており、その順なら長い連がまとまって13文字まで縮む。
不正解エ
88.0% は 22÷25 に当たる値で、圧縮を一部の連にしか適用しなかった場合の数字である。例えば目立つ1行目の黒5個だけを B5 に置き換えて残りを元のまま数えると 25−5+2 = 22文字となり 88% になる。実際には2文字以上続く連はすべて置き換え対象で、図2には4個以上続く連が5か所 (黒6個・黒4個・白4個が3か所) あるため13文字まで縮む。置き換え漏れがないよう、連を最後まで数え切る必要がある。
ここがポイント
- ランレングス法 (連長圧縮) の基本 — 同じ値が続く部分を記号と連続個数の組に置き換える可逆圧縮。指定された走査順 (本問は左上から1行ずつ右方向) を必ず守り、行の切れ目でも同じ色が続くなら1つの連としてつなげて数える。この行またぎを見落とすと文字数を数え違える。
- 圧縮率の定義は問題文が与えたものに従う — 本問では圧縮後の文字数÷圧縮前の文字数で、値が小さいほどよく縮んだことを表す (図1の 6÷9 = 66.7% が見本)。また n は2以上と決められているため、1文字だけの連は置き換えない。置き換えるとかえって2文字に増えてしまうからである。
用語