Drkcore

14122007 perl MAWP

MAWP 9章終了

後半はparserとか

Mastering Algorithms With Perl
Jon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 4,054 (1999-07)
通常3～5週間以内に発送

HOPも読んだし、再帰下降パーサもいじったことあるのでさらさらと。あとハフマン符号化とか。

結局1週間近くかけて読んだが文字列検索アルゴリズムがなかなか面白かった。

10122007 perl MAWP Python

PythonでBoyer-Moore法

Mastering Algorithms With Perl
Jon Orwant
Oreilly & Associates Inc / 2553円 ( 1999-07 )

perlは写経でいまいち理解度があやしいため、pythonでBoyer-Moore法を。パターンとの不一致の場合には何文字スキップできるか、一致した場合に何文字スキップできるかのテーブルを最初に作っておいて、スキップ幅の大きいほうでスキップしながらパターンマッチを進めていく。

def boyer_moore_bad_character (P):
   m = len(P)
   bc = [m] * 256
   j = m
   for char in list(P):
       bc[ord(char)] = j - 1
       j -= 1

   return m, bc

def boyer_moore_good_suffix (m,P):
   j = m + 1
   gs = [0] * j
   k = [0] * j
   k[m] = j
   for i in reversed(range(1,j)):
       while j <= m and P[i-1] != P[j-1]:
           if gs[j] == 0:
               gs[j] = j - i
           j = k[j]
       j -= 1
       k[i-1] = j

   kn = k[0]
   for j in range(m+1):
       if gs[j] == 0: gs[j] = kn
       if j == kn: kn = k[kn]

   gs.pop(0)
   return gs

def boyer_moore (T,P):
    (m,bc) = boyer_moore_bad_character(P)
    gs    = boyer_moore_good_suffix(m,P)

    (i, last_i, first_j) = (0, len(T)-m, m-1)

    for i in range(last_i+1):
        j = first_j
        while j >= 0 and T[i+j] == P[j]:
            j -= 1
        if j < 0:
            return i
        else:
            bcn = bc[ord(T[i+j])] - m + j + 1
            gsn = gs[j]
            i += bcn if bcn > gsn else gsn
    return -1

if __name__ == '__main__':
    print boyer_moore("perlpypythonruby","python")

pythonはコードの見通しがよいですな
perlと違ってsubstrとかやらなくてもいいので見通しがよい
perlのshiftがpop(0)なのがあれ。先頭をpopするってのが。
perlだと$a[5]=5とやれるけど、pythonはそれ以前の要素が自動的ににundefで埋まらない

for文でカウンタ変数使いたかったのでrangeをつかったけどPython流はどうやるのがよろしいんだろうか、、、カウンタ変数減算するのにfor i in reversed(range(1,j))だしな。

09122007 perl MAWP

MAWP 9章はStrings

パターンマッチングとか。

Mastering Algorithms With Perl
Jon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 4,036 (1999-07)
通常8～11日以内に発送

色々と検索アルゴリズムが紹介されていてなかなか進まない。

Boyer-Moore法を写経して、ついでにPythonで書き直してみたけどgood suffixのアルゴリズムがうまくかけません。perlのfor文とpythonのfor文は大分違うなと。というか、文字列の位置を記憶しながら逆向きに移動していってごにょごにょする方法が分からん。

for(;;)みたいなこと(カウンタ変数を使うっていうの?)をpythonでやる場合にはどういうことをすればいいんじゃと調べてみたら、そういう場合にはfor文は使わないのがお約束としか書いてなかったが、どうもwhile文を使えということらしい。

ふむ。

perlのコード見ながらpythonのコードに移植しようとすんのが間違ってるのかな。

06122007 chemoinformatics perl MAWP

MAWP 8章はグラフ

Graphなどを使ってグラフ

Mastering Algorithms With Perl
Jon Orwant
Oreilly & Associates Inc / 2960円 ( 1999-07 )

Kruskal's minimum spanning tree
Prim's minimum spanning tree
Dijkstra's SSSP

なんかをコードを追いながら理解することができた。Primはこっちの説明が分かりやすくてお奨め。

Pythonだとnetworkxがあってこっちは視覚化できてよさげ。

chemoinformaticsでグラフは化合物の構造表現なんかでよく使う。というか、売り物ツールが勝手にやってくれるのであまりちゃんと理解してなかったんだけど、アルゴリズムしらないで理解しないで使うと痛い目見たりとか、中身がよく分からんので痒いところに手が届かない感じが嫌だなと思うことがあったので、MAWP読んで基本的なところをちょっと押さえた気になった。

そういえば、gSpanなんかで、部分構造いじってみたいと思ってたんだけど、放ってあるなぁ。

04122007 perl MAWP