人力LZW圧縮/展開/グリッチ

授業第2回。去年は山本さんに『算道』の実演をしてもらったりeasy6502を使った授業をしてたんだけど、今年はプログラムを書く体験の前の「プログラムを実行する体験」として、圧縮/展開アルゴリズムを受講生の手で実行してもらう授業をやってみた。

もともとはComputer Science Unpluggedを見てたなかでText Compressionのアクティビティが見た目楽しそうで、こういう「テキストが圧縮(コーディング)される」という結果が得られるアルゴリズムが題材なら、コンピュータとプログラムがすることを実感して興味を持ってもらえるイントロダクションの授業ができるんじゃないかと思ったことがきっかけ。

CS Unpluggedの「Text Compression」アクティビティの解説pdfより

でもよく考えたら圧縮アルゴリズムの内容ってよく知らなくてハフマン圧縮とかでできるのかなーと思いながら思って調べているうちに、テキストの圧縮過程を実感できそうでかつ学生も常々お世話になってるだろうLZW圧縮に決めた(検討にはデータ圧縮法概説がとても参考になった。最終的に例文にした早口言葉もこの概説の実演で使用されていたもの)。

当初「受講生の好きな歌の歌詞を圧縮させて、圧縮データを他の受講生と交換して展開する授業にしよう」と思っていたんだけど、実際に自分の手でLZW圧縮のアルゴリズムを実行してみると思った以上に時間がかかる(2,30文字の処理に20分以上)うえ、意図的に歌詞の繰り返しの多い歌を選ばないかぎりは圧縮のおもしろみも味わえない単なる作業になってしまうことが予想できたので、後ろ髪をひかれつつ元テキストは圧縮が効きやすい早口言葉(「カエルピョコピョコ…」)に固定して、プログラム手実行の過程を理解するところにフォーカスできるように手順やワークシートをまとめて授業に臨んだ。

ワークシートその1(入力・出力)(pdf)

ワークシートその2(ワークメモリ:圧縮用辞書)(pdf)(亜展開用辞書(内容は同じです)

圧縮手順書(プログラム部)(pdf )(展開手順pdf

実行時のポインタの役割をするものとして色ごとに役割を決めた付箋を配って使ってもらうようにしたんだけど、これはなかなかうまくいったような気がする。実際に学生(8人)にやってもらったらやってるうちに手順を飛ばしてしまうことが続出したので、もう一つ付箋を配っていま実行している手順を指す(つまりプログラムポインタ)ようにしたほうがよかったかもしれない。手違いで途中からやり直しになってしまった人もいたけど、見たところみんな最初の意味のわからないことをやらされている、という感じから途中でこのアルゴリズムの巧妙さにはっと気づき、最後まで興味を持って作業してもらえていたように思う。

デバッグ中

kotaro tanakaさん(@doppac)がシェアした投稿 -

そして、LZW圧縮といえばGIF画像の圧縮アルゴリズムであり、アーカイブデータのコードをいくつかスワップさせれば簡単にグリッチさせることができる。今回圧縮しているのは文字単位のテキストなので、「カエルピョコピョコミピョコピョコアワセテピョコピョコムピョコピョコ」が「エカルピョピョココミココアココワセココアョピテョムコ」になったりする。というのを、受講生にそれぞれ好きなところでグリッチしたデータを展開させて結果を見てもらった。これ、正常データとグリッチデータを両方手で展開してみると、データの入れ替えが辞書にどのように波及していくかがよくわかってとてもおもしろい。(4,5箇所グリッチするよう指示したけど、2つくらいでもいいのかも)。

というわけで、僕がこれまでいろいろ試したなかでも一番手応えのある授業になってよかった。来週からは普通のプログラミングの授業に入っていくけど、今回やったことがプログラム言語の諸概念の参照(変数は人力圧縮でいうところのワークシートのところだよとか)にできるはずなので、そこの飲み込みやすさにもつながるといいなと思う。あと以前からデバッガのおもしろさをプログラミング入門の文脈で使えないものかなと思ってたんだけど、考えてみると今回のはその点にもかなっている面があって個人的な満足度が高い。


Scrapboxを授業グループウェアに使う

2017年の授業第1回。ここのところの定番になっている正規表現ワークショップをした。

新機軸としては授業の情報共有用のグループウェアにScrapboxを使うことにしたこと。去年のSlackは発言の敷居がとても低かったり絵文字が使えたりする点はとてもよかったんだけど、情報をストックするのが困難なのはどうにもならなそうだったのでやめた。scrapboxはチャットみたいに気軽に書いてもらうのは無理とはいえ、今のところいい感じ。受講者をプロジェクトに参加してもらう手順を楽に組めた(参加URLをgoo.glで短くしたurlを打ち込んでもらう)のは助かった。Googleアカウントを持ってない学生も今年はいなかった。

CTRL-I で自分のプロフィールページの画像がアイコンがわりにおける機能がなかなかいいので、活用できないかなと思っている

出席者一覧として

アンケート