ぎゅっと圧縮郵便局

よく出る記号は短い符号、まれな記号は長い符号!泡を合体させてハフマン符号の木を作り、最少ビットで手紙を送ろう。すき間のないビット列を記号に切りもどす問題もあります。

あそぶ

コンピューターの「データ圧縮」を知るパズルゲームです。郵便局は、記号(星、ハート、葉、しずく、月、雲、音符、花)がならんだ手紙を 0 と 1 で送ります。どの記号にも同じ長さの符号をつけるのが固定長符号。でも、よく出る記号とめったに出ない記号があるので、よく出る記号に短い符号をつけると手紙全体が短くなります。記号ごとの「回数の泡」を 2 つずつ合体させて回数をたし、木が 1 本になるまで続けます。根から記号までの 0 と 1 の枝の道すじが、その記号の符号です。

合体するたびに、そのノードの下の記号の符号がみんな 1 ビットのびるので、合計ビットはそのノードの回数だけふえます。画面にはこの合計がその場で表示されます。どの順番で合体しても読みもどせる符号はできますが、いちばん少なくなるのは「いつも回数がいちばん少ない 2 つ」を合体させたときだけ。これがハフマン符号です。「ビットを切る」ステージでは、すき間のない 0 と 1 の列がとどき、符号表を見ながら記号の符号が終わるところで切ります。接頭符号に区切り記号がいらない理由を体験できます。

全 5 章 30 ステージ:はじめての合体、ビット列を切る、記号をふやそう、小さくなるのはいつ?(同じ回数ずつだと小さくならない、半分・4 分の 1 だときれいに小さくなる、引き分けのとき)、送って、返事を読む(自分で木を作って送り、友だちがその木で書いた返事を自分の符号表で読む)。さらに無限の「ランダム手紙」があります。問題はプログラムで作られ、得な合体と損な合体の両方があることを確かめています。送った手紙は切手になって切手帳に集まります。

あそびかた

  1. 「送りはじめる」でまだクリアしていないステージから、または「ステージ」から章を選びます。新しい章にはじめて入ると「郵便局メモ」が小さな図でその章の考え方を説明します。タイトル画面の「郵便局メモ」でいつでも読み返せます。
  2. 木を作る:上に送る手紙、下の泡はそれぞれ 1 種類の記号と、出てくる回数です(×4 なら 4 回)。泡をタップして選び、もう 1 つタップすると、2 つが回数の合計を書いたノードに合体し、0 と 1 の枝でつながります。合体ずみの小さな木も、ほかの泡や木とさらに合体できます。上の「合計」は合体のたびにその数だけふえ、となりには固定長符号のビット数が出ています。木が 1 本になると記号の横に符号が出るので、「送る!」をタップ。
  3. ビットを切る:上に符号表、下に 0 と 1 の長い列があります。左から読んで、ある記号の符号が終わるビットをタップすると、そのうしろで切れて、その部分の上に記号が出ます。早すぎたりおそすぎたりしたら、どこがちがうかやさしく教えてくれます。第 5 章では先に木を作って送り、友だちの返事を自分の木で読みます。
  4. 合体ステージ:合計が最少なら星 3 つ、少し多い(10% 以内)なら 2 つ、それより多いと 1 つ。ビットを切るステージ:切りまちがいなしで 3 つ、1~2 回なら 2 つ。ヒントを使うと最大 2 つです。もどす・やり直しはいつでもでき、制限時間もありません。1 つの章で 3 ステージクリアすると次の章が開きます。

そうさ方法

保護者の方へ

最終更新:

こちらもおすすめ