Pythonでダイクストラアルゴリズムを実装した

しばらく忙しくて，更新が途絶えてしまいました．
少なくとも今年度中は，2週間に1回更新を続けていきたいです．

本題．

競技プログラミングで，ダイクストラアルゴリズムを実装する機会があったので，ソースコードを載せておきます．

ダイクストラアルゴリズムとは？

ダイクストラアルゴリズム(ダイクストラ法)とは，重み付きグラフの探索アルゴリズムの一種で，すべての辺の重みが非負なグラフの単一始点最短経路問題を解くためのアルゴリズムです．
グラフの始点が与えられた時，そこから他の(すべての)頂点までの最短経路と，そこまでの重みの和(最短距離)を求めることができます．

ダイクストラ法 - Wikipedia

ナイーブなダイクストラアルゴリズムはO(|V|^2)ですが，プライオリティキュー(優先度付きキュー)と呼ばれるデータ構造を用いることで，O(|E|log|V|)程度で最短経路を求められます．

優先度つきキュー - Wikipedia

Pythonでプライオリティキューを実装する際には，heapqというモジュールを用いるのが一番良さそうです．
8.4. heapq — ヒープキューアルゴリズム — Python 2.7ja1 documentation
以下，使い方．

>>> import heapq
>>> q = [] # プライオリティキュー
>>> heapq.heappush(q, 1) # 1をpush
>>> q
[1]
>>> heapq.heappush(q, 2) # 2をpush
>>> q
[1, 2] # 1より2の方が優先度が低いので先頭以外に追加される
>>> heapq.heappush(q, 0) # 0をpush
>>> q
[0, 2, 1] # 0の優先度が最も高いので先頭に追加される
>>> heapq.heappop(q)
0
>>> q
[1, 2]

常に，先頭に最小(優先度最高)の要素が来るようになっています(それ以外の順序は保証されません)．
ヒープを用いてインデックスを管理しているため，要素の追加，削除などの操作をO(log n)で行えるのが特徴です．

また，下記のように，Pythonでは，タプルを比較する時に，最初の要素から順に比較して大小を判定するらしいです．
今回は，プライオリティキューの優先度の計算にその性質を使っています．

>>> (1, 1) < (1, 2)
True
>>> (1, 1) < (0, 2)
False
>>> import heapq
>>> q = []
>>> heapq.heappush(q, (1, 1)) # (1, 1)をpush
>>> q
[(1, 1)]
>>> heapq.heappush(q, (0, 2)) # (0, 2)をpush
[(0, 2), (1, 1)] # (0, 2)の優先度が最も高いので先頭に追加される

実装

gistcca597c45148c5e55c3f

競技プログラミング用のライブラリにしたいということもあり，無駄な処理はなるべく省くようにしたつもりです．

また，これは，グラフの表現方法として隣接行列を用いた時の解法です．
隣接リストを用いると，少しコードが変わると思います．

参考

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

CODE THANKS FESTIVAL A日程に参加してきました

12/7(日)に東京で行われた，リクルートホールディングス社主催のプログラミングコンテストであるCODE THANKS FESTIVALのA日程に参加してきました．

この大会は，先日行われた別のプロコンであるCODE FESTIVALの予選を通過できなかった人に向けて，より多くの人に大会に参加してもらいたいというリクルート社側のご厚意により開催されたものでした*1．
自分は予選で，あと一歩の所で本戦参加を逃してしまったので，大会参加できることは純粋に嬉しかったです．

何してたかだけまとめときたいと思います．

コンテスト前

5時半起きで当日入り．
寒さが厳しかった．

受付を済ませた後に即昼食が出た．
叙々苑の焼肉弁当だった(めっちゃうまかった)．

昼食を食べながら，隣の人と話す．
年齢層的に大学1，2回生が多そうで，若干場違い感．

WebDB Forumの昼食会でお会いしたリクルートの人事の方に(2週間ぶりに)再会する．
「前回は服装ちゃんとしてたのに…」って言われた(笑)

ルール説明にchokudaiさんが登場．
初めてお会いしたけど，わりとイメージ通りの人で安心した(？)

コンテストとsubmitした解答

問題はすべてPythonで解いた．

事前に聞いていたように，いつもの大会よりは難易度易しめだったと思う*2．

A問題

与えられた入力値a，bに対して，4 * a + 2 * bを返す．

First Accept狙ったけど，同時開催されてたオープンコンテストの方にsubmitしてしまった*3．

B問題

A，B，Cを生産量の降順にソートし，順番に使っていくと最小の時間で処理が終了する．

C問題

S_iの値に応じて，P_iの値を足していく．
インデックスが微妙にズレてるのだけが注意点．

D問題

区間[s, t]と[a, b]の差を求めて100をかける．
場合分けしてしまったが，後で解説を聞いて，区間の共通部分はmax(0, min(t, b) - max(s, a))で求められることを知って悶えた．

この辺から手が止まり出す．

E問題

最初，問題の意味が解読できなかったので，先にF問題を解いて戻ってきた．

少し考えなおして，N回試行した後に各々の手順の分戻せばよいと気づくが，それでもO(RCN)=O(50*50*5000)となり，「Pythonだとギリギリだなー，もっと良い解法ないかなー」と20分ぐらい悩む．
でも特に思いつかなかったのでsubmitしてみると通った．

F問題

与えられた情報から，確定している順位の最上位を求めるとよい．
DFSを使っても良いが，N<=50なので，情報を何度もなめて，参加者1より上位の参加者を新たに追加できなくなるまで追加し続ける手法でもO(N^2)で十分間に合う．

ここまではすべて一発Accept．

G問題

手が出なかった．
少なくともブルートフォースのシミュレートで部分点ぐらいは取りたかったが，意外に場合分けが面倒だった．

想定解は，DPで，「何番目の人を見ているか」，「すでに着席している中で，最も番号の大きい人から番号の小さい側にいくつ空席があるか」，「すでに着席している中で，最も番号の大きい人の座標」を保存する手法らしい．
これは後で復習したい．

H問題

見た感じ，自分には手に負えない問題だと感じた*4．

Hに取り掛かった時点で残り1時間ぐらいだった．
順位表を見てみると，13位ぐらいだったので，部分点を通すだけでも入賞できそうだと思い，そこに注力した．

書いたコードがこれ↓
O(R^3C^3)という糞コード． 5分ぐらいジャッジ結果が返ってこなくて焦ったが，無事15点は取れた．

想定解は，中心の座標を決定し，そこから生地の左端までの長方形を考え，点対称となるかどうかを見ていくらしい(？)*5．

結果

615点で9位入賞．
正直，こんなので入賞してしまって申し訳ない感じはあるが，嬉しかった*6．

オープンコンテストの方で見ても45位ぐらいだったので，自分にしては上出来だったのでは．

懇親会

立食形式での懇親会だった*7．

DDRや太鼓の達人が置いてあった．
chokudaiさんめっちゃ頑張ってた．

個人的には書道コーディングが面白かった．
これは，普段コンピュータで行うコーディングを，筆で行うというもの．
結構いろんなネタがあった*8．

自分が書いたのがこれ↓

上でも書いたように，大学の学部生が多かったように思う．
般教の話とか久しぶりにした．

また，今回たまたまなのかもしれないが，女子率も結構高かった．
「プロコン」というと，どうしても男所帯のイメージがあるが，裾野を見るとそうでもないのかなと思った．

食事も豪華で，自分は寿司ばかり食べていた．

---

自分にとってはたぶん，学生生活最後のオンサイトのプログラミングコンテストになるかと思います*9．

本戦出場できなかった時は悔しかったですが，そこそこの結果を残せてよかったのではないかと思います．

そろそろ修論に取り掛かるべき時期が来てしまいました．
何とか修了できるように頑張ります．

*1:ありがたいと思う反面，少し複雑な感じ…

*2:ABCぐらい？

*3:普通に最速じゃなかった

*4:それを知ることができただけでも成長できている感じはあるけど

*5:解説を聞いたがあまり良くわからなかった…

*6:賞品は焼肉会食らしい

*7:未成年者も多いということでアルコールはなし

*8:エディタ戦争ネタはどこでも出てくるな…

*9:最後もクソも2回目だけど

WebDB Forum 2014で発表してきた

夏に執筆した論文が採択されたので，東京で学会に参加してきました．

11/19，20に行われた，WebDB Forum 2014という国内向けの学会でした．

Web系，DB系の研究発表が中心の学会で，採録率は6割程度だそうです．
個人的に，修士の間にもう1度ぐらい査読付き論文を通しておきたかったので，採択されてよかったです．

Web系，DB系の学会だと，日本のものでは，DEIMと呼ばれる研究会が有名です．

トップページ - DEIM2014

こちらの学会には論文の査読がないのと，3日間ほど泊まりがけで参加するのですが，どちらかと言うと飲み会交流会のような側面が強く，「研究発表の場」としてはWebDBの方が圧倒的に上だと感じました*1．

また，Web系企業を中心とした企業のエンジニアも多数来られ，技術についての発表も聞くことができました．
来年からエンジニアとして就職する身としては，こちらもぜひ聞いておきたかったので有意義でした*2．

以下，軽くメモ(研究内容のメモというよりは，自分用の日記として)．

1日目

朝にオープニングがあり，講演，論文発表と続いた．
講演での「研究者も自分の実装をもっと公に晒すべき」という意見には非常に共感した．

企業ブースの常設展示があったので見た． HOME'sなどが有名なネクスト社のデモが面白かった．
クライアントに注文住宅のイメージを持ってもらうために，レゴブロックを置くと，ブロックに対応する場所に壁やドアなどのオブジェクトが配置され，パソコンの画面に3Dモデルとして表示されるというシステムだった．

夕飯とともにポスター発表のセッションが行われ，寿司を頬張りながら研究の話を聞いていた．
内定先の企業や，選考を受けた企業の方とも(短い時間だったけど)お話した*3．
個人的には，多腕バンディットアルゴリズムによる広告の効果検証の話が面白かった．
他の講演などで何度か聞いても論点をつかめなかったのだが，被験者を等分割するA/Bテストに対して，KPIの高いインタフェースに被験者を割いて検証効率を高めるというのがこのアルゴリズムのキモらしい．
やっと初歩を理解できたような気がする．

2日目

午前中に自分の発表があった．
ディスプレイの接続の調子が悪くてスライドが映らない，映ったと思ったら今度はマイクの使い方がわからない…など，終始gdgdな発表だったが，何とか終えることができた．
自分の研究は問題山積みであることに気付かされた．

お昼に大学院の先輩にお会いした．
就職先の企業を代表しての参加らしい．
仲の良い方だったので，久しぶりに話ができて楽しかった．

最後の講演では，身体データのセンシングについての話を聞いた．
センサをつけている人が今何をしているかを検出するシステムのデモが面白かった． 例えば，「プレゼンしている」，「歯を磨いている」など，結構細かい粒度の行動検出ができるようになっているらしい．

自分の論文は受賞を逃してしまったが，数多くの良質な研究発表を聞けて刺激になった*4．

---

今年うちの大学から出していたのは自分たちだけだったらしく，若干肩身の狭い思いをしました．

国際学会は発表がすべて英語なので，どうしても細かい所が聞けなかったりしますが，国内の学会ではそういったことがないので，ちゃんと研究内容を聞くのに集中できた気がします(ダメ学生並の感想)．

WebDBに参加するにあたって，

修士1年の皆さんがWebDB Forum 2014に投稿するべき7つの理由, , , , , , , - 豊田正史のSLとは関係ございません(2014-06-23)

こちらの記事を読ませていただきました．
意識の低い修士2年の学生には耳の痛い話でしたが，M1の間に投稿論文を1本まとめることができれば，修論ももう少し楽だったのかなという気がします*5．

11月は心ぴょんぴょんな日々が続いて，進捗に問題をきたしています．
きっと12月から本気が出るのでしょう…

*1:もちろん，国際学会の方がよりよいのは自明

*2:どちらかと言うとコネ作りの方が目的だったことはナイショ．参加者も少ないしね

*3:内定先の同期やツイッター関係の人もいたらしいけど，会えなかった

*4:てか今回の参加者はみんなプレゼンもうまかったと思う．正直，自分には全く勝てる要素がなかった

*5:いまさら取り返しの付かない反省です

Pythonで単方向連結リストを実装した

特に更新するようなこともないので，前に書いたコードを晒しておきます．

Pythonで単方向連結リストを実装しました．

といっても，連結リストは挿入，削除，要素の取得ぐらいができれば任意の処理が可能なので，どちらかと言うとPythonicなコードを心がけました．

gistaf03c4e31fc763cffec4

特に，特殊メソッドについては，今まで適当に使っていた部分が多かったので勉強になりました．

また，このコードでは，doctestというモジュールを使っています．

doctestでは，コメントにREPLっぽくコードを書き，プログラム*1を実行すると，その部分がテストとして実行され，期待される出力と比較されるようになっています．
このコードは正しい(はず)なので実行しても何も起こりませんが，期待されない出力がなされた場合にはアラートが表示されます．

あと，全然関係ないですが，最近，オライリーの「入門自然言語処理」を読み始めています．

入門 自然言語処理

まだ2章までしか読めていませんが，nltkを用いてのテキスト分類，機械学習の具体的な手法について記載されているようです．
Pythonの解説もそこそこ丁寧なので，思い出しながら読んでいけるような気がします．

*1:ここだとSinglyLinkedList.py

「オブジェクト指向JavaScript」を読んだ

現在，研究用のプログラムでフロントエンドにJavaScriptを扱っています．

JavaScript自体(jQuery含む)は何度か書いたことがあるのですが，正直，「動けばいい」ぐらいの気持ちで書いたものばかりで，しっかりと設計をしたことはありませんでした．

実際，JavaScriptについて書かれた本は数多くありますが，Webデザイナ向けの平易な本がほとんどで，JSの言語仕様やベストプラクティスなどに踏み込んだ本はそう多くないような気がします．
この機会に一度勉強しておこうと思っていたところで，図書館に下記の本があったので，これを読むことにしました．

オブジェクト指向JavaScript

簡単なメモ

1章

「イントロダクション」として，JSとオブジェクト指向についての説明が記載されている．

2章

JSのデータ構造，制御構造について書かれている．

多くは他の言語にもある仕様で，すでに知っていたが，"=="と"==="の違いや，"undefined"の扱い，変数宣言時に"var"をつける/つけないによって変数がローカル/グローバルになる，など，JS独特の言語仕様に驚くところも多々あった．

3章

関数についての内容．

「JSの関数はオブジェクトである」というところから，無名関数，自己実行可能関数，クロージャなど，「Webページを読んでいると見かけるけどよくわからない」ようなJSの文法についての説明があった．
「JSではスコープが関数単位で設定されている」というのが個人的には驚きだった*1．
クロージャについては，一度読んだだけでは必要性を感じることが出来なかったので，もう一度勉強し直そうと思う．

4章

実際にJSでオブジェクトを生成するにはどうすればいいかについての記載．

JSではプロパティにアクセスすることでオブジェクト固有の値やメソッドにアクセスできるといった話や，コンストラクタ関数とnewキーワードによってユーザ定義のオブジェクトを生成することができるといった話があった．

「JSはプロトタイプベースのオブジェクト指向言語」ということは知識として知っていたが，実際に言語仕様を見てみると，クラスベースの言語との違いに戸惑った．

5章

プロトタイプについての話．

JSの関数オブジェクトには，オブジェクト自身のプロパティとは別に，「prototype」と呼ばれるプロパティを持っており，オブジェクトからこの値をたどることができる．
プロトタイプはコンストラクタ関数を用いて新たなオブジェクトを生成した時にも用いることができる．
などといったことが書いてあった．

この辺からは難しくてなかなか読み進めることが出来なかった．

6章

継承についての話．

JSでは，プロトタイプチェーンと呼ばれる，オブジェクトのプロトタイプ間に定義されるリンク構造を用いて，子オブジェクトのプロトタイプを親オブジェクトのコンストラクタ関数から生成されるオブジェクトに置き換えることで継承を実装する．
子オブジェクトのあるプロパティを呼ぶと，処理系は，まず子オブジェクト自身のプロパティを探し，なければプロトタイプチェーンをたどって親オブジェクトのプロパティを探す，という動きになる．

最後のケーススタディはわりとわかりやすかった．

7章

実際にJSをブラウザで使う際の注意点についての記述．

この辺は何度か開発をしたことがあるので知っていることも多かった*2．

8章

JS固有のコーディングテクニックと，デザインパターンの実装についての話．

グローバル変数の数を減らすために，大きなオブジェクトを作ってその中に名前空間を定義するという手法は面白かった．
実際に飲み込むまでには時間がかかりそう．

---

全体的に，コード例が充実しており，実際に試すまでもなくわかるような作りになっていました．
「オブジェクト指向」と題してあるので，もう少しオブジェクト指向を用いてどのような実装をすればいいのかの例について記載されているとよかったのかなと思います．

*1:これが諸悪の根源な気がする

*2:日本語版は2012年発行だったので，わりと新しい本なのかと思っていたが，この辺の記述を読む当たり，原著は若干古い本かもしれないと思った

ネットワークスペシャリスト試験を受けてきた

10/19に行われた情報処理技術者試験の1つ，ネットワークスペシャリスト試験(NW試験)を受験してきました．

記憶があるうちに，試験前に何をやってたかと，当日の感想をまとめておきたいと思います．

2014年8月上旬

春のデータベーススペシャリスト試験(DB試験)に合格した時に，秋はNW試験を受けると決めていた．
申し込み開始したのを見つけた時点でさっさと申し込む．

この時点ではそのまま放置．

8月下旬～9月上旬

DB試験の時に，短時間で詰め込むつらさを痛いほど学んだので，今回は書いていた論文の投稿が終了した時点ですぐに取り掛かるようにした．
この時点で残り1ヶ月と2週間程度．

情報処理技術者試験自体は5回目の受験になるので，さすがにどんな感じはつかめている(と思う)が，ネットワークについてマジメに勉強したことはなかった．
DBとは違って専門外であり，大学院生の自分には実務知識もないので，最初に教本を読んで知識の詰め込みを行い，そこから広げていくという，いつものスタイルを踏襲した．

とりあえず買った本を晒しておく．

平成26年度 ネットワークスペシャリスト 合格教本 (情報処理技術者試験)

この時はまだ，ヒマがある時にパラパラとめくる程度だった．
情報セキュリティスペシャリスト試験(SC試験)で触れた内容もあったが，それでもわりと覚えることが多いなと感じた(特にレイヤ2以下の知識)．

今までの経験から，早いうちに過去問を何問か解いて，合格点との間にどの程度の乖離があるかを測っておくと，勉強のモチベーションになっていいと考え，実際にやってみた．

感想としては，「知らないことが多くて答えようがない」．
パケットの動きやルーティングなど，具体的なイメージを持てないと解けないと感じた．

SC試験のように頭をひねれば解ける問題が多いわけでもなく，DB分野ほど自分の知識があるわけでもない．
この時点で「少し厳しいかも」と思うようになった．

もちろん，わからなかった問題については解説を読むようにし，ついでにその辺の知識を補うようにした．

解説目当てで買った問題集*1．

平成26年度 ネットワークスペシャリスト パーフェクトラーニング過去問題集 (情報処理技術者試験)

9月下旬

修士論文の中間試問対策で少し勉強から遠ざかっていた．

復帰した後は，問題演習を繰り返しつつ，知識を拾っていった．

特に，研究室にあったので読んだマスタリングTCP/IP入門編は本当にいい本だった．

マスタリングTCP/IP 入門編 第5版

OSI参照モデルがなぜこのようになったのか，各層において実際にどのようにパケットを処理しているかなど，明確に理由を示して(必要ならばそうなるに至った歴史も含めて)書くように心がけられているので，説明が腑に落ちるし，問題を解く際にもイメージが持ちやすい*2．

読み終わる頃には，TCP/IPについての問題なら午後1合格点レベルぐらいに到達すると思う．

10月上旬

この時点で試験2週間前．
だいぶ余裕がなくなってきた*3．

この頃には過去問4年分に(問題選択含めて)1回触れることができた．

ここまでやってみての感想として，

• PCやスイッチ，サーバがネットワーク構成図に現れ，パケットの流れを追っていくタイプの問題は解答しやすい．

  • この手の問題では，LB，STP，VLANなどの技術は頻出で，これらに加えて，VRRPなど比較的新しい技術が用いられる．

• 逆に，スイッチの物理配線やIP電話など，IP以外の知識が必要となるタイプの問題は解答しにくい．

といった感じ．

過去問ではIP電話についての出題も多かったが，たぶん午後2では解かずに済むんじゃないかなという希望的観測のもと，今回は上のタイプの問題に集中することにした．

ネット上でわりと評判の良かったネスペの剣25を買う．

ネスぺの剣25 ~ネットワークスペシャリストの最も詳しい過去問解説 (情報処理技術者試験)

この本は，2013年(去年)の過去問のみの解説書となっているが，設問に関係する部分以外についても，「出題者はなぜここでこの記述をしたのか」について細かな説明が施されており，過去問を骨の髄まで吸い尽くしている．
また，設問部分については，「なぜその解答になるのか」だけでなく，「なぜその解答以外の解答にならないのか」についてまで記載されており，理解の深まる構成になっている．

たった1年分の過去問解説に2500円出すのはちょっと…と思って敬遠していたが，結果的には「もっと早く買っておけばよかった」と思う参考書だった．

10月中旬

試験まで1週間を切った．
ここからは研究室の用事はほぼすべてほっぽりかして勉強していた．

基本的には午後試験を1日1問，午後1→午後2→午後1→…の順でローテしていく．

NW試験に限らず，情報処理技術者試験の午後問題は，設問箇所以外にも，問題文の所々に設問のための布石を打つ書き方になっているので，1度問題を解いて解説を見た後にもう1度問題文を読むと，全体構成を理解できるようになり，見えなかった部分が見えてくるようになっている*4．
したがって，1度解いた問題についても，しばらく経ってから解き直すようにした．

当日

朝起きたら若干喉が痛かったが，熱はなさそうだったので会場に向かう．

午前1

免除．

午前2

過去問覚えゲー．
5年分しっかり覚えれば6割は固い．

午後1

ここからが本番．

問3がセキュリティの話で，穴埋め問題ができそうだったので取ることにした．
問1はOSPFの話が面倒そうだったので却下．
結果として問3,問2を取ることに．

問3:
DNSキャッシュポイズニングやセキュリティインシデントに対する対策など，完全にSC試験の問題だった．
勉強したのが1年前なので記憶が飛んでいるところもあったが，そこそこ埋められたように思う．

問2:
障害対応についての問題．
こちらも手順さえわかれば何とかなったように思う．
でも設問3はよくわからなかった．

解答速報などは見ていないが，手応え的には6割弱ぐらい．

午後2

最初にパラパラ見て，VoIP-GW，IP-PBXという文字を見た時点で問2を読むのをやめた．
それに対して，問1はなんかいけそうなので取った．

問1:
SPFも出てきて，いよいよSC試験になってきた*5．
と言っても，SPFについてそこまで勉強したわけでもないので，問題文の誘導にしたがって解いたつもり．
パケットフィルタリングのルール設定はNWっぽいかなという感じだったが，SSL，ログ取得のメリットなどの問題を解いていると，完全に自分が1年前に戻ったような錯覚を受けた．

6割は取れる解答を書けたと思う．
でも，Twitterとか2chとか見てる限りあまり難しかったという話を聞かないし，採点厳しくなりそう．

全体的に

院生生活の1/6(1ヶ月*4回(AP，SC，DB，NW)/24ヶ月)を費やした私の情報処理技術者試験が終わった．

最初は，「情報系の学部出るけど情報のこと何も知らないな…」という危機感から受験した試験だったけど，個人的に少しは成長できたのではないかと思う．

情報処理技術者試験では，OSやベンダ依存の知識は全く扱わないので，こんなものは役に立たないという意見もあるが，基本的な仕組みと，それを応用するための方法を学べば，後はツールの使い方を知るだけで，そこまで学習コストの大きいものではないのではないかと思う*6．

また，「高難度の資格試験合格」という，そこそこ高い目標を持って勉強することで，ただ漫然と本を読むより格段に効率のいい学習ができると感じた．
あと，これは実務的にいいのかわからないが，試験日までの短期間に集中して勉強することも，効率面では重要だと思う*7．

知識だけあっても，使わなければただの持ち腐れになる．
試験を足がかりにして，最終的には実際の機器も触れるようになりたい．

最後に，これが合格体験記になればいいな，と．

続き

lethe2211.hatenablog.com

*1:問題も解答もWeb上に上がっているんだから，もう少し解説に力を入れてもいいんじゃないかな…

*2:断片的な知識であればWebページに書かれているものでも十分だと思う時があるが，体系的に情報を表現できることに関しては本に勝るものはないと感じた

*3:書いた論文は無事採択されたが，カメラレディに向けての修正にはほとんど時間をかけられなかった

*4:「あ，ここの1文ちょっと不自然だったけど，この設問のためだったのか」みたいな

*5:試験教室を間違えたのかと思って問題用紙の表紙を確認したレベル

*6:もちろん，ベンダ依存の仕組みがあるならそれは勉強しないといけないけど

*7:個人的には，これに加えて，受験料やら参考書やらに金をかけることで後戻りできなくすると，より勉強のモチベーション(プレッシャー？)になっていいと思う

Microsoft Academic APIを利用してみた

Microsoft Academic APIは，Microsoftの文献検索用の検索エンジンであるMicrosoft Academic Searchのデータを外部プログラムから利用するための，いわゆるWeb APIです．

以前は登録制で，使用目的などをメールでMS社に伝えると，IDが送られる形式だったそうですが，現在はMicrosoft Azure Marketplace上でWebサービスとして提供されているようです．*1

このAPIについてはあまり情報が多くないため，できることについてまとめておこうと思います．

Microsoft Academic APIでできること

とりあえず
https://api.datamarket.azure.com/MRC/MicrosoftAcademic/v2/Paper?$filter=ID%20eq%20224857
このURLを実行してみるとよい．

これは，Paperというスキーマから，idが224857となる論文の情報を取り出すリクエストである．

こんな感じで，文献，著者，論文誌，引用についての情報をMASのデータベース(RDB)から抽出できる．

一応，リファレンスは存在して，詳細については
MicrosoftAcademicSchemaRef.docx - Microsoft Word Online
に記載されている．
しかし，Paper_Refのスキーマ情報がなかったり，完全なものではない様子．

APIを試してみる

最も手っ取り早くこのAPIを試してみる方法として，Webインタフェースを用いる方法がある．
Microsoft Academic APIは，Webインタフェースを持っており，クエリに対する結果をテーブルの形で確認することができる．

今回は，わかりやすさのため，この方法を紹介することとする．
※外部プログラムからAPIを利用するだけなら，(適切なクエリがわかっていれば)以下の手順は必要なく，上のようなリクエストを送信するだけでよいことに注意．

• Microsoft Azure Marketplaceへサインインする．

Microsoftアカウントがあれば，そのアカウントでログインできる．
ない人は取得を．

• 「marketplaceの検索」と書かれた検索ボックスに，"Microsoft Academic"と入力し，「Microsoft Academic」データセットを検索する．

• 「サインアップ」をクリックして次の画面に移動し，利用規約を読んだ上で，「サインアップ」をクリックする．

• 「マイアカウント」 -> 「マイデータ」 -> 「Microsoft Academic」から，「使用」をクリックする．

• 下のような画面が表示されたらOK．

この画面では，GUIのインタフェースで，文献情報の検索結果と，同じ検索を行いたい時のクエリとなるリクエストURLを表示している．
例えば，文献引用数が200以上の論文誌を検索したい場合には，「PaperJournalCount」スキーマのタブをクリックし，「paperCount」カラムにフィルターをかければよい．

このページ上部に表示されているURLにGETリクエストを送信すると，検索結果に対応するデータがXML形式(かJSON形式)で返される．

このXMLをスクレイピングツールなどでいじって，欲しい情報を取り出せばよい．

使用する上での注意点

• このAPIは無料で利用でき，トランザクション数にも制限はない．
  しかし，同一IPアドレスから分間300以上のトランザクションを要求されると，503を返すとのこと．

• 実際のURLを見てもらうとわかるが，クエリパラメータの記法がわかりにくい*2．
  サポートされる OData クエリ オプション
  JSON のサポート
  ↑のあたりは参考になった*3．

• このAPIで用いられている"PaperID"，"AuthorID"は，Microsoft Academic Searchで用いられているものと一致している*4．
  例えば，
  http://academic.research.microsoft.com/Author/1272548/eric-lander
  は，Eric Landerについての著者詳細ページだが，APIにおける"Author"スキーマにで，IDが"1272548"の著者を確認すると，これもEric Landerとなる．

• このAPIは，一般的な文献検索(例えば，"pagerank"のようなクエリを入力して対応する検索結果を得る)に対応していない．
  個人的にはこれが一番必要な機能なのだが…

参考

Microsoft Academic Search API dataset in Windows Azure Marketplace

*1:なぜこんなことを知っているかというと，Web上には新APIの情報が少なく，旧APIの情報を見てMS社にメールを送ってしまったから．赤っ恥をかいた

*2:Microsoft独特の記法っぽい

*3:この記事を書く際に調べて，初めてJSON形式をサポートしていることを知った．全体的にドキュメントが不足している感は強い

*4:他のIDにも一致しているものがあると思うが，確認していない