次の二つの章が特に面白かった。

• 5 Pythonから見たオブジェクト指向
• 7 Jythonの応用例

Jythonプログラミング
西尾 泰和
毎日コミュニケーションズ / ￥ 3,150 ()
在庫あり。

単なるjythonの使い方の本というよりは、jythonのような複数の言語を混ぜ合わせた処理系を通して見えるものを感じ取りましょう的な内容だったように思う。あとその場合に固さやわらかさの長所をうまくのばしてやるようなプログラミングのお作法はこんな感じですよみたいな指針。

perlでもInline系のモジュールを使えば直接他の言語を埋め込んだりできて他言語のライブラリを使えるけど、言語自体が両方の世界に干渉できるともっと楽ができる。

• Inline::JavaでCDKのニ次元構造立ち上げをperlから
• Statistics::R なんかいまいち

Inline::みたいなやり方でも、jythonみたいなシームレスな言語でも結局複数の言語を理解してないとうまいことやれないので、その分習得コストはかかると思うんだけど、シームレスな言語使うと楽しいのはスケッチするような感覚が得られることなのかなと思ってる。

そういう意味ではGainerも似たような感じかも。

Make: Technology on Your Time Volume 04
オライリー・ジャパン
オライリージャパン / ￥ 1,575 ()
在庫あり。

あとシームレスな言語を使うっていうことはそれにあわせてライブラリのほうも対応していかないといくのが望ましいのかなとPybel as a generic API for cheminformatics libraries - proof of concept using CDKというエントリを見てふと思った。

chemoinformaticsだとopenbabelっていうc++の大きいライブラリとCDKっていうjavaのライブラリがあって、その上にpython(とruby)がまたがっている感じなのだけど、さらにこれらでいじくったデータを解析にもっていくためにRが必要だったりとかするのでRpyが役に立ったりする。

Beautiful codeは予想してたよりも二倍くらい分厚かった。あとエッセイ集なので、好きなところから読み始める事ができるし、ちょっとした時間があるときに暇つぶし代わりに読めたりしてよさげ。

とりあえず、最初の方と最後のほうの対談を読んで、29章のまつもとゆきひろさんの「エッセイのごときプログラム」を読んで、そのうちRubyもなんて思った。

ビューティフルコード
Brian Kernighan,Jon Bentley,まつもとゆきひろ
オライリージャパン / ￥ 3,990 ()
在庫あり。

さて、18章はpythonにおける辞書実装の話。

[アルゴリズム百選 - ハッシュを再発明する](アルゴリズム百選 - ハッシュを再発明する)はリストを使う方法で実装していて、これはchainingと呼ぶらしい。

pythonはopen addressingという往々で空きスロットを探しているらしい。線形探査でなくとびとびに探していくことでブロックの発生を抑える効能があるらしい。

イメージできないのでスロットを探していく順番を見てみた。32個のスロットでハッシュ値が8の場合はまずスロット8を探すけど埋まっている場合に次はどこを探すのか。

use strict;
use warnings;
use Perl6::Say;

my $ma_mask = 31;
my $hash = 8;
my $pertub = $hash;
my $slot = $hash; 

for my $i (0..31) {
  $slot = (5 * $slot) + 1 + $pertub;
  $pertub >>= 5;
  $slot %= 32;
  say "[ $i ] slot:$slot, pertub:$pertub";
}

こんな感じ？

[ 0 ] slot:17, pertub:0
[ 1 ] slot:22, pertub:0
[ 2 ] slot:15, pertub:0
[ 3 ] slot:12, pertub:0
[ 4 ] slot:29, pertub:0
[ 5 ] slot:18, pertub:0
[ 6 ] slot:27, pertub:0
[ 7 ] slot:8, pertub:0
[ 8 ] slot:9, pertub:0
[ 9 ] slot:14, pertub:0
[ 10 ] slot:7, pertub:0
[ 11 ] slot:4, pertub:0
[ 12 ] slot:21, pertub:0
[ 13 ] slot:10, pertub:0
[ 14 ] slot:19, pertub:0
[ 15 ] slot:0, pertub:0
[ 16 ] slot:1, pertub:0
[ 17 ] slot:6, pertub:0
[ 18 ] slot:31, pertub:0
[ 19 ] slot:28, pertub:0
[ 20 ] slot:13, pertub:0
[ 21 ] slot:2, pertub:0
[ 22 ] slot:11, pertub:0
[ 23 ] slot:24, pertub:0
[ 24 ] slot:25, pertub:0
[ 25 ] slot:30, pertub:0
[ 26 ] slot:23, pertub:0
[ 27 ] slot:20, pertub:0
[ 28 ] slot:5, pertub:0
[ 29 ] slot:26, pertub:0
[ 30 ] slot:3, pertub:0
[ 31 ] slot:16, pertub:0

最小と最大の数を与えられた時にそのレンジの数の最小公倍数を求める。

順繰りにかけていって、その際に最大公約数で割ってく。最大公約数はユークリッドの互除法で。

def lcm(first,last):
    l =1  
    for i in range(first,last):
        l = l * i / gcd(l,i)
    return l 

def gcd(a,b):
    if(b==0): return a
    return gcd(b, a % b)

print lcm(1,5)
print lcm(4,5)
print lcm(1,12)

実行

/usr/bin/python  /Users/kzfm/python/lcmr.py 
12
4
27720

jythonがmacbookにインストールできなかったのでとりあえずlinuxで。

といってもgcjだとエラーを吐くので、sunのjavaをインストール。 ここみて設定。alternativeコマンドを使うとjavaの共存ができるのね。いままで、シンボリックリンクを上書きしてたのでめんどいなーと思ってたけど、これだとらくちん。

jythonをインストールしたら、あとはopsinのjarを落としてきてクラスパスに通す。

>>> import uk.ac.cam.ch.wwmm.opsin as opsin
>>> opsin.NameToStructure().parseToCML("4-iodobenzoic acid").toXML() 

二行でIUPAC名がCMLに。 すばらしい。

jrubyの例もある。

ちなみにjrubyはmacbookにさくっと入って、この例の通りにやれば動いた。

perlで同じ事をやる場合にはInline::Javaを使ってやればいいけど、Javaのライブラリを有効に利用するのはJavaで実装された言語処理系がやっぱ楽だ。

JRubyとかjythonとかはCGI書くのに苦労するよなとかつぶやいてみたけどjythonではSimpleHTTPSeverが使えることに気づいた。

% jython
Jython 2.2.1 on java1.6.0_06
Type "copyright", "credits" or "license" for more information.
>>> import SimpleHTTPServer
>>> SimpleHTTPServer.test()
Serving HTTP on 0:0:0:0:0:0:0:0 port 8000 ...
192.168.11.xx - - [26/Jun/2008 21:34:28] "GET / HTTP/1.1" 200 -
192.168.11.xx - - [26/Jun/2008 21:34:28] code 404, message File not found
192.168.11.xx - - [26/Jun/2008 21:34:28] "GET /favicon.ico HTTP/1.1" 404 -

あーでも、これだと、結局jythonスクリプトでCGI実行しないとあかんからうまくいかんわ。

というわけで、明日は会社にWebアプリ編を持ってってjythonでwebappサーバーつくるのにチャレンジ。

みんなのPython Webアプリ編 [みんなのシリーズ]
柴田 淳
ソフトバンククリエイティブ / ￥ 2,604 ()
在庫あり。

なんかやる気出てきた。

Programming Collective Intelligenceを読み始めた。

Programming Collective Intelligence: Building Smart Web 2.0 Applications
Toby Segaran
Oreilly & Associates Inc / 3446円 ( 2007-08 )

英語だとスペースで分割すれば単語に分けられるのだけど、日本語は品詞分解できないと類似度を計れないしクラスタリングもできないので、まずMeCabを使えるようにしておく。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys,re,feedparser
import MeCab

d = feedparser.parse('http://blog.kzfmix.com/rss/')
txt = ''
for entry in d.entries:
    txt += re.compile(r'<[^>]+>').sub('',entry.summary_detail.value)

try:
    t = MeCab.Tagger()
    m = t.parseToNode(txt.encode('utf-8'))
    while m:
        if m.stat < 2:
            if re.match('名詞',m.feature): print m.surface
        m = m.next
except RuntimeError, e:
    print "RuntimeError:", e;

1章はcollective intelligenceの紹介。

2章は類似性を評価するための距離の計りかた。ユークリッド距離とピアソン距離。あとエクササイズにタニモト距離。

Programming Collective Intelligence: Building Smart Web 2.0 Applications
Toby Segaran
Oreilly & Associates Inc / 3446円 ( 2007-08 )

無難に読み流す。

LDRのOPMLからRSSのURLを抜き出す

from xml.dom.minidom import parse, parseString
urls = []
dom = parse("export.xml")
for outline in dom.getElementsByTagName("outline"):
    url = outline.getAttribute("xmlUrl")
    if url: urls.append(url)

楽ちん

LDRで購読しているフィードから単語セットを抽出して遊びたい。 データセットは一度取っておけばいいので、永続化をしておく。入力はLDRから吐き出したOPMLファイル(export.xml)

集合知プログラミング
Toby Segaran
オライリージャパン / ￥ 3,570 ()
在庫あり。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys,re,feedparser,shelve,MeCab,sgmllib
from xml.dom.minidom import parse, parseString

opmlfile = "/Users/kzfm/export.xml"

def getwordcounts(i,url):
    print "#%d feedparser parse: %s" % (i,url)
    try:
        d = feedparser.parse(url)
    except UnicodeDecodeError,e:
        print "UnicodeDecodeError ", e
        return {}
    except sgmllib.SGMLParseError,e:
        print "sgmllib.SGMLParseError", e
        return {}

    txt = ''
    tage = re.compile(r'<[^>]+>');
    for entry in d.entries:
            if hasattr(entry,"summary_detail") : txt += tage.sub('',entry.summary_detail.value)

    try:
        t = MeCab.Tagger()
        m = t.parseToNode(txt.encode('utf-8'))
        wc = {}
        while m:
            if m.stat < 2:
                if re.match('名詞',m.feature): wc[m.surface] = wc.get(m.surface,0)+1
            m = m.next
        return  wc
    except RuntimeError, e:
        print "RuntimeError:", e;

def parse_opml(file):
    urls = []
    dom = parse(file)
    for outline in dom.getElementsByTagName("outline"):
        url = outline.getAttribute("xmlUrl")
        if url: urls.append(url)
    return urls;

if __name__ == "__main__":
    url_lists = parse_opml(opmlfile)
    tag_data = shelve.open("myldrwordsets")

    for i,url in enumerate(url_lists):
        tag_data[url] = getwordcounts(i,url)

    tag_data.close()

• 1000件ぐらい取ってくるのに30分ぐらいかかったが、ダウンしているサイトをずっと待っているのはよくない。feedparserのタイムアウトの設定ってどうやんのかな。
• 今回はshelveを使ってみたがpickleとの使い分けの基準がいまいちわからん

できたファイルのサイズは15Mくらいだった。これで類似度を計算したり、クラスタリングするためのデータは揃った。

追記 08.07.13

shelveだとなぜか辞書の復元がうまくいかなかったのでcPickleに変更した

if __name__ == "__main__":
    url_lists = parse_opml(opmlfile)
    tag_data = {}

    for i,url in enumerate(url_lists):
        tag_data[url] = getwordcounts(i,url)

    f=file("myldrwordsets","wb")
    pickle.dump(tag_data,f)
    f.close()

RSSから単語セットを抽出したら続いて、頻度のマトリックスを作成する。

集合知プログラミング
Toby Segaran
オライリージャパン / ￥ 3,570 ()
在庫あり。

流れとしては、全単語セットからある頻度以上の単語リストを作成（これが行のセット）し、それぞれのURL毎に何個含まれているかを調べてマトリックスにする。この時、あまりにもマイナーな単語とか、逆にあまりにもよく出る単語は類似性をはかるときに情報量ゼロにしかならないので除く。 今回1100件のフィードからなる（かなり多様性の高い）セットだったので、minの頻度はかなり低く設定した。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import cPickle,sys

def get_tagset(tag_data,min=0.1,max=0.7):
    all_tags = []
    tag_counts = {}
    size = float(len(tag_data))

    for tags in tag_data.values():
        for tag in tags:
            tag_counts[tag] = tag_counts.get(tag,0)+1

    for (tag,count) in tag_counts.items():
        if min < count/size < max: all_tags.append(tag)
    return all_tags

if __name__ == "__main__":
    out=file('blogdata.txt','w')
    f=file('myldrwordsets','rb')
    tag_data = cPickle.load(f)
    wordlist = get_tagset(tag_data,min=0.1,max=0.5)
    totalwords = len(wordlist)
    out.write('Blog')
    for word in wordlist: out.write('\t%s' % word)
    out.write('\n')

    for url,wordcount in tag_data.items():
        out.write(url)
        count = 0
        txt = ""
        for word in wordlist:
            c = wordcount.get(word,0)
            txt += '\t%s' % c
            if (c != 0): count += 1
        if float(count)/totalwords > 0.000000001:
            out.write(txt + '\n')
            print "%s: %2.8f" % (url,float(count)/totalwords)

実際に作成してみたデータを眺めた。というより、ケモインフォマティクス系はタニモト距離をよく使う関係上、密度(density)には非常に敏感。というわけで、url毎に非0の単語がどのくらいの割合含まれているかをチェック。やたらとビット密度の低いフィードは距離を算出しても仕方ないので除く事にした。

        if float(count)/totalwords > 0.000000001:
            out.write(txt + '\n')
            print "%s: %2.8f" % (url,float(count)/totalwords)

結局、915x300くらいのマトリックスが作成された。

類似度はかるのに尺度はなにを使おうか、、、とりあえず本にある通りにピアソン使おうかな。それとも今回の場合は単語の出現頻度よりも、ある文書に単語リスト中の文字が含まれるかどうかのほうが重要そうだからタニモトのほうがよさそうな気もする。