検索エンジンの基礎の基礎

検索エンジンの基礎の基礎

• euler.bonjour@gmail.com / https://github.com/khj1977 / @pcaffeine77

• 代表 CEO 兼 Principal (戦略コンサルタント 兼 ITアーキテクト)

• 金輝俊 / Hwi Jun KIM

Intoroduction

えっ、スマフォでなんかカラフルなアイコンのChromeってやつタップして起動するとなんか出てくるんだけど。何、この簡素なアプリ？上のバーの中に「カレー　レシピ」って入れてみ。なんか出てくるよ何これ？

色がついた文字列タップしてみ。あっ、文章と画像が出た。何これ、ワープロなの？HTML/CSS何それ？まあいいや。へー、これ、ホームページって言うんだ。何か、Wordみたいやつあるの？テキストエディタ何それ？

この探すやつが検索エンジンでGoogleって言うんだ。Chromeの上のバーにGoogleって入れて、リターンしてみれば呼び出せるよ。

えっ、ホームページって世界中に何十億とか何百億ページとあるの？へー、でも、このGoogleってどうやって、一瞬で見つけてるの？超速いパソコンがあるの？

まあ、説明するよ。

Introduction to the Internet

実は君がLINEを使っている時、LINEのアプリとアプリは直接通信してない。インターネット上にある、サーバーというものを介している。サーバーはパソコンの一種で、ネットのどこかに繋がっている。例えば、LINEで誰かにメッセを打つと、スマフォがサーバーに繋いで、サーバーにスマフォのアプリからデータが転送される。そして、その誰かがLINEを立ち上げるとサーバーにメッセを取りに行く。

ブラウザは文章と画像の塊をカレーのレシピとして表示したと思うが、これもサーバーのどっかにある。ブラウザがURLという場所を指定されるとそのURLが示すサーバーに繋いで、このURLの示すデータを下さいとサーバーの中で動くプログラムに頼んで、その結果返されるHTML/CSSを持ってきて、それを元にブラウザがワープロみたいなアウトプットを表示する。

これがホームページとサーバー。大雑把に言って、Webとも言う。

で、Googleはどうやって、何百億というホームページから一瞬でカレーのレシピを見つけ出して、ブラウザに返しているのだろう？結構、基本的な考え方は簡単。実際はもっと複雑になるけどね。そのイントロを説明しようと思う。

Binary Tree

簡単な樹形図を考えてみよう。下記に文字で図を書く。

O -- O--O
   |  |-O
   |-O--O
      |-O

最初の右端の根っこ、これをroot nodeという。root nodeは一つしかない。次に二個のO、つまり、ノードがつながっている。そこから、それぞれのノードに対して、二個づつのノードがつながっている。

何か、気づかないかな？階層が深くなるごとに倍々ゲームで数が増えていく。

0, 2, 4と増えていくね。では、4階層目は？そう、8個。分からないら、自分でノートに図を書いて数えて見ること。

これをBinary Treeという。

指数関数と逆関数としての対数関数

では、これは公式化できるのでは？そうズバリ、2の指数関数になる。num node = y = 2^kでkは0から始まる階層となる。kは0, 1, 2, 3, 4と増えていく。

面白いね、では、y = 2^kはどう増えていくのか、電卓を叩いてみよう。1, 2, 4, 8, 16, 32と増えていく。確かに、では、k = 10だと？1024。では、k = 24だと？約1677万となる。

もっというと、2^32は約40億。すごい数になるね。何か気づかない？こういうふうに探していくと、32回探すだけで、40億個の何かを探したことになる。

すごく、大雑把に言うと、Googleみたいな検索エンジンはこの変種の考え方を元にしている。ちょっと違うし、この上に色々数学がのるけどね。

計算量とBinary Treeの高速性

ここで、対数関数logを導入してみよう。覚えてないなら、高校の数学の教科書を引っ張り出して欲しい。

x = log_2(y)

y = 40億なら、x = 32となる。すごく伸びるのが遅い。詰まるところ、このBinary Treeを使うと、凄い数のホームページを凄い少ない計算量で探せることになる。

検索エンジン、例えばGoogleの構成要素はたくさんある

これが検索エンジンのイントロのイントロ。結構簡単でしょう？これは実はMySQLみたいなデータベースにも関係がある。ただ、Googleの場合は色々な数学を使ったり、大量のデータを元に計算するために、特殊な並列分散処理のプログラムを持っていたりする。これは、昔の設計で今は違うと思うけど。

サーバーは何万か何十万かわからないけど、たくさんが協調動作していると思う。でも、それだけじゃ無理。40億回探すのと32回探すの、どちらの方が速いと思う？これが、コンピュータサイエンスの基礎的な考え方の一つ。面白いでしょ？

PS: より深くBinary Treeについて知りたい人へ。

1.データ構造とアルゴリズムの教科書をきちんと読むこと。ここでの説明は文理問わず分かりやすくするために、理論的厳密性をある程度犠牲にしている。なので、詳しく知りたい人は自分で教科書を読んでみることを薦める。

2.自分でPHPなりC++なりを使って、Binary Treeを実装する事。このエントリや教科書をきちんと読めば、ある程度の理解を得られると思う。しかし、自分で実装してみると、また別の視点を得られるのも経験的に事実かと思う。言語はなんでもいいから、実際に実装してみるのもいいかもしれない。

3.もし、勉強のコミュニティを持っているのなら、勉強なり、実装の成果をシェアしてみよう。議論するのもいいし、発表する事で理解が深まるかもしれない。

4.漫画のだめカンタービレで次のようなセリフがある。「音楽あるいは楽譜に真剣に向かいあえば、あちらから語りかけて来るよ」これは、コンピューターサイエンスでも戦略論でも同様である。もし、コンピューターサイエンスの教科書が単なる単語とコードの羅列にしか見えないなら、時間をかけて、じっくりと向き合う事を薦める。

今日はここまで。

著者略歴

金輝俊 / Hwi Jun KIM
Position: 代表 CEO 兼 Principal
Role: 戦略コンサルタント 兼 ITアーキテクト

ハイテクITベンチャーのProduct Manager / Chief IT Architect、Webベンチャーのグループリーダー、外資系IT企業のProject Manager 兼 Systems Architectなどを経験。会社を離れて数年後、Webベンチャーと外資系IT企業グローバル本社は、それぞれ東証マザーズとNYSEに上場した。

ファッションテックベンチャーのグロースハック室 室長 兼 システム開発部スペシャリストに。30人4部門を参謀長として指揮統括し、約10億円の株式による増資に成功。シーリズCへと導く。その後、起業。NMD Soft, Principalとして活動を開始。

社会貢献活動として、原爆の実相を伝えるためと、東日本大震災の解析のために、Nagasaki Archive、Hiroshima Archive、Mass Media Coverage Map of The East Japan Earthquakeなどの開発と一部企画に関わった。

主な著作にThe Real M.Phil Thesis: The Mathematical Foundation of Smart Material Systems / Yet Another Mori-TanakaやMBA Thesis: The Modern Strategy from Japanがある。

筑波大学 第三学群 工学システム学類 学士(工学) First Class (イングランド基準。70%以上がA評価)

Coventry University大学院 Control Theory and Applications Centre, Master of Philosophy (Upper Master, Research Degree)。飛び級入学。返済義務無し奨学金付き。

主な受賞にアレスエレクトロニカ展Honorary mention、経済産業大臣賞、文化庁メディア芸術祭審査委員会推薦作品など。

詳細なプロフィールはこちら：https://www.khj1977.net/

以上