インターネットとその最も目立つコンポーネントである World Wide Web に関する良いニュースは、利用可能なページが何億もあり、驚くほど多様なトピックに関する情報の提供を待っていることです。インターネットに関する悪いニュースは、何億ものページが利用可能であり、そのほとんどが作成者の気まぐれなタイトルであり、ほとんどすべてが不可解な名前でサーバー上に存在していることです。特定の主題について知りたいとき、どのページを読めばよいかどうやってわかりますか?あなたもほとんどの人と同じように、インターネット検索エンジンにアクセスするでしょう。
インターネット検索エンジンは、他のサイトに保存されている情報を検索できるように設計された Web 上の特別なサイトです。さまざまな検索エンジンの動作方法には違いがありますが、いずれも次の 3 つの基本的なタスクを実行します。
- 彼らは重要な単語に基づいてインターネットを検索したり、インターネットの一部を選択したりします。
- 彼らは、見つけた単語と、それを見つけた場所のインデックスを保持します。
- これらを使用すると、ユーザーはそのインデックス内で見つかった単語または単語の組み合わせを検索できます。
初期の検索エンジンは数十万のページとドキュメントのインデックスを保持しており、毎日 1 ～ 2,000 件の問い合わせを受けていました。現在、トップの検索エンジンは数億のページのインデックスを作成し、1 日に数千万のクエリに応答します。この記事では、これらの主要なタスクがどのように実行されるか、また、必要な情報を Web 上で見つけられるようにするために、インターネット検索エンジンがどのように各要素を組み立てるかについて説明します。
ウェブクローリング
ほとんどの人がインターネット検索エンジンについて話すとき、それは実際には World Wide Web 検索エンジンを意味します。 Web がインターネットで最も目立つ部分になる前に、人々がネット上の情報を見つけるのを助ける検索エンジンがすでに存在していました。 「gopher」や「Archie」などの名前のプログラムは、インターネットに接続されたサーバーに保存されているファイルのインデックスを保持し、プログラムやドキュメントの検索に必要な時間を大幅に短縮しました。 1980 年代後半、インターネットから本格的な価値を得ることは、ゴーファー、アーチー、ベロニカなどの使い方を知ることを意味していました。
現在、ほとんどのインターネット ユーザーは検索を Web に限定しているため、この記事ではWeb ページのコンテンツに焦点を当てた検索エンジンに限定します。
検索エンジンがファイルやドキュメントの場所を知らせるには、まずそれを見つける必要があります。存在する何億もの Web ページに関する情報を見つけるために、検索エンジンはスパイダーと呼ばれる特別なソフトウェア ロボットを使用して、Web サイトで見つかった単語のリストを作成します。スパイダーがリストを作成するときのプロセスは、 Web クローリングと呼ばれます。 (インターネットの一部を World Wide Web と呼ぶことにはいくつかの欠点があります。クモ類を中心としたツールの名前が大量にあることもその 1 つです。) 有用な単語のリストを作成し維持するために、検索エンジンのスパイダーは次のような機能を備えています。たくさんのページを見るために。
クモはどのようにしてウェブ上を移動し始めるのでしょうか?通常、開始点は、頻繁に使用されるサーバーと非常に人気のあるページのリストです。スパイダーは人気のあるサイトから始めて、ページ上の単語のインデックスを作成し、サイト内で見つかったすべてのリンクをたどります。このようにして、スパイダー システムはすぐに移動を開始し、Web の最も広く使用されている部分に広がります。
Google は学術検索エンジンとして始まりました。このシステムがどのように構築されたかを説明する論文の中で、サーゲイ・ブリンとローレンス・ペイジは、スパイダーがいかに早く機能するかを例として挙げています。彼らは、複数のスパイダー (通常は一度に 3 つ) を使用する最初のシステムを構築しました。各スパイダーは、一度に Web ページへの約 300 の接続を開いたままにすることができます。最高のパフォーマンスでは、4 つのスパイダーを使用してシステムは 1 秒あたり 100 ページ以上をクロールし、毎秒約 600 キロバイトのデータを生成できました。
すべてを迅速に実行し続けるには、必要な情報をスパイダーに供給するシステムを構築する必要があります。初期の Google システムには、スパイダーに URL を提供する専用のサーバーがありました。サーバー名をアドレスに変換するドメイン ネーム サーバー(DNS) をインターネット サービス プロバイダーに依存するのではなく、Google は遅延を最小限に抑えるために独自の DNS を持っていました。
Google スパイダーがHTMLページを見たとき、次の 2 つの点に注目しました。
- ページ内の単語
- 言葉が見つかった場所
タイトル、サブタイトル、メタタグ、およびその他の相対的に重要な位置に出現する単語は、その後のユーザー検索時に特別な考慮事項として記録されました。 Google スパイダーは、冠詞「a」、「an」、「the」を除いて、ページ上のすべての重要な単語にインデックスを付けるように構築されています。他のクモは異なるアプローチを取ります。
これらのさまざまなアプローチは通常、スパイダーの動作を高速化するか、ユーザーがより効率的に検索できるようにするか、あるいはその両方を試みます。たとえば、一部のスパイダーは、タイトル、小見出し、リンクの単語を追跡するほか、ページ上で最も頻繁に使用される 100 の単語とテキストの最初の 20 行の各単語を追跡します。 Lycos は、Web をスパイダー化するためにこのアプローチを使用していると言われています。
AltaVista などの他のシステムは、逆の方向に進み、「a」、「an」、「the」、その他の「重要でない」単語を含む、ページ上のすべての単語にインデックスを付けます。このアプローチの完全性への取り組みは、Web ページの目に見えない部分であるメタ タグに注意が払われるという点で他のシステムと同等です。メタタグの詳細については、次のページをご覧ください。
メタタグ
メタ タグを使用すると、ページの所有者は、ページのインデックス付けに使用するキーワードと概念を指定できます。これは、特にページ上の単語に二重または三重の意味がある場合に役立ちます。メタ タグは、これらの単語に考えられるいくつかの意味のうちどれが正しいかを検索エンジンが選択するようにガイドできます。ただし、メタ タグに過度に依存することには危険があります。不注意または不謹慎なページ所有者が、非常に人気のあるトピックには適合するものの、ページの実際のコンテンツとはまったく関係のないメタ タグを追加する可能性があるためです。これを防ぐために、スパイダーはメタ タグをページ コンテンツと関連付け、ページ上の単語と一致しないメタ タグを拒否します。
これらすべては、ページの所有者が実際にそのページを検索エンジンのアクティビティの結果に含めることを望んでいることを前提としています。多くの場合、ページの所有者は、そのページが主要な検索エンジンに表示されることを望まなかったり、ページにアクセスするスパイダーの活動を望まなかったりします。たとえば、ページのセクションが表示されるか、新しいリンクがたどられるたびに、新しいアクティブなページを構築するゲームを考えてみましょう。ウェブ スパイダーがこれらのページのいずれかにアクセスし、新しいページへのすべてのリンクをたどり始めると、ゲームはそのアクティビティを高速の人間プレイヤーと誤認し、制御不能になる可能性があります。このような状況を回避するために、ロボット排除プロトコルが開発されました。このプロトコルは、Web ページの先頭のメタタグ セクションに実装されており、スパイダーにページをそのままにし、ページ上の単語にインデックスを付けたり、そのリンクをたどったりしないように指示します。
インデックスの構築
スパイダーが Web ページ上の情報を見つけるタスクを完了すると (これは実際には決して完了しないタスクであることに注意してください。Web の絶えず変化する性質により、スパイダーは常に巡回していることになります)、検索エンジンは次のことを行う必要があります。情報を役立つ方法で保存します。収集されたデータにユーザーがアクセスできるようにするには、次の 2 つの重要なコンポーネントが関係します。
- データとともに保存される情報
- 情報にインデックスを付ける方法
最も単純なケースでは、検索エンジンは単語とそれが見つかった URL を保存するだけです。実際には、その単語がページ上で重要な意味で使われたのか些細な意味で使われたのか、その単語が一度使われたのか何度も使われたのか、あるいはページ上で使われたかどうかを知る方法がないため、これは限定された用途のエンジンになります。単語を含む他のページへのリンクが含まれていました。言い換えれば、最も有用なページを検索結果リストの上位に表示するランキングリストを作成する方法はありません。
より有用な結果を得るために、ほとんどの検索エンジンは単語や URL 以外の情報も保存します。エンジンは、ページ上にその単語が出現した回数を保存する場合があります。エンジンは各エントリに重みを割り当て、ドキュメントの先頭付近、小見出し、リンク、メタ タグ、またはページのタイトルに出現する単語に応じて増加する値を割り当てます。各商用検索エンジンには、インデックス内の単語に重みを割り当てるための異なる式があります。これが、異なる検索エンジンで同じ単語を検索すると、異なるリストが生成され、ページが異なる順序で表示される理由の 1 つです。
検索エンジンによって保存される追加情報の正確な組み合わせに関係なく、データはストレージ容量を節約するためにエンコードされます。たとえば、Google の元の論文では、重み付けに関する情報 (単語が大文字かどうか、フォント サイズ、位置、およびヒットのランキングに役立つその他の情報) を格納するために、それぞれ 8ビットの 2バイトを使用すると説明されています。各係数は、2 バイトのグループ化 (8 ビット = 1 バイト) 内で 2 ビットまたは 3 ビットを占める場合があります。その結果、大量の情報を非常にコンパクトな形式で保存できます。情報が圧縮されると、インデックスを作成できるようになります。
インデックスの目的は 1 つです。インデックスにより、情報をできるだけ早く見つけられるようになります。インデックスを構築するにはさまざまな方法がありますが、最も効果的な方法の 1 つはハッシュ テーブルを構築することです。ハッシュ化では、式を適用して各単語に数値を付加します。この式は、所定の数の部門にわたってエントリを均等に分配するように設計されています。この数値分布はアルファベット全体の単語の分布とは異なり、それがハッシュ テーブルの有効性の鍵となります。
英語には、多くの単語で始まる文字もあれば、少ない単語で始まる文字もあります。たとえば、辞書の「M」セクションは「X」セクションよりもはるかに厚いことがわかります。この不公平性は、非常に「人気のある」文字で始まる単語を見つけるには、あまり人気のない文字で始まる単語を見つけるよりもはるかに長い時間がかかる可能性があることを意味します。ハッシュにより差が平準化され、エントリを見つけるのにかかる平均時間が短縮されます。また、インデックスを実際のエントリから分離します。ハッシュ テーブルには、ハッシュされた数値と実際のデータへのポインタが含まれており、最も効率的に保存できる方法で並べ替えることができます。効率的なインデックス作成と効果的なストレージを組み合わせることで、ユーザーが複雑な検索を作成した場合でも、結果を迅速に取得できます。
検索の構築
インデックスによる検索には、ユーザーがクエリを作成し、検索エンジンを通じて送信することが含まれます。クエリは非常に単純で、少なくとも 1 つの単語にすることができます。より複雑なクエリを作成するには、検索条件を絞り込んだり拡張したりできるブール演算子を使用する必要があります。
最もよく見られるブール演算子は次のとおりです。
- AND – 「AND」で結合されたすべての用語がページまたはドキュメントに表示される必要があります。一部の検索エンジンでは、単語 AND を演算子「+」に置き換えます。
- OR – 「OR」で結合された少なくとも 1 つの用語がページまたはドキュメントに表示されている必要があります。
- NOT – 「NOT」に続く用語は、ページまたはドキュメント内に出現してはなりません。一部の検索エンジンでは、NOT という単語を演算子「-」に置き換えます。
- FOLLOWED BY – いずれかの用語の後に、もう一方の用語が直接続く必要があります。
- NEAR – 一方の用語は、他方の用語の指定された単語数以内にある必要があります。
- 引用符– 引用符で囲まれた単語は語句として扱われ、その語句が文書またはファイル内に存在する必要があります。
検索エンジンは私たちの生活に不可欠な部分となっているため、少なくとも 1 つの組織化されたゲームがこのツールを中心に進化しています。 Googlewhackingでは、正確に1 つの結果 (これらの単語の両方が表示される 1 つの Web ページ) を受け取ることを期待して、 に 2 つの単語を入力します。これはまったくの衝撃です。
これは非常に難しい作業です。まったく無関係な単語を 2 つ選択する必要があります。そうしないと、複数の結果が得られますが、完全に無関係な単語が多数あると、結果はゼロになります。
純粋な打撃を達成した場合は、それを に提出することができます。その結果は、 The Whack Stackに (名前または自分自身を呼びたいものと一緒に) 掲載され、全員が見ることができます。現在、The Whack Stack にある純粋な 1 つの攻撃は、「両手利きのScallywags」です。
未来の探索
ブール演算子で定義された検索はリテラル検索です。エンジンは、入力されたとおりに単語または語句を検索します。入力した単語に複数の意味がある場合、これが問題になる可能性があります。たとえば、「ベッド」は寝る場所であったり、花が植えられている場所であったり、トラックの保管場所であったり、魚が卵を産む場所であったりします。これらの意味のうち 1 つだけに興味がある場合は、他のすべての意味を取り上げたページは見たくないかもしれません。不要な意味を排除しようとする文字通りの検索を構築することもできますが、検索エンジン自体がそれを支援できると便利です。
検索エンジンの研究分野の 1 つは、コンセプトベースの検索です。この調査の一部には、興味のある他のページを見つけるために、検索する単語や語句を含むページの統計分析が含まれます。明らかに、各ページについて保存される情報は、コンセプトベースの検索エンジンの方が大きいです。検索ごとにはるかに多くの処理が必要になります。それでも、多くのグループがこのタイプの検索エンジンの結果とパフォーマンスの両方を改善するために取り組んでいます。自然言語クエリと呼ばれる別の研究分野に移った研究者もいます。
自然言語クエリの背後にある考え方は、隣に座っている人間に質問するのと同じ方法で質問を入力できるということです。ブール演算子や複雑なクエリ構造を追跡する必要はありません。現在最も人気のある自然言語クエリ サイトは、キーワードのクエリを解析し、構築したサイトのインデックスに適用します。これは単純なクエリでのみ機能します。しかし、非常に複雑なクエリを受け入れることができる自然言語クエリ エンジンを開発するには、競争が激しいです。
