Loading article…
情報科学では、転置インデックス（投稿リスト、投稿ファイル、または転置ファイルとも呼ばれる）は、単語や数字などのコンテンツから、テーブル内、またはドキュメント内、あるいはドキュメントセット内のその位置へのマッピングを格納するデータベースインデックスです（ドキュメントからコンテンツへのマッピングを行う順方向インデックスとは対照的に命名されています）。[ 1 ]転置インデックスの目的は、ドキュメントがデータベースに追加される際の処理の増加という代償を伴うものの、高速な全文検索を可能にすることです。 [ 2 ]転置ファイルは、インデックスではなく、データベースファイル自体である場合があります。これは、ドキュメント検索システムで使用される最も一般的なデータ構造であり、[ 3 ]検索エンジンなどで大規模に使用されています。さらに、 ADABAS、DATACOM/DB、Model 204など、いくつかの重要な汎用メインフレームベースのデータベース管理システムでは、転置リストアーキテクチャが使用されています。
転置インデックスには主に 2 つの種類があります。レコード レベルの転置インデックス(または転置ファイル インデックス、または単に転置ファイル) には、各単語に対応するドキュメントへの参照のリストが含まれています。単語 レベルの転置インデックス(または完全転置インデックス、または転置リスト) には、さらにドキュメント内の各単語の位置が含まれています。[ 4 ]後者の形式は、フレーズ検索などのより多くの機能を提供しますが、作成するにはより多くの処理能力とスペースが必要です。
転置インデックスのデータ構造は、一般的な検索エンジンのインデックス作成アルゴリズムの中核となる要素です。[ 5 ]検索エンジンの実装の目標は、クエリの速度を最適化することです。つまり、単語 X が出現するドキュメントを見つけることです。 [ 6 ]ドキュメントごとに単語のリストを格納する順方向インデックスが作成されると、次にそれを反転して転置インデックスを作成します。順方向インデックスをクエリするには、一致するドキュメントを確認するために、各ドキュメントと各単語を順次反復する必要があります。このようなクエリを実行するための時間、メモリ、および処理リソースは、技術的に常に現実的とは限りません。順方向インデックスにドキュメントごとに単語をリストする代わりに、単語ごとにドキュメントをリストする転置インデックスのデータ構造が作成されます。
転置インデックスが作成されると、転置インデックス内の単語IDに（ランダムアクセスによって）ジャンプすることでクエリを解決できます。
コンピューターが普及する以前は、重要な書籍の索引は手作業で作成されていた。これらは実質的には逆索引であり、わずかな解説が付随する程度で、作成には膨大な労力を要した。
バイオインフォマティクスでは、配列決定されたDNAの短い断片の配列アセンブリにおいて、転置インデックスが非常に重要です。断片の由来を見つける方法の一つは、参照DNA配列に対して検索することです。配列決定されたDNAと参照DNAの違い、つまりエラーによる少数のミスマッチは、断片をより小さな断片に分割することで対処できます。少なくとも1つのサブフラグメントは参照DNA配列と一致する可能性が高いです。このマッチングには、参照DNA配列から特定の長さのすべてのサブストリングの転置インデックスを作成する必要があります。ヒトDNAは30億塩基対以上あり、インデックスごとにDNAサブストリングを、インデックス自体には32ビット整数を格納する必要があるため、このような転置インデックスのストレージ要件は数十ギガバイトになるでしょう。
歴史的な理由から、逆リスト圧縮とビットマップ圧縮は別々の研究分野として開発され、後に本質的に同じ問題を解決するものとして認識されるようになった。[ 7 ]
{{cite book}}:|website=無視されました (ヘルプ)