SHOYAN BLOG

I am a pragmatic programmer.

ハフマン符号化のアルゴリズムとエントロピーを学ぶ

ハフマン符号とは1952年にデビッド・ハフマンという人が考え出したアルゴリズムです。
文字列をはじめとするデータの可逆圧縮に使われます。
よく使われる文字には短いビットを、あまり使われない文字には長いビットを割り当てることで全体としてサイズが削減されることを狙ったアルゴリズムです。

符号化の原理

実際にアルゴリズムを確認していきます。

DAEBCBACBBBC という12文字のメッセージをハフマン符号化します。

このメッセージでは、ABCDEという5種類の文字が使われているため、それぞれの文字を固有のビット長で表す場合は、3ビットが必要です。

1
2
3
4
5
A: 000
B: 001
C: 010
D: 011
E: 100

上記の対応表をもとに、文字列をビットに変換します。

1
2
DAEBCBACBBBC
011 000 100 001 010 001 000 010 001 001 001 010

1文字3ビットで12文字あることから全体のビット数は36ビットとなります。

ここで、よく出てくる文字には短いビットを、あまりでてこない文字には短いビットを与えます。
対応表を以下のように作ります。

1
2
3
4
5
A: 110
B: 0
C: 10
D: 1110
E: 1111

メッセージ全体では以下のようになります。

1
2
DAEBCBACBBBC
1110 110 1111 0 10 0 110 10 0 0 0 10

全体のビット数は25ビットとなり、固定長の方式と比べると70%ほどのデータ量に抑えられています。

対応表をつくる

以下の手順で文字とビット列の対応表をつくります。

  • データに出現する文字の出現回数を求める
  • それをもとにハフマン木とよばれる二分木(バイナリツリー)を構成する

ハフマン木の構成の仕方は次のアルゴリズムとなります。

  1. 各記号に対応する葉を作成する。この葉には、記号の出現頻度をあらかじめ格納しておく。
  2. 出現頻度の最も少ない2つの葉をとりだす。取り出した2つの葉を格納する節をつくり、左右の枝に記号0と1を割り当てる。この節には2つの葉の出現頻度を足した値を格納し、新しい葉として追加する
  3. 葉が1つになるまで手順2を繰り返す。

DAEBCBACBBBC を題材に、ハフマン木を作ります。

1. 各記号に対応する葉を作成する

まずは、各記号に対応する葉を作成し、データの出現回数をあらかじめ格納しておきます。

1
{"B"=>5, "C"=>3, "A"=>2, "D"=>1, "E"=>1}

2.出現頻度が少ない2つの葉をとりだす

DとEが1番小さいので、この2つを取り出します。
そして、DとEの葉を足し合わせた節を1つ作ります。
この手順を最終的に葉が1つになるまで繰り返します。

ハフマン木が作られる工程

DAEBCBACBBBC を作成した対応表で符号化します。

文字 個数 符号
B 5 0
C 3 10
A 2 110
D 1 1110
E 1 1111

データ圧縮アルゴリズムについて

一般的にデータ圧縮アルゴリズムは「モデル化」と「符号化」の2つにわけて考えることができます。
「モデル化」は入力された記号(データ)から各記号の出現確率を求めます。
「符号化」は出現確率に基づいて符号語を割り当て、入力されたデータを各符号語に変換して出力します。
モデル化についてはいろいろな方法がありますが、ハフマン符号のように記号の出現確率を求めそれに基づいて符号語を割り当てるモデルを「無記憶情報源モデル」といいます。
「情報源」は記号を生成する基となるデータのことです。
情報源が記号を生成するとき、以前に生成した記号との間に関連性がないことを「無記憶」といいます。
記号aの次は記号bが生成されるといった関係性はなく、確率でのみ記号が作成されるということです。

データ圧縮アルゴリズムを評価する場合、圧縮率のほかに「平均符号長」という尺度があります。
これは、符号化された記号列のビット長を入力された記号数で割った値として定義されます。

たとえば DAEBCBACBBBC をハフマン符号化すると1110110111101001101000010となります。
符号化された記号列のビット長(1110110111101001101000010)を入力された記号数(DAEBCBACBBBC)で割ると平均符号長は 25 / 12 = 2.0833333 となります。

無記憶情報源モデルの場合、各記号 の出現確率 がわかると、次の式で平均符号長の下限値を求めることができます。

を平均情報量、またはエントロピー(Entropy)と呼びます。

情報源符号化定理によると、平均符号長はエントロピーより短くすることができません。

情報源符号化定理

意復号可能な平均符号長 L は、無記憶情報源のエントロピー H よりも小さくすることができない。すなわち不等式 H <= L が成り立つ。また、平均符号長 L が H <= L < H + 1 を満足する瞬時に復号可能な符号が構成できる。

先ほどの記号列のエントロピーを求めてみます。

1
2
3
4
5
6
7
8
9
10
11
記号列: DAEBCBACBBBC
記号: 確率: -p(ai) / log2 p(ai)
------------------------------------------
D: 1 / 12: 0.29874687506009634
A: 2 / 12: 0.430827083453526
E: 1 / 12: 0.29874687506009634
B: 5 / 12: 0.5262643357640807
C: 3 / 12: 0.5
------------------------------------------
エントロピー = 2.054585169337799
12 * 2.054585169337799 = 24.65502203205359 bit

したがって、この記号列では平均符号長を 2.05 ビット以下にすることはできません。
いいかえると、この記号列を表すには少なくても 12 * 2.054585169337799 = 24.65502203205359 ビット以上が必要になる、ということです。

エントロピーの算出コード

エントロピーを算出するコードをRubyで書きました。

以下のように使います。

1
2
$ ./entropy file.txt
2.054585169337799

文字列を渡す場合はパイプで繋ぎます。

1
2
$ echo "DAEBCBACBBBC" | ./entropy
2.054585169337799

また、 -v オプションで詳細を表示できます。

1
2
3
4
5
6
7
8
9
10
$ ./entropy -v file.txt
記号: 確率 : 値
D: 1 / 12: 0.29874687506009634
A: 2 / 12: 0.430827083453526
E: 1 / 12: 0.29874687506009634
B: 5 / 12: 0.5262643357640807
C: 3 / 12: 0.5

サイズ エントロピー 下限値
12 2.054585169337799 3

ファイルサイズ * エントロピー で圧縮の下限値を計算することができます。
上記の場合は3バイトよりも圧縮することはできないということです。

ただし、この結果は無記憶情報源モデルの場合であり、モデル化によってエントロピーの値は異なることに注意してください。エントロピーをより小さくするモデルを作成することがでれきば、これよりも高い圧縮率を達成することができます。

参考リンク

Sedやawkを使ってテキストから必要な列のみ取得する

以下のような文字列(ファイルに保存されているとする)からsedやawkを使ってlabelだけとるshell芸を紹介します。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
+-------------------------+-------+
| label                   | state |
+-------------------------+-------+
| A                       |     0 |
| B                       |     0 |
| C                       |     0 |
| D                       |     0 |
| E                       |     0 |
| F                       |     0 |
| G                       |     0 |
| H                       |     2 |
| I                       |     0 |
| J                       |     0 |
| K                       |     0 |
+-------------------------+----———+

label列のみ取得

1
2
3
4
5
6
7
8
9
10
11
12
⇒  sed -n '4,14p' table.txt | awk '{print $2}'
A
B
C
D
E
F
G
H
I
J
K

スペース区切りに加工する

1
2
⇒  sed -n '4,14p' table.txt | awk '{print $2 " "}' | tr -d '\n'
A B C D E F G H I J K

sed -n '4,14p’ で指定した行数のみ取得しています
次にawk '{print $2}’ でlabel列のみ抽出しています。
改行を消すのは tr -d '\n’ が便利です。

Rdiscountからkramdownへmarkdownのparserを変更した

数式を扱うために前回の記事で、markdownをkramdownに変更したのですが、コードのシンタックスハイライトが効かなくなってしまいました。

kramdownのparserをGFMにしてやるとうまくいきました。

_config.yml

1
2
kramdown:
  input: GFM

GFMを使わない場合は、プラグインがあるのでそちらでも対応できます。

kramdown-with-pygments

使い方ですが、pluginsディレクトリにkramdown_pygments.rbを置きます。
そして、_config.ymlのmarkdownを以下のように修正します。

1
markdown: KramdownPygments

また、parserにkramdownを使う場合はRdiscountとkramdownでcodeのmarkdownのフォーマットが違うのでgenerate時にエラーがでるかもしれません。

自分は以下のワンライナーで書き換えました。

1
2
find source/_posts -type f -name "*.markdown" | xargs sed -i '' -e 's/\`\`\`/\
~~~/g'

また、URLに自動でリンクを付与してくれる機能がRdiscountにはあったのですが、kramdownでは明示的に指定する必要があります。
Rdiscountのように自動的にリンクを付与するプラグインを作成しました。

使い方はkramdown_easy_link.rbplugins/ディレクトリに置いて、_config.ymlを以下のように修正します。

1
2
3
markdown: kramdown
kramdown:
  input: KramdownEasyLink

Jekyllで数式を表示する方法

Jekyllで数式を使いたい場合は、markdownにkramdownを使うのがおすすめです。
というのも、redcarpet はワンライナーの書式しか使えません。
rdiscount は自分が試したところ、動作しませんでした。

次にMathjax.jsを読み込みます。

1
<script type="text/javascript" src="//cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>

これで準備は整いました。

Kramdown のドキュメントに書かれているサンプルを表示します。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
$$
\begin{align*}
  & \phi(x,y) = \phi \left(\sum_{i=1}^n x_ie_i, \sum_{j=1}^n y_je_j \right)
  = \sum_{i=1}^n \sum_{j=1}^n x_i y_j \phi(e_i, e_j) = \\
  & (x_1, \ldots, x_n) \left( \begin{array}{ccc}
      \phi(e_1, e_1) & \cdots & \phi(e_1, e_n) \\
      \vdots & \ddots & \vdots \\
      \phi(e_n, e_1) & \cdots & \phi(e_n, e_n)
    \end{array} \right)
  \left( \begin{array}{c}
      y_1 \\
      \vdots \\
      y_n
    \end{array} \right)
\end{align*}
$$

基本的な書式は以下のようになります。

1
2
3
4
5
6
7
$$
\begin{align*}

LaTexの数式

\end{align*}
$$

また$$を使ってワンライナーで書くことも可能です。

1
$$ 5 + 5 $$

インラインにしたいときは\$$を使います。

1
\$$ 5 + 5 $$

このように文字中に数式を埋め込むことができます。

光は真空中を1秒間に約 メートル進む。 光速を で表す

1
光は真空中を1秒間に約 $$ 3.0 × 10^8  $$メートル進む。 光速を $$ cc $$ で表す

表記の確認にはMathJax checker を使うと便利です。
LaTeX 書式の数式をリアルタイムで確認することができます。

LaTexの書式に関しては以下を参考にしてください。

http://www.onemathematicalcat.org/MathJaxDocumentation/TeXSyntax.htm

参考リンク

レガシーコード向けに修正した部分だけPHP構文チェックをする仕組みを作った

修正した部分だけPHPの構文チェックをする仕組みを作ってみました。
構文に問題があればGithubのPull Requestにコメントされます。

2016-06-23_php-syntax-check

この方法のよいところは既存のソースを変えることなくPHPの構文チェックの仕組みを導入できることです。
規約に沿っていないコードが大量にあり、かつテストコードがないような環境(レガシー環境)にも導入することができます。

使用したツールは以下です。

また、packsaddleのツールはRuby製ですので、Rubyが動作する環境が必要です。

サンプルとしてGithubにphp-syntax-checkというリポジトリを作成しているので参考にしてください。

以下のスクリプトをCircleCIで実行しています。

check_syntax.sh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/bin/bash

echo "Start"
LIST=`git diff --name-only origin/master | grep -e '.php$'`

if [ -z "$LIST" ]; then
    echo "PHP file not changed."
    exit 0
fi

if [ -n "$CI_PULL_REQUEST" ]; then
    git diff --name-only origin/master \
        | grep -e '.php$' \
        | xargs vendor/bin/phpcs -n --standard=PSR2 --report=checkstyle \
        | bundle exec checkstyle_filter-git diff origin/master \
        | bundle exec saddler report \
        --require saddler/reporter/github \
        --reporter Saddler::Reporter::Github::PullRequestReviewComment
fi

仕組み

以下の3つのセクションに分類されます。

  • 対象のファイルを抽出
  • 構文チェック
  • 結果をレポート

1. 対象のファイルを抽出

以下のコマンドでmasterと差分のあるファイル名を取得します。

1
git diff --name-only origin/master

さらに grepで拡張子が .phpのファイルのみ対象にします。

1
git diff --name-only origin/master | grep -e ‘.php$'

2. 構文チェック

構文チェックツールは好きなものを使えます(CheckStyleフォーマットで出力できるものに限りますが)。
今回はPHP_CodeSnifferを使いました。

1
xargs vendor/bin/phpcs -n --standard=PSR2 --report=checkstyle

xargsは前のコマンドを引数でとるために必要です。

以下のコマンドでmasterとブランチの差分をチェックして、差分があるところのエラーを検知対象のエラーとしています。

1
bundle exec checkstyle_filter-git diff origin/master

エラーの差分の抽出にcheckstyle_filter-gitというツールを使っています。
これは、入力として渡したCheckStyle formatの文字列から、変更した内容の部分のエラーを抽出するツールです。
例えばファイルの10行目〜15行目を変更した場合、その行で発生したエラーのみを抽出します。

3. 結果をレポート

saddlerを使って結果をGithubに通知します。

1
2
3
bundle exec saddler report \
        --require saddler/reporter/github \
        --reporter Saddler::Reporter::Github::PullRequestReviewComment

注意点としては、PRを作っていないと通知でエラーとなります。

ですので、Pull Requestがあるかどうかをチェックするif文をいれています。
$CI_PULL_REQUEST はCIrcleCIの変数で、Pull Requestが作られていればこの変数にURLが格納されています。

1
2
3
if [ -n "$CI_PULL_REQUESTS" ]; then

fi

また、通知にはGITHUB_ACCESS_TOKENを発行して環境変数に登録しておく必要があります。

CircleCIの環境変数の設定については、以下を参照ください。

また、通知ではなく単に結果を出力する場合は、saddler/reporter/textを指定します。

1
2
3
bundle exec saddler report \
  --require saddler/reporter/text \
  --reporter Saddler::Reporter::Text

以下は、出力があった場合はエラーにする例です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
RESULT=`git diff --name-only origin/master \
    | grep -e '.php$' \
    | xargs vendor/bin/phpcs -n --standard=custom_ruleset.xml --report=checkstyle \
    | bundle exec checkstyle_filter-git diff origin/master \
    | bundle exec saddler report \
      --require saddler/reporter/text \
      --reporter Saddler::Reporter::Text`

if [ -n "$RESULT" ]; then
    echo ""
    echo "An error has been detected,this following:"
    echo "$RESULT"
    exit 1
fi

その他

ファイルのエンコードがEUC-JPのソースコードに適用したところエラーとなりました。 リポジトリをフォークして対応しました。
1.1.0より使えるようになりました!

以下のように設定します。

Gemfile

1
gem "checkstyle_filter-git", git: "https://github.com/shoyan/ruby-checkstyle_filter-git.git", branch: "implement-exec"

iconvでgit diffの出力結果の文字コードをEUC-JP->UTF-8に変換して渡せるようにしました。

1
2
3
4
git diff --name-only origin/master \
  | grep -e '.php$' \
  | xargs phpcs -n --standard=custom_ruleset.xml --report=checkstyle \
  | bundle exec checkstyle_filter-git exec "git diff origin/master | iconv -f EUCJP -t UTF8"

PRもしているので直ることに期待です。
Mergeいただきました。

サンプルとしてGithubにphp-syntax-checkというリポジトリを作成しているので参考にしてください。

関連記事

参考リンク