Loading article…
検索エンジンのインデックス作成とは、迅速かつ正確な情報検索を容易にするために、データを収集、解析、保存するプロセスです。インデックス設計には、言語学、認知心理学、数学、情報科学、コンピュータ科学といった学際的な概念が取り入れられています。インターネット上のウェブページを検索するように設計された検索エンジンの文脈では、このプロセスはウェブインデックス作成とも呼ばれます。
人気の検索エンジンは、オンラインの自然言語文書の全文インデックス作成に重点を置いています。[ 1 ]画像、ビデオ、音声[ 2 ] 、グラフィック[ 3 ]などのメディアタイプも検索可能です。
メタ検索エンジンは他のサービスのインデックスを再利用し、ローカルインデックスを保存しませんが、キャッシュベースの検索エンジンはコーパスとともにインデックスを永続的に保存します。全文インデックスとは異なり、部分テキストサービスはインデックスの深さを制限してインデックスのサイズを小さくします。大規模なサービスは通常、必要な時間と処理コストのため、あらかじめ決められた時間間隔でインデックスを実行しますが、エージェントベースの検索エンジンはリアルタイムでインデックスを作成します。
インデックスを保存する目的は、検索クエリに関連する文書を迅速に見つけるための速度とパフォーマンスを最適化することです。インデックスがない場合、検索エンジンはコーパス内のすべての文書をスキャンすることになり、かなりの時間と計算能力が必要になります。例えば、10,000件の文書のインデックスであれば数ミリ秒以内にクエリを実行できますが、10,000件の大きな文書のすべての単語を順番にスキャンするには数時間かかる可能性があります。インデックスを保存するために必要な追加のコンピュータストレージ容量と、更新に必要な時間の著しい増加は、情報検索時の時間短縮というメリットとトレードオフの関係にあります。
検索エンジンのアーキテクチャを設計する際の主な要素は以下のとおりです。
検索エンジンのアーキテクチャは、さまざまな設計上の要件を満たすために、インデックスの作成方法やインデックスの保存方法において多様である。
検索エンジンの設計における大きな課題は、逐次処理の管理です。競合状態や一貫性障害が発生する可能性が数多くあります。たとえば、新しいドキュメントがコーパスに追加され、インデックスを更新する必要がありますが、同時にインデックスは検索クエリへの応答を継続する必要があります。これは、2 つの競合するタスク間の衝突です。著者は情報の生産者であり、Web クローラーはこの情報の消費者であり、テキストを取得してキャッシュ (またはコーパス) に保存します。順方向インデックスはコーパスによって生成された情報の消費者であり、逆方向インデックスは順方向インデックスによって生成された情報の消費者です。これは一般的に生産者-消費者モデルと呼ばれます。インデクサーは検索可能な情報の生産者であり、ユーザーは検索を必要とする消費者です。分散ストレージと分散処理を扱う場合、この課題はさらに大きくなります。インデックス化された情報の量を増やすために、検索エンジンのアーキテクチャは分散コンピューティングを採用することがあり、その場合、検索エンジンは連携して動作する複数のマシンで構成されます。これにより、非整合性の可能性が高まり、完全に同期された分散並列アーキテクチャを維持することがより困難になります。[ 13 ]
多くの検索エンジンは、検索クエリを評価する際に転置インデックスを組み込み、クエリ内の単語を含む文書を迅速に見つけ出し、関連性に基づいてこれらの文書をランク付けします。転置インデックスには各単語を含む文書のリストが格納されているため、検索エンジンは直接アクセスしてクエリ内の各単語に関連付けられた文書を見つけ出し、一致する文書を迅速に取得できます。以下は、転置インデックスの簡略化された図です。
このインデックスは、単語の頻度や位置に関する情報を格納しないため、特定の文書内に単語が存在するかどうかのみを判定できます。したがって、これはブールインデックスとみなされます。このようなインデックスは、クエリに一致する文書を決定しますが、一致した文書の順位付けは行いません。一部の設計では、インデックスには、各文書内の各単語の頻度や各文書内の単語の位置などの追加情報が含まれます。[ 14 ]位置情報により、検索アルゴリズムは単語の近接性を特定してフレーズの検索をサポートできます。頻度は、クエリに対する文書の関連性の順位付けに役立ちます。このようなトピックは、情報検索の中心的な研究対象です。
転置インデックスは、すべての単語が各ドキュメントに存在するわけではないため、疎行列です。コンピュータのストレージメモリ要件を削減するために、2 次元配列とは異なる方法で格納されます。インデックスは、潜在意味解析で使用される用語ドキュメント行列に似ています。転置インデックスは、ハッシュテーブルの一種と考えることができます。場合によっては、インデックスはバイナリツリーの一種であり、追加のストレージが必要ですが、検索時間を短縮できる可能性があります。大規模なインデックスでは、アーキテクチャは通常、分散ハッシュテーブルです。[ 15 ]
フレーズ検索では、位置インデックスと呼ばれる特殊な転置インデックスが使用されます。位置インデックスは、トークンを含むドキュメントのIDだけでなく、ポスティングリスト内のドキュメント内のトークンの正確な位置も格納します。クエリで指定されたフレーズの出現箇所は、これらのポスティングリストをナビゲートし、目的の用語が期待される順序（フレーズ内の順序と同じ）で出現するインデックスを特定することによって取得されます。したがって、「First Witch」というフレーズの出現箇所を検索する場合は、次のようになります。
投稿リストは、この手順の時間計算量を最小限に抑えるために、二分探索を使用してナビゲートできます。[ 16 ]
転置インデックスは、マージまたは再構築によって埋められます。再構築はマージに似ていますが、最初に転置インデックスの内容を削除します。アーキテクチャは増分インデックス作成をサポートするように設計されている場合があり、[ 17 ]マージでは追加または更新するドキュメントを識別し、各ドキュメントを単語に解析します。技術的な正確さを期すために、マージでは、通常仮想メモリに存在する新しくインデックス化されたドキュメントと、1 つ以上のコンピュータハードドライブに存在するインデックスキャッシュを統合します。
解析後、インデクサーは参照された文書を該当する単語の文書リストに追加します。大規模な検索エンジンでは、転置インデックス内の各単語を検索して（文書内に出現したことを報告するため）処理に時間がかかりすぎる場合があるため、この処理は通常、順方向インデックスの作成と、順方向インデックスの内容を転置インデックスに並べ替える処理の2つの部分に分割されます。転置インデックスは、順方向インデックスを反転させたものであるため、そのように名付けられています。
フォワードインデックスには、各文書に対応する単語のリストが格納されます。以下は、フォワードインデックスの簡略化された例です。
順方向インデックスを開発する根拠は、ドキュメントが解析される際に、ドキュメントごとに単語を中間的に保存する方が良いという点にある。この区分けにより、非同期システム処理が可能になり、転置インデックス更新のボトルネックを部分的に回避できる。[ 18 ]順方向インデックスは、転置インデックスに変換するためにソートされる。順方向インデックスは基本的に、ドキュメントと単語のペアのリストであり、ドキュメントごとに照合される。順方向インデックスを転置インデックスに変換するには、単語ごとにペアをソートするだけでよい。この点において、転置インデックスは単語でソートされた順方向インデックスである。
大規模な検索エンジンのインデックスを生成または維持することは、ストレージと処理において大きな課題となります。多くの検索エンジンは、ディスク上のインデックスのサイズを小さくするために圧縮方式を利用しています。[ 19 ]全文検索を行うインターネット検索エンジンの次のシナリオを考えてみましょう。
このシナリオでは、 20億のウェブページに対して非圧縮インデックス（非統合のシンプルなインデックスを想定）を保存するには、5000億語のエントリが必要になります。1文字あたり1バイト、つまり1語あたり5バイトとすると、これだけで2500ギガバイトのストレージ容量が必要になります。耐障害性のある分散ストレージアーキテクチャの場合、この容量要件はさらに大きくなる可能性があります。選択する圧縮技術によっては、インデックスのサイズをこのサイズの数分の一にまで縮小できます。ただし、圧縮と解凍に必要な時間と処理能力がトレードオフとなります。
特に、大規模な検索エンジンの設計には、ストレージのコストだけでなく、ストレージを稼働させるための電気代も含まれる。したがって、圧縮はコストの一指標となる。
文書解析は、文書やその他のメディアの構成要素（単語）を分解し、順方向および逆方向のインデックスに挿入します。見つかった単語はトークンと呼ばれ、検索エンジンのインデックス作成や自然言語処理の文脈では、解析はトークン化と呼ばれることが一般的です。また、単語境界の曖昧性解消、タグ付け、テキスト分割、コンテンツ分析、テキスト分析、テキストマイニング、コンコーダンス生成、音声分割、レキシング、または語彙分析と呼ばれることもあります。「インデックス作成」、「解析」、「トークン化」という用語は、企業スラングでは互換的に使用されます。
自然言語処理は、継続的な研究と技術改良の対象となっています。トークン化は、質の高い検索をサポートするために文書から必要な情報を抽出してインデックスを作成する際に、多くの課題を伴います。インデックス作成のためのトークン化には複数の技術が用いられますが、その実装方法は一般的に企業秘密として扱われています。
文字を理解できる人間とは異なり、コンピュータは自然言語文書の構造を理解できず、単語や文を自動的に認識することはできません。コンピュータにとって、文書は単なるバイト列です。コンピュータは、文書内でスペース文字が単語を区切っていることを「認識」しません。そのため、人間はコンピュータに、トークンと呼ばれる個々の単語を識別するようにプログラムする必要があります。このようなプログラムは、一般的にトークナイザー、パーサー、またはレクサーと呼ばれます。多くの検索エンジンやその他の自然言語処理ソフトウェアには、YACCやLexなどの構文解析専用プログラムが組み込まれています。
トークン化の過程で、パーサーは単語や句読点などの要素を表す文字シーケンスを識別します。句読点は数値コードで表され、その中には印刷されない制御文字も含まれます。パーサーは、電子メールアドレス、電話番号、URLなどのエンティティも識別できます。各トークンを識別する際には、トークンの大文字・小文字、混合、固有表現、言語またはエンコーディング、語彙カテゴリ（品詞、「名詞」や「動詞」など）、位置、文番号、文中の位置、長さ、行番号など、いくつかの特性が保存される場合があります。
検索エンジンが複数の言語をサポートしている場合、トークン化の一般的な最初のステップは、各ドキュメントの言語を識別することです。その後の多くのステップは言語に依存します (ステミングや品詞タグ付けなど)。言語認識は、コンピュータ プログラムがドキュメントの言語を自動的に識別または分類しようとするプロセスです。言語認識の他の名称には、言語分類、言語分析、言語識別、言語タグ付けなどがあります。自動言語認識は、自然言語処理における継続的な研究の対象です。単語がどの言語に属するかを見つけるには、言語認識チャートの使用が必要になる場合があります。
検索エンジンが複数のドキュメント形式をサポートしている場合、ドキュメントはトークン化のために準備する必要があります。課題は、多くのドキュメント形式がテキストコンテンツに加えて書式情報を含んでいることです。たとえば、HTMLドキュメントには、改行、太字強調、フォントサイズやスタイルなどの書式情報を指定する HTML タグが含まれています。検索エンジンがコンテンツと「マークアップ」の違いを無視すると、不要な情報がインデックスに含まれてしまい、検索結果が悪くなります。フォーマット分析とは、ドキュメントに埋め込まれた書式コンテンツを識別して処理することです。書式コンテンツは、ドキュメントがコンピュータ画面にレンダリングされる方法やソフトウェアプログラムによって解釈される方法を制御します。フォーマット分析は、構造分析、フォーマット解析、タグ除去、フォーマット除去、テキスト正規化、テキストクリーニング、テキスト準備とも呼ばれます。フォーマット分析の課題は、さまざまなファイル形式の複雑さによってさらに複雑になります。特定のファイル形式は独自仕様で情報がほとんど公開されていませんが、他のファイル形式は十分に文書化されています。多くの検索エンジンがサポートする、一般的で十分に文書化されたファイル形式には、次のものがあります。
さまざまなフォーマットに対応するための選択肢としては、そのフォーマットを開発、維持、または所有している組織が提供する、一般に利用可能な商用解析ツールを使用すること、およびカスタムパーサーを作成することが挙げられます。
一部の検索エンジンは、圧縮または暗号化されたファイル形式で保存されたファイルの検査をサポートしています。圧縮形式を扱う場合、インデクサーはまずドキュメントを解凍します。この手順により、1つまたは複数のファイルが生成され、それぞれを個別にインデックス化する必要があります。一般的にサポートされている圧縮ファイル形式には、次のものがあります。
フォーマット分析では、インデックスに「不適切な情報」が含まれないようにするための品質改善手法を用いることができます。コンテンツは、フォーマット情報を操作して追加コンテンツを含めることができます。スパムデキシングのためにドキュメントのフォーマットを悪用する例：
一部の検索エンジンは、トークン化の前に、文書の主要部分を識別するセクション認識を組み込んでいます。コーパス内のすべての文書が、整理された章とページに分かれた、よく書かれた本のように読めるわけではありません。ニュースレターや企業レポートなど、 Web上の多くの文書には、誤った内容や、主要な内容 (文書の主題) を含まないサイドセクションが含まれています。たとえば、Wikipedia Web サイトの記事には、他の Web ページへのリンクを含むサイド メニューが表示されます。HTML や PDF などの一部のファイル形式では、コンテンツを列で表示できます。コンテンツがビューの異なる領域に表示またはレンダリングされていても、生のマークアップ コンテンツにはこの情報が順番に格納されている場合があります。生のソース コンテンツに順番に現れる単語は、これらの文や段落がコンピュータ画面の異なる場所にレンダリングされていても、順番にインデックス化されます。検索エンジンがこのコンテンツを通常のコンテンツであるかのようにインデックス化すると、混在したコンテンツと不適切な単語の近接性により、インデックスの品質と検索品質が低下する可能性があります。主な問題点は 2 つあります。
セクション分析では、検索エンジンが各ドキュメントのレンダリングロジック（実質的には実際のドキュメントの抽象的な表現）を実装し、その表現をインデックス化する必要がある場合があります。たとえば、インターネット上のコンテンツの中には、JavaScript を介してレンダリングされるものがあります。検索エンジンがページをレンダリングしてページ内の JavaScript を評価しない場合、検索エンジンはこのコンテンツを同じように「認識」できず、ドキュメントを誤ってインデックス化してしまう可能性があります。一部の検索エンジンはレンダリングの問題を気にしないため、多くのウェブページデザイナーは、JavaScript を介してコンテンツを表示することを避けるか、ウェブページが適切にインデックス化されるように Noscript タグを使用します。同時に、この事実は、検索エンジンのインデクサーが閲覧者とは異なるコンテンツを「認識」するように仕向けるために悪用される可能性もあります。
インデックス作成では、優先順位を整理するためにHTMLタグを認識する必要があることがよくあります。優先順位の低いものから高いマージンを持つものまで、strongやlinkなどのラベルにインデックスを作成して優先順位の順序を最適化しても、これらのラベルがテキストの先頭にある場合は関連性がないことが判明する可能性があります。GoogleやBingなどの一部のインデクサーは、強力なタイプシステムとの互換性により、検索エンジンが長いテキストを関連ソースとして認識しないようにしています。 [ 22 ]
メタタグのインデックス作成は、Web コンテンツの整理と分類において重要な役割を果たします。特定のドキュメントには、作成者、キーワード、説明、言語などのメタ情報が埋め込まれていることがよくあります。HTML ページの場合、メタタグにはインデックスにも含まれるキーワードが含まれています。以前のインターネット検索エンジン技術では、前方インデックスのためにメタタグ内のキーワードのみがインデックス化され、ドキュメント全体が解析されることはありませんでした。当時、全文インデックス作成はそれほど確立されておらず、コンピュータ ハードウェアもそのような技術をサポートできませんでした。HTML マークアップ言語の設計には、トークン化を必要とせずに適切かつ容易にインデックス化されることを目的として、メタタグのサポートが当初含まれていました。[ 23 ]
1990年代にインターネットが普及するにつれ、多くの実店舗を持つ企業が「オンライン」に進出し、企業ウェブサイトを開設しました。ウェブページ（その多くは製品パンフレットのような企業向けウェブページでした）を説明するために使用されるキーワードは、説明的なものから、特定の検索クエリに対する検索結果の上位にウェブページを表示させることで売上を促進することを目的としたマーケティング指向のキーワードへと変化しました。これらのキーワードが主観的に指定されていたため、スパムデキシングが発生し、1990年代には多くの検索エンジンが全文インデックス技術を採用するに至りました。検索エンジンの設計者や企業は、ウェブページのコンテンツに「マーケティングキーワード」を詰め込みすぎると、興味深く有用な情報がすべて失われてしまうという限界がありました。ユーザー中心で「定着する」ウェブサイトを設計するというビジネス目標との利害の衝突を考慮し、顧客生涯価値の計算式は、訪問者の定着を期待して、ウェブサイトに有用なコンテンツをより多く組み込むように変更されました。この意味で、全文インデックス作成はより客観的であり、検索エンジンの結果の順位付けに対する主観的な制御からさらに一歩遠ざかることで、検索エンジンの結果の質を高め、ひいては全文インデックス作成技術の研究を促進した。
デスクトップ検索では、多くのソリューションがメタタグを組み込んでおり、ファイルの内容からは明らかにならないさまざまなファイルのコンテンツを検索エンジンがどのようにインデックス化するかを、作成者がさらにカスタマイズできるようにしています。デスクトップ検索はユーザーの制御下に置かれることが多いのに対し、インターネット検索エンジンは全文インデックスに重点を置く必要があります。