平均符号長・とは？初心者にも分かる基本と実例で学ぶ共起語・同意語・対義語も併せて解説！

この記事を書いた人

高岡智則

年齢：33歳性別：男性職業：Webディレクター（兼ライティング・SNS運用担当）居住地：東京都杉並区・永福町の1LDKマンション出身地：神奈川県川崎市身長：176cm 体系：細身〜普通（最近ちょっとお腹が気になる）血液型：A型誕生日：1992年11月20日最終学歴：明治大学・情報コミュニケーション学部卒通勤：京王井の頭線で渋谷まで（通勤20分）家族構成：一人暮らし、実家には両親と2歳下の妹恋愛事情：独身。彼女は2年いない（本人は「忙しいだけ」と言い張る）

平均符号長・とは？

データを短い文字列で表すとき、私たちは記号ごとに決められた長さのコードを作ります。平均符号長は、そんなコードの「長さの平均」を表す考え方です。ここでは、中学生にも分かるように、平均符号長が何を意味するのか、どう計算するのか、そして実際の例を交えて説明します。

まず、ある記号 i が現れる確率を p(i)、その記号を表すコードの長さを l(i) とします。全ての記号について L = Σ p(i) · l(i) という式で平均符号長を求めます。たとえば、A が出る確率が 0.5、B と C がそれぞれ 0.25 のとき、それぞれの符号長を 1、2、2 と決めれば、L = 0.5×1 + 0.25×2 + 0.25×2 = 1.5 ビット程度の平均長になります。

なぜ平均符号長が重要か

私たちは情報を小さく送るほど便利です。平均符号長ができるだけ小さいコードを選ぶと、データを送るときの全体のデータ量が減ります。しかし、長いコードを作りすぎると実際には不便です。そこで、プレフィックス符号と呼ばれる仕組みを使います。これは、あるコードが別のコードの先頭になっていない性質で、途中で誤解して解読されることを防ぎます。

このような前提のもと、実は ハフマン符号 のような方法を使うと、与えられた確率分布のもとで 可能な限り平均符号長を小さくできます。つまり、同じ情報を伝えるのに必要なビット数を最小化する近似解として有名です。

もう少し詳しい話

平均符号長には理論的な下限があり、それは情報の不確定さを表す量「エントロピー」と呼ばれます。エントロピーを表す式は H(P) = - Σ p(i) log2 p(i) です。ここで底が 2 の対数を使うと単位はビットになります。重要な性質として エントロピー ≤ 平均符号長 という不等式が成り立ちます。つまり、情報の不確実性を表すエントロピーを下回ることは、一般のコードでは難しいということです。

さらに、Kraftの不等式 という条件も覚えておくと役に立ちます。プレフィックス符号を作るときには Σ 2^{-l(i)} ≤ 1 という関係が成立する必要があります。これがコードの設計を難しくしつつも、最適性の指針にもなります。

具体的な例で見てみよう

確率が A: 0.5、B: 0.25、C: 0.25 のとき、短いコードを次のように決めるとします。A の符号長を 1、B と C の符号長を 2 とします。これを使うと、各記号の寄与は 0.5×1 = 0.5、0.25×2 = 0.5、0.25×2 = 0.5 となり、合計 1.5 ビットになります。理論的にはこのケースのエントロピーも 1.5 ビット程度で、最適性が評価できます。