6.2. 【例題】文章の情報エントロピー

6.2.1. 情報エントロピー

シャノンの情報エントロピーは、各情報の出現確率を とすると

(1)

で定義されます。これは平均情報量とも呼ばれます。 単位はビットです（対数の底を2としているため）。 統計力学のエントロピーと同じ形をしていることから、情報「エントロピー」と呼ばれていますが、意味は全く違います。 ここでは、数値計算により情報エントロピーを実際に評価して、その意味を理解することを目指します。

情報エントロピーの意味

情報エントロピーを解説している本として、文献 [8] は分かりやすいのでおすすめです。

文章を0, 1の羅列で表現することを考えます。 具体的に、a, b, c, dの4つの文字で作られた文章を0, 1で表そうとした場合、

a→00, b→01, c→10, d→11 (符号化A)

と置き換えます。 例えば、acbなら001001と表します。 このような置き換えを 符号化 といいます。 4つの文字で構成された文章を符号化するには、平均で2ビット必要であることが分かります。

いま、a, b, c, dで作られた文章に含まれる各文字の出現確率が一様でないとします。 例えば、aがたくさん含まれているけど、dは少ししか含まれていないとします。 このような場合、aとdに同じように2ビットを割り当てるのは効率的ではありません。 具体的に、出現確率 が

であるとします。このとき、

a→0, b→10, c→110, d→111 (符号化B)

という符号化を考えます。 出現確率の大きい文字に短い符号を割り当てています。 この符号化法を用いた場合の1文字あたりのビット数は、(1/2)×1+(1/4)×2+(1/8)×3+(1/8)×3=7/4=1.75ビットになります。 つまり、符号化法を工夫することで、情報を圧縮できたということです。

(1) 式の情報エントロピーは情報の圧縮限界を与えます。 上の例で、具体的に情報エントロピーを計算すると となり、符号化Bによる平均ビット数と一致します。 実際には、平均ビット数が に一致する符号化法が必ずしも存在するわけではないので、 は理論上の圧縮限界と解釈します。 これを 情報源符号化定理 といいます。

注釈

情報源符号化定理を理解するために、極端な例として、 や の場合を考えてみてください。

注釈

符号化Bのように文字ごとに長さの異なる符号を割り当てる場合には、少し注意が必要です。例えばbの符号化を少し変えて ..

a→0, b→01, c→110, d→111 (符号化B')

とすると、文章を復元できなくなってしまいます（例えば、01110という符号はadaとbcの2通りに解釈できてしまいます）。復元可能（より正確には 即時復元可能）な符号化はツリー構造を考えることで生成できます。詳細は、例えば文献 [8] を参照。

実際の文章はどのくらい圧縮可能か

日本語は文字数が多いので、英語の文章を考えましょう。英語の小説はどのくらい圧縮可能でしょうか？ アルファベットは全部で26個あります。大文字・小文字を区別すると52個になります。実際の文章には数字や記号（スペースやハイフンなど）も含まれるので、文章を完全に表現するには最低でも7ビット（2^7=128個）は必要です。 実際の文字コードは7ビットや8ビット（2^8=256個）です。 実際の英語の文章では、eはたくさん使われますが、zは少ししか使われません。出現確率が一様でないので、圧縮可能です。英語の文章の情報エントロピーを計算して、どのくらい圧縮可能か見てみます。

6.2.2. 実装

ソースコード shannon.py

ファイル読み込みはとりあえず後回しにして、 テキストから情報エントロピーを計算する関数を先に見ていきましょう。 ここでは、引数textはテキスト1行ごとを要素に持つリスト型と仮定します（ファイル読み込みの解説を参照）。

from collections import Counter

def calc_entropy(text):

    # flatten text (make list of characters), and set Counter
    chars = list(chain.from_iterable(text))
    c = Counter(chars)

    # total number of characters
    total = len(chars)
    print(f"No. of characters = {total}")
    assert total == np.sum(list(c.values()))

    prob = np.array([n/float(total) for n in c.values()])
    entropy = np.sum(-prob * np.log2(prob))
    print(f"Shannon entropy = {entropy:.4f}")

    print("Statistics of characters")
    for key, n in c.most_common():
        p = n / float(total) * 100
        print(f" {key!r:6}  {n:7d}  {p:8.2f}%")

文字の出現回数を調べるには標準ライブラリの collections.Counter を使うのが便利です。 29行目～30行目：テキストから出現回数を計算する部分は、Counterを使えばたったこれだけで書けます。 Counterは引数にリストをとり、要素の出現回数を数えます。 text はテキスト1行ごとを要素として持つリストなので、このままCounterに与えると正しく動作しません。 そこで、itertools.chain.from_iterable 関数を使って、1文字ごとにバラバラになったリストに変換してからCounterに入力しています。

33行目～35行目：総文字数をチェックすることで、Counterが正しく動作しているかチェックしています。 35行目は assert文 です。 assertの右側には変数などが満たしているべき条件を書きます。 条件が満たされていない場合（Falseの場合）には例外が発生して、それ以降は実行されません（例外処理をしないと強制終了します）。 バグの早期発見と原因の特定に役に立ちます。 また、assert文は、コードを読む人（自分も含む）に対して、「ここでこうあるべき」というメッセージにもなります。 積極的に使いましょう。

37行目：Counterが持っている各文字の出現回数の情報を使って、出現確率 を計算します。 リスト内包表記 と呼ばれる書き方を使っています。 これを使うと、簡単なリストなら1行で作れるので便利です。

注釈

リスト内包表記 は便利ですが、内包表記を入れ子にするなど、複雑な表現はかえって可読性を下げてバグにつながるので、シンプルなものに限った方が無難です（文献 [2] を参照）。

38行目：(1) 式で定義される情報エントロピー を計算します。 NumPy配列の演算規則を使うとたった一行で書けてしまいます。np.log2(prob) はNumPy配列 prob の全ての要素に対してlog2をとった配列を返します。それにより得られた配列と prob の 積 ``*`` は配列の各要素同士（element-wise）の掛け算 です。この配列を np.sum に与えると、配列の全要素の和が得られます。

ファイル読み込み

def read_file(filename):

    # check if file exists
    if os.path.isfile(filename) != True:
        print(f"{filename!r} does not exist")
        sys.exit(1)

    # read text in the file
    #   NOTE: 'encoding' option works only in python3
    with open(filename, 'r', encoding='utf-8-sig') as f:
        text = f.readlines()

    return text

まず、ファイルの存在チェックをしています。 os.path モジュールにパス関連の関数がいろいろあります。

withを使ってファイルを開くと、そのブロックの終了時点で自動的にファイルが閉じられます。 withを使わない場合には f.close() で明示的にファイルを閉じる必要があります。 withを使えばファイルの閉じ忘れが防げるので便利です。 with open() as f は必ずセットで使うと覚えておくと良いでしょう。

ファイルから一行づつ読み込む方法などもありますが、今回はファイル全体を一度に読み込んで、それを戻り値にしています。

コマンドライン引数

さて、最後にmain関数ですが、異なるテキストファイルを読み込むたびにスクリプト内のファイル名を毎回書き換えるのは面倒です。 そこで、ファイル名を実行時にコマンドラインから入力するようにしましょう。 それには argparse モジュールのArgmentParserクラスを使います。

import argparse

このようにインポートします。 main関数は以下のように書けます。

def main():
    # set commandline argument
    parser = argparse.ArgumentParser()
    parser.add_argument('filename', help="filename of a text file. The line break must be LF.")
    args = parser.parse_args()
    print(args)

    txt = read_file(args.filename)
    calc_entropy(txt)

add_argumentメソッドで引数を追加していきます。 '-'や'--'で始まるオプションも設定できますし、デフォルト値、排他オプションなど様々な動作を設定できます。 詳細は公式ドキュメントを参照してください。

また、ArgumentParserはヘルプを自動で作ってくれる点も便利です。 コマンドラインで-hオプションを付けて実行するとヘルプメッセージが表示されます。

$ python shannon.py -h
usage: shannon.py [-h] filename

positional arguments:
  filename    filename of a text file. The line break must be LF.

optional arguments:
  -h, --help  show this help message and exit

6.2.3. 実行結果

Lewis Carrollの"Alice's Adventures in Wonderland" の情報エントロピーを計算してみることにします。 Project Gutenberg は日本の青空文庫のようなものです。 リンク先からテキストファイル（Plain Text UTF-8）をダウンロードし、これをスクリプトshannon.pyと同じディレクトリにおいて、そのままスクリプトに読み込ませます。 テキストファイルには本文以外の情報（ヘッダーなど）も含まれていますが、テキストファイル全体がどれだけ圧縮可能かを調べるという意味で、特にテキストの前処理のようなものは行ないません。

以下が実行結果です（途中まで）

$ python shannon.py pg11.txt
Namespace(filename='pg11.txt')
No. of characters = 163780
Shannon entropy = 4.5901
Statistics of characters
 ' '       27964     17.07%
 'e'       15082      9.21%
 't'       11629      7.10%
 'o'        9243      5.64%
 'a'        9081      5.54%
 'n'        7869      4.80%
 'i'        7802      4.76%
 'h'        7580      4.63%
 's'        6980      4.26%
 'r'        6398      3.91%
 'd'        5227      3.19%
 'l'        5053      3.09%
 'u'        3867      2.36%
 '\n'       3735      2.28%
 "'"        2885      1.76%
 'c'        2815      1.72%

情報エントロピーは4.59でした。 つまり、理論上は1文字あたり平均5ビットあればこのテキストを符号化できるということです。

注釈

ここでは、圧縮限界を示しましたが、それをどのように実現するかは、また別の問題です。出現頻度の多い文字（eなど）に短い符号を割り当て、出現頻度の低い文字（記号など）に長い符号を割り当てる、というのが基本的な方針です。どのようにしてより効率的な、圧縮限界に近い圧縮法を実現するか、考えてみてください。