「入部届、書いてきました」
由紀が書類を差し出すと、葵が受け取った。
「正式に新入部員だね。おめでとう」
「ありがとうございます！」
陸が拍手した。「仲間が増えた！じゃあ、今日は歓迎会？」
「部活動をしっかりやることが、最高の歓迎だ」葵が笑った。「今日のテーマは、情報源符号化」
「情報源符号化？」由紀が首を傾げた。
「データ圧縮の理論。メッセージを効率的に符号化する技術だ」
葵はホワイトボードに文字を書いた。
「例えば、この文章を送信するとしよう。『aaaabbbbc』」
「aが4つ、bが4つ、cが1つ」陸が数えた。
「通常、各文字を8ビットで表すと、9文字で72ビット必要だ」
「でも、aとbは何回も出てくるから、もっと短くできそう」由紀が言った。
「鋭い！それが符号化の基本発想」葵が頷いた。「頻繁に出る文字には短い符号を、稀な文字には長い符号を割り当てる」
「具体的には？」
「ハフマン符号という方法がある。最適な符号を機械的に作れる」
葵は表を描いた。
「a: 44パーセント b: 44パーセント c: 11パーセント」
「この確率分布に対して、ハフマン木を構築する」
陸が不安そうに言った。「木？」
「心配しなくていい。簡単な手順だ」葵が図を描き始める。
「1. 最も確率の低い二つを組み合わせる 2. 新しいノードの確率は、合計になる 3. 全部が一つの木になるまで繰り返す」
「cは11パーセントだから、まず単独で…」由紀が考える。
「いや、aとbを先に組み合わせることもできる。順番は複数ある」
葵が完成した木を示した。
「a: 0 b: 10 c: 11」
「aは1ビット、bとcは2ビット！」陸が驚いた。
「平均符号長は、0.44×1 + 0.44×2 + 0.11×2 = 1.54ビット」
「元は8ビットだったから、大幅に削減！」由紀が計算する。
「そう。でも、これは理想的な例。実際は文脈も考慮する」
陸が疑問を持った。「でも、どうやって区切りが分かるの？『010』は『a,b』なのか『a,0,…』なのか」
「良い質問。これは前置符号の性質だ」葵が説明した。「どの符号も、他の符号の前置になっていない。だから一意に復号できる」
「前置？」
「例えば、aが『0』でbが『01』だったら、『01』はaの前置になる。これだと区切りが曖昧になる」
「だから、『0』『10』『11』みたいに設計する必要がある」由紀が理解した。
「正確。ハフマン符号は、常に前置符号になる」
陸がノートに書き込んだ。「じゃあ、もっと長いメッセージなら、もっと圧縮できる？」
「エントロピーに近づく。情報源のエントロピーが理論的な限界だ」
「エントロピー、また出てきた」由紀が笑った。
「情報理論の全てに関わる基本概念だからね」
葵は別の例を示した。「英語のテキストは、エントロピーが約1.5ビット/文字。だから、理論的には8ビットから1.5ビットに圧縮可能」
「でも、zipやrarは実際どうやってるの？」陸が聞く。
「辞書ベースの方法を使う。繰り返しパターンを見つけて、参照で置き換える。LZ77、LZ78、LZWなど」
「複雑そう…」
「アルゴリズムは複雑だけど、原理は同じ。冗長性を削減する」
由紀が真剣に言った。「もっと勉強したいです」
「じゃあ、来週はハフマン符号を実際に手で構築してみよう」葵が提案した。
「やります！」
陸も頷いた。「俺も頑張る」
「二人とも、良い部員になりそうだ」葵が満足そうに言った。
由紀は胸が高鳴った。情報理論部での日々が、本格的に始まる。