インターネット検索エンジンのアルゴリズム - ツリーとStopLead

インターネットには毎秒500万もの新しいページが追加されており、この割合は常に増加している。この膨大な情報の海に秩序を与え、その中から何かを見つけ出すために、検索エンジンが存在する。以下の作品は、検索の問題を紹介し、新しいページを作成してから検索エンジンで見つけるまでの一連のプロセスを説明することを目的としています。

何十億という文書の集合を見つけ出し、分類する作業は容易ではありません。この作業を数時間でこなすには、グーグルだけでも30万台のウェブサーバーが必要です。実は、問い合わせをするよりもずっと前に、検索が行われているのです。Googleは、あなたがこれから求める検索結果をすでにメモリに保存しています。

検索エンジンアーキテクチャ

.

検索エンジンの設計には、数百にも及ぶ多くの部品が使われています。この図は、検索エンジンが機能するために最低限含まなければならない、最も基本的な要素を説明したものです。これは古くてもう使われていないアーキテクチャで、ウェブ上の文書が数百万しかなかった2005年頃までは機能していた。このアーキテクチャでは、コンテンツの量が「無限」ではなく、また検索サーバー（ベース検索）がダウンする可能性もあります。一つの部品が停止した場合、システム全体が機能しなくなり、検索エンジンは利用できなくなります。

新しいアーキテクチャの設計に関する現在の動向については、通常、大企業の企業秘密であるため、本稿の範囲外である。本稿の目的は、この基本アーキテクチャの仕組みについて説明することである。個々の構成要素については、次の章で詳しく説明します。

クエリーの入力

一般ユーザーでも最も目につきやすいのはクエリ入力で、現在はテキストボックスで表現されることが多い。入力欄は、通常、入力専用の特別なページに設置されています。

次の段階では、ユーザーが検索文字列を入力し、検索エンジンサーバーにフォームを送信することで、調剤コンポーネントとの通信が開始され、メイン検索とも呼ばれることがあります。調剤サーバは、ユーザーからの膨大な負荷を処理するために構築されており、すべての検索者を一度に処理できることが求められます。

ディスパッチサーバのアーキテクチャは、通常、基本的なインストールと優れたネットワーク帯域幅を持つシンプルなApacheサーバです。クエリーがサーバーに入ると、回帰決定木によって処理され、ユーザーが実際に何を探しているのかを明確にするために、他の意味の周りの完全なセマンティクスをキャプチャする「クエリーマップ」が作成される。クエリ書き換えの方法は、この論文の範囲を超えすぎているので、書き換えが可能なものと不可能なものの一般的な説明を示すにとどめる。

次のようなクエリを考えてみましょう。

"O pejskovi a kočičce"

このクエリは、その意味的な本質を捉えたバイナリツリーに変換される。

.

解析ツリーの要点は、検索エンジンが検索結果をどのように見るかを捉えることである。このツリーは、クエリとともに補助検索サーバ（本稿ではBase searchと表記）に送られ、個々のキーワードを検索（インデックスリード）し、ルールに従ってソート（オペレーションによる）される。

| NOT｜補集合

検索結果の実際の並べ替えはなく、このコンポーネントは膨大な量のデータ（多くは数百万レコード）に対して高速なバイナリ演算を行い、基本的には個々の文書のIDを比較するだけである。

結果ページの検索結果の実際の並べ替えがどのように行われるかは、次のセクションで説明します。出力サーバーは、全体のパフォーマンスを上げ、負荷を分散するために、異なる検索サーバーの多くのデータを組み合わせ、数十のサーバーからの合成情報を含む結果ページ（これを「Webページ」と呼ぶ）に検出値を送り込むために使われるだけである。

二分木への書き換え

前章で述べたように、検索全体は、結果がどのように見えるか、何を探せばよいかを示す二分木の上に成り立っている。サーチエンジンの「論理」と「知能」全体は、ツリーを作成するプログラム、すなわちディスクリプタの品質に直接依存します。

適切に構築されたツリーは、クエリに関する必要なメタ情報をすべて含み、ディスクの順次読み込みの助けを借りても容易に処理でき、メモリへのランダムアクセスを排除できる形式でなければなりません。したがって、通常、（ユーザーからの）個々の検索語、その転写（およびスペルアウト形式）、最後に、単語間のリンク、すなわちテキスト内の相対距離を含んでいます。

クエリーの転写方法

クエリを書き起こす最も基本的な方法は、クエリを（スペースに従って）個々の単語に解析することであり、これはさらに作業することになる。次に、StopWordsを検索し、変数ポインタに置き換えます（後で示すように、StopWordsを検索する意味が全くないからです）。

犬と猫について」というクエリがあったとして、その最も基本的な書き方は次のようなものである。

"O (and) pejskovi (and) a (and) kočičce"

第二段階は、検索と関連性のない単語を排除することである。もちろん、例えば「about」や「and」という言葉は、私たち人間にとっては意味のある言葉ですが、データベース検索にとっては、別の言葉に置き換えて結果を一覧できるため、意味がないのです。インターネット上のテキストでは、しばしば単語の綴りが異なるため、この方法では、ユーザーから得たものとは別の形式で結果を見つけようとするのである。したがって、これは「インテリジェント」な検索エンジンの最初の兆候である。

これらの無意味な単語はしばしば「ストップワード」と呼ばれ、すべての検索エンジンはこのような単語のインデックスを保持し、このインデックスは頻繁に（手動で）更新されなければならないのです。

["pejskovi (and) * (and) kočičce"]

このとき、2つの異なる単語（「dog」と「cat」）とその間にある別の単語（内部的にはアスタリスクでマークしている）を探すことになる。

この改造の目的は、検索の質を上げることではなく、パフォーマンスを上げることである。これは、頻度の高すぎる単語を検索すると、急激な負荷がかかるためで、この修正は、特に、とにかくほとんどの文書でその位置にあるであろう単語を検索しないことで処理を助けているのです。

また、この調整（単語の省略）は常にできるわけではないので、各検索エンジンはインターネット上にあるフレーズのインデックスを別途作成し、どの調整が良い結果につながり、どの調整がそうでないかをチェックする必要があります。特に、ユーザーが重要な単語を検索している場合、その単語の最初のページに重要なページがあると予想され、ユーザーは通常それらを要求するため、この「エラー」を上書きしてしまうのです。

最後は英語との連携で、クエリから不要な文字を取り除く「クリーニング」です。例えば、"washing machine" というクエリでは、ユーザーは通常 "washing machine" という単語だけの結果を期待するので、カンマ文字を無視することができる。

この仕組みの正確な方法は分かっておらず、各検索エンジンが独自に行っている。ほとんどが、データベースに登録された数十億のテキストの知識に基づいて、これらの調整を行う統計モデルに過ぎないと考えられている。

英語テープ起こしは、それ自体が科学でもあるので、ここでも基本的な説明しかしません。多くの場合、各単語にハイフン（辞書に載っている形）を付けて、その単語と一緒に検索すればよいので、検索エンジンはその単語が基本形（ユーザーが入力した形）だけでなく、屈折した形でも文書を見つけることができるという効果があり、非常に便利な機能である。この方法の問題点は、不明瞭で問題のある単語の屈折と、短い（そのため文脈から単語の屈折を判断できない）クエリの屈折にある。ゲーム」という言葉を、問題のある抑揚のある例として挙げてみましょう。

I love her "という英語のクエリがあった場合、下手な屈折器では "games "という単語を例えば "games, gaming, gaming room, ... "と屈折させてしまうので、周囲の単語をフレーズとしてインデックスし、なじみ深い状況でのみ屈折を行うか、別の手順を用いることも必要になる（ここでしばしば音声アルゴリズムの出番になる）。

最後のステップは、完成したツリーをベースサーチサーバーに送り、そこで実際のバレル検索を行うことである。これは次の章の主題である。

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:

Kontakt