[Go For It] 暗号検索の高速化
Go For It の3問目。文章に隠された暗号を探すという問題。
例によってプログラムはGithubに上げておいたのでそちらを参照。
https://github.com/shogo82148/GoForIt/tree/master/q03
アルゴリズム自体は簡単で、スキップ数と位置の組み合わせを選んでキーワードと一致しているか試しているだけ。
Pythonでシンプルに書くとこんな感じ。
#!/usr/bin/env python # -*- coding:utf-8 -*- import sys def main(): word = sys.argv[1] rword = word[::-1] R = raw_input() for skip in xrange(1,len(R)/(len(word)-1)): for i in xrange(len(R)-skip*(len(word)-1)): t = R[i:i+len(word)*skip:skip] if t==word or t==rword: print '%s,%s' % (skip, i+1) if __name__=="__main__": main()
ただしこれを実行すると、ランダム文字列の長さをn、キーワードの長さをmとした時、だいたいn^2/2m 回くらいの文字列の比較が必要です。
この問題は n=30万, m=4 なので、約100億回。検索範囲を多少絞ったものの、さすがにこの比較回数だと時間がかかります。実際Pythonでやってみたら150分かかりました。
そこで、スキップ数と位置の組み合わせを全部試すのではなく、可能性のある組み合わせだけ試すことにします。
スキップ数と位置は、キーワード中の任意の2文字の位置がわかっていれば、一意に決まります。
例えば、長さ300文字のランダム文字列の中身を走査して、文字「s」と「o」が次の位置にあることがわかったとします。
- s (出現位置: 100, 120)
- o (出現位置: 150, 170, 300)
この時、「sony」というキーワードが出現する可能性があるのは、
- スキップ数50, 位置100(sが100文字目、oが150文字目)
- スキップ数70, 位置100(sが100文字目、oが170文字目)
- スキップ数200, 位置120(sが100文字目、oが300文字目)
- スキップ数30, 位置120(sが120文字目、oが150文字目)
- スキップ数50, 位置120(sが120文字目、oが170文字目)
- スキップ数180, 位置120(sが120文字目、oが300文字目)
の6通りのみです。
文字の種類がa〜zまでの26種類あるので、30万文字中、それぞれの文字は大体1万回程度現れると期待できます。
全部の組み合わせを試すと1万×1万=1億回。1/100になりました。
ここまでは簡単。もうちょっと頑張って工夫して見ました。
先ほどの例の続きを考えましょう。
列挙したスキップ数と位置の組み合わせはあくまで候補なので、元のランダム文字列を参照して答えであるかどうかを確かめます。
はじめの2文字はすでに存在することがわかっているので確かめなければならないのは次の文字です。
- スキップ数50, 位置100(200文字目がn?、250文字目がy?)
- スキップ数70, 位置100(240文字目がn?、310文字目がy?)
- スキップ数200, 位置120(500文字目がn?、700文字目がy?)
- スキップ数30, 位置120(180文字目がn?、210文字目がy?)
- スキップ数50, 位置120(230文字目がn?、280文字目がy?)
- スキップ数180, 位置120(480文字目がn?、560文字目がy?)
実際にランダム文字列を参照してこれを確かめれば良いのですが、元のランダム文字列は300文字しかありません。
301文字以降と比較しようとしている「(スキップ数70, 位置100), (スキップ数200, 位置120), (スキップ数180, 位置120)」は、ランダム文字列を参照するまでもなく、不正解だとわかります。
このような候補を除外するのは簡単ですが、除外するのにも時間はかかります。はじめから候補に含まない方法は無いでしょうか。
そこで、「キーワードのはじめの2文字の位置」ではなく「キーワードの先頭と末尾の位置」から候補を作ればいいのではと考えました。
先頭と末尾が範囲内にあれば、キーワードの途中での範囲外か否かのチェックは不要となります。
しかし、それだけでは候補の数は変わりませんね。もうひと工夫します。
「キーワードのはじめの2文字の位置」を使った場合、スキップ数は2つの文字の距離から簡単にわかりました。
「キーワードの先頭と末尾の位置」を使った場合は単に距離からは直接わからず、次のように計算する必要があります。
スキップ数=(末尾位置−先頭位置)÷(キーワードの長さ-1)
スキップ数は文字数なので整数であるはずです。そのためには、末尾位置と先頭位置は次の関係を満たす必要があります。
末尾位置−先頭位置=(キーワードの長さ-1)の倍数
これは「(キーワードの長さ-1)を法としたときの合同関係」ですね。
この条件を満たすのは「文字の位置 mod (キーワードの長さ-1)」が等しいもの同士なので、これを使ってグループ分けをしておき、グループ内のみで候補を作れば、余計な候補を作らずに済みます。
候補の数は1/グループの数になるので、今回の場合、候補数は1/3、およそ3000万まで減ります。はじめの1/300です。
定数部分は少なくなったけど、O(n^2)なのは変わらず。もっとオーダーが少ない方法があるのかもしれないけど、これで実装。Pythonで作ったら処理時間が結構長くなってしまったので、今回はC++で。Pythonで40秒かかってたのが、C++では4秒になりました。さすがC++。
追記:
C++には最適化オプションがあるのを忘れてました。-O3をつけたら0.6秒で終わりました。さすがC++。
[Go For It] 実数の階乗
前回に引き続き Go For It。二問目の問題にチャレンジ。
前回同様コードはGithubを参照。
https://github.com/shogo82148/GoForIt/tree/master/q02
Pythonのmathモジュールを使えばmath.gammaで一発ですが、この問題では使っちゃいけないみたいなので、
C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)
に載っているコードをPythonに書きなおして使いました。
「ある検索サイト」の答えとだいたい合っているようなのできっと大丈夫。
[Go For It]人生の時計
Sonyが主催するソフトウェアスペシャリストコンテスト Go For Itなるものが昨日から始まりましたね。
現実逃避をするためにとりあえず一問Pythonで解いてみましたよ。
https://github.com/shogo82148/GoForIt/tree/master/q01
日付の処理って結構面倒なので、僕が参加しているような競技プログラムではあんまり見かけませんね(ただ単に経験が浅いだけかもしれないけど)。
問題の意図するところはよくわかりませんが、面倒な日付計算はすべてライブラリにお任せして書いてみました。
単純に(現在時刻-誕生日)/(亡くなる時刻-誕生日)を求めるだけです。
計算自体はそう難しくはありませんが、2つほど注意するところがあります。
1つ目は死ぬ時刻。例えば2000年1月1日午前0時ちょうどに生まれて、80歳まで生きるとしましょう。
問題文には「n歳のときは生きていてn+1歳にはなれない」とあります。問題文では例が示されていませんが、僕は以下のように解釈しました。
2080年1月1日から2080年12月31日はちょうど80歳なので生きています。2081年1月1日になった瞬間、81歳になってしまうので亡くなることになります。
つまりこの場合、上の式の「亡くなる時刻」は2081年1月1日となります。
2つ目は閏年の存在。
今度は、2000年2月29日に生まれて、99歳まで生きるとしましょう。さて、亡くなるのはいつでしょう?
残念ながら2100年2月29日ではありません。2100年は閏年ではないので2月は28日で終わってしまいまい、2月29日は存在しないのです。閏日 - Wikipediaによると、2月29日生まれの人は2月28日が終わった時に年齢が変わるそうです。つまり、この答えは2100年3月1日午前0時ということになります。
問題の解釈とか、プログラムとか間違ってたら教えてください。
追記
閏年の判定は言語によっては不要で、JavaScriptとかだと2100年2月29日を指定してもエラーにはならず2100年3月1日として扱われるみたい。
Pythonだとダメだった。
CRFを用いたオンドゥル語の翻訳
いろんなものから逃げたくて、こんなことをしているshogoです。
JO_RI_botにオンドゥル語翻訳機能をつけてみました。
オンドゥル語については http://ja.wikipedia.org/wiki/%E3%82%AA%E3%83%B3%E3%83%89%E3%82%A5%E3%83%AB%E8%AA%9E とかを参照。
で、つけたはいいですが、少し微妙です。オリジナルのオンドゥル語よりも濁音がかなり多い気がします(オディジナドゥドオンドゥゥドゥゴヨディボダグオンガカナディオオイクガシバズ)。
この翻訳は前後関係を一切見ずに単純な置換のみで翻訳を行なっています。
しかし、まとめサイトにかかれたオンドゥル語を見る限り、毎回同じ音に濁音をつけているわけではなさそうです。
http://www.doumori.com/design/show.php?kiji_id=357442
同じ「タ」という音でも「ダ」と濁ったり、そのまま「タ」となっていることもあります。
このオリジナルのオンドゥル語に近づけるにはどうすればいいでしょう?
置換ルールを増やせばなんとかなりそうですが、ルールを考えるのはかなり大変そうです。
例えば「俺」という単語を見てみると「ゥレハ(俺は)」「オデノ(俺の)」「オレァ(俺は)」「オレノ(俺の)」と同じ「オレ」という音でも前後の関係によってかなり変化しています。
「俺」という一単語だけならまだしも、他の単語もいろいろ変化していそうです。
それを全部やるのは不可能でしょう。
ルールベースの翻訳には限界が見えてきました。じゃあ、どうしよう?
普通の自然言語の翻訳を参考にしてみましょう。一般的な翻訳も初期の頃はルールベースのものが研究されていました。
その方法でもある程度の性能は出せるのですが、すぐに限界が見えてきました。
そこで頭のいい人達が目をつけたのは人間がすでに翻訳した結果。これをコンピュータで分析することにより翻訳できないかと考えました。
僕たちもこれを試してみましょう。普通の翻訳タスクだと、構文解析(どれが主語でどれが述語かを判断)して、適切に並べ替えを行うという面倒なことをしなくてはいけません。しかし、オンドゥル語は日本語と語順が一致しているので、このことは考えなくてよさそうです。また、普通の翻訳に必要な意味解析も必要なく、必要なのは「読み方」だけですね。
次の文章は「ホントウニウラギッタンデスカ」という日本語が「オンドゥルルラギッタンディスカ」に翻訳される様子を表しています。
ホ/オ ン/ン ト/ド ウ/ゥ ニ/ル ウ/ル ラ/ラ ギ/ギ ッ/ッ タ/タ ン/ン デ/ディ ス/ス カ/カー !/!
これは
- はじめの「ホ」は「オ」と読む
- 次の「ン」は「ン」と読む
という事をあらわしています。
これをよく見ると、「ウ」を「ゥ」に変換する場合と、「ウ」を「ル」に変換する場合がありますね。実際にどちらへ変換するかというのは前後関係を見ながら決定する必要があります。
そのためのルールを決定するにはどうすればいいでしょう?
今回のような読みを考える問題は、一般的に「系列ラベリング問題」と呼ばれる問題の一種です。ここでは日本語の読みが「系列」、オンドゥル語の読みが「ラベル」ですね。両者の関係を見つけるのが「系列ラベリング問題」です。系列ラベリング問題の学習方法というのはいろいろ考えられていて、現在のところ条件付き確率場(CRF)が最も性能が高いと言われています。僕らもこれを使ってみましょう。
とは言ったものの、一からCRFの学習を実装するのは大変です。CRFを使って簡単に読みを推定する方法はないでしょうか。
普通の日本語だったら、読みを知るソフトにはいろいろあって、フリーのソフトだとMeCabというのが有名です。このMeCabは本来日本語の形態素解析(単語への分割)を行うソフトなのですが、その副産物として読みも取得できます。本来はそうやって使うものなのですが、MeCabはかなり汎用性が高く、簡単なテキスト変換ならMeCabだけでできてしまいます。製作者の方もいろいろ遊んでいます(ルー語変換してますね→http://chasen.org/~taku/blog/archives/2007/01/ )。
実は、このMeCab日本語文章の解析・学習にCRFを使っています。そして、なんとデータさえ用意してあげれば、自分で学習も出来ます。
日本語とオンドゥル語の読みの関係を与えてあげれば勝手にルールを作ってくれます。素晴らしいですね!(学習するためのデータを用意するのが一番大変だったりするのですがね)
思いついたらやりたくなってしまったので、やってみました。さっきの「ホントウニ(ry」の例のような日本語-オンドゥル語対訳リストを100組み分ほど作成し、学習させてみました。
作成したコーパスと辞書はgithubに上げてあります。(https://github.com/shogo82148/Ondulish-dict)
実際に翻訳してみると次のようになります。
「オリジナルのオンドゥル語よりも濁音がかなり多い気がします(オリイシガルノオンドゥルゴヨニコダヂオンガタダディオンガゲチマシ)」
単なる置換よりも変化のパターンが増えてました。これが正しいオンドゥル語なのかはよくわからないですが、予測のできない面白い結果を返してくれそうなので、これに置き換える方向で検討したいと思います。
今回は対訳リスト100でやりましたが、こういう統計を取る場合、1000とか10000用意するのが普通です。全然足らないですね・・・。誰か大量の対訳リストを持っている方がいれば、教えてください。
以下、オンドゥル語
ンドンドモノカラリレテクテ、コンドゴトヲチニshogoデス。
JO_RI_botディオンドゥルゴ-ナヤグゲナリヲスギタイマジカ。
オンドゥルゴニスレテハ http://ja.wikipedia.org/wiki/%E3%82%AA%E3%83%B3%E3%83%89%E3%82%A5%E3%83%AB%E8%AA%9Eタカンサンショー。
デ、スケテハイレテスガ、シイシヴィビョウディス。オニジラルノオンドゥルゴヨニコダヂオンガタダディオンゲガチマシ(オディジナドゥドオンドゥゥドゥゴヨディボダグオンガカナディオオイクガシバズ)。
コロ-ナヤクワデナゴガナギレヲイサイミズンドンデュンダディガナノミテホンヤクコロコガッタイワス。
ジャラヒ、マナヘィサレトニカラリカロンドゥルゴコイルガキリ、ナイタイオガシオドーンダヂオニヲスギニワギレンナサソウディス。
http://www.doumori.com/design/show.php?kiji_id=357442
オガチ「タ」トイェゥーソレモ「ダ」トニゴッタニ、ソノママ「タ」トダッニゴトモーニワス。
コノリシガルノオンドゥルゴンツカヅケルルンドースレバイレテシロ?
チタニウーウヲズヤシァーナンドガナニズルデスガ、ウーウコガナァイルノハカラリカレヘソウディス。
ダナイヴァ「オデ」トイーカニゴーミテイルト「ゥレハ(オレハ)」「オデノ(オレノ)」「オレァ(オレハ)」「オレノ(オレノ)」トオガチ「オデ」トイェゥーソレモデナゴノカンゲンディオッタカラリヘタチタイワス。
「オデ」トイーッチェダナゴラギガダバラヒモ、カノカニゴモンドンドヘタチタイソウディス。
オモレヲデンムヤルローズカローレシロ。
ウーウイースノホンヤクニンゲタイァイエタキマジカ。ジャー、ダージヨウ?
ズチュルノジデンゲゴノホンヤクンサニコロンショミマシロ。イッバンタキディオンヤクマシギノコドバルーウイースノモノガギナキリサレチマジカ。
ソノホーホーデモーウテイモノシンドーハラシルノデスガ、シグンゲタイァイエタキマジカ。
ソコレワテワナイレヒトタチュガメヲスギタノハルンゲガタレンホンヤクジャラギッタ。コレヲコニピューカテムナジキスルゴトニヨニホンヤクテキノガタカンガイッマジカ。
ボグテツモコレンタチタイマシロ。フチュルノホンヤクカタクダドゥー、コロヴニタイシキ(モレァシュゴレトレァデュツゴタヲレハンダナ)ショ、テキィスンダライァイヲオコガリナイゥメンダリナゴトヲジャラクテハイケマシン。シカジャ、オンドゥルゴンディオニゴトゴデュナァイツシニノデ、コノコドーハカンガンドグデヨサソウディス。マカ、ズチュルノホンヤクニイツヨウノミタイシキボイツヨウニャク、イツヨウナノハ「ヨミタカ」ダギレスネェ。
スギノムナショーハ「ホンドゥルルラギッタンデスカ」トイェゥルホンゴガ「オンドゥルルラギッタンディスカ」ディオンヤクサリヨウシンワエワシタイワス。
ホ/オ ニ/ン ソ/ドロ/ゥ ニ/ル ロ/ル ダ/ラ キ/ギッ/ッ カ/タ ニ/ン デ/ディ ス/ス カ/カー!/!
コレン
- ハチメノ「ホ」ハ「オ」トヨノ
- シノ「ン」ハ「ン」トヨノ
ナイーコドーンワエワシタイワス。
コレヲヨグミウソ、「ウ」ヲ「ゥ」ニヘタニスルァーアンド、「ウ」ヲ「ル」ニヘタニスルァーアイラーニワスネェ。ジッサインダチェダベヘタニスルガナイルノワデナゴガナギレヲミドガラギッチスルヒツヨウラーニワス。
ソノカベノウーウヲケッチスルルンドースレバイレテシロ?
コニカレノヨウディオミヲガナガイッウモンダレハ、イバンタキニ「ケイレツダイニニグモンダイ」トヨバルルモンダンナイツシュレス。ココレンディオニゴノヨイァ「ケイレツ」、オンドゥルゴノヨイァ「ラベル」デスネェ。リョーシャノガナギレヲミスケルノガ「ケイレツダイニニグモンダイ」デス。ケイレツダイニニグモンダンドガヂシュルホーホルトイルノハンドンドガナァイエレチタ、ゲゲンナトコロジョウゲッキタクニツトォ(CRF)ガマッチョマシンナリガタカレトイワレテイワス。ボクロモコレヲスカッタイマシロ。
ナハイッテモノーン、イツカラCRFドガヂシュルヲジッドースルノハタイヘディス。CRFヲスカッテクンドンディオミヲスレチスルホーホーハアイレショーカ。
ズチュルナニホンゴダッタラ、オミヲジウソヴトニハンドンドアッデ、ズニウノゾヴトダドゥーMeCabトイルノガイッペベルデス。コロMeCabハオンラーンディオニゴノゲンドンドガイシキ(カニゴベノムンタス)コロコガーソヴソガノデスガ、ソノズクサンブツトシタヨイモシュソクテキワス。ホンダレンドゥヤッデスカロモノガノデスガ、MeCabハラナニンナヨウシンガタタク、カンドンガタキシタヘクンダダMeCabラギレテキチマイワス。センサクシーナホウモンドンドーズンデンワス(ウーイゴヘクンショマシネェ→http://chasen.org/~taku/blog/archives/2007/01/)。
シツハ、コロMeCabディオニゴヴニシロノカイシキ・ァクシュルンCRFヲスカッタイワス。ソショ、ナンドゥーデーカサイヨーッシテワゲレァー、シムナレァクシュウモテキワス。
ディオニゴトオンドゥルゴノヨミノガナギレンワタイテワゲレァーカッテルルーウヲスクテクレワス。スバラシーデスネェ!(ァクシュースルタノデーカヲヨーッスルノガイツアンドンヘダッタニスルノデスガニャ)
オモレスンカラヤリテクガッチマッタノデ、ヤッタイマジカ。サッキロ「ホンドゥル(ry」ノデンドヨウダディオニゴ-オンドゥルゴタイヤクニストヲ100ヂミムナオモサクシイシ、ァクシュルサシタイマジカ。
サクシイシタイーイバストシショッハgithubニワレテワニワス。(https://github.com/shogo82148/Ondulish-dict)
ジッサイディオンヤクシタイルトスギノヨウンナニワス。
「オニジラルノオンドゥルゴヨニコダヂオンガタダディオンゲガチマシ(オリイシガルノオンドゥルゴヨニコダヂオンガタダディオンガゲチマシ)」
カンドウツカニヨニコヘガドバラーニァズンタマジカ。コレァカラシオンドゥルゴナノカァヨクワガダナイレスガ、ヨソクロレギナイオモシロイケッタヲガンショグデソウナノデ、コレンオキタイッルホウコロレゲタージカレトオモレワス。
コニカレハタイヤクニスソ100レヤニナジカガ、イーッリナリギレヲチョウヴァアイ、1000タカ10000ヨーッスルノガヴチュルデス。ゼニズェンカラナイレスネェ…。ダレタカレニョウノカイヤクニストヲモッニホウァイレァー、オシイテクラサイ。
便利機能
学食メニューツイート機能
学食のメニューを聞くと、技大の第一食堂のメニューを教えてくれます。
@shogo82148 / @JO_RI_bot 学食のA定食教えて
@JO_RI_bot / @shogo82148 2012/01/24の夕食のA定食...
お薦めを聞くとランダムにメニューを返してくれます。
@shogo82148 / @JO_RI_bot 学食の今日のお薦めメニューは?
@JO_RI_bot / @shogo82148 2012/01/24の夕食のおすす...
この機能で使っているデータは手動で入力してます。誰か手伝って><
https://docs.google.com/spreadsheet/ccc?key=0AmjmnXFuHdP0dDh0UHE4LU5EYXZtMzBZNUtOZnRnWmc