読者です 読者をやめる 読者になる 読者になる

符号化に最低限必要なビット長

雑記 algorithm

長さ制限付きハフマン符号の整理中。
気づいたことメモ。
N個のコードを符号化するには、ビット長が最低(log N 2)*1は必要。
一番(最大の)ビット長が短くて済むのは、全てのコードを同じビット長でエンコードした場合。
いわゆる普通の文字表現(256文字を、8ビット=(log 256 2)で表現)がそれ。
気づいてみれば当たり前。

*1:common lispのlog関数表記。この場合2が底