zsh エントロピー kusa (2008/06/11)


ZSHell Case InsenSitive CompleTion

3.x の頃は補完システムをおおむね理解していた(アホや…w) が、 過剰な適応がたたったのか解脱したのか 4.x の補完を全く理解できなくなっていた。 なんせ大文字/小文字の区別なく補完すらうまく設定できなくなっていた。

私の場合もパソコンの操作のほとんどはキー入力なのですが、 XEmacs では、補完対象を大文字小文字の区別なく選ぶ設定になっている一方、 zshell ではそうなっていないのは非常に具合が悪い。 しかし、自分で調べてもどうすりゃいいのかさっぱり理解できなかった。 だからここ数年は、便利が悪いままで放置していたのである。

こういう我慢は良くない我慢だ. そこで、思い立っていきなり zshell case insensitive completion で検索してみたら次の記事が出た。

http://forums.macosxhints.com/archive/index.php/t-6493.html

この記事の設定例のうち

zstyle ':completion:*' matcher-list 'm:{a-z}={A-Z}' 'r:|[._-]=* r:|=*' 'l:|=* r:|=*'

これを自分の設定ファイルに追加してみたら、うまくいった。 あいかわらず謎の呪文だ。ほとんど sendmail.cf 並の可読性ですね。 この種の設定が腐る理由は、キーワードが m とか r とか 一文字だからである。 さすがにこういう設定を自力で書く情熱はもう無い。

というわけで、この設定の言いたい事はなんとなく判るが、 その構造および処理内容は全く理解していないし、 理解したいとも思わないし、 たとえ挑戦しても、索引からの調査がほぼ不可能という点で、 うまくいくとは到底思えない。 身近に作者でも居ない限り、わしには無理。

ここまで書いてから、 macosxhints なんてドメイン名なのに気づいた。 OSX は zsh が入ってるからか。 なかなか深いな、OSX。ぜひがんばって欲しい(ぼうよみ)。

情報エントロピー

先日来、ssh の脆弱性で「鍵のエントロピーが」とか「乱数生成のエントロピーが」 などの記事を目にされた方もあると思います。

そもそも entropyって何じゃいな。 と思ったのでちょいと調べてみました。情報エントロピー。

定義の出発点は一個の確率変数です。 確率変数 x の確率密度関数 p(x) として この確率変数のエントロピー は (- p(x) (log 2 p(x))) を x について 積分したものです。2値で均等な確率なら (- (* 0.5 (log2 0.5))) が二つで 1.0 ですな。 一般に、最大のエントロピーを与えるのは均等な確率分布です。

分布が均等だったらエントロピーが最大、とはならないところが、 この概念のトラップその一でしょうか。分布が偏っていれば、 最大のエントロピーは得られない、の対偶はエントロピー最大なら均等な確率分布、 であり、その逆は成り立たない。 たとえば2値の確率変数がn個並んでいて、0も1も同じ数だけ出て来るのだが、 その出て来るパタンが 0101010101010101… だったらどうすんの?

直観的にいって、これはエントロピーが低いですね。でも分布は均等です。 どちらも出て来る割合は半分です。しかし明らかに予測可能なので それは具合が悪いはず。どこがおかしいのか?

01を新しく1とエンコードしてやれば、長さ半分の全部1からなる変数列になります。 片方が出現率100%でエントロピーはちゃんと少なくなりますね。 逆に、ランダムなビットストリームであれば、このようなエンコーディングは 不可能です。 この話しを野蛮に一般化すると、 情報エントロピーはエンコーディングによる無損失圧縮の 圧縮率の限界になることが予想されますね。 もしくは、0の次は必ず1って事で、係数-1の負の相関がある、と解釈することも できます。そう考えると確率変数の独立性もエントロピーに影響を与えそうです。 果して次の性質が成り立ちます。

(独立な確率変数のエントロピー加法性)
確率変数 x のエントロピーが a で y のが b のとき x と y が独立なら、その直積のエントロピーは a + b

ちょっとややこしいのですが、あるいみ納得できる単位として、 1ビットのランダムな確率変数のエントロピーを 1bit とします。 すると上記の定理より長さ n の独立でランダムなビット列のエントロピーは n bit になります。同じ名前で別のものを指すのでややこしいようですが、 ある意味自然な定義です。

なお、上の定義では対数の底を2にしていますが、場合によっては e にした方が 計算上都合が良い場合や10にしたほうが良い場合もあり、 e の場合の単位を nat 10 では dit というそうな。 わしらが使っているバイナリコンピュータでは、 エントロピーの単位としてbitが一番使いやすいでしょう。 たとえば、あるデータのエントロピーが15bitだといった場合、 それがどれくらいのエントロピーなのか、直観的に把握しやすいですね。

(演習) エントロピー加法性を証明しよう

もじれつをわらかす関数作った。

(defun kusa (&optional len)
  (interactive "p")
  (if (= len 1) (setq len 6))
  ((lambda (str)
     (kill-region (region-beginning) (region-end))
     (insert-string (kusawww len str "")))
   (buffer-substring (region-beginning) (region-end))))

(defun kusawww (len str ret)
  (cond
   ((equal str "")      ret)
   (t (kusawww len (substring str 1) (concat ret (substring str 0 1) (wara len))))))

(defun wara (&optional len wlist)
  (cond ((null wlist) (setq wlist '("w" "W"))))
  ((lambda (len ret)
     (while (> len 0)
       (setq ret (concat (nth (random (length wlist)) wlist) ret))
       (setq len (- len 1)))
     ret)
   (random len) ""))

使い方は簡単。わらかす範囲を指定して、 Mx kusa でおk

生やす草の種類は選べるようになっているが、 選ぶインタフェースを考えるのは面倒だったので事実上 w と W の2択です。 お好みで v とか うぇ とか追加して使って下さい。 草の量は prefix arg で調wWWWwWW整しwwWwwWWWてwWWwwwwWくだwwWしwwWあwww


記事リストへ