検索エンジンの原理 by Python
久しぶりの1日オフです。
最近ずっと会社のほうではAndroidばかりしてたので、かなり久しぶりにPythonとかFlaskとかwebに関するメモを読み返していたら、4ヶ月ぐらい前にUdacity等で勉強してた検索エンジンの内容があったので、復習がてらここにまとめてみようと思います!とりあえず、Webクローラーの原理までまとめて、続きは次回時間あるとき、気が向いたらすることにします!
・検索エンジンの仕組み
Googleに代表される検索エンジンは誰でも一度は使ったことがあるとおもうのですが、そのロジック的なことについてかいていきます。
Googleの場合、ユーザーが検索エンジンを使用する時、実はWebをそのまま検索しているわけではありません。Googleの持つwebのindex(索引)、すなわちGoogleが見つけ、情報を集めることのできたものの中から検索しています。
つまり検索処理は、検索キーワードが入力されるはるか前から始まっています。GoogleではWebクローラと呼ばれるソフトウェアロボットを使い、 検索結果に表示するためのウェブページを探します。そしてGoogleのソフトウェアはこれらのページに関するデータをデータセンターに保存し、検索時にはその中から情報を取り出しているのです。
Google のindexは 1 億ギガバイトを超え、indexの構築に費やした処理時間は累積で 100 万時間を超えているらしいです。
多すぎわろた。
そして検索時には、Rank付けのアルゴリズムによって200個以上の要素を瞬時に処理し、ランクずけして、検索画面に表示されます。このアルゴリズムは、改良に改良を重ね、進化していているらしいです。
・Webクローラー
Webクローラーはあるページをクロールした時に、正しくリンクをみつけ、そのリンクをたどっていくのですが、この時に制限をかけないと無限にクロールしてしまうので、深さ(リンクをどの階層までたどるか)を考える必要があります。
# pageというhtmlを文字列化したものの中から、URLを探し出す def get_next_target(page): start_link = page.find('<a href=') if start_link == -1: return None, 0 #pageからURLのみを取り出すためにURLの最初と最後の"を抽出 start_quote = page.find('"', start_link) end_quote = page.find('"', start_quote + 1) url = page[start_quote + 1:end_quote] return url, end_quote def print_all_links(page): while True: url, endpos = get_next_target(page) if url: print url page = page[endpos:] else: break #例外で、上で取り出したURLがない場合を処理 def get_page(url): try: import urllib return urllib.urlopen(url).read() except: return "" def union(p,q): for e in q: if e not in p: p.append(e) #全てのリンク def get_all_links(page): links = [] while True: url,endpos = get_next_target(page) if url: links.append(url) page = page[endpos:] else: break return links #深さ優先探索。深さを指定することで、効率よくクローリング def crawl_web(seed,max_depth): tocrawl = [seed] crawled = [] next_depth = [] depth = 0 """ 一度クローリングしたページを重複しないようにtocrawlから終了したページをとりだし、crawldに順番に格納 """ while tocrawl and depth <= max_depth: page = tocrawl.pop() if page not in crawled: union(next_depth, get_all_links(get_page(page))) crawled.append(page) if not tocrawl: tocrawl, next_depth = next_depth, [] depth = depth + 1 return crawled
これが、最低限の機能は持ち合わせているクローラーです。
ブログとして自分の勉強内容をまとめたのは初めてなのでクッソ時間がかかりました。一応これからも自分用の忘備録的な感じで書いていきたいのですが、最後まで見ていただいた方で内容が不明瞭だったり、間違ったことやまずいこと等が書かれていましたら、ぜひぜひコメントしていただきたいです!!
・参考資料
Intro to Computer Science & Programming Course - Udacity
検索の仕組み – 検索サービス – Google
Amazon.co.jp: Google誕生 —ガレージで生まれたサーチ・モンスター: デビッド ヴァイス, マーク マルシード, 田村 理香: 本