「短い方が勝ちだ！」
陸が紙を叩いた。部室で符号化の課題に取り組んでいた。
「でも、一意に復号できないとダメなんだよ」葵が冷静に指摘する。
由紀が二人の間に座った。「何を競ってるんですか？」
「符号長の最適化」葵が説明した。「4つの記号A, B, C, Dに符号を割り当てる。できるだけ短い平均符号長を目指す」
陸が自分の案を見せた。
「A: 0 B: 1 C: 00 D: 01」
「うーん」葵が首を振った。「Aが『0』でCが『00』だと、『00』を受信したとき、AなのかCなのか分からない」
「あ、確かに！」
「これを一意復号可能性という。どんなビット列も、ただ一通りに解釈できなければならない」
由紀がノートに書き込んだ。「じゃあ、どうすればいいんですか？」
葵が新しい符号を書いた。
「A: 0 B: 10 C: 110 D: 111」
「これなら一意復号可能。先頭から読んでいけば、必ず一つに決まる」
「でも長くない？」陸が不満そうだった。
「それは記号の出現確率による」葵が確率表を描いた。
「A: 50% B: 25% C: 15% D: 10%」
「平均符号長は、0.5×1 + 0.25×2 + 0.15×3 + 0.10×3 = 1.75ビット」
由紀が計算を確認した。「頻繁に出る記号に短い符号を割り当てる…」
「そう。それがハフマン符号の原理だ」
陸が考え込んだ。「じゃあ、逆にDを『0』にしたら？」
葵が即答した。「平均符号長は増える。3.15ビット。非効率だ」
「なんか不公平だな」陸が言った。
「不公平じゃない。情報理論的に公平なんだ」葵が説明した。「頻繁に起こるイベントは、情報量が少ない。だから短い符号でいい。珍しいイベントは情報量が多いから、長い符号を使っても損失は小さい」
由紀が目を輝かせた。「エントロピーと符号長の関係ですね」
「正確。エントロピーH(X)が、平均符号長の理論的下限を与える。今回のエントロピーは約1.75ビット。ハフマン符号は、この下限にほぼ到達する」
陸がホワイトボードに別の符号を描いた。
「全部2ビット固定にしたら？ A: 00 B: 01 C: 10 D: 11」
「平均符号長は2ビット。一意復号可能だけど、非効率」葵が言った。
「でも実装は簡単だよね」陸が反論した。
「そう。だからASCIIやUnicodeは固定長。でも、圧縮では可変長が優れる」
由紀がふと思いついた。「日本語とか、英語とか、言語によって最適符号は変わりますよね？」
葵が感心した。「鋭い。言語ごとに文字の出現頻度が違うから、最適符号も異なる。だから、圧縮は文脈依存なんだ」
「文脈…」
「そう。汎用圧縮は難しい。だから、ZIPやgzipは、データを分析してから符号化する」
陸が笑った。「符号長の戦い、奥が深いな」
「ささやかな戦いどころか、計算理論の核心だ」葵が静かに言った。
由紀はノートに整理した。短い符号、長い符号。それぞれに役割がある。平等ではなく、公平であること。情報理論の美学が、ここにあった。
「次は、実際にハフマン木を構築してみよう」葵が提案した。
「木？」陸が驚いた。
「また新しい概念だ」由紀が微笑んだ。
符号長をめぐる戦いは、まだ始まったばかりだった。