応用情報知識メモ03（情報理論）
確認問題
以下にスラスラ答えられる人は読まなくても大丈夫。
・情報量を算出して、どのような用途で用いるのかを説明せよ。
・情報量とは何かを説明せよ。
・平均情報量(エントロピー)を導く式を説明せよ。またエントロピーを求めた値から何がわかるのかを説明せよ。
・ハフマン符号化、ランレングス符号化を説明せよ。
・ハフマン符号化において、２進数で４つの符号を定める必要がある場合、具体的にどのような符号となるかを答えよ。
・オートマトンにおいて、受理状態の表記方法を答えよ。
・正規表現において次の記号の意味を答えよ。「.」「*」「+」
・形式言語について具体的にイメージせよ。
情報量
情報量って何に使うの？
アナログからデジタルにデータを変換する際に、より効率よく表現する際に考慮する。
例えば英語では「e」が頻出する。英語のテキストをデジタルデータにする際、「e」に短めのビット数を割り当てれば、デジタルデータ自体が短くなり、より効率的にデータを送受信できることになる。
上記の話は後述する「符号化」にて。
ちなみに、このあたりは親指シフトの発想と近いかも。親指シフトでも頻出する平仮名はシフトキー押さないでも表示できるもんね。
情報量の計算方法
情報量とは「その事象の発生しづらさ」を表す。
言い換えると「その事象が発生する確率を何bitで表せるか」を指す。
コイントスで表が出る確率＝1/2 を情報量で表すと。
$$
-\log_2 \frac 1 2 = 1
$$
平均情報量（エントロピー）
平均情報量は下記の数式で求められる。
平均情報量を算出することによって、各データを表すために必要な最小のビット数（の理論値）がわかる。
後述する符号化を実行した後、符号化した場合の期待値を算出して平均情報量と比較することで、その符号化手法がどのぐらい優れているかをはかることができる。
$$
平均情報量＝\displaystyle\sum_{k=1}^n 事象Xの発生確率×事象Xの情報量
$$
ハフマン符号化
ハフマン木と呼ばれる木構造を使用し、各ノードに対して、どのbit列を割り当てるかを決める手法。
例えばデータが４つあるとき、[0] [10] [110] [111] の４つだと定めれば、0 と 1 がどのように並んでいても復号できる、言い換えれば元のデータを復旧させることができる。
もしこれが [0] [01] [11] と分けた場合、[0011…] という値は [0] [01] [1…] なのか [0] [0] [11] […] なのか、区別がつかない。要するに先頭から見て復号できるのが大事。
ランレングス符号化
同じデータが繰り返されるような場合に使用する。画像情報は同じ色がしばらく続くことが多いので、画像情報を表す際によく使われるイメージ。
例えばXXX YYYY XXX ZZ …というデータは X3 Y4 X3 Z2 と符号化する。
画像で言えばRGB値が同じデータがしばらく続くので、それを符号化するのだろう。
オートマトン
状態遷移表や状態遷移図を用いて状態変化をモデル化する手法。
状態遷移表についてはWiki参照。
状態遷移表において大切なのは、二重丸（◎）が受理状態を表す点。入力値を入力して、最終時点で二重丸（◎）に遷移していれば、入力値が使用可能だといえる。
正規表現
メジャーなものだけ記載する。
[1..9]：１～９のうち任意の１文字
. (ドット)：任意の１文字
* (アスタリスク)：直前の文字を０回以上繰り返し
+ (プラス)：直前の文字を１回以上繰り返し
形式言語
そもそも形式言語とは、プログラミング言語などの構文的ルールを表したもの。SQL文で言えば、例えば「SELECT + 対象 + FROM + テーブル名 + WHERE + 条件…」などと続く。WHERE以降は無くても問題ない、というのが構文のルールとして存在する。
用語としては「非終端記号」「終端記号」がある。
非終端記号とは「まだ変換可能な記号」であり、終端記号とは「これ以上変換できない記号」を指す。
例えば、非終端記号「ゲーム」があり、これの終端記号の候補として「ポケモン」「モンハン」「スプラトゥーン」があるとする。「私はゲームをして遊ぶ」という文章にて、「ゲーム」を「ポケモン」などに置換してもよい。
BNF記法（バッカス・ナウア記法）
形式言語を示すメジャーな手法。直感的に理解できるものなので名前とかを覚える必要はない。
記号を<記号> と示す。左辺と右辺を ::== で結ぶ。| が or を表す。
参考
この記事が気に入ったらサポートをしてみませんか？