python3対応 Mecabの紹介
python3対応 Mecabの紹介
4月から大学院に来て，授業やらなんやらでブログを3ヶ月程放置していました．なんかすみません．
今，MeCabとか使っているのですが，デフォルトではpython3に対応していないため，python3に対応させinstallもpipで出来るようにしました．（github経由だけど）
今日は，python3に対応したMeCabをインストールする方法を紹介します．
と，その前に１つ言わせて下さい．皆さん，もうそろそろpython3にした方がいいですよ． python3はpython2のゴミを取ったよりpythonicなpythonです． python3こそpythonです．皆さんpython3に移行しましょう！
MeCabのinstall
私がMecab python3 のレポジトリに書いたように，インストールは以下の通りにすればできます．
pip install mecab-python3
installしたら下記のコードでテストしてみましょう！
import MeCab mecab = MeCab.Tagger ("-Ochasen") print(mecab.parse("python3が大好きです"))
インストールがうまく出来ていれば，以下のように表示されます．
python python python 名詞-一般 3 3 3 名詞-数 が ガ が 助詞-格助詞-一般 大好き ダイスキ 大好き 名詞-形容動詞語幹 です デス です 助動詞 特殊・デス 基本形 EOS
python3は最高です． 皆さんもpython3に乗り換えましょう！
Small World GraphとDijkstra
Small World GraphとDijkstra
今Think Complexity
chap4)で勉強した
について簡単にまとめを行いたいと思います． Think Complexity は無料で読む事もできます！
Small World Graph
社会学者であるStanley Milgram は権威に対する服従についてのMilgramの実験やスモールワールド現象 についての実験で有名な人です．スモールワールドの実験は 任意の人を選び，目標人物に平均して何人を経由する事で 手紙を渡せるかを検証した実験です．成功した例はわずかでしたが， その中での平均は6人だったそうです．詳しくはこちらをご覧下さい．
その後，Duncan WattsとSteven Strogatzが
このスモールワールド現象について説明した論文を発表しました．
彼らはランダムグラフと正則グラフに着目し，２つの特徴を定式化しました．
それはclustering coefficient: C(p) (クラスタリング係数)とaverage path length: L(p)(平均パス距離)です．
clusteringは簡単に言うと共通の知人を持つaとbが直接の 知人である確立を表しています．
path lengthは各ノードと全てのノードとの最短パスの距離を平均したものです．
詳しい定義はこちらで一番最初に出てくるpdfをご覧下さい．
Small worldというグラフ構造はノードがクラスタ状
に集まっている
（ノード間に張られているエッジの密度が高いノードの集まり）
にも関わらず，ノード間のパス
が短いという特徴をもつグラフです．つまり，クラスタリング係数Cが
大きく，パスの距離Lが小さい状態のことを言います．
スモールワールドグラフの実装は非常に簡単です．n個のノードがあり
次数がkである時に，ノードをリング状につなぎます（正則グラフ）．
その後，各々のノードの各々のエッジを確立pでランダムに再接続(rewire)します．
この確立p が~0.01の付近でスモールグラフになります．
スモールグラフは次数kのリング状の正則グラフを作成(add_regular_edges)したあとに，
再接続(rewire)することで作成できます．以下が実装例となります．
Dijkstra
続いて，semaphore(セマフォ)やダイクストラのアルゴリズムで有名な オランダのコンピュータサイエンティストEdsger W. Dijkstraの Dijkstraのアルゴリズムを紹介します．
Dijkstraのアルゴリズムは任意のノード間の最短パスを 効率的に求めるアルゴリズムです．一般的にはエッジに重みがあるグラフを 考えますが，今回はエッジの重みを考慮しない簡易化したものを考えます．
簡易化したDijkstraのアルゴリズムはBFSと殆ど同じで， 訪問した時にマークする代わりに距離のラベルを与えます．
アルゴリズムは以下のようになります．
- step1 ソースノードに距離0を与え，wokrlistに追加します．他のノード には無限の距離を与えます．
- step2 wokrlistからノードを削除し距離dに代入します．続いて，そのノードが隣接する隣接ノードを探します．それらのノードに距離d+1を代入しworklistに追加します．
- step3 worklistが空なら終了し，それ以外はstep2に戻ります．
ここでは，エッジの重みがない場合（全て均等）としているので，距離に
1を足しています．本来なら重みを足します．
以下に，上で紹介した簡易化したdijkstraの実装例， clustering coefficient:C(p)，average path length:L(p)の 実装例を示します．
まとめ
今回は，Small World Graphの説明・実装例， dijkstraのアルゴリズムの説明・実装例とクラスタリング係数と 平均パス距離の実装を紹介しました．
スモールワールドグラフはクラスタリングがある場所 （ノードが人間であればコミュニティ）と他のコミュニティを つなぐ部分を理解する助けになり，ビジネスにも活用出来ると思います． 例えば，そこに集中して広告することで複数の コミュニティに効果的に広告出来る事が考えられます． スモールワールドはビジネスへの応用が期待出来るなと感じる事ができました．
reference
二分探索法とハッシュテーブル
二分探索法とハッシュテーブルの実装例
今Think Complexitychap3)で勉強した
について簡単にまとめを行いたいと思います． Think Complexity は無料で読む事もできます！
Binary Search（二分探索）の実装
pythonでのBinary Searchの実装方法を2つ紹介します．
例えば，私たちが英語の辞書から単語を探す時に使っているのが
Binary Searchです．Binary Searchでは最初から逐次的に調べるのでなく，
真ん中から探索を開始し，探している単語が
それより後か前かを調べ，前なら前半を調べ，後なら後半を調べる．
この作業を繰り返すことで目的の単語を探索する方法のことを
Binary Searchと呼びます．この計算量はO(logn)です．
ただし，使用するリストがソートされている事が事前条件です．
従って，ソートと探索の計算量はO(nlogn) + O(logn)でO(nlogn)になるかと思います．
詳しい説明は色々なところでされていると思うので，
説明はこれくらいにして，Pythonでの実装例を紹介します．
下記のコードにある関数bisection()はpythonのモジュールであるbisect
を使って実装した例で，関数binary_search()
は地道にアルゴリズム通り実装した例です．両関数ともtargetとしている要素がリストにあればそのインデックスを返し，なければNoneを返します．
bisection()では，挿入点を探し挿入点のインデックスを返すbisect_leftを使います．リストt内でのtargetの挿入点をbisect_leftより算出しiに代入します．t[i]がtargetでない場合Noneを返します．また，targetが
存在しない場合はtのサイズより大きな値を返すので
その場合もNoneを返します．
binary_search()では初めに，tのサイズをhiに
格納します．またlo<hiになると探索を終了します．
それ以外は要素をtargetと比較し，前半または後半の
中間に位置するインデックスの値を用い再帰的に探索します．
Hashtables(ハッシュテーブル)の実装例
最後に，簡単なHashtableの実装例を紹介します．
ハッシュテーブルはとても高速で，
探索，挿入，削除の計算量はconstant(定数)です．つまりO(1)です．pythonでは辞書がhashtableです．
hashtableの理解を深めるために一度辞書型のことは 忘れて，簡単なhastableの実装を紹介します．（衝突の事は考えません）
下記のコードにあるクラスLinearMapは要素の追加にリストのappendを使っているため計算量はO(1)ですが，getではitemsを
走査しているためO(n)となります．（nはitemsの要素数）
続いて，BetterMapクラスは100個のLinearMapを要素として持ちます．
BetterMapではインスタント時にO(n)の計算量が掛かります．
要素の追加では，find_mapでkeyのハッシュ値を計算しmapsの
サイズに収まるようなindexを算出します（ここでは衝突は
考慮していません）．算出されたindexを用いて要素をmapsに追加します．
衝突が起こらないと考えれば，addはO(1)となります．
最後に,HashMapクラスはLinearMapを2個要素としてもつBetterMapを
保持し，要素を追加してサイズが大きくなるたびに
リサイズします．リサイズするたびに計算量は一時的に
増えますが，n回要素を追加したときのトータルコストは
2n-2となります．そのため1回の操作は2n-2/n = 1 - 2/n となり，
計算量がO(1)となります．これで計算量が定数のハッシュテーブルが
完成です．実際のhashtableではこれに衝突した時の処理を追加しないといけません．
まとめ
今回は，二分探索の実装例，ハッシュテーブルの実装例を簡単に 紹介しました．
アルゴリズムの実装をする事がアルゴリズムを理解するための近道だと 思います．アルゴリズムを自分で実装し各言語にデフォルトで付随しているアルゴリズムと 計算量を比較することでアルゴリズムの重要性が身にしみたりします．
Reference
