検索エンジンのインデックス作成

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

検索エンジンのインデックス作成は、データの収集、解析、および保存であり、高速で正確な情報検索を容易にします。インデックスデザインには、言語学、認知心理学、数学、情報学、およびコンピュータサイエンスからの学際的な概念が組み込まれています。インターネット上のWebページを検索するように設計された検索エンジンのコンテキストでのプロセスの別名は、Webインデックスです。

人気のあるエンジンは、オンラインの自然言語ドキュメントのフルテキストインデックス作成に重点を置いています。[1] ビデオ、[2]オーディオ、[3]、グラフィックス[4]などのメディアタイプも検索できます。

メタ検索エンジンは他のサービスのインデックスを再利用し、ローカルインデックスを保存しませんが、キャッシュベースの検索エンジンはコーパスとともにインデックスを永続的に保存しますフルテキストインデックスとは異なり、パーシャルテキストサービスはインデックスサイズを減らすためにインデックスの深さを制限します。大規模なサービスは通常、必要な時間と処理コストのために所定の時間間隔でインデックス作成を実行しますが、エージェントベースの検索エンジンはリアルタイムでインデックス作成します。

索引付け

インデックスを保存する目的は、検索クエリに関連するドキュメントを見つける際の速度とパフォーマンスを最適化することです。インデックスがないと、検索エンジンはコーパス内のすべてのドキュメントをスキャンするため、かなりの時間と計算能力が必要になります。たとえば、10,000のドキュメントのインデックスは数ミリ秒以内にクエリできますが、10,000の大きなドキュメントのすべての単語を順次スキャンすると数時間かかる場合があります。インデックスを保存するために必要な追加のコンピュータストレージ、および更新が行われるのに必要な時間の大幅な増加は、情報検索中に節約された時間と引き換えになります。

インデックスデザインファクター

検索エンジンのアーキテクチャを設計する際の主な要因は次のとおりです。

マージファクター
データがインデックスに入力される方法、またはテキストコーパストラバーサル中に単語または主題の特徴がインデックスに追加される方法、および複数のインデクサーが非同期で機能できるかどうか。インデクサーは、最初に古いコンテンツを更新しているか、新しいコンテンツを追加しているかを確認する必要があります。トラバーサルは通常、データ収集ポリシーに関連しています。検索エンジンインデックスのマージは、 SQLマージコマンドやその他のマージアルゴリズムと概念が似ています。[5]
ストレージ技術
インデックスデータの保存方法、つまり、情報をデータ圧縮するかフィルタリングするか。
インデックスサイズ
インデックスをサポートするために必要なコンピューターストレージの量。
ルックアップ速度
転置インデックスで単語がどれだけ早く見つかるかデータ構造内のエントリを見つける速度は、更新または削除できる速度と比較して、コンピュータサイエンスの中心的な焦点です。
メンテナンス
インデックスが時間の経過とともにどのように維持されるか。[6]
フォールトトレランス
サービスの信頼性はどれほど重要か。問題には、インデックスの破損の処理、不良データを分離して処理できるかどうかの判断、不良ハードウェアの処理、パーティショニング、ハッシュベースまたはコンポジットパーティショニングなどのスキーム[7]、およびレプリケーションが含まれます。

インデックスデータ構造

検索エンジンのアーキテクチャは、さまざまな設計要素を満たすために、インデックス作成の実行方法とインデックスストレージの方法が異なります。

接尾辞木
木のように比喩的に構造化され、線形時間ルックアップをサポートします。単語の接尾辞を保存することによって構築されます。接尾辞木はトライの一種です。試行は拡張可能なハッシュをサポートします。これは検索エンジンのインデックス作成にとって重要です。[8] DNA配列のパターンの検索とクラスタリングに使用されます。主な欠点は、ツリーに単語を格納すると、単語自体を格納するために必要なスペースを超えるスペースが必要になる場合があることです。[9]代替表現は接尾辞配列であり、これはより少ない仮想メモリを必要とすると考えられ、 BWTアルゴリズムなどのデータ圧縮をサポートします。
転置インデックス
各アトミック検索基準の出現リスト[10]を、通常はハッシュテーブルまたはバイナリツリーの形式で格納します。[11] [12]
引用索引
計量書誌学の主題である引用分析をサポートするために、ドキュメント間の引用またはハイパーリンクを保存します。
nグラムインデックス
他のタイプの検索またはテキストマイニングをサポートするために、データの長さのシーケンスを格納します[13]
文書用語マトリックス
潜在意味解析で使用され、ドキュメント内の単語の出現を2次元のスパース行列に格納します。

並列処理の課題

検索エンジンの設計における主要な課題は、シリアルコンピューティングプロセスの管理です。競合状態やコヒーレントな障害には多くの機会があります。たとえば、新しいドキュメントがコーパスに追加され、インデックスを更新する必要がありますが、同時にインデックスは検索クエリに応答し続ける必要があります。これは、2つの競合するタスク間の衝突です。著者は情報の作成者であり、Webクローラーはこの情報の利用者であり、テキストを取得してキャッシュ(またはコーパス)に保存するとします。フォワードインデックスはコーパスによって生成された情報の消費者であり、転置インデックスはフォワードインデックスによって生成された情報の消費者です。これは一般的に生産者/消費者モデルインデクサーは検索可能な情報のプロデューサーであり、ユーザーは検索する必要のあるコンシューマーです。分散ストレージと分散処理を使用する場合、課題はさらに大きくなります。大量のインデックス付き情報に合わせて拡張するために、検索エンジンのアーキテクチャには分散コンピューティングが含まれる場合があります。この場合、検索エンジンは、同時に動作する複数のマシンで構成されます。これにより、一貫性が失われる可能性が高くなり、完全に同期された分散並列アーキテクチャを維持することがより困難になります。[14]

転置インデックス

多くの検索エンジンは、検索クエリを評価するときに転置インデックスを組み込んで、クエリ内の単語を含むドキュメントをすばやく見つけ、関連性によってこれらのドキュメントをランク付けします。転置インデックスには各単語を含むドキュメントのリストが格納されるため、検索エンジンは直接アクセスを使用してクエリ内の各単語に関連付けられたドキュメントを検索し、一致するドキュメントをすばやく取得できます。以下は、転置インデックスの簡略図です。

転置インデックス
ドキュメント
the ドキュメント1、ドキュメント3、ドキュメント4、ドキュメント5、ドキュメント7
ドキュメント2、ドキュメント3、ドキュメント4
言う 文書5
moo 文書7

このインデックスは、単語の頻度と位置に関する情報を格納しないため、特定のドキュメント内に単語が存在するかどうかを判断することしかできません。したがって、ブールインデックスと見なされます。このようなインデックスは、どのドキュメントがクエリに一致するかを決定しますが、一致するドキュメントはランク付けしません。一部の設計では、インデックスには、各ドキュメント内の各単語の頻度や各ドキュメント内の単語の位置などの追加情報が含まれています。[15]位置情報により、検索アルゴリズムは単語の近接性を識別して、フレーズの検索をサポートできます。頻度は、クエリに対するドキュメントの関連性をランク付けするのに役立ちます。このようなトピックは、情報検索の中心的な研究の焦点です

各ドキュメントにすべての単語が含まれているわけではないため、転置インデックスはスパース行列です。コンピュータのストレージメモリ要件を減らすために、2次元配列とは異なる方法で保存されますインデックスは、潜在意味解析で使用されるドキュメントマトリックスという用語に似ています転置インデックスは、ハッシュテーブルの形式と見なすことができます。場合によっては、インデックスはバイナリツリーの形式であり、追加のストレージが必要ですが、ルックアップ時間が短縮される可能性があります。より大きなインデックスでは、アーキテクチャは通常、分散ハッシュテーブルです。[16]

インデックスのマージ

転置インデックスは、マージまたは再構築によって埋められます。再構築はマージに似ていますが、最初に転置インデックスの内容を削除します。アーキテクチャは、インクリメンタルインデックスをサポートするように設計できます[17]。マージでは、追加または更新する1つまたは複数のドキュメントを識別し、各ドキュメントを単語に解析します。技術的な正確さのために、マージは、通常は仮想メモリに存在する新しくインデックス付けされたドキュメントを、1つ以上のコンピューターのハードドライブに存在するインデックスキャッシュと統合します。

解析後、インデクサーは参照されたドキュメントを適切な単語のドキュメントリストに追加します。大規模な検索エンジンでは、転置インデックス内の各単語を検索するプロセス(ドキュメント内で発生したことを報告するため)に時間がかかりすぎる可能性があるため、このプロセスは通常2つの部分に分割されます。フォワードインデックスと、フォワードインデックスの内容をインバーテッドインデックスにソートするプロセス。転置インデックスは、順インデックスの反転であるため、そのように名付けられています。

フォワードインデックス

フォワードインデックスは、各ドキュメントの単語のリストを格納します。以下は、フォワードインデックスの簡略化された形式です。

フォワードインデックス
書類 言葉
ドキュメント1 the、cow、says、moo
ドキュメント2 the、cat、and、the、hat
ドキュメント3 the、dish、ran、away、with、the、spoon

フォワードインデックスを開発する理由は、ドキュメントが解析されるときに、ドキュメントごとに単語を中間的に保存する方がよいということです。この描写により、非同期システム処理が可能になり、転置インデックス更新のボトルネックが部分的に回避されます。[18]順方向インデックスは、転置インデックスに変換するためにソートされます。フォワードインデックスは、基本的に、ドキュメントと単語で構成されるペアのリストであり、ドキュメントによって照合されます。順インデックスを転置インデックスに変換するのは、単語でペアを並べ替えるだけです。この点で、転置インデックスは単語でソートされたフォワードインデックスです。

圧縮

大規模な検索エンジンインデックスを生成または維持することは、ストレージと処理に関する重大な課題です。多くの検索エンジンは、圧縮の形式を利用して、ディスク上のインデックスのサイズを縮小します[19]全文インターネット検索エンジンについて、次のシナリオを検討してください。

このシナリオを考えると、20億のWebページの非圧縮インデックス(非圧縮の単純なインデックスを想定は、5,000億の単語エントリを格納する必要があります。1文字あたり1バイト、または1ワードあたり5バイトの場合、これには2500ギガバイトのストレージスペースだけが必要になります。このスペース要件は、フォールトトレラントな分散ストレージアーキテクチャの場合はさらに大きくなる可能性があります。選択した圧縮手法に応じて、インデックスをこのサイズの何分の1かに減らすことができます。トレードオフは、圧縮と解凍を実行するために必要な時間と処理能力です。

特に、大規模な検索エンジンの設計には、ストレージのコストと、ストレージに電力を供給するための電力のコストが組み込まれています。したがって、圧縮はコストの尺度です。

ドキュメントの解析

ドキュメントの解析では、ドキュメントまたは他の形式のメディアのコンポーネント(単語)を分解して、転置インデックスと転置インデックスに挿入します。見つかった単語はトークンと呼ばれるため、検索エンジンのインデックス作成と自然言語処理のコンテキストでは、構文解析はより一般的にトークン化と呼ばれます。また、単語境界の明確化、タグ付けテキストセグメンテーションコンテンツ分析、テキスト分析、テキストマイニング一致生成、音声セグメンテーション字句解析、または字句解析と呼ばれることもあります。「索引付け」、「構文解析」、および「トークン化」という用語は、企業用語では同じ意味で使用されます。

自然言語処理は、継続的な研究と技術改善の対象です。トークン化は、質の高い検索をサポートするために、インデックス作成のためにドキュメントから必要な情報を抽出する際に多くの課題を提示します。インデックス作成のトークン化には複数のテクノロジが含まれ、その実装は通常、企業の秘密として保持されます。[要出典]

自然言語処理の課題

単語の境界のあいまいさ
英語を母国語とする人は、最初はトークン化を簡単な作業と見なすかもしれませんが、多言語インデクサーを設計する場合はそうではありません。デジタル形式では、中国語日本語アラビア語などの他の言語のテキストは、単語が空白で明確に描写されていないため、より大きな課題を表しますトークン化中の目標は、ユーザーが検索する単語を特定することです。言語固有のロジックを使用して、単語の境界を適切に識別します。これは、サポートされている各言語(または同様の境界マーカーと構文を持つ言語のグループ)のパーサーを設計する理由となることがよくあります。
言語のあいまいさ
一致するドキュメントを適切にランク付けするために[22] 、多くの検索エンジンは、言語や品詞品詞)など、各単語に関する追加情報を収集します構文は言語によって異なるため、これらの手法は言語に依存します。ドキュメントは、ドキュメントの言語を常に明確に識別したり、正確に表現したりするわけではありません。ドキュメントをトークン化する際に、一部の検索エンジンはドキュメントの言語を自動的に識別しようとします。
多様なファイル形式
ドキュメントのどのバイトが文字を表すかを正しく識別するには、ファイル形式を正しく処理する必要があります。複数のファイル形式をサポートする検索エンジンは、ドキュメントを正しく開いてアクセスでき、ドキュメントの文字をトークン化できる必要があります。
障害のあるストレージ
自然言語データの品質は必ずしも完璧ではない場合があります。特にインターネット上の不特定の数のドキュメントは、適切なファイルプロトコルに厳密に従っていません。バイナリ文字は、ドキュメントのさまざまな部分に誤ってエンコードされる可能性があります。これらの文字の認識と適切な処理がないと、インデックスの品質またはインデクサのパフォーマンスが低下する可能性があります。

トークン化

読み書きのできる人間とは異なり、コンピューターは自然言語の文書の構造を理解せず、単語や文を自動的に認識できません。コンピュータにとって、ドキュメントは単なるバイトのシーケンスです。コンピュータは、スペース文字がドキュメント内の単語を区切ることを「認識」していません。代わりに、人間は、トークンと呼ばれる個々の単語または個別の単語を構成するものを識別するようにコンピューターをプログラムする必要があります。このようなプログラムは、一般に、トークナイザーパーサー、またはレクサーと呼ばれます。多くの検索エンジンやその他の自然言語処理ソフトウェアには、YACCLexなどの解析専用プログラムが組み込まれています。

トークン化中に、パーサーは、単語や句読点などの他の要素を表す文字のシーケンスを識別します。これらの要素は、数値コードで表され、一部は非印刷制御文字です。パーサーは、電子メールアドレス、電話番号、URLなどのエンティティを識別することもできます。各トークンを識別するとき、トークンの大文字小文字(上、下、混合、適切)、言語またはエンコーディング、語彙カテゴリ(「名詞」や「動詞」などの品詞)、位置、文など、いくつかの特性が保存される場合があります。数、品詞、長さ、行番号。

言語認識

検索エンジンが複数の言語をサポートしている場合、トークン化中の一般的な最初のステップは、各ドキュメントの言語を識別することです。後続の手順の多くは言語に依存します(ステミング品詞のタグ付けなど)。言語認識は、コンピュータプログラムがドキュメントの言語を自動的に識別または分類しようとするプロセスです。言語認識の他の名前には、言語分類、言語分析、言語識別、および言語タグ付けが含まれます。自動言語認識は、自然言語処理の継続的な研究の対象です単語がどの言語に属しているかを見つけるには、言語認識チャートを使用する必要があります

フォーマット分析

検索エンジンが複数のドキュメント形式をサポートしている場合は、トークン化のためにドキュメントを準備する必要があります。課題は、多くのドキュメント形式にテキストコンテンツに加えてフォーマット情報が含まれていることです。たとえば、HTMLドキュメントには、改行の開始、太字の強調、フォントのサイズやスタイルなどの書式設定情報を指定するHTMLタグが含まれています。検索エンジンがコンテンツと「マークアップ」の違いを無視すると、無関係な情報がインデックスに含まれ、検索結果が低下します。フォーマット分析は、ドキュメントに埋め込まれたフォーマットコンテンツの識別と処理であり、ドキュメントがコンピュータ画面にレンダリングされる方法やソフトウェアプログラムによって解釈される方法を制御します。フォーマット分析は、構造分析、フォーマット解析、タグストリッピング、フォーマットストリッピング、テキスト正規化、テキストクリーニング、およびテキスト準備とも呼ばれます。フォーマット分析の課題は、さまざまなファイルフォーマットの複雑さによってさらに複雑になっています。一部のファイル形式は独自のものであり、情報はほとんど開示されていませんが、他の形式は十分に文書化されています。多くの検索エンジンがサポートする一般的な、十分に文書化されたファイル形式には、次のものがあります。

さまざまな形式を処理するためのオプションには、形式を開発、維持、または所有する組織によって提供される公開されている商用の解析ツールの使用、およびカスタムパーサーの作成が含まれます。

一部の検索エンジンは、圧縮または暗号化されたファイル形式で保存されているファイルの検査をサポートしています。圧縮形式で作業する場合、インデクサーは最初にドキュメントを解凍します。この手順により、1つ以上のファイルが作成される場合があり、各ファイルには個別にインデックスを付ける必要があります。一般的にサポートされている圧縮ファイル形式は次のとおりです。

フォーマット分析には、インデックスに「悪い情報」が含まれないようにするための品質改善方法が含まれる場合があります。コンテンツは、フォーマット情報を操作して、追加のコンテンツを含めることができます。スパムデキシングのためにドキュメントのフォーマットを悪用する例

  • 書式設定を使用して、コンピューター画面には表示されないがインデクサーには表示されるセクションに数百または数千の単語を含める(たとえばHTMLの非表示の「div」タグ。CSSまたはJavaScriptの使用を組み込むことができます)。それで)。
  • 単語の前景色を背景色と同じに設定し、コンピューター画面上でドキュメントを表示している人には単語を非表示にしますが、インデクサーには非表示にしません。

セクション認識

一部の検索エンジンには、トークン化の前に、セクション認識、つまりドキュメントの主要部分の識別が組み込まれています。コーパス内のすべてのドキュメントが、整理された章とページに分割された、よく書かれた本のように読まれるわけではありません。Web上の多くのドキュメント、ニュースレターや企業レポートなどには、主要な資料(ドキュメントの内容)を含まない誤ったコンテンツやサイドセクションが含まれています。たとえば、この記事には、他のWebページへのリンクを含むサイドメニューが表示されます。HTMLやPDFなどの一部のファイル形式では、コンテンツを列に表示できます。コンテンツがビューのさまざまな領域に表示またはレンダリングされている場合でも、生のマークアップコンテンツはこの情報を順番に格納する場合があります。これらの文と段落がコンピューター画面の異なる部分にレンダリングされている場合でも、生のソースコンテンツに順番に表示される単語は順番に索引付けされます。検索エンジンがこのコンテンツを通常のコンテンツであるかのようにインデックスに登録すると、コンテンツが混在し、単語が不適切に近接しているため、インデックスの品質と検索品質が低下する可能性があります。

  • 異なるセクションのコンテンツは、実際には関連していないのに、インデックスでは関連しているものとして扱われます。
  • 組織の「サイドバー」コンテンツはインデックスに含まれていますが、サイドバーコンテンツはドキュメントの意味に寄与せず、インデックスはそのドキュメントの不十分な表現で埋められています。

セクション分析では、検索エンジンが各ドキュメントのレンダリングロジック(基本的には実際のドキュメントの抽象的な表現)を実装し、代わりに表現にインデックスを付ける必要がある場合があります。たとえば、インターネット上の一部のコンテンツはJavaScriptを介してレンダリングされます。検索エンジンがページをレンダリングせず、ページ内のJavaScriptを評価しない場合、同じ方法でこのコンテンツを「表示」せず、ドキュメントのインデックスを誤って作成します。一部の検索エンジンはレンダリングの問題を気にしないため、多くのWebページ設計者はJavaScriptを介したコンテンツの表示を回避するか、Noscriptタグを使用してWebページが適切にインデックス付けされるようにします。同時に、この事実を利用して、検索エンジンのインデクサーにビューアとは異なるコンテンツを「表示」させることもできます。

HTML優先システム

インデックス作成では、優先順位を整理するためにHTMLタグを認識しなければならないことがよくあります。優先度の低いものからマージンの高いものへのインデックス付けは、それらのラベルがテキストの先頭にある場合に優先度の順序を最適化するために強いリンクのようなラベルに関連性があることを証明できませんでした。GoogleBingなどの一部のインデクサーは、タイプシステムとの互換性が高いため検索エンジンが大きなテキストを関連するソースとして受け取らないようにしています。[23]

メタタグのインデックス作成

特定のドキュメントには、作成者、キーワード、説明、言語などのメタ情報が埋め込まれていることがよくあります。HTMLページの場合、メタタグには、インデックスにも含まれるキーワードが含まれます。以前のインターネット検索エンジンテクノロジーは、フォワードインデックスのメタタグ内のキーワードのみをインデックスに登録していました。ドキュメント全体は解析されません。当時、全文索引は十分に確立されておらず、コンピューターハードウェアもそのような技術をサポートできませんでした。HTMLマークアップ言語の設計には、トークン化を必要とせずに、適切かつ簡単にインデックスを作成するという目的のために、当初はメタタグのサポートが含まれていました。[24]

インターネットが1990年代に成長するにつれて、多くの実店舗の企業が「オンライン」になり、企業のWebサイトを確立しました。ウェブページを説明するために使用されるキーワード(その多くは製品パンフレットに似た企業向けのウェブページでした)は、特定の検索クエリの検索結果の上位にウェブページを配置することで売り上げを伸ばすように設計された説明的なキーワードからマーケティング指向のキーワードに変更されました。これらのキーワードが主観的に指定されたという事実は、スパムデキシングにつながりました、1990年代に多くの検索エンジンが全文索引技術を採用するようになりました。検索エンジンの設計者や企業は、ウェブページのコンテンツに非常に多くの「マーケティングキーワード」を配置してから、興味深く有用な情報をすべて削除するしかありませんでした。「スティッキー」なユーザー指向のWebサイトを設計するというビジネス目標との利害の対立を考慮して、顧客生涯価値の方程式は、訪問者を維持することを期待して、より有用なコンテンツをWebサイトに組み込むように変更されました。この意味で、全文索引付けはより客観的であり、検索エンジン結果の配置の主観的な制御からさらに一歩離れたため、検索エンジン結果の品質が向上しました。これにより、全文索引付けテクノロジーの研究がさらに進みました。

デスクトップ検索では、多くのソリューションにメタタグが組み込まれており、作成者がファイルのコンテンツからは明らかではないさまざまなファイルのコンテンツを検索エンジンがインデックス付けする方法をさらにカスタマイズする方法を提供します。デスクトップ検索はユーザーの管理下にありますが、インターネット検索エンジンは全文索引に重点を置く必要があります。

も参照してください

参考文献

  1. ^ Clarke、C.、Cormack、G .:分散フルテキスト検索システムの動的転置インデックス。TechRep MT-95-01、ウォータールー大学、1995年2月。
  2. ^ Sikos、LF(2016年8月)。「次世代ビデオインデックス作成のためのリンクトデータへのコンセプトマッピングを備えたRDFを利用したセマンティックビデオ注釈ツール」マルチメディアツールとアプリケーション土井10.1007 / s11042-016-3705-7
  3. ^ http://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf
  4. ^ チャールズ・E・ジェイコブス、アダム・フィンケルスタイン、デビッド・H・サレシン。高速多重解像度画像クエリワシントン大学コンピュータサイエンス工学部。1995年。2006年12月に検証済み
  5. ^ ブラウン、EW:全文情報検索における実行パフォーマンスの問題。マサチューセッツ大学アマースト校コンピュータサイエンス学部、テクニカルレポート95-81、1995年10月。
  6. ^ カッティング、D。、ペダーセン、J .:動的転置インデックスメンテナンスの最適化。SIGIRの議事録、405-411、1990。
  7. ^ 線形ハッシュ分割MySQL5.1リファレンスマニュアル。2006年12月に検証済み
  8. ^ トライアルゴリズムとデータ構造の辞書米国国立標準技術研究所
  9. ^ ガスフィールド、ダン(1999)[1997]。文字列、ツリー、シーケンスのアルゴリズム:コンピュータサイエンスと計算生物学アメリカ:ケンブリッジ大学出版局。ISBN 0-521-58519-8
  10. ^ Black、Paul E.、転置インデックスアルゴリズムとデータ構造の辞書米国国立標準技術研究所、 2006年10月。2006年12月に検証済み。
  11. ^ CC Foster、情報検索:AVLツリーを使用した情報の保存と検索、1965年第20回全国会議の議事録、p.192-205、1965年8月24〜26日、米国オハイオ州クリーブランド
  12. ^ ウィスコンシン州ランダウアー:バランスの取れたツリーと情報検索におけるその利用。IEEETrans。電子コンピュータ、Vol。EC-12、No。6、1963年12月。
  13. ^ LDCカタログで販売されているGoogleNgramデータセット
  14. ^ ジェフリーディーンとサンジャイゲマワット。MapReduce:大規模クラスターでの簡素化されたデータ処理。Google、Inc.OSDI。2004年。
  15. ^ グロスマン、フリーダー、ゴハリアン。転置インデックスのIRの基本2002年。2011年8月に検証。
  16. ^ 唐、フンチャン。ドワルカダス、サンディヤ「効率的なピアツーピア情報検索のためのハイブリッドグローバルローカルインデックス」。ロチェスター大学。ページ1。http://www.cs.rochester.edu/u/sandhya/papers/nsdi04.ps
  17. ^ Tomasic、A.、et al .:テキストドキュメント検索のための転置リストのインクリメンタルアップデート。スタンフォード大学コンピュータサイエンステクニカルノートSTAN-CS-TN-93-1のショートバージョン、1993年12月。
  18. ^ セルゲイブリンとローレンスページ。大規模なハイパーテキストWeb検索エンジンの構造スタンフォード大学1998年。2006年12月に検証。
  19. ^ HSヒープ。ドキュメントデータベースの圧縮コーディングのストレージ分析。1NFOR、I0(i):47-61、1972年2月。
  20. ^ Unicode標準-よくある質問2006年12月に確認済み。
  21. ^ ストレージの見積もり2006年12月に確認済み。
  22. ^ 「検索エンジン最適化」2016年9月21日取得
  23. ^ Googleウェブマスターツール、「ハイパーテキストマークアップ言語5」、SEOのための会議2012年1月。
  24. ^ Berners-Lee、T。、「ハイパーテキストマークアップ言語-2.0」、RFC 1866、ネットワークワーキンググループ、1995年11月。

さらに読む

  • R.バイエルとE.マクレイト。大規模な順序付けされたインデックスの編成と保守。Acta Informatica、173-189、1972。
  • ドナルドE.クヌースThe Art of Computer Programming、第1巻(第3版):基本的なアルゴリズム、Addison Wesley Longman Publishing Co.、カリフォルニア州レッドウッドシティー、1997年。
  • ドナルドE.クヌースコンピュータプログラミングの芸術、第3巻:(第2版)並べ替えと検索、Addison Wesley Longman Publishing Co.、カリフォルニア州レッドウッドシティー、1998年。
  • ジェラルド・サルトン自動テキスト処理、Addison-Wesley Longman Publishing Co.、Inc。、マサチューセッツ州ボストン、1988年。
  • ジェラルド・サルトンMichael J. McGill、Introduction to Modern Information Retrieval、McGraw-Hill、Inc。、ニューヨーク、ニューヨーク、1986年。
  • ジェラルド・サルトンLesk、ME:索引付けとテキスト処理のコンピューター評価。ACMのジャーナル。1968年1月。
  • ジェラルド・サルトンSMART検索システム-自動ドキュメント処理の実験。Prentice Hall Inc.、イングルウッドクリフ、1971年。
  • ジェラルド・サルトンコンピュータによる情報の変換、分析、および検索、Addison-Wesley、Reading、MA、1989年。
  • Baeza-Yates、R.、Ribeiro-Neto、B .:現代の情報検索。第8章ACMPress1999。
  • GKZipf。人間の行動と最小限の努力の原則。アディソン-ウェスリー、1949年。
  • Adelson-Velskii、GM、Landis、EM:情報組織化アルゴリズム。DANSSSR、146、263-266(1962)。
  • エドワードH.サッセンガスジュニア、ファイルを処理するためのツリー構造の使用、ACMの通信、v.6 n.5、p。272-279、1963年5月
  • Harman、DK、et al .:反転ファイル。In Information Retrieval:Data Structures and Algorithms、Prentice-Hall、pp 28–43、1992。
  • Lim、L.、et al。:Characterizing Web Document Change、LNCS 2118、133–146、2001。
  • Lim、L.、et al .:ランドマークを使用したWebインデックスの動的保守。Proc。2003年の第12回W3会議の報告。
  • Moffat、A.、Zobel、J .:高速テキスト検索のための自己索引付け反転ファイル。ACM TIS、349〜379、1996年10月、第14巻、第4号。
  • Mehlhorn、K。:データ構造と効率的なアルゴリズム、Springer Verlag、EATCSモノグラフ、1984年。
  • Mehlhorn、K.Overmars、MH:分解可能な検索問題の最適なダイナミゼーション。IPL 12、93–98、1981。
  • Mehlhorn、K . :静的データ構造を動的データ構造に変換する効率の下限。算数。システム理論15、1–16、1981。
  • Koster、M。:ALIWEB:Archie-Webでのインデックス作成のようなものです。コンピュータネットワークとISDNシステム、Vol。27、No。2(1994)175-182(Proc。FirstInt'l World Wide Web Conf。、Elsevier Science、Amsterdam、1994、pp。175–182も参照)
  • SergeAbiteboulVictorVianuWebでのクエリと計算データベース理論に関する国際会議の議事録。デルファイ、ギリシャ1997。
  • イアン・H・ウィッテン、アリスター・モファット、ティモシー・C・ベル。ギガバイトの管理:ドキュメントと画像の圧縮とインデックス作成。ニューヨーク:Van Nostrand Reinhold、1994年。
  • A.EmtageおよびP.Deutsch、「Archie--インターネット用の電子ディレクトリサービス」。Proc。Usenix Winter 1992Tech。Conf。、Usenix Assoc。、Berkeley、CA、1992、pp。93–110。
  • M.グレイ、ワールドワイドウェブワンダラー
  • D.カッティングとJ.ペダーセン。「動的転置インデックス保守の最適化」。情報検索における研究開発に関する第13回国際会議の議事録、pp。405–411、1990年9月。
  • ステファンビュッチャー、チャールズLAクラーク、ゴードンV.コーマック。情報検索:検索エンジンの実装と評価MIT Press、マサチューセッツ州ケンブリッジ、2010年。