debugger って案外実際のデバグに役に立つ場合よりもですね、 コードを見る時に役に立たないですかね。
つまり emacs で M-x gdb してスペースキーを連打するわけです。 フレームスタックも見れるから、呼出の履歴みたいのも一応 (その時点のものなら)参照できる。 特に、通常のソースコードビュワーに比べて良いな、と思うのは、 変数に実データとして何が入ってるかも見れるところです。
まぁこの手口はいろいろと制限も多いのですが。 普通はユーザ空間限定とか。 でも、通りいっぺん処理がどう行くのか、 みたいなところを間違いなく一発でトレースできるところは、 ちょっと他では無いありがたみではないでしょうか。
発音の容易さにしたがって、生成したアナグラムを並べるアルゴリズム考えた。 Shannon のエントロピーの論文と オライリーからしばらくまえに出た「集合知プログラミング」読んでたら (正確に言うと眺めてたら)、 思い付いた。
アルゴリズム思い付くなんて、すげぇなと以前は思っていたが、 自分でやってみるとこれは、べつに普通というか自明というか、 全然凄くない。 アルゴリズム自体は最後に載せるケーキのイチゴみたいなもので、 あれば良いが無かったからだからどうだ、というようなものでもない感じ。 あるいはそのうち誰かやるだろ、みたいな。 これに対して、 問題を見出して、それを解けるように定式化するところは、 ショボい問題でもそれなりに大変だ。
Shannon の業績というのは Mathematical Theory of Communication という論文で、PDFで普通にダウンロード可能だ。 かなり長い論文で、複数の成果がまとめてあって読むのはけっこう大変なのだが、 どれも文句無く面白くてナイスだ。 今日的な評価でいうとそのなかで最もよく使われているのは 情報エントロピーの概念ではないだろうか。
そのなかで、離散的なシグナルで完全にランダムではない例として 英語などの自然言語がとりあげられる。 ランダムではないのなら、どんな法則性があるというのだろうか？ もっとも一般的に知られているのはおそらく、 探偵ホームズの「The Adventure of the Dancing Men」で有名な、「Eが一番よく出て来る」 というあれだろう。
各文字の出現確率は異なっていて、一様ではない。 そこで、これを自然言語のテキストで測定して その確率に従って文字を選んで出力してみよるとどう見えるだろうか？ 英語っぽく見えるだろうか？ という実験を Shannon はやってみる。 コンピュータなんて無い時代で、乱数表などを使った手計算だ。
残念ながら、一文字ではあまり英語には見えない。 だが、2文字でやってみたらどうだろう？3文字ならば？ じつは2文字で既に、けっこうそれっぽい文字列が出て来るところがおかしい。 凄く面白いのでそこだけでも読んでみて欲しい。
そこでわしは逆に考えてみた。 もし、たとえば2文字が実在の言語に近い出現頻度で出て来るような文字列があったら、 それは、そうでない文字列よりも、英語っぽいといえるのではないだろうか。 つまりでたらめに作った文字列に出現している、 2文字組み(あるいは3文字でもいいが)の 出現頻度を元に発音しやすさのスコアを計算できるのではないだろうか。
そこで早速やってみよう。まず 2gram の出現確率テーブルを作成する。 これは本質的にはそれなりに大きな規模のテキストを2文字ずつ切って数を数えればよい。 それができたとして、 ある単語を permutate した文字列のスコアは具体的にどう計算しようか？
文字 "a" のあとに "b" が来る確率は、 テーブルから探せばすぐに判る。これを p1 としよう。 "b" のあとに "c" が来る確率もテーブルから探せる。 これを p2 とする。 かりに、"abc" の尤もらしさスコアは p1*p2 としてみよう。 もちろん実在の言語であるからして、 "ab" と "bc" の出現は一般に独立ではない。 つまり "a" のあとに "bc" と続く確率は一般に p1*p2 ではない。 だが、独立でないとしても、さほど相関が強くなければ、 ひょっとしてそこそこ良い近似にはなっているかもしれない。 なにしろ、 Shannon の実験例では 各々の n-gram の出現は独立であるにも関わらず、 けっこうソレっぽい文字列ができているわけで、 そうであるならば、 それっぽさの評価においても独立だとしても案外、 良い近似になっているのではないだろうか？
ここまで考えたら、あれこれ計算してみるよりも、実際にこれでスコアをつけて ランダムな文字列をその成績順に並べてみようではないか。 もし十分な近似になっていれば、整列結果の一方の端は読める文字列、 他方は読めない文字列になっているはずだ。
あとは やってみるだけ。 最初は irb 上で作った Proc で計算まわしてやってみた。
[演習] 確率テーブルの取得に使うテキストは、同じ単語が一回しかでてこない 辞書と、実際のテキストで、どちらが望ましいだろうか？
手元にあった大きなテキスト集合は Bugtraq のアーカイブで、 これは若干語彙が偏っている恐れはあるが、とりあえずうまく動いている。 github にあげたコードでは、好きなようにテキスト集合を入れ換えて 遊べるようになっているので、そのへんをいじくって遊んでみて欲しい。 また、簡単な改編と、異なる言語の単語セットで確率テーブルを初期化すれば、 類似の確率モデルに従う言語であれば、その言語っぽさに応じて アナグラムがソートできると思いますが、実験はしていません。
急募！ ここで募集したい事があります。 どこでスコアが良い文字列が出て来るか、私にはいまいち判らなかったので、 このアルゴリズムでは計算量が factorial で増大し、あっというまに動かなくなってしまいます。 スコアの良いもの幾つかを拾う場合には、そんな計算は必要無いように 思われるのですが、うまい最適化を思い付かないので、 どなたか心当たりがありましたら、是非よろしくお願いします。
Nelder-Meade 法のコードも github で公開してみたわけだが、 公開してしばらくしてから、 なんとなく現実逃避で一回計算した点はもう計算しないように最適化してみた。 しかし残念ながら、この改良ではあまり速くはならなかった。 これはこのアルゴリズムでは、収束まえには、 最高成績の点に向かって他の点を全て縮めるという処理が案外でてくるからで、 その場合、n次元単体ではわずか 1/n+1 の計算量が節約できるにすぎない。 まぁどうでもよいのだ。一回やった計算をまたやってる、 と考えただけで作者の自分が気分が悪かった、というだけのことです。
実装は、計算結果をセーブしておく メモ変数を用意して、計算するまえにその変数を参照するようにしただけです。 それだけですが、かなりコードが読みにくくなってしまいました。
久々に、何か具体的に役に立ちそうなコンピュータの本買った。 「集合知プログラミング」である。
この本の良いところは、アルゴリズムの解説だけでなく、 コードとデータと適用結果まで載っているところです。 幾つか、以前勉強しようと思って記事を読んでも解るようにならなかった アルゴリズムがこの本で説明してあったので、買いました。 いくら俺さまでも、そこまで説明してあったら解るだろ、と思いまして。
オライリーのサイトで立ち読みできるのは自明な事しか書いてない2章だけで、 これは残念な気もする。 3章(クラスタリング)も読めれば、ぐっと市場は広がるはず。 というかオンラインでその場で買ったと思う。
自分が。