2010-09-21
行列分解ライブラリredsvdで潜在的意味インデキシングを試してみたの巻
久しぶりに自然言語処理的な話です。
すこし前にPFIの岡野原さんが公開されたredsvdを試してみました。
redsvd は行列分解を解くためのC++ライブラリであり、特異値分解（SVD)、主成分分析(PCA)、固有値分解などをサポートしています （中略） 例えば、行と列がそれぞれ10万、非零 の要素が100万からなる行列に対する上位20位までの特異値分解を1秒未満で行うことができます．
１秒未満って、す、す、すごくねぇだべか？
というわけで早速導入してみますた。
インストール
redsvdは内部の行列演算などにeigen3を使っているとのことなので、まずはこいつをセットアップ。あ、そうそうCMAKEも必要だよ。
ちなみに自分の環境でmake checkしたらエラーが少し出てたけど、気にせずそのまま突っ込んでみました。
続いてredsvdをインストール。
マニュアルサイト見ながらやれば問題ないかと思われますので、ここらへんの詳細は省略します。
下ごしらえ
さて、さっそく！
と言いたいところですが、いろいろと下ごしらえが必要です。
今回は解析対象データとして、某検索サイトの検索ログを数万件分を持って来て、この検索クエリーを関連語で適当に拡張させたものを使います。
検索クエリーを関連語に拡張させるのは、拙作のLingua::JA::Expandというperlモジュールでもできるし、YahooAPIの「関連検索ワード」を使ってもいいかもね。まぁ、データは適当に用意した、という前提ですすめましょう。
ちなみにこの時点では以下のような
「検索クエリ key value key value key value .....」
というようなフォーマットだと仮定します。
要するに検索クエリに対して関連語が bag of words として並んでいるようなフォーマットです。
実例↓
feature_vector.txt
B-1グランプリ順位 グランプリ 57.5651697754102 順位 55.2949308955951 厚木 49.9866441630489 B-1グランプリ 39.3727412201767 祭典 34.3234789476085 中間 32.5569044283475 横手 32.4415825522972 -1 29.5295559151325 投票 24.6079632626104 富士
宮 24.1869095999417 津山 23.9561674837952 八戸 21.9336671532829 久留米 20.8208354120631 発表 19.8165814990785 八戸せんべい汁 19.6863706100883 ご当地グルメ 19.6863706100883 りう 19.0337310644589 行田 16.6138645318661 開催 15.4453195644505
横手やきそば 14.7647779575663 B級グルメ 14.7647779575663 箸 13.5186705477277 グルメ 12.8579683394308 太田 12.2752941145721 日本一 12.1918731374094 初日 11.6451320212923 最終 11.3429842290652 ゴールド 10.5028675612984 優勝 10.3416080924982 三浦海岸 10.185320100199
・
・
・
この例だと「B-1グランプリ順位」という検索クエリに対して、それ以降で「グランプリ => 57.5651...」や「順位 => 55.294...」のように素性が並んでいます。
なお数値部分はTFIDFなどの重み付けされたスコアを使ってます。
さて、早速redsvdをぶん回してみたいのですが、このままだと食べてくれません。
疎行列の場合にはlibsvdでつかわれている表現方法と同じように各行毎に、0では無い列番号とその値をコロン区切りで書く方法で行列を表します．
むぅ。面倒ですがこんな感じのスクリプトで加工。
use strict; use warnings; my $word_idx; my @labels; while (<>) { chomp $_; my @f = split "\t", $_; my $label = shift @f; my %wordset = @f; push @labels, $label; my @item; while ( my ( $key, $value ) = each %wordset ) { my $idx = _idx($key); push @item, $idx. ':' . $value; } print join(" ", @item); print "\n"; } # ラベル（検索キーワード）は別ファイルでとっておく open(OUT, "+>", "labels.txt"); for(@labels){ print OUT $_,"\n"; } close(OUT); sub _idx { my $key = shift; $word_idx->{$key} || do { $word_idx->{$key} = int( keys %$word_idx ) + 1; }; }
走らせてみます。えい。
perl filter.pl feature_vector.txt > svd_in.txt
そうするとこんな感じ。
1:4.81836340644913 2:7.03558865049202 3:7.83207818255356 4:4.36772932997306 5:7.02204442538426 6:3.65583160006774 7:2.32278780031156 8:7.41858090274813 9:2.94124408826992 10:1.77431255562433 11:5.86254376704114 12:4.52082903755434 13:5.92492802330774 14:7.1665260079395 15:2.44876760317213 16:3.70365474023736 17:3.70365474023736 18:6.51841955280386 19:5.417100902538 20:6.00759392903787 21:5.63127578386945 22:6.57701371706991 23:4.81836340644913 24:3.70365474023736 25:6.1247673944224 26:7.67562600573802 27:10.1468338111679 28:7.41858090274813 29:4.66279929882473 30:1.84769510155836
・
・
・
ラベル（検索クエリー）がなくなって、素性のキー部分が１から始まる数値に置き換わりました。
これでredsvdのスパース行列のフォーマットになりました。
ようやく本番
さて、redsvdの登場です！
今回試してみるデータですが、24万クエリくらい。
こいつを特異値分解により200次元に圧縮してみます。
[miki@godzilla work]$ redsvd -i svd_in.txt -o svd_out -r 200 -f sparse
compute SVD
read matrix from svd_in.txt ... 12.0844 sec.
rows: 281280
cols: 243421
rank: 200
compute ... 148.231 sec.
write svd_out.U
write svd_out.S
write svd_out.V
50.6651 sec.
finished.
[miki@godzilla work]$
終わりました。
データの読み込みに12秒、計算に148秒、その後の行列を分解したデータの書き出しに50秒かかったよ、という意味のようです。
え、これってめちゃくちゃ速くない？
さて、結果としてsvd_out.U、svd_out.S、svd_out.Vという３つのファイルが生成されました。
なお、octave等でsvdを使って次元縮退させる際は特異値分解の後に、S（固有値を降順にならべた配列）の累積寄与率(?)を自分で計算して、再度 U x sqrt(S) などすることで結果のマトリックスを得るという手順でしたが、redsvdはこの時点でそこまでやってくれています。
つまりsvd_out.Uがそのものズバリ、ということのようです。（たぶん）
なので、上のperlスクリプトで「とっておいた」ラベルのファイル（もとの検索クエリ文字列が順番に書かれたもの）とくっつければ、「200次元に圧縮された行列」のできあがりです。（たぶん）
検証してみる
上で「たぶん」と書いたのは、本当にこれで合ってるのか、結果の行列睨んでいてもわからないからです。
なんとかして検証しなければ、ということで簡単な「潜在的意味インデキシング風」なスクリプトを用意します。（以前も紹介したネタですが）
ここまでの処理で出来上がった「検索クエリーのSVD行列」をすべてメモリにのっけて、適当な文字列を入力として受け取ったら、メモリ上の全レコード分と総当たりに距離を測定して、近いものから１０件を表示するスクリプトです。
総当たりなのですごく遅いですが、検証にはなるでしょう。
use strict; use warnings; use Data::Dumper; # データ復元 my $featured_vector; open( VEC, "query_svd_matrix.txt" ); while (<VEC>) { chomp $_; my @f = split( "\t", $_ ); my $key = shift @f; $featured_vector->{$key} = \@f; } close(VEC); # 標準入力からのデータ取得 print "INPUT NAME : "; my $query = <>; chomp $query; my $query_vec = $featured_vector->{$query}; # 近傍検索 my @sorted = sort { $a->{dist} <=> $b->{dist} } map { my $name = $_; my $vec = $featured_vector->{$name}; my $dist = distance( $query_vec, $vec ); { name => $name, dist => $dist } } keys %$featured_vector; # 上位10件を表示 for ( 1 .. 10 ) { print Dumper shift @sorted; } # ユークリッド距離を計算する関数 sub distance { my $vector_1 = shift; my $vector_2 = shift; my @vec1 = @$vector_1; my @vec2 = @$vector_2; my $sum; for my $i ( 0 .. $#vec1 ) { my $d = ( $vec1[$i] - $vec2[$i] )**2; $sum += $d; } my $distance = sqrt($sum); return $distance; }
さっそく走らせてみます。
まずはラーメン。
[miki@godzilla work]$ perl test.pl
INPUT NAME : ラーメン
$VAR1 = {
'name' => 'ラーメン',
'dist' => 0
};
$VAR1 = {
'name' => 'ぼぶ ラーメン紀行',
'dist' => '0.0177238305396999'
};
$VAR1 = {
'name' => 'とん太ラーメン',
'dist' => '0.0211681702090663'
};
$VAR1 = {
'name' => 'ラーメン 醤油亭',
'dist' => '0.0218072035346121'
};
$VAR1 = {
'name' => 'らーめん',
'dist' => '0.0235849467881528'
};
$VAR1 = {
'name' => '百福ラーメン',
'dist' => '0.0261412958171549'
};
$VAR1 = {
'name' => 'ラーメン虎ジ',
'dist' => '0.0265464345063513'
};
$VAR1 = {
'name' => 'ラーメン 二郎',
'dist' => '0.0292685444803803'
};
$VAR1 = {
'name' => 'ラーメン 彩味',
'dist' => '0.0299031733934711'
};
$VAR1 = {
'name' => 'げんこつ ラーメン',
'dist' => '0.0302795406669256'
};
[miki@godzilla work]$
おお！見事にラーメン関連のクエリが並びました。200次元に圧縮してもちゃんと意味が残ってたんですね！
おつぎは今話題のコレ。
INPUT NAME : 尖閣諸島
$VAR1 = {
'name' => '尖閣諸島',
'dist' => 0
};
$VAR1 = {
'name' => '日中尖閣諸島問題',
'dist' => '0.0146660394449217'
};
$VAR1 = {
'name' => '尖閣諸島領海',
'dist' => '0.0250298066312946'
};
$VAR1 = {
'dist' => '0.025504166345913'
};
$VAR1 = {
'dist' => '0.030786449957733'
};
$VAR1 = {
'dist' => '0.030786449957733'
};
$VAR1 = {
'dist' => '0.0325268407472967'
};
$VAR1 = {
'dist' => '0.0345627984399412'
};
$VAR1 = {
'dist' => '0.0360544180926554'
};
$VAR1 = {
'dist' => '0.0400427653890188'
};
ふむ。。。不穏な空気を感じますね。。。
最後にオマケでもう１発。
INPUT NAME : 焼肉
$VAR1 = {
'name' => '焼肉',
'dist' => 0
};
$VAR1 = {
'name' => '焼肉キング',
'dist' => '0.0354135623031629'
};
$VAR1 = {
'name' => '焼肉の仁',
'dist' => '0.0355411440586822'
};
$VAR1 = {
'name' => '焼肉店',
'dist' => '0.0363344784467866'
};
$VAR1 = {
'name' => 'ホルモン市場 じゅうじゅう',
'dist' => '0.0388911970759451'
};
$VAR1 = {
'name' => '焼肉幸 四日市',
'dist' => '0.0394660728474471'
};
$VAR1 = {
'name' => '焼肉 チェーン',
'dist' => '0.0395717680550162'
};
$VAR1 = {
'name' => '焼肉 チェーン 安',
'dist' => '0.0395717680550162'
};
$VAR1 = {
'name' => 'プルコギ',
'dist' => '0.0398892503564557'
};
$VAR1 = {
'name' => '焼肉明洞',
'dist' => '0.0399250527864397'
};
ホルモンとかプルコギとか、直接「焼肉」というコトバではないものがしっかり意味的に「近い」と評価してくれてるあたり、いいですね。
検証してみる その２
その２としてbayonでクラスタリングしたみたよ、って内容を書こうと思ったんですが、眠くなって来たので、省略。
ポイントというか、気になったことだけ書いておきます。
元のデータをbayonで 「-l 1.5」という条件でクラスタリングしたら25000くらいのクラスタになったんですが、redsvdで次元圧縮したデータをくわせたら13000程度のクラスタにしか分割されませんでした。
つまり、SVD（特異値分解）による潜在的意味インデキシングだと、単にサイズをちいさくするだけでなく、ノイズもカットしてることになるので、その影響で細かいクラスタには分かれなくなったんだと思います。
「ノイズをカットする = 大事なところだけにする = 特徴がよりはっきりする = あんまり細かくは分けられない」
といったところでしょうか。
当方シロウトにつき、識者の意見求ム。
まとめ
redsvdはえー。
岡野原さんすげー。
おわり。
Permalink | コメント(0) | トラックバック(0) | 02:29 
2010-09-06
Hadoopに入門してみた - セットアップからHadoop Streaming まで -
大規模データを処理する必要が出て来たので、Hadoopを導入してみることになりました。
以下、導入メモです。
セットアップ
以下のような構成で試してみます。環境はCentOSです。
マスター（host001) ━┳ スレーブ（host002）
┣ スレーブ（host003）
┣ スレーブ（host004）
┗ スレーブ（host005）
まずは各マシンにJavaをインストール。JDK1.6を落として来てrpmでインストールするか、yum install java-1.6.0*などとたたけばOKです。（rpmでインストールする場合は http://java.sun.com/javase/ja/6/download.html から jdk-6u18-linux-i586-rpm.binをダウンロードして、実行権限を与えてルートで実行すればインストールできます。）
続いてマスターノードにHadoop本体をダウンロードします。 ここら辺から適当に落としてきます。
tarballを落として来たら適当な場所で展開し、以下の設定ファイルをいじります。
conf/hadoop-env.sh
JAVA_HOMEは設定必須です。javaをyumでインストールした場合は export JAVA_HOME=/usr/lib/jvm/java-1.6.0-openjdk-1.6.0.0/ とか。rpmで入れた場合は export /usr/java/default にしておけばよいでしょう。
core-site.xml
マスターノードのホスト名を書き入れます。
<?xml version="1.0"?> <?xml-stylesheet type="text/xsl" href="configuration.xsl"?> <!-- Put site-specific property overrides in this file. --> <configuration> <property> <name>fs.default.name</name> <value>hdfs://host001:9000</value> <final>true</final> </property> </configuration>
hdfs-site.xml
今回は試しなのでレプリケーションを１としました。
<?xml version="1.0"?> <?xml-stylesheet type="text/xsl" href="configuration.xsl"?> <!-- Put site-specific property overrides in this file. --> <configuration> <property> <name>dfs.replication</name> <value>1</value> </property> </configuration>
mapred-site.xml
job trackerにはマスターノードのホストを指定します。mapperとreducerは各々３個に指定してみました。
<?xml version="1.0"?> <?xml-stylesheet type="text/xsl" href="configuration.xsl"?> <!-- Put site-specific property overrides in this file. --> <configuration> <property> <name>mapred.job.tracker</name> <value>host001:9001</value> </property> <property> <name>mapred.tasktracker.map.tasks.maximum</name> <value>3</value> </property> <property> <name>mapred.tasktracker.reduce.tasks.maximum</name> <value>3</value> </property> </configuration>
以上の設定ファイルを書いたら、hadoopディレクトリごと全サーバにrsyncします。
Hadoop本体の設置は以上で終わり。意外と簡単ですね！
解析対象となるファイルを設置する
Hadoopで解析させたいファイルをhdfs上に設置します。
hdfsへのファイルのコピーはマスターノード上で bin/hadoop fs コマンドを使って行ないます。ここでは/data/logs/以下にapacheのアクセスログが１ヶ月分置いてあると仮定しましょう。
その場合のコマンドはこんな感じになります。
[miki@host001 hadoop]$ bin/hadoop fs -put /data/logs/* input
上記のコマンドを叩くことで分散ファイルシステム上へのコピーが始まります。
デフォルト設定だと各スレーブの /tmp/hadoop-ユーザ名/dfs の下に64Mごとのチャンクに分割されたファイルが格納されていきます。
ためしにコンソールを複数立ち上げて、host002〜host005 で各々 watch -n 0 "du -s /tmp/hadoop-ユーザ名/dfs" などとすると、１台づつ順繰りにデータが渡されて来る様子を確認できます。
ここら辺、もっと一気に並列でどばっと撒いてくれると短時間で済むと思うんですが、どうやらそうなってはいないようです。Hadoopの全行程において、この「分散ファイルシステムへのコピー」は相当時間のかかる行為なので、イライラします。
なお後からわかったんですが、実は今回試した環境が100Mbpsしかスループットが出ないswitchに収容されていたため、600Gのデータを撒くのに、１２時間もかかってしまいました。まずはギガビット出るようにしておかないとお話にならないようですね。
さてさて、なにはともあれhdfsへの転送が終了したので、確認してみます。
/user/ユーザ名/input/ というhdfs上のディレクトリにアクセスログが格納された様子がわかると思います。あとはこのhdfs上のデータに対してmap-reduceの処理を実行させていくことになります。
Hadoop Streaming を使ってmapperとreducerを書く
さて、ここまでくれば後は map-reduceの処理を走らせるだけなんですが、実は hadoop-streaming というAPIを使えば、javaでなくとも好きな言語でmapperとreducerを書くことができます。その際のルールは「標準入力からデータをもらって標準出力に書き出す」というきわめて単純なものとなっています。ありがたい！
というわけで、perlでmapperとreducer書いてみました。
まずはmap.pl。
#!/usr/local/bin/perl use strict; use warnings; my $counter; while(<STDIN>){ chomp $_; my @f = split(" ", $_); $counter->{$f[5]}++; } while(my ($key, $value) = each %$counter){ print $_,"\t", $counter->{$_},"\n"; }
標準入力からログを１行づつ読み込んで、適当にsplitなりなんなりして、データを数え上げます。
ここでは自前で$counterを設けていますが、どうせreducerに渡される前後でも同じようなことは処理されるので、これはなくてもいいです。メモリの無駄かも。その場合は単純に print $_,"\t1\n"; としておけばいいでしょう。
なお、きわめてシンプルなスクリプトを例示してしまいましたが、実際にはクロールやDB問い合わせ、エンコード／デコードなどなど、イロイロな処理をすることになるでしょう。
また現実的にはシンプルなkey => valueではなくて、多段のハッシュ構造などでデータを渡したいことが多いでしょう。その場合は key の部分に適当な文字列をセパレータにして複数のデータ項目を格納してしまえばよいと思います。reducerで分解すればよいので。
というわけで、おつぎはreduce.pl
#!/usr/local/bin/perl use strict; use warnings; my $counter; while(<STDIN>){ chomp $_; my ($key ,$value) = split "\t"; next if !($key && $value); $counter->{$key} += $value; } for( sort { $counter->{$a} <=> $counter->{$b} } keys %$counter ){ print $_,"\t", $counter->{$_}, "\n"; }
見てわかる通り、reducerもシンプルです。もう好きなように書けばいいです。
ちなみに、naoyaさんが２年くらい前にhadoop streamingの記事を書いています。
その中でイテレータつかったより効率的なフレームワークを作られているので、本格的に導入する際にはこれを使うといいでしょう。
mapperとreducerを準備したので実際に処理を走らせてみます。
マスターノードで以下のコマンドを叩きます。
[miki@host001 hadoop]$ bin/hadoop jar contrib/streaming/hadoop-0.20.2-streaming.jar -input /user/miki/input -output output -mapper /home/miki/hadoop/perl_script/map.pl -reducer /home/miki/hadoop/perl_script/reduce.pl
hadoop-streamingを実行してくれるjarファイルはcontribの下にあるので、bin/hadoop jar で呼び出します。あとはhdfs上の -input と -outputの指定、それと -mapperと -reducerを指定します。
なお、mapperとreducerを絶対パスで直接指定していますが、そうする場合には事前に各スレーブ（host002からhost005まで）にperl_scriptをrsync しておく必要あります。またそんな面倒なことをしなくても、-file というオプションを指定することで任意のファイルを実行時にスレーブに転送することもできるようです。
map-reduceの処理が始まるとコンソール上に進捗状況が表示されます。
おわったらhdfs上の/user/ユーザ名/output/part-00000というファイルに結果が出力されるはずなので、 それをlinuxのファイルシステムに持ってきます。
[miki@host001 hadoop]$ bin/hadoop/fs get /user/ユーザ名/output/part-00000 /home/ユーザ名/output.txt
これで結果ファイルを取得できました。お疲れ〜。
まとめ
Hadoopの導入は意外と簡単でした。今回試してみた環境には古いサーバ（RedhatEL4）も混ざっていたんですが、Javaの導入も問題なかったしHadoopもちゃんと動いてくれました。
「map-reduceのメリットは最低でも２０台くらいないとわからない」なんて言いますが、まずは4〜5台程度で試してみることをオススメします。
というのは、map-reduceのカッコいい側面だけではなく、まずは小さい規模でシステムを組んでみて、どこらへんにどれくらい時間や負荷がかかるのか、総合的なコスト感というものを把握すべきかと思います。
その上で本当にイケルと確信したならば数十台規模のシステムを構築すべきかな、と感じました。
規模が小さくて簡単な処理だったら、実は普通に集計スクリプトを書いて複数プロセスで動かした方が速い場合もあるしね。（少なくともhdfsへの大量データコピーはかなり時間がかかります！）
とはいえ、Hadoop面白かったです。そのうちHiveを試してみます。
Permalink | コメント(1) | トラックバック(1) | 07:11 
2010-08-19
Javaで暗号化したデータをPerlで復号化しようとしたら大変だった件
JavaでRijndael(AES)で暗号化されたデータをPerlで復号化しようと思います。
「暗号方式と秘密鍵だけ聞いておけば簡単にデコードできるっしょ、余裕っしょ」とタカをくくっていたら、思いっきり天罰がくだりました。久しぶりにハマったのであります。
ちゃんと確認しておくべきだった情報
まずは暗号方式と秘密鍵だけでなく、以下の情報をしっかりと確認しておく必要アリでした。
暗号のことちゃんと勉強した事がないので、なんだかよくわからんけど、必要らしい。
せめて事前にここらへんを読んで勉強しておけばよかった。
ぱせらんメモ
http://d.hatena.ne.jp/pasela/20100612/crypto
DESに代わる次世代暗号「AES」の最終候補が「Rijndael」に決定
http://itpro.nikkeibp.co.jp/members/ITPro/ITARTICLE/20001003/1/
ブロック暗号化モード
http://www.triplefalcon.com/Lexicon/Encryption-Block-Mode-1.htm
今回はこれらの情報を全然把握せず、よその開発チームからJavaのソースコード（ドキュメントなし）と断片的な情報（「暗号鍵はたぶんこれ」といった感じの不確かな情報）だけを入手して、「まぁ適当に復号化できるだろう」とナメた態度で臨んだら、思いのほかハマってしまったわけです。
結局、いろいろ調べるのにJavaのソースを読んだり書いたりして、えらい手間がかかりました。。。
Javaで暗号化
条件は以下のとおり。
- 暗号アルゴリズム => AES（Rijndael）
- 秘密鍵 => 0123456789ABCDEF
- 秘密鍵の長さ => 128bit
- ブロック暗号化モード => CBC
- IV => 0000000000000000
- padding方式 => PKCS5Padding
「Hello World!」という文字列を暗号化してみます。
以下おソースです。
import java.security.*; import javax.crypto.*; import javax.crypto.spec.IvParameterSpec; import javax.crypto.spec.SecretKeySpec; public class Encrypt { public static void main(String[] args) { try { // 元データはHello World! String plainText = "Hello World!"; System.out.println( "PLAIN TEXT: " + plainText ); // 秘密鍵とIV byte[] key = "0123456789ABCDEF".getBytes(); byte[] iv = "0000000000000000".getBytes(); SecretKey cipherKey = new SecretKeySpec(key, "AES"); IvParameterSpec ivSpec = new IvParameterSpec(iv); // 条件を指定してCipherを暗号モードで初期化 Cipher cipher = Cipher.getInstance("AES/CBC/PKCS5Padding"); cipher.init(Cipher.ENCRYPT_MODE, cipherKey, ivSpec); // 暗号化してみる。結果のバイト配列を16進文字列で表示 byte[] cipherText = cipher.doFinal(plainText.getBytes()); System.out.println( "ENCRYPTED : " + asHex(cipherText) ); // 今度は複合化。 cipher.init(Cipher.DECRYPT_MODE, cipherKey, ivSpec); byte[] output = cipher.doFinal(cipherText); System.out.println("DECRYPTED : " + new String(output)); } catch(Exception e) { e.printStackTrace(); } } // byte配列を16進で返す関数。 private static String asHex(byte bytes[]) { StringBuffer strbuf = new StringBuffer(bytes.length * 2); for (int index = 0; index < bytes.length; index++) { int bt = bytes[index] & 0xff; if (bt < 0x10) { strbuf.append("0"); } strbuf.append(Integer.toHexString(bt)); } return strbuf.toString(); } }
実行すると以下のようになります。
PLAIN TEXT: Hello World!
ENCRYPTED : d481e7bc55b0ef8b74221d497d6bc259
DECRYPTED : Hello World!
「Hello World!」という文字列を暗号化して16進にした文字が「d481e7bc55b0ef8b74221d497d6bc259」として取得できました。
そいつをさらに復号すると元の「Hello World!」になるのも確認できました。
Perlで復号化
さて、こいつをPerlで復号化します。Crypt::CBCを使います。
use strict; use warnings; use Crypt::CBC; # Javaで暗号化した文字列 my $encrypted = "d481e7bc55b0ef8b74221d497d6bc259"; # Crypt::CBCのコンストラクタ。パラメータが重要。 my $cipher = Crypt::CBC->new( -key => '0123456789ABCDEF', -keysize => 16, -literal_key => 1, -cipher => "Crypt::Rijndael", -iv => '0000000000000000', -header => 'none', ); # 16進文字列をバイトに変換 $encrypted = pack( "H*", $encrypted ); # 復号化して表示 my $decrypted = $cipher->decrypt($encrypted); print "decrypted: ", $decrypted, "\n";
このスクリプトによってPerl側で「Hello World!」と復元できました。それにしてもここに至るまで長かった。。。
Crypt::CBCのコンストラクタに渡す全てのパラメータが重要で、少しでも組み合わせが違うとまともにデコードできません。
さらに言うとこの中で「-literarl_key => 1」がかなり盲点です。
当初このパラメータの存在に気づかずだいぶ悩んでいたら、ようやくこんな書き込みを発見。
Java Solution会議室 > perl java暗号化復号化ロジックに関して
http://ap.atmarkit.co.jp/bbs/core/fjava/22485
言い忘れましたが、javaで暗号化しても、perlで暗号化しても、こちらでは同じ暗号文が出力されました。ただしliteral_key => trueを指定した場合です。
これを指定しないと、Crypt::CBCのほうは、デフォルトでは指定したキーをパスワードとみなし、
その文字列を複数回ハッシュした結果からキーを生成するようです（標準的なPBEではなく、おそらく独自方式ではないかと思います）。
OH! そんなの知らないってば。
これがわかるまで１日かかってしまったあるyo！
「JavaとPerl」のような異なる言語間での暗号／復号処理は、ナメてかかると意外と苦労するよ、というお話でした。
Permalink | コメント(0) | トラックバック(1) | 08:18 
2010-07-23
遺伝的アルゴリズムを楽しく理解できるサイトをまとめてみた
女優の菊川怜さんが学生時代に研究テーマにしていたという事で有名な「遺伝的アルゴリズム」ですが、名前の仰々しさとは裏腹に、意外と直感的に理解できる取っ付きやすいアルゴリズムだったりします。
それにしても菊川怜さん、美人ですねー。こんな先生にイロイロと教えてもらいたかったなぁ。。。
という願望はおいといて、「遺伝的アルゴリズム」を目で見て＆手で触って、直感的に「理解したつもり」になれそうなサイトをまとめてみました！
学術的なことはガン無視でいきます。
動画で見て雰囲気を知る
まずは動画で見て楽しみましょう。ニコ動から何本か動画を紹介します。
いきなりですが、強烈なインパクトをはなつ動画です。
人工生命がうにょうにょ動きながら、勝手に「歩き方」を学んでいきます。超キモイですが、スゴイ作品だと思います。物理エンジンと遺伝的アルゴリズムを駆使してるらしいです。
anlife
これも同じ作者の人のものなのかな？ちょっと定かではありませんが、人工生命を育成するゲームのようなシミュレータです。
ちなみに、だいぶ脱線になりますが、ニコニコ動画で「anlife」で検索すると、人工生命が増殖する動画がたくさん出てきます。尺の長い動画ですが、我慢して見ていくと、2分30秒過ぎあたりから人口爆発的に増殖していって、寒気がするほど気持ち悪いです。
次もニコ動から。
ミクが出てこないと何も理解できない、という人にはおすすめ。
一応、局所最適解のこととか説明していて、それなりにしっかりした内容かと思います。
デモを触って雰囲気で知る
続いて、実際のデモプログラムなどを見たり触ったりして雰囲気をつかめるサイトを紹介します。
遺伝的アルゴリズムで進化していく車
http://www.wreck.devisland.net/ga/
ここで紹介されてた→ http://sasapong.s41.xrea.com/diary/archives/003503.php
海外ネタですが、車がどんどん進化してでこぼこ道を走れるように進化していくデモです。
赤い車輪を地面に接触させないで進んでいけるようになることが目的のようです。
4つの車輪の大きさ，初期位置，8つのバネの長さとバネ定数，ダンピング係数といったパラメータを変えていくようです。
最初のうちは全くのダメダメくんですが、しばらく我慢してみていてると結構走れるようになってきます。やや面白いです。
Image evolution
http://alteredqualia.com/visualization/evolve/
http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/
ここで紹介されてた→ http://sasapong.s41.xrea.com/diary/archives/003503.php
こちらも海外ネタです。
ランダムにポリゴンを配置していって、徐々に進化を重ねて、モナリザの顔に近づいていきます。
実際にデモプログラムを動かすと長時間かかりますが、これはちょっとスゴイかも。。。
続いて３本、国内のデモアプリを紹介。大学の教材的なものもあるので、基本からちゃんと勉強したい人にはオススメです。
Web教材 Chapter.1 遺伝的アルゴリズム
http://carnation.is.konan-u.ac.jp/xoops/CJcontents/chapter01/chapter1.html
全体的に丁寧に解説された教材ですが、特にページの下部にある「GAシミュレータ」が、きれいでわかりやすい。パラメータを色々いじって何度か試してみてください。
http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/GA/GA.htm
静岡理工科大学 の研究室のサイトです。いかにも大学のサイトって感じですが、
ページの真ん中らへんにjava appletによるデモがあります。あまり面白くはありませんが、遺伝アルゴリズムの仕組みを実感的に理解するにはとてもよいデモかと思います。
遺伝的アルゴリズムを用いたTSPデモ
巡回セールスマン問題というやつです。
適当に配置された複数の点を、どういう順番で回ったら一番効率的に巡回できるか、というのを解く問題です。flashで実際に操作できるので一度やってみるとよくわかります。
実ビジネスでの利用事例
ちょっと嗜好を変えて、ネット広告での活用事例の紹介です。
ADエビスで有名なロックオンのサイトから。
Googleリスティング広告の広告文を題材に、どのクリエイティブが最も効果が高くなるかシミュレーション的にわかるエクセルファイルがダウンロードできます。エクセルで触れるってところが、なんとなくうれしいですね。
iogous
これもネット広告で実際に遺伝アルゴリズムを使っている実例になります。
最近話題の「クリエイティブ最適化」を商用化したサービスです。
自動的に生成した複数の広告バナーのうち、徐々にクリック率の高かったものが生き残っていき、最終的にはCTRが何倍にもなるよ、という仕組みです。興味深いシステムですね。
読み物の紹介
新型新幹線「N700系」の“顔”を生んだ「遺伝的アルゴリズム」の秘密【その１】
http://trendy.nikkeibp.co.jp/article/column/20070620/1001047/
新幹線のデザインにも遺伝アルゴリズムが使われたよ、というお話。
自分は鉄っちゃんではないので、ふーんとしか思いませんでしたが、その筋の人にはどうなんでしょう？垂涎ものなんでしょうか？ちなみにこのデザイン変更で東京〜新大阪間の所要時間を５分短縮したとか。へぇー。
最後におまけ。昔から人気のある有名サイトですね。
遺伝アルゴリズムのことだけなく、人工知能のこと全般をわかりやすく面白く紹介したコンテンツです。
全くの初学者の人でも安心してよめるわかりやすい記事なので、AIに興味はあるけど、どこから入ったらいいかわからない、という人に超オススメです。
以上、遺伝的アルゴリズムとそれに関係ありそうな面白サイトを紹介してみました。
表面を撫でただけの記事になってしまいましたが、まずは興味を持ってもらえればいいかなーと思ってます。
Permalink | コメント(0) | トラックバック(1) | 07:31 
2010-06-16
perlでテトリス！
偶然おもしろいモノを発見しました。コンソールで遊べるperlテトリスです。
スクリーンショットとってみました。
なんと、macbookのターミナル上でカラフルなテトリスが元気よく動いてます！
それにしても、俺テトリス下手だな。。。
ってのはおいといて、ソースを見てみましょう。難読化されてます。
#!/usr/bin/perl $_='A=15; B=30; select(stdin); $|=1; select(stdout);$|=1; system "stty -echo -icanon eol \001"; for C(split(/\s/,"010.010.010.010 77.77 022.020.020 330.030.030 440.044.000 055.550.000 666.060.". "000")){D=0;for E(split(/\./,C)){F=0;for G(split("",E)){C[P][F++ ][D]=G} D++}J[P]=F; I[P++] =D}%L=split(/ /,"m _".chr(72)." c 2". chr(74)." a _m");sub a{for K(split(/ /,shift)){(K,L)=split(/=/,K );K=L{K};K=~s/_/L/; printf "%c[K",27}}sub u{a("a=40");for D(0..B -1){for F(0..A-1){M=G[F][D];if(R[F][D]!=M) {R[F][D]=M;a("m"."=". (5+D).";".(F*2+5)); a("a=".(40+M).";" .(30+M));print " "x2}}}a( "m=0;0 a=37;40")}sub r{(N)=@_;while(N--) {Q=W;W=O=H;H=Q;for F( 0 ..Q-1){for D(0..O-1) {Q[F][D]=K[F][D]}}for F(0..O-1){for D(0..Q- 1){K[F][D]= Q[Q-D-1][F]}}}}sub l{for F(0..W-1){for D(0..H-1){(K[ F][D]&& ((G[X+F][Y+D])|| (X+F<0)||(X+F>=A)|| (Y+D>=B)))&& return 0}}1}sub p{for F(0..W-1){for D(0..H-1){(K[F][D]>0)&&(G[X+F][Y+D] =K[F][D]) }}1}sub o{for F(0..W-1){for D(0..H-1){(K[F][D]>0)&&(G[ X+F][ Y+D]=0)}}}sub n{C=int(rand(P)) ;W=J[C];H=I[C];X=int(A/2)-1 ;Y=0;for F(0..W-1){for D(0..H-1){K[F][D]= C[C][F][D]}}r(int(rand (4)));l&&p}sub c{d:for(D=B;D>=0;D--){for F(0..A-1){G[F][D]||next d}for(D2=D;D2>=0; D2--){for F(0..A-1){G[F][D2]= (D2>1)?G[F][D2-1 ]:0; }}u;}}a ("m=0;0 a=0;37;40 c");print "\n\n".4x" "." "x(A-4). "perltris\n".(" "x4)."--"xA."\n".((" "x3)."|"." "x(A*2)."|\n")xB .(" "x4). "--"xA."\n";n;for(;;) {u;R=chr(1); (S,T)=select(R,U,V, 0.01);if(S) {Z=getc;}else {if($e++>20){Z=" ";$e=0;}else{next;} } if(Z eq "k"){o;r(1);l||r(3);p}; if(Z eq "j"){o;X--;l||X++;p}; if (Z eq "l"){o;X++;l||X--;p};if(Z eq " "){o;Y++;(E=l)||Y--;p;E|| c |c|c|c|c|n||goto g;};if(Z eq "q"){last;}}g: a("a=0 m=".(B+8).";0 " ); system "stty sane"; '; s/([A-Z])/\$$1/g; s/\%\$/\%/g; eval;
きゃー 変態！
と叫びたくなりますね。
でもぐっとこらえて、こいつをコピペしてlinuxの上で走らせてみてください。
どうですか？テトリスできましたか！？
ちなみに操作はj,kで左右移動、lでアイテムを回転。それだけです。
ちょっと整形してみる
さて、この難読コード、ちょっと面白そうだから、分解＆整形してみます。
最後のevalの部分をprint $_に変更して実行結果をファイルに出力。それでもってperltidyで整形。
・・・なんと、整形してもなお十分に意味不明なコードでした。読み下すにはだいぶ根性が必要です。
$A = 15; $B = 30; select(stdin); $| = 1; select(stdout); $| = 1; system "stty -echo -icanon eol \001"; for $C ( split( /\s/, "010.010.010.010 77.77 022.020.020 330.030.030 440.044.000 055.550.000 666.060." . "000" ) ) { $D = 0; for $E ( split( /\./, $C ) ) { $F = 0; for $G ( split( "", $E ) ) { $C[$P][ $F++ ][$D] = $G; } $D++; } $J[$P] = $F; $I[ $P++ ] = $D; } %L = split( / /, "m _" . chr(72) . " c 2" . chr(74) . " a _m" ); sub a { for $K ( split( / /, shift ) ) { ( $K, $L ) = split( /=/, $K ); $K = $L{$K}; $K =~ s/_/$L/; printf "%c[$K", 27; } } sub u { a("a=40"); for $D ( 0 .. $B - 1 ) { for $F ( 0 .. $A - 1 ) { $M = $G[$F][$D]; if ( $R[$F][$D] != $M ) { $R[$F][$D] = $M; a( "m" . "=" . ( 5 + $D ) . ";" . ( $F * 2 + 5 ) ); a( "a=" . ( 40 + $M ) . ";" . ( 30 + $M ) ); print " " x 2; } } } a("m=0;0 a=37;40"); } sub r { ($N) = @_; while ( $N-- ) { $Q = $W; $W = $O = $H; $H = $Q; for $F ( 0 .. $Q - 1 ) { for $D ( 0 .. $O - 1 ) { $Q[$F][$D] = $K[$F][$D] } } for $F ( 0 .. $O - 1 ) { for $D ( 0 .. $Q - 1 ) { $K[$F][$D] = $Q[ $Q - $D - 1 ][$F] } } } } sub l { for $F ( 0 .. $W - 1 ) { for $D ( 0 .. $H - 1 ) { ( $K[$F][$D] && ( ( $G[ $X + $F ][ $Y + $D ] ) || ( $X + $F < 0 ) || ( $X + $F >= $A ) || ( $Y + $D >= $B ) ) ) && return 0; } } 1; } sub p { for $F ( 0 .. $W - 1 ) { for $D ( 0 .. $H - 1 ) { ( $K[$F][$D] > 0 ) && ( $G[ $X + $F ][ $Y + $D ] = $K[$F][$D] ); } } 1; } sub o { for $F ( 0 .. $W - 1 ) { for $D ( 0 .. $H - 1 ) { ( $K[$F][$D] > 0 ) && ( $G[ $X + $F ][ $Y + $D ] = 0 ); } } } sub n { $C = int( rand($P) ); $W = $J[$C]; $H = $I[$C]; $X = int( $A / 2 ) - 1; $Y = 0; for $F ( 0 .. $W - 1 ) { for $D ( 0 .. $H - 1 ) { $K[$F][$D] = $C[$C][$F][$D] } } r( int( rand(4) ) ); l && p; } sub c { d: for ( $D = $B; $D >= 0; $D-- ) { for $F ( 0 .. $A - 1 ) { $G[$F][$D] || next d; } for ( $D2 = $D; $D2 >= 0; $D2-- ) { for $F ( 0 .. $A - 1 ) { $G[$F][$D2] = ( $D2 > 1 ) ? $G[$F][ $D2 - 1 ] : 0; } } u; } } a("m=0;0 a=0;37;40 c"); print "\n\n" . 4 x " " . " " x ( $A - 4 ) . "perltris\n" . ( " " x 4 ) . "--" x $A . "\n" . ( ( " " x 3 ) . "|" . " " x ( $A * 2 ) . "|\n" ) x $B . ( " " x 4 ) . "--" x $A . "\n"; n; for ( ;; ) { u; $R = chr(1); ( $S, $T ) = select( $R, $U, $V, 0.01 ); if ($S) { $Z = getc; } else { if ( $e++ > 20 ) { $Z = " "; $e = 0; } else { next; } } if ( $Z eq "k" ) { o; r(1); l || r(3); p } if ( $Z eq "j" ) { o; $X--; l || $X++; p } if ( $Z eq "l" ) { o; $X++; l || $X--; p } if ( $Z eq " " ) { o; $Y++; ( $E = l ) || $Y--; p; $E || c | c | c | c | c | n || goto g; } if ( $Z eq "q" ) { last; } } g: a( "a=0 m=" . ( $B + 8 ) . ";0 " ); system "stty sane";
やばいです。血圧があがりそう。
全面的にグローバル変数まみれ。変数名も故意にわかりづらくしてあります。
また時折まったく意味のない関数や変数がトラップのようにちりばめれていて、まさに難読コードここにありって感じです。
しかし頑張って読んでみると、なんとも味わい深いテクニックが何カ所か発見できます。
注目すべきテクニック
なんともレガシー感あふれるコードですが、以下のポイントが気になりました。
- sttyでコンソールの挙動変更
- printf("\e[0;0H");やprintf("\e[0;37;40m"); でカーソル操作や色設定
- 座標の回転
- selectを使ったループ内でのスピード制御
いいですねぇ。古き良き日の「スクリプト」って感じがします。
時間がある時にでもじっくり追ってみたいコードです。
ちなみに元ソースはココ↓
http://www.colinfahey.com/tetris/tetris_ja.html
テトリスのなにか。なんだかよくわからん。日本語が激しくでたらめ。たぶんまともな日本人には読めません。
なにはともあれ、コンソールの上でテトリスで遊べるようになってヨカッタです。
さぁ、仕事してるフリして Let'sテトリス！
Permalink | コメント(2) | トラックバック(1) | 08:23 
