Loading article…
検索エンジンのインデックス作成とは、データの収集、解析、保存を行うことで、情報の高速かつ正確な検索を可能にします。インデックス設計には、言語学、認知心理学、数学、情報科学、コンピューター サイエンスの学際的な概念が組み込まれています。インターネット上のWeb ページを見つけるために設計された検索エンジンのコンテキストでは、このプロセスの別名はWeb インデックス作成です。
一般的な検索エンジンは、オンラインの自然言語文書の全文索引作成に重点を置いています。 [1]画像、ビデオ、 [2]オーディオ、[3]グラフィックス[4]などのメディアタイプも検索可能です。
メタ検索エンジンは他のサービスのインデックスを再利用し、ローカルインデックスを保存しませんが、キャッシュベースの検索エンジンはコーパスとともにインデックスを永続的に保存します。全文インデックスとは異なり、部分テキストサービスではインデックスの深さを制限してインデックスサイズを削減します。大規模なサービスでは通常、必要な時間と処理コストを考慮して、事前に決定された時間間隔でインデックスを作成しますが、エージェントベースの検索エンジンではリアルタイムでインデックスを作成します。
インデックス作成
インデックスを保存する目的は、検索クエリに関連するドキュメントを見つける際の速度とパフォーマンスを最適化することです。インデックスがないと、検索エンジンはコーパス内のすべてのドキュメントをスキャンすることになり、かなりの時間と計算能力が必要になります。たとえば、10,000 ドキュメントのインデックスは数ミリ秒以内にクエリできますが、10,000 の大きなドキュメント内のすべての単語を順番にスキャンすると、数時間かかる場合があります。インデックスを保存するために必要な追加のコンピューター ストレージと、更新に必要な時間の大幅な増加は、情報検索中に節約される時間と引き換えに得られます。
インデックス設計要因
検索エンジンのアーキテクチャを設計する際の主な要素は次のとおりです。
- マージ要因
- データがインデックスにどのように入力されるか、またはテキスト コーパスのトラバーサル中に単語や主題の特徴がどのようにインデックスに追加されるか、および複数のインデクサーが非同期で動作できるかどうか。インデクサーは、まず古いコンテンツを更新しているのか、新しいコンテンツを追加しているのかを確認する必要があります。トラバーサルは通常、データ収集ポリシーと相関しています。検索エンジンのインデックス マージは、 SQL Mergeコマンドやその他のマージ アルゴリズムと概念的に似ています。 [5]
- 保管技術
- インデックスデータをどのように保存するか、つまり、情報をデータ圧縮するか、フィルタリングするかを指定します。
- インデックスサイズ
- インデックスをサポートするために必要なコンピューター ストレージの量。
- 検索速度
- 転置インデックスで単語がどれだけ速く見つかるか。データ構造内のエントリがどれだけ速く見つかるかと、エントリがどれだけ速く更新または削除されるかを比較することは、コンピュータ サイエンスの中心的な焦点です。
- メンテナンス
- インデックスが時間の経過とともにどのように維持されるか。[6]
- フォールトトレランス
- サービスの信頼性がどの程度重要か。問題には、インデックス破損への対処、不良データを個別に処理できるかどうかの判断、不良ハードウェアへの対処、パーティショニング、ハッシュベースまたは複合パーティショニングなどのスキーム[7] 、レプリケーションなどがあります。
インデックスデータ構造
検索エンジンのアーキテクチャは、さまざまな設計要因を満たすために、インデックス作成の実行方法やインデックスの保存方法が異なります。
- サフィックスツリー
- 比喩的に木のような構造をしており、線形時間検索をサポートします。単語の接尾辞を格納することによって構築されます。接尾辞木はトライ木の一種です。トライ木は拡張可能なハッシュをサポートしており、これは検索エンジンのインデックス作成に重要です。[8] DNA配列のパターンの検索やクラスタリングに使用されます。大きな欠点は、単語を木に格納すると、単語自体を格納するために必要なスペースを超えるスペースが必要になる可能性があることです。[9]代替表現は接尾辞配列であり、必要な仮想メモリが少なくて済むと考えられており、 BWTアルゴリズムなどのデータ圧縮をサポートします。
- 引用索引
- 計量書誌学の主題である引用分析をサポートするために、文書間の引用またはハイパーリンクを保存します。
- nグラムインデックス
- 他の種類の検索やテキストマイニングをサポートするために、データの長さのシーケンスを格納します。[13]
- 文書用語マトリックス
- 潜在的意味解析で使用され、文書内の単語の出現を 2 次元スパース マトリックスに格納します。
並列処理の課題
検索エンジンの設計における大きな課題は、シリアル コンピューティング プロセスの管理です。競合状態やコヒーレント障害が発生する機会は数多くあります。たとえば、新しいドキュメントがコーパスに追加され、インデックスを更新する必要がありますが、同時にインデックスは検索クエリに応答し続ける必要があります。これは、2 つの競合するタスク間の衝突です。著者は情報のプロデューサーであり、Web クローラーはこの情報のコンシューマーであり、テキストを取得してキャッシュ (またはコーパス) に格納すると考えてください。フォワード インデックスはコーパスによって生成された情報のコンシューマーであり、逆インデックスはフォワード インデックスによって生成された情報のコンシューマーです。これは一般にプロデューサー - コンシューマー モデルと呼ばれます。インデクサーは検索可能な情報のプロデューサーであり、ユーザーは検索する必要があるコンシューマーです。分散ストレージと分散処理を使用する場合、この課題はさらに大きくなります。インデックス付けされた情報の量を増やすために、検索エンジンのアーキテクチャには分散コンピューティングが含まれる場合があります。分散コンピューティングでは、検索エンジンは同時に動作する複数のマシンで構成されます。これにより、不整合の可能性が高まり、完全に同期された分散型の並列アーキテクチャを維持することが困難になります。[14]
逆インデックス
多くの検索エンジンは、検索クエリを評価する際に逆インデックスを組み込んで、クエリ内の単語を含むドキュメントをすばやく見つけ、それらのドキュメントを関連性によってランク付けします。逆インデックスには各単語を含むドキュメントのリストが格納されているため、検索エンジンは直接アクセスを使用して、クエリ内の各単語に関連付けられたドキュメントを見つけ、一致するドキュメントをすばやく取得できます。以下は、逆インデックスの簡略化された図です。
このインデックスは、単語の出現頻度や位置に関する情報を格納していないため、特定の文書内に単語が存在するかどうかしか判断できません。そのため、ブールインデックスであると考えられます。このようなインデックスは、クエリに一致する文書を判断しますが、一致した文書の順位付けは行いません。一部の設計では、インデックスには、各文書内の各単語の出現頻度や各文書内の単語の位置などの追加情報が含まれます。[15]位置情報により、検索アルゴリズムは単語の近接性を識別してフレーズの検索をサポートできます。頻度は、クエリに対する文書の関連性を順位付けするために使用できます。このようなトピックは、情報検索の中心的な研究焦点です。
転置インデックスは、すべての単語が各文書に存在するわけではないため、疎行列です。コンピュータのストレージメモリ要件を削減するため、2次元配列とは異なる方法で格納されます。インデックスは、潜在的意味解析で使用される用語ドキュメントマトリックスに似ています。転置インデックスはハッシュテーブルの一種と考えることができます。場合によっては、インデックスはバイナリツリーの形式であり、追加のストレージが必要になりますが、検索時間を短縮できます。大規模なインデックスでは、アーキテクチャは通常、分散ハッシュテーブルです。[16]
転置インデックスを使用したフレーズ検索の実装
フレーズ検索では、位置インデックスと呼ばれる特殊な形式の逆インデックスが使用されます。位置インデックスは、トークンを含むドキュメントの ID だけでなく、投稿リスト内のドキュメント内のトークンの正確な位置も保存します。クエリで指定されたフレーズの出現は、これらの投稿リストをナビゲートし、目的の用語が予想される順序 (フレーズ内の順序と同じ) で出現するインデックスを識別することによって取得されます。したがって、「First Witch」というフレーズの出現を検索する場合は、次のようになります。
- 「first」と「witch」の投稿リストを取得します
- 「最初」の後に「魔女」が最初に現れる場所を特定します
- この出現が「first」の出現の直後であることを確認します。
- そうでない場合は、次の「first」の出現に進みます。
この手順の時間の複雑さを最小限に抑えるために、投稿リストはバイナリ検索を使用してナビゲートすることができます。[17]
インデックスのマージ
転置インデックスは、マージまたは再構築によって埋められます。再構築はマージに似ていますが、まず転置インデックスの内容を削除します。アーキテクチャは増分インデックスをサポートするように設計されることがあります。[18]マージでは、追加または更新するドキュメントを識別し、各ドキュメントを単語に解析します。技術的に正確に言うと、マージでは、通常仮想メモリに存在する新しくインデックスが作成されたドキュメントと、1 つ以上のコンピューターのハード ドライブに存在するインデックス キャッシュが結合されます。
解析後、インデクサーは参照されたドキュメントを適切な単語のドキュメント リストに追加します。大規模な検索エンジンでは、各単語を転置インデックスで検索するプロセス (ドキュメント内で出現したことを報告するため) は時間がかかりすぎる可能性があるため、このプロセスは通常、順方向インデックスの開発と、順方向インデックスの内容を転置インデックスに分類するプロセスの 2 つの部分に分割されます。転置インデックスは、順方向インデックスの逆であるため、このように呼ばれています。
前方インデックス
前方インデックスには、各ドキュメントの単語のリストが格納されます。以下は、前方インデックスの簡略化された形式です。
順方向インデックスを開発する根拠は、文書を解析する際に、文書ごとに単語を中間的に格納する方がよいということである。この区別により非同期システム処理が可能になり、転置インデックス更新のボトルネックを部分的に回避できる。[19]順方向インデックスはソートされて転置インデックスに変換される。順方向インデックスは基本的に、文書と単語のペアのリストであり、文書によって照合される。順方向インデックスを転置インデックスに変換するには、単語でペアをソートするだけである。この点で、転置インデックスは単語でソートされた順方向インデックスである。
圧縮
大規模な検索エンジンのインデックスを生成または維持することは、ストレージと処理の面で大きな課題となります。多くの検索エンジンは、ディスク上のインデックスのサイズを縮小するために、何らかの圧縮形式を利用しています。[20]全文インターネット検索エンジンの次のシナリオを考えてみましょう。
- 1文字を格納するには8ビット（または1バイト）かかります。一部のエンコードでは1文字あたり2バイトを使用します[21] [22]
- ページ上の任意の単語の平均文字数は 5 と推定されます ( Wikipedia:サイズの比較)
このシナリオでは、 20 億の Web ページに対する圧縮されていないインデックス (非結合の単純なインデックスを想定) には、5,000 億語のエントリを格納する必要があります。1 文字あたり 1 バイト、または 1 単語あたり 5 バイトの場合、これだけで 2,500 ギガバイトのストレージ スペースが必要になります。 [引用が必要]このスペース要件は、フォールト トレラント分散ストレージ アーキテクチャの場合、さらに大きくなる可能性があります。選択した圧縮手法によっては、インデックスをこのサイズのほんの一部にまで縮小できます。トレードオフは、圧縮と解凍を実行するために必要な時間と処理能力です。[引用が必要]
特に、大規模な検索エンジンの設計には、ストレージのコストだけでなく、ストレージに電力を供給するための電気コストも組み込まれています。したがって、圧縮はコストの尺度です。[引用が必要]
ドキュメント解析
文書解析では、文書またはその他の形式のメディアの構成要素 (単語) を分解して、順方向インデックスと逆方向インデックスに挿入します。見つかった単語はトークンと呼ばれるため、検索エンジンのインデックス作成や自然言語処理の文脈では、解析はトークン化と呼ばれることが一般的です。また、単語境界の曖昧さ解消、タグ付け、テキスト分割、コンテンツ分析、テキスト分析、テキスト マイニング、コンコーダンス生成、音声分割、語彙解析、語彙分析と呼ばれることもあります。「インデックス作成」、「解析」、「トークン化」という用語は、企業内スラングでは同じ意味で使用されます。
自然言語処理は、継続的な研究と技術改善の対象です。トークン化では、質の高い検索をサポートするために、ドキュメントから必要な情報を抽出してインデックスを作成する際に多くの課題が生じます。インデックス作成のためのトークン化には複数の技術が関係しており、その実装は一般に企業秘密として保持されています。[要出典]
自然言語処理における課題
- 単語境界の曖昧さ
- 英語を母国語とする人は、最初はトークン化は簡単な作業だと考えるかもしれませんが、多言語インデックス作成ツールの設計はそうではありません。デジタル形式では、中国語や日本語などの他の言語のテキストは、単語が空白で明確に区切られていないため、より大きな課題となります。トークン化の目的は、ユーザーが検索する単語を識別することです。言語固有のロジックを使用して単語の境界を適切に識別します。これは、サポートされている各言語（または同様の境界マーカーと構文を持つ言語のグループ）のパーサーを設計する根拠となることがよくあります。
- 言語の曖昧さ
- 一致するドキュメントを適切にランク付けするために、多くの検索エンジンは、各単語について、その言語や語彙カテゴリ(品詞) などの追加情報を収集します。構文は言語によって異なるため、これらの手法は言語に依存します。ドキュメントは必ずしもその言語を明確に識別したり、正確に表現したりするわけではありません。ドキュメントをトークン化する際に、一部の検索エンジンはドキュメントの言語を自動的に識別しようとします。
- 多様なファイル形式
- 文書のどのバイトが文字を表しているかを正しく識別するには、ファイル形式を正しく処理する必要があります。複数のファイル形式をサポートする検索エンジンは、文書を正しく開いてアクセスでき、文書の文字をトークン化できる必要があります。
- ストレージの不具合
- 自然言語データの品質は、必ずしも完璧であるとは限りません。特にインターネット上の不特定多数のドキュメントは、適切なファイル プロトコルに厳密に従っていません。バイナリ文字がドキュメントのさまざまな部分に誤ってエンコードされている可能性があります。これらの文字を認識して適切に処理しないと、インデックスの品質またはインデクサーのパフォーマンスが低下する可能性があります。
トークン化
読み書きができる人間とは異なり、コンピュータは自然言語文書の構造を理解できず、単語や文を自動的に認識できません。コンピュータにとって、文書はバイトのシーケンスにすぎません。コンピュータは、文書内の単語をスペース文字で区切っていることを「知りません」。代わりに、人間はコンピュータをプログラムして、トークンと呼ばれる個別の単語または明確な単語を構成するものを識別しなければなりません。このようなプログラムは一般にトークナイザー、パーサー、またはレクサーと呼ばれます。多くの検索エンジンやその他の自然言語処理ソフトウェアには、YACCやLexなどの解析専用のプログラムが組み込まれています。
トークン化中に、パーサーは、数値コードで表され、一部は非印刷制御文字である単語やその他の要素 (句読点など) を表す文字のシーケンスを識別します。パーサーは、電子メールアドレス、電話番号、URLなどのエンティティも識別できます。各トークンを識別するときに、トークンの大文字/小文字 (大文字、小文字、混合、固有)、言語またはエンコード、語彙カテゴリ (品詞、たとえば「名詞」や「動詞」)、位置、文番号、文の位置、長さ、行番号など、いくつかの特性が保存される場合があります。
言語認識
検索エンジンが複数の言語をサポートしている場合、トークン化の一般的な最初の手順は、各ドキュメントの言語を識別することです。その後の手順の多くは言語に依存します (語幹抽出や品詞のタグ付けなど)。言語認識とは、コンピュータ プログラムがドキュメントの言語を自動的に識別または分類しようとするプロセスです。言語認識には、言語分類、言語分析、言語識別、言語タグ付けなどの別名もあります。自動言語認識は、自然言語処理における継続的な研究の対象です。単語がどの言語に属するかを調べるには、言語認識チャートを使用する場合があります。
フォーマット分析
検索エンジンが複数のドキュメント形式をサポートしている場合、ドキュメントをトークン化できるように準備する必要があります。多くのドキュメント形式には、テキスト コンテンツに加えて書式設定情報が含まれているという問題があります。たとえば、HTMLドキュメントには HTML タグが含まれており、改行、太字の強調、フォントサイズやスタイルなどの書式設定情報を指定します。検索エンジンがコンテンツと「マークアップ」の違いを無視すると、インデックスに不要な情報が含まれ、検索結果の質が低下します。形式分析とは、ドキュメント内に埋め込まれた書式設定コンテンツを識別して処理することであり、ドキュメントがコンピューター画面に表示される方法やソフトウェア プログラムによって解釈される方法を制御します。形式分析は、構造分析、形式解析、タグ除去、形式除去、テキスト正規化、テキスト クリーニング、テキスト準備とも呼ばれます。形式分析の課題は、さまざまなファイル形式の複雑さによってさらに複雑になります。一部のファイル形式は独自のものであり、ほとんど情報が公開されていませんが、他のファイル形式は十分に文書化されています。多くの検索エンジンがサポートする、よく文書化された一般的なファイル形式には、次のものがあります。
- html
- ASCIIテキスト ファイル (特定のコンピューター読み取り可能なフォーマットを持たないテキスト ドキュメント)
- Adobeのポータブル ドキュメント フォーマット ( PDF )
- ポストスクリプト(PS)
- ラテックス
- UseNetネットニュース サーバー形式
- XMLおよびRSSなどの派生
- SGML
- ID3のようなマルチメディアメタデータ形式
- マイクロソフトワード
- マイクロソフトエクセル
- マイクロソフト パワーポイント
- IBMロータスノーツ
さまざまな形式を処理するためのオプションとしては、形式を開発、保守、または所有する組織によって提供される、公開されている商用解析ツールを使用することと、カスタムパーサーを作成することが挙げられます。
一部の検索エンジンは、圧縮または暗号化されたファイル形式で保存されたファイルの検査をサポートしています。圧縮形式で作業する場合、インデクサーは最初にドキュメントを解凍します。この手順により、1 つ以上のファイルが作成される可能性があり、各ファイルは個別にインデックス付けする必要があります。一般的にサポートされている圧縮ファイル形式は次のとおりです。
- ZIP - Zip アーカイブ ファイル
- RAR - Roshal ARchive ファイル
- CAB - Microsoft Windowsキャビネット ファイル
- Gzip - gzip で圧縮されたファイル
- BZIP - bzip2 を使用して圧縮されたファイル
- テープアーカイブ (TAR)、Unixアーカイブファイル、(それ自体は) 圧縮されていない
- TAR.Z、TAR.GZ、または TAR.BZ2 - Compress、GZIP、または BZIP2 で圧縮されたUnixアーカイブ ファイル
フォーマット分析には、インデックスに「不正な情報」が含まれないようにするための品質改善方法が含まれる場合があります。コンテンツは、フォーマット情報を操作して追加のコンテンツを含めることができます。スパムデクシングのためにドキュメントのフォーマットを悪用する例:
- 書式設定を使用することで、コンピューターの画面では表示されませんが、インデクサーには表示されるセクションに数百または数千の単語を含めます (例: HTML内の非表示の「div」タグ。これにはCSSまたはJavaScriptの使用が組み込まれている場合があります)。
- 単語の前景色のフォント色を背景色と同じに設定すると、文書を閲覧するユーザーに対してはコンピュータ画面上で単語が非表示になりますが、インデクサーに対しては非表示になりません。
セクション認識
一部の検索エンジンでは、トークン化の前にセクション認識、つまりドキュメントの主要部分の識別が組み込まれています。コーパス内のすべてのドキュメントが、整理された章やページに分かれた、よく書かれた本のように読めるわけではありません。ニュースレターや企業レポートなど、 Web上の多くのドキュメントには、誤ったコンテンツや、主要な資料 (ドキュメントの内容) を含まないサイド セクションが含まれています。たとえば、Wikipedia Web サイトの記事には、他の Web ページへのリンクを含むサイド メニューが表示されます。HTML や PDF などの一部のファイル形式では、コンテンツを列に表示できます。コンテンツがビューのさまざまな領域に表示またはレンダリングされている場合でも、生のマークアップ コンテンツではこの情報が順番に格納される場合があります。生のソース コンテンツで順番に表示される単語は、これらの文や段落がコンピューター画面のさまざまな部分にレンダリングされている場合でも、順番にインデックス付けされます。検索エンジンがこのコンテンツを通常のコンテンツのようにインデックス付けすると、コンテンツが混在し、単語の近接性が不適切なため、インデックスの品質と検索品質が低下する可能性があります。次の 2 つの主な問題が指摘されています。
- 異なるセクションのコンテンツは、実際には関連していないにもかかわらず、インデックスでは関連しているものとして扱われます。
- 組織サイドバーのコンテンツはインデックスに含まれていますが、サイドバーのコンテンツはドキュメントの意味に寄与せず、インデックスにはドキュメントの不適切な表現が詰め込まれています。
セクション分析では、検索エンジンが各ドキュメントのレンダリング ロジック (基本的には実際のドキュメントの抽象表現) を実装し、代わりにその表現をインデックス化することが必要な場合があります。たとえば、インターネット上の一部のコンテンツは JavaScript でレンダリングされます。検索エンジンがページをレンダリングせず、ページ内の JavaScript を評価しない場合、このコンテンツを同じように「認識」できず、ドキュメントを誤ってインデックス化します。一部の検索エンジンはレンダリングの問題を気にしないため、多くの Web ページ デザイナーは JavaScript でコンテンツを表示しないようにするか、Noscript タグを使用して Web ページが適切にインデックス化されるようにします。同時に、この事実を悪用して、検索エンジンのインデクサーが閲覧者とは異なるコンテンツを「認識」するようにすることもできます。
HTML 優先システム
インデックス作成では、優先順位を整理するためにHTMLタグを認識する必要があることがよくあります。優先順位を低くして、strongやlinkなどのラベルにインデックスを作成して優先順位を最適化すると、それらのラベルがテキストの先頭にある場合、関連性がないことが判明する可能性があります。GoogleやBingなどの一部のインデクサーは、強力な型システムの互換性により、検索エンジンが大きなテキストを関連するソースとして扱わないようにしています。 [23]
メタタグのインデックス作成
メタタグのインデックス作成は、Web コンテンツの整理と分類に重要な役割を果たします。特定のドキュメントには、著者、キーワード、説明、言語などのメタ情報が埋め込まれていることがよくあります。HTML ページの場合、メタタグにはインデックスにも含まれるキーワードが含まれます。以前のインターネット検索エンジン技術では、前方インデックスのメタタグ内のキーワードのみをインデックス作成し、ドキュメント全体を解析することはありませんでした。当時は、フルテキスト インデックス作成は十分に確立されておらず、コンピューター ハードウェアもそのような技術をサポートしていませんでした。HTML マークアップ言語の設計には、トークン化を必要とせずに適切かつ簡単にインデックス作成できるようにするために、当初メタタグのサポートが含まれていました。[24]
1990 年代を通じてインターネットが成長するにつれ、多くの実店舗企業が「オンライン」になり、企業の Web サイトを開設しました。Web ページ (その多くは製品パンフレットに似た企業向け Web ページ) の説明に使用されるキーワードは、説明的なキーワードから、特定の検索クエリに対する検索結果で Web ページを上位に表示することで売上を伸ばすことを目的としたマーケティング向けキーワードに変わりました。これらのキーワードが主観的に指定されたという事実は、スパムデクシングにつながり、1990 年代には多くの検索エンジンが全文インデックス技術を採用するようになりました。検索エンジンの設計者や企業は、Web ページのコンテンツに「マーケティング キーワード」を多く配置することしかできず、それ以上配置すると、興味深く有用な情報がすべて失われてしまいます。ユーザー向けの「スティッキー」な Web サイトを設計するというビジネス目標との利益相反を考慮して、顧客生涯価値の式は、訪問者を維持することを期待して、より有用なコンテンツを Web サイトに組み込むように変更されました。この意味で、フルテキスト インデックスはより客観的であり、検索エンジンの結果の配置の主観的な制御からさらに一歩離れたものであったため、検索エンジンの結果の品質が向上し、フルテキスト インデックス テクノロジの研究が促進されました。
デスクトップ検索では、多くのソリューションにメタ タグが組み込まれており、ファイルの内容からは明らかでないさまざまなファイルのコンテンツを検索エンジンがインデックスする方法を、作成者がさらにカスタマイズする方法が提供されています。デスクトップ検索はユーザーの制御下にありますが、インターネット検索エンジンはフルテキスト インデックスに重点を置く必要があります。
参照
参考文献
- ^ Clarke, C.、Cormack, G.: 分散型全文検索システムのための動的逆インデックス。TechRep MT-95-01、ウォータールー大学、1995 年 2 月。
- ^ Sikos, LF (2016 年 8 月)。「次世代のビデオ索引付けのための、リンク データへの概念マッピングを備えた RDF を利用したセマンティック ビデオ注釈ツール」。マルチメディア ツールとアプリケーション。doi :10.1007/s11042-016-3705-7。S2CID 254832794 。[永久リンク切れ ]
- ^ http://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf [ベア URL PDF ]
- ^ Charles E. Jacobs、Adam Finkelstein、David H. Salesin。高速マルチ解像度画像クエリ。ワシントン大学コンピュータサイエンス工学部。1995 年。2006 年 12 月検証
- ^ Brown, EW: 全文情報検索における実行パフォーマンスの問題。マサチューセッツ大学アマースト校コンピュータサイエンス学部、技術レポート 95-81、1995 年 10 月。
- ^ Cutting, D.、Pedersen, J.: 動的転置インデックスメンテナンスの最適化。SIGIR Proceedings、405-411、1990 年。
- ^ リニアハッシュパーティショニング。MySQL 5.1 リファレンスマニュアル。2006 年 12 月検証済み
- ^ trie、アルゴリズムとデータ構造の辞書、米国国立標準技術研究所。
- ^ ガスフィールド、ダン (1999) [1997]。文字列、木、シーケンスのアルゴリズム：コンピュータサイエンスと計算生物学。米国：ケンブリッジ大学出版局。ISBN 0-521-58519-8。。
- ^ Black, Paul E.、「逆インデックス」、アルゴリズムとデータ構造の辞書、米国国立標準技術研究所、2006 年 10 月。2006 年 12 月に検証。
- ^ CC Foster、「情報検索：AVL ツリーを使用した情報の保存と検索」、1965 年第 20 回全国会議の議事録、p.192-205、1965 年 8 月 24 ～ 26 日、オハイオ州クリーブランド、米国
- ^ Landauer, WI: バランスツリーと情報検索におけるその利用。IEEE Trans. on Electronic Computers、Vol. EC-12、No. 6、1963 年 12 月。
- ^ Google Ngram データセットは 2013-09-29 にWayback Machineにアーカイブされ、LDC Catalog で販売されています
- ^ Jeffrey Dean および Sanjay Ghemawat。MapReduce: 大規模クラスターでの簡素化されたデータ処理。Google, Inc. OSDI。2004 年。
- ^ Grossman、Frieder、Goharian。IR 逆インデックスの基礎。2002 年。2011 年 8 月検証。
- ^ Tang, Hunqiang. Dwarkadas, Sandhya . 「効率的なピアツーピア情報検索のためのハイブリッドグローバルローカルインデックス」ロチェスター大学。1 ページ。http://www.cs.rochester.edu/u/sandhya/papers/nsdi04.ps
- ^ Büttcher, Stefan; Clarke, Charles LA; Cormack, Gordon V. (2016).情報検索: 検索エンジンの実装と評価( First MIT Press ペーパーバック版)。マサチューセッツ州ケンブリッジ、イギリス、ロンドン: The MIT Press。ISBN 978-0-262-52887-0。
- ^ Tomasic, A., et al.: テキスト文書検索のための反転リストの増分更新。スタンフォード大学コンピュータサイエンス技術ノート STAN-CS-TN-93-1 の短縮版、1993 年 12 月。
- ^ Sergey Brin と Lawrence Page。大規模ハイパーテキスト Web 検索エンジンの構造。スタンフォード大学。1998 年。2006 年 12 月検証。
- ^ HSヒープ。文書データベースの圧縮コーディングのストレージ分析。1NFOR、I0(i):47-61、1972年2月。
- ^ Unicode 標準 - よくある質問。2006 年 12 月確認。
- ^ ストレージの推定値。2006 年 12 月に確認。
- ^ Google ウェブマスター ツール、「ハイパーテキスト マークアップ言語 5」、SEO カンファレンス 2012 年 1 月。
- ^ Berners-Lee, T.、「Hypertext Markup Language - 2.0」、RFC 1866、ネットワークワーキンググループ、1995 年 11 月。
さらに読む
- R. Bayer と E. McCreight。「大規模順序付きインデックスの構成と保守」Acta Informatica、173-189、1972 年。
- Donald E. Knuth著『The Art of Computer Programming』第 1 巻 (第 3 版): 基本アルゴリズム、Addison Wesley Longman Publishing Co. Redwood City、CA、1997 年。
- ドナルド E. クヌース著『コンピュータプログラミングの技法、第 3 巻: (第 2 版) ソートと検索』、Addison Wesley Longman Publishing Co.、カリフォルニア州レッドウッドシティ、1998 年。
- ジェラルド・サルトン著『自動テキスト処理』、Addison-Wesley Longman Publishing Co., Inc.、ボストン、マサチューセッツ州、1988年。
- ジェラルド・サルトン、マイケル・J・マギル著『現代情報検索入門』、McGraw-Hill 社、ニューヨーク、NY、1986 年。
- ジェラルド・サルトン、レスク、ME: 索引作成とテキスト処理のコンピュータ評価。ACM ジャーナル。1968 年 1 月。
- ジェラルド・サルトン。SMART 検索システム - 自動文書処理の実験。Prentice Hall Inc.、Englewood Cliffs、1971 年。
- ジェラルド・サルトン著『コンピュータによる情報の変換、分析、検索』、アディソン・ウェズレー社、マサチューセッツ州レディング、1989年。
- Baeza-Yates, R.、Ribeiro-Neto, B.: 現代の情報検索。第 8 章。ACM Press 1999。
- GK Zipf. 人間の行動と最小努力の原理。Addison-Wesley、1949年。
- Adelson-Velskii, GM, Landis, EM: 情報組織化アルゴリズム。DANSSSR、146、263-266 (1962)。
- Edward H. Sussenguth Jr.、「ファイル処理のためのツリー構造の使用」、Communications of the ACM、v.6 n.5、p. 272-279、1963 年 5 月
- Harman, DK, et al.: 反転ファイル。情報検索: データ構造とアルゴリズム、Prentice-Hall、pp 28–43、1992年。
- Lim, L.、他：「Web文書の変更の特徴づけ」、LNCS 2118、133–146、2001年。
- Lim, L.、他：「ランドマークを使用した Web インデックスの動的メンテナンス」第 12 回 W3 カンファレンスの議事録、2003 年。
- Moffat, A.、Zobel, J.: 高速テキスト検索のための自己インデックス反転ファイル。ACM TIS、349–379、1996 年 10 月、第 14 巻、第 4 号。
- Mehlhorn, K.:データ構造と効率的なアルゴリズム、Springer Verlag、EATCS Monographs、1984 年。
- Mehlhorn, K. , Overmars, MH : 分解可能な探索問題の最適ダイナミゼーション。IPL 12, 93–98, 1981。
- Mehlhorn, K. : 静的データ構造を動的データ構造に変換する効率の下限。数学システム理論 15, 1–16, 1981。
- Koster, M.: ALIWEB: Archie のような Web のインデックス作成。Computer Networks and ISDN Systems、Vol. 27、No. 2 (1994) 175-182 (Proc. First Int'l World Wide Web Conf.、Elsevier Science、アムステルダム、1994、pp. 175–182 も参照)
- Serge AbiteboulおよびVictor Vianu。Web上のクエリと計算。データベース理論に関する国際会議の議事録。デルファイ、ギリシャ、1997 年。
- Ian H Witten、Alistair Moffat、Timothy C. Bell。『Managing Gigabytes: Compressing and Indexing Documents and Images』。ニューヨーク：Van Nostrand Reinhold、1994 年。
- A. Emtage および P. Deutsch、「Archie - インターネット用電子ディレクトリ サービス」。Proc. Usenix Winter 1992 Tech. Conf.、Usenix Assoc.、カリフォルニア州バークレー、1992 年、93 ～ 110 ページ。
- M. グレイ、ワールド ワイド ウェブの放浪者。
- D. Cutting および J. Pedersen。「動的逆インデックス保守の最適化」。情報検索の研究開発に関する第 13 回国際会議の議事録、pp. 405-411、1990 年 9 月。
- Stefan Büttcher、Charles LA Clarke、Gordon V. Cormack。情報検索：検索エンジンの実装と評価。Wayback Machineに 2020-10-05 にアーカイブ。MIT Press、マサチューセッツ州ケンブリッジ、2010 年。