インターネット検索エンジンのアルゴリズム - かろうじてクローラーになる

11. 09. 2016

Obsah článku

今日のレッスンでは、データバレルとその構造、StopSlovasについて説明し、最後にクローラーについて説明します。

データバレルズ

これは、複数のサーバーに同時に複数コピーで存在する特殊なデータ型である。原則として数百GBのデータ量の多いファイルで、読むのに時間がかかり（そのため分割されている）、編集は事実上不可能です。もし、わずかでも変更を加えようとすれば、バレル全体を計算し直さなければならないのです。例えば、検索エンジンのSeznamは、せいぜい数日から数週間に一度、データバレルを再計算する程度だが、Googleは数時間に一度（しかも一部だけで、全体を一度に計算することはない）再計算している。

バレルには、インターネット上の単語とその出現頻度が含まれています。検索結果をまだソートされていない状態（相対的重要度で部分的にソートされている場合もある）で、あらかじめ用意された生データといえる。検索自体は、ユーザーが検索クエリを尋ねるずっと前に行われ、すべての結果がここで準備されます。検索そのものはリアルタイムでは不可能なので、検索エンジンは基本的にここで既に用意された結果を読むことになる（検索は別章で説明するインデクサコンポーネントが行う）。

樽の中には、インターネット上で発生するあらゆる単語の検索結果を構築するために必要な基本情報がすべて含まれているため、順次読み進める際のパフォーマンス上の問題に対処する必要があります。実際には、バレルは複数のサーバーに一括して保存され、さらに高速アクセスのためにRAMにも保存される傾向にある。例えば、Googleの検索エンジンは、ディスクからバレルを一切読み込まず、完全にRAMに保持し、RAMからデータが失われた場合に備えて、ディスクにはそのコピーしか保持しない。

十分なリソースを持つ大規模な検索エンジンでは、いわゆる「ゴールデンバレル」と呼ばれる、インターネット上で最も重要なページを保存し、検索負荷が高い場合に検索されるようになっています。例えば、複数の検索サーバーがクラッシュした場合、ゴールドバレルが一時的に検索に対応する。検索エンジンはすべての結果を見つけることはできませんが、少なくとも検索が完全に中断されることはなく、検索される文書の数が一時的に制限されるだけです。また、インターネット上のページ数は常に増加しているため、定期的にバレルを更新する必要があります。バレルは通常ギガバイトオーダーのサイズなので、インクリメンタルメンテナンスはできず、一定時間ごとに一度全体を再構築する必要がある。そのため、検索エンジンは、すべてのデータが大きなテーブルの形になっている補助的なバレルを保持し、そこからバレルを構築している--たとえば、Googleは約12時間ごとにバレルを構築している。大きな課題は、まさに、少なくとも部分的に分類され、インターネットの実際の状態を反映したバレルでなければならないことです。そのため、検索エンジンがバレルを更新しない限り、ユーザーは新しいウェブページを見つけることができません。

バレル構造

実際には、検索語が出現する各文書のIDと、現在検索されている語の出現位置を含む大きなテキストファイルとして、バレルが保存される。

3ページの極小バレル例。

[1:5,8,12,27,30;5:1,3,6;12:4,8,10]

このサンプルバレルには、識別子 1、5、12 のページが含まれています。関連する数字は、文書中の単語の出現位置を示す。このようなバレルは、1つの単語の出現頻度しか捕捉しないため、インターネット上の単語はそれぞれ独自のバレルを持つことになる。複数のキーワードを検索する場合、複数のバレル（単語ごとに異なるバレル）を読み込んで、バイナリツリーに従って演算を行う必要がある（詳しくは前章で説明）。

交差は通常、片方の書類を調べて、もう片方を検索することで行われます。樽が大きいと、完全に読まれないことがあるので、検索エンジンはその一部しか読むことができず、結果を返さなければならないことがよくあります。ですから、少なくとも部分的に樽を分類し、最も重要なページ（ユーザーが探していると思われるもの）を樽の最初に、それ以外は樽の最後に置くことは理にかなっていると言えるでしょう。

ストップリード

言葉によっては、樽が大きくて作業がしにくいのではと思われるかもしれません。例えば、aや1という単語は半分以上の文書に含まれているが、検索者にとって何の意味も持たない（ほとんど検索されず、より多くの周辺単語を必要とするからである）。このような単語をStopwordsと呼ぶ。

ストップワードの問題は、すべてを検索することができないため、検索エンジンは、検索ワードに対して実際にインターネットがどのように見えるかという歪んだ現実しか示さないことである。

StopSlovyを使った検索の例として、Prague 1というクエリがあります。

検索エンジンは、このクエリに対して「3,020,000件」の結果しか出しません。しかし、実際にはもっと多くのサイトが存在します。ただし、パフォーマンス上の理由から、すべてを検索するわけではありません。

StopSlovyでアクセスオプションを検索します。

全くインデックスさせず、樽も作らない（小規模な検索エンジンはこうしている）
インデックスを作成するが、関連するページのみをバレルに保存する（これはGoogleやSeznamなどが行っている）。
通常の単語としてインデックスを付け、完全なバレルを作成する（このソリューションには、バレルが通常のハードディスクのサイズを簡単に超えてしまうため、保存できず、読み取りに数秒かかってしまうという問題がある - したがって、このソリューションは実際には使われないか、小規模で特殊な検索エンジンのみに使われる）

一般的に、普遍的に正しいアプローチはなく、Googleでさえも完璧に使いこなしているわけではありません。これは一生かかっても解決できないほど大きな問題です。しかし、この論文の目的には、この一般的な説明で十分である。

クローラー

クローラーとは、インターネットを体系的に巡回し、どのページにどのような言葉が出現するかを記録したり、補助情報（メタ情報ともいう）を収集したりするプログラムのことです。クローラーは通常、多くのサーバーで動作する。インターネットのクローリングはネットワークの帯域幅を必要とするため、多くのページを同時にクローリングする必要があるからである。Googleは、一度に最大3万ページが同時にクロールされると見積もっている。

クローラーは、ページを開く前に、今後どのようなアドレスに行く予定なのかをデータベースで調べます。すでにそのアドレスに行ったことがある場合は、記録を更新するだけです（主要なサイトには数時間おき、ニュースサイトには数分おき、通常のサイトにはせいぜい1ヶ月に1回程度行っています）。

ロボットが知らない新しいアドレスに到着すると、そこに含まれる他の文書（ページ）へのリンクを調べます。それぞれのリンクについて、重要度を計算し、重要なリンクであれば、そのページにも後からやってくる。

例えば、Listはこの方法で各サイトの数段階のリンクしかクロールしないが、Googleは重要でない文書も含めてサイト全体をクロールしようとするので、インターネット上で最も包括的な検索エンジンと言える。また、ロボットはクロールしながらページのランク付けを試み、そのページがインターネット上でどれだけ重要かを数値化した「ランク」を算出します。これまでGoogleは、0から10までの範囲を持つPageRankを使用してきました。Googleは、自分自身とmicrosoft.comやw3c.orgなどのサイトに対してのみPageRank10を算出しています。今は違う値で計算する（人工知能とベクトル数学）。

チェコ共和国で最も高いPageRankはSeznam.czで、値は7です。このランクは、ロボットがページを訪れる頻度や検索結果での上位表示などに高い影響を及ぼします。ランクは、目的のページを指すバックリンクだけで計算されます。

クローラーはデータに対して他に何もせず、ただインターネットからデータをダウンロードし、データベースに保存してインデックス作成処理を待ちます。

Jan Barášek Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu: