Drkcore

12012010 perl MAWP Python

PythonでWu-Manber

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)

12012010 perl MAWP Python

PythonでShift-ADD

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)

12012010 perl MAWP Python

PythonでShift-OR

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(こっちは組み込みのメソッド)

20122008 perl SICP HOP MAWP

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

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 )

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

20122007 perl R MAWP

MAWP14章はProbability

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も終了。ソート、マトリックス、グラフ、文字列マッチング、暗号あたりが面白かった。

19122007 perl MAWP

ElGamal暗号

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

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

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

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

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

18122007 perl MAWP

MAWP 13章はCryptography

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

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るのか。

16122007 perl MAWP