MAWP / Drkcore

PythonでWu-Manber

Tue, 12 Jan 2010 11:15:33 +0919

Mastering Algorithms With Perl
Jon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 3,263 ()
在庫あり。

ビット演算を利用したアルゴリズム。Shift-ADDと違いdifference,insertion,deletionを考慮する。

可能性を論理和として積み上げていってShift-ORみたいなアプローチで評価するとこだと思う。いまいちちゃんと理解できてないが。

   for j in range(1,k+1):
       s[j]  = (r[j] << 1) & Tc
       s[j] |= (r[j-1] | s[j-1]) << 1
       s[j] |= r[j-1]
       s[j] |= 1

あと、perlで@a = @bとやれるところがpythonではa=bとできず、 b = copy.copy(a)なのね。

#!/usr/bin/env python

import copy

def amatch (T,P,k=-1):

   text_length = len(T)
   pattern_length = len(P)
   po2 = map(lambda(x): 1 << x,range(31))

   if k == -1: k = int(pattern_length/10) + 1

   Table = [0] * 256
   for i in range(pattern_length):
       Table[ord(P[i])] |= po2[i]

   r = [0] * (k+1)
   for i in range(1,k+1):
       r[i] = r[i-1] | po2[i-1]

   mb = po2[pattern_length-1]

   s = [0] * (k+1)
   for i in range(text_length):
       s[0] <<= 1
       s[0] |= 1
       Tc = Table[ord(T[i])]
       s[0] &= Tc

       for j in range(1,k+1):
           s[j]  = (r[j] << 1) & Tc
           s[j] |= (r[j-1] | s[j-1]) << 1
           s[j] |= r[j-1]
           s[j] |= 1

       if s[k] & mb:
           return i - pattern_length + 1 if i > pattern_length else 0
       r = copy.copy(s)
   return -1

if __name__ == '__main__':
   print "match: ", amatch("pearl","perl",1)

PythonでShift-ADD

Tue, 12 Jan 2010 11:15:15 +0919

Mastering Algorithms With Perl
Jon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 3,263 ()
在庫あり。

これもビット演算を利用したアルゴリズム。differenceを許容するけどinsertion,deletionは駄目。

#!/usr/bin/env python

from math import *

def shift_ADD (T, P, k=-1):
   text_length = len(T)
   pattern_length = len(P)

   if k == -1: k = int(log(text_length)+1)
   if k == 0:  return T.find(P)
   if pattern_length == 1: return T.find(P)
   if pattern_length > text_length: return -1
   if pattern_length == text_length and P == T: return 0

   bits = int(log(k+1,2)) + 1 # ????
   mask = 1 << ( bits - 1 )
   ovmask = 0

   for i in range(pattern_length):
       ovmask |= mask
       mask <<= bits

   table = [ovmask >> (bits-1)] * 256

   nmask = 1
   for i in range(pattern_length):
       table[ord(P[i])] &= ~nmask
       nmask <<= bits

   mask = ( 1 << ( pattern_length * bits )) -1
   state = mask & ~ovmask
   ov = ovmask
   watch = ( k + 1 ) << ( bits  * ( pattern_length - 1 ) )

   for i in range(text_length):
       state = ((state << bits) + table[ord(T[i])]) & mask
       ov    = ((ov << bits) | (state & ovmask))    & mask
       state &= ~ovmask
       if (state | ov) < watch:
           return i - pattern_length + 1

   return -1

if __name__ == '__main__':
   print shift_ADD("perlpethonxx","python",2)

PythonでShift-OR

Tue, 12 Jan 2010 11:14:41 +0919

Mastering Algorithms With Perl
Jon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 3,263 ()
在庫あり。

Shift-ORってのはshiftしてORとって、どんどこどんどこと0を左送りにしていって最後まで0送りできた場合にパターンマッチ成功。最後がマッチしたかどうかは補数(一番左が0で残りが1)のANDをとって0が帰ってくるかどうかで判断するという文字列検索アルゴリズム。

#!/usr/bin/env python

def shift_OR_exact (T,P):

   text_length = len(T)
   pattern_length = len(P)

   if pattern_length > text_length: return -1
   if pattern_length == text_length: return 0
   if pattern_length == 1: return T.find(P)

   m1b = (1 << pattern_length ) -1
   table = [m1b] * 256

   mask = 1
   for i in range(pattern_length):
       table[ord(P[i])] &= ~mask
       mask <<= 1

   watch = 1 << ( pattern_length - 1 )

   for i in range(text_length):
       i = T.find(P[0],i)
       if i == -1: return -1

       state = m1b

       while i < text_length:
           state = ( state << 1 ) | table[ord(T[i])]
           if ( state & watch ) == 0:
               return i - pattern_length + 1

           if state == m1b: break
           i += 1

   return -1

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

ビット演算はperlもpythonも似た感じ
perlのindexはpythonのfind(こっちは組み込みのメソッド)

今年は本をよく読んだ気がする

Sat, 20 Dec 2008 09:46:23 +0919

SICPからHOPへのコンボがperlを扱う上でとても役立った。

計算機プログラムの構造と解釈
ジェラルド・ジェイサスマン
ピアソンエデュケーション / 4830円 ( 2000-02 )

特にHOPは値段以上の価値があったと思ってるので満足。

Higher-Order Perl: Transforming Programs with Programs
Mark Jason Dominus
Morgan Kaufmann / 5976円 ( 2005-03-28 )

そしてMAWP

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

来年もこの調子で。あと、もっとコードを書く。

MAWP14章はProbability

Thu, 20 Dec 2007 22:24:51 +0919

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

こういうのはRに任す。確率分布とか充実してる。

15章も統計なのでRで。

16章は微分とかsmoothingとかSICPな感じなので流し読みして終了。

ってことで、MAWPも終了。ソート、マトリックス、グラフ、文字列マッチング、暗号あたりが面白かった。

ElGamal暗号

Wed, 19 Dec 2007 20:54:09 +0919

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

位数が大きな群の離散対数問題が困難であることを安全性の根拠にした暗号化方式

巡回群を利用しているらしい。そういや、ガウス平面上の回転って数学ガールの3章で読んだなと。

数学ガール
結城浩
ソフトバンククリエイティブ / 1890円 ( 2007-06-27 )

modも回転か何かで考えることが出来るのかね。

MAWP 13章はCryptography

Tue, 18 Dec 2007 22:19:38 +0919

アンゴウよりアンコウ+日本酒のほうが好きなんだけど。

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

というより、数式を避けてただけだった。ちゃんと読んでみると暗号も面白いかも。法とか合同をほうとかいいながら読んでた。MAWPの説明だけだと分かりにくかったのでRSA暗号を参考にした。

MAWPにあったSSLeayっていうモジュールがなかったのでCrypt::RSAで遊んだ。

use Crypt::RSA;
use Data::Dumper;

my $rsa = new Crypt::RSA;

my ($public, $private) =
  $rsa->keygen (
        Identity  => 'Kzfm Ohkw <xxxx@gmail.com>', 
        Size      => 1024,
        Password  => 'drumnbass',
        Verbosity => 1,
           ) or die $rsa->errstr();

print Dumper($public);

公開鍵

$VAR1 = bless( {
                 'e' => 65537,
                 'n' => '12390802849571403672579795755491999585878694
                         2679376999148135793744998012786068647404317033
                         4506694188629007869741465370712440443624446804
                         8813574622838502197241514075336790104367156693
                         3189856420057871502127203513391621825674392638
                         5941923712730877023358276499112454722795081438
                         05979844138326376749179360228658183',
                 'Version' => '1.91',
                 'Identity' => 'Kzfm Ohkw <xxxx@gmail.com>'
               }, 'Crypt::RSA::Key::Public' );

おー65537乗してnでmodるのか。

MAWP 12章はNumber Theory

Sun, 16 Dec 2007 21:34:42 +0919

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

Modularとか。Chinese Remainder Theoremってなにがおもろいんだろうとか思ったが、RSA暗号がらみ？そのうちちゃんと読んでみる。

あとMiller-Rabinとかコラッツ予想とかそんな感じ。

MAWP 11章はNumber System

Sat, 15 Dec 2007 22:09:23 +0919

perlで複素数とか極座標とか扱うって話あまり興味がなかったので流した。

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

最後の例のリーマンゼータ関数は面白かった。

まだ2章くらいしか読んでない数学ガールにも出てくるらしい

数学ガール (数学ガールシリーズ 1)
結城浩
ソフトバンククリエイティブ / 1890円 ( 2007-06-27 )

これも早く読みたいなぁ。

MAWP 10章はGeometric Algorithm

Sat, 15 Dec 2007 22:05:12 +0919

さわりだけなので、さらっとしている。

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

ちゃんと学びたければC++とかの本を探したほうがよいのかな？pymolとかAvogadroのソースを読むのがいいのかもしれんなぁ。

ドッキングシミュレーションとか色々気に入らない部分があるので、手を加えたい部分があったりとか、Caverみたいなの自分で書いてみたかったりするんだけどそういう書籍はないもんかな。