問題タブ [inverted-index]

ネストされた python 辞書の形で完全な逆インデックスがあります。その構造は次のとおりです。

たとえば、辞書の名前を index とすると、「 spam 」という単語のエントリは次のようになります。

Python dict はかなり最適化されており、プログラミングが容易になるため、この構造を使用しました。

任意の単語「スパム」について、それを含むドキュメントは次のように指定できます。

ドキュメント doc1 の投稿リスト:

現在、cPickle を使用してこの辞書を保存およびロードしています。しかし、ピクルス化されたファイルは約 380 MB で、読み込みに長い時間がかかります - 112 秒 (約time.time()を使用して時間を計測しました) で、メモリ使用量は 1.2 GB になります (Gnome システム モニター)。ロードしたら、問題ありません。私は4GBのRAMを持っています。

len(index.keys())229758を与える

コード

読み込みを速くする方法を教えてください。アプリケーションの起動時に一度だけロードする必要があります。あとは、クエリに応答するためのアクセス時間が重要です。

SQLite のようなデータベースに切り替えて、そのキーにインデックスを作成する必要がありますか? はいの場合、同等のスキーマを持つように値を保存する方法を教えてください。これにより、取得が容易になります。他に調べるべきことはありますか？

補遺

ティムの答えを使用pickle.dump(index, file, -1)すると、ピクルス化されたファイルはかなり小さくなります-約237 MB（ダンプに300秒かかりました）...そしてロードに半分の時間がかかります（61秒...以前の112秒とは対照的に.... time.time () )

しかし、スケーラビリティのためにデータベースに移行する必要がありますか?

今のところ、Tim の回答を承認済みとしてマークしています。

PS :Lucene や Xapian は使いたくない... この質問は、逆インデックスの保存に関するものです。以前の質問を削除できなかったので、新しい質問をしなければなりませんでした。

現在、ユーザーがプレゼンテーション、ドキュメント、電子書籍 (scribd や slideshare など) をアップロードできる Web サイトを開発しているため、ファイルのコンテンツを検索できるようにする必要があります。現在、txt ファイル内のファイルからテキストを抽出しています。MySQL を使用しているため、2 つのオプションを検討しています。

1. プレーン テキストを別のテーブルに保存し、mysql のフルテキスト インデックスを使用して検索します。
2. 転置インデックスを使用して単語を保存し、それらを検索します。(2 つの新しいテーブル - 単語とドキュメント テーブルとの多対多)。この場合、結果との関連性を高める繰り返しの単語を処理するにはどうすればよいでしょうか。

テキストは検索にのみ使用されます。(1)の問題は、電子書籍のテキストが巨大になる可能性があるため、(たとえば) 50kb 以下に制限することを検討しています。(2) はまた、電子書籍に多くの単語があるという問題を抱えていますが、これも制限される可能性があります。

それで、テキストにインデックスを付けて、全文検索を高速に実行できるようにする最善の方法を教えていただけませんか。この場合、mysql を最大限に活用する必要があります。

私のプロジェクトの 1 つで Sphinx 検索を使用することを検討しているので、それに関連していくつか質問があります。

1. SphinxSE および RT インデックスを使用する場合、SphinxSE テーブル内のすべての UPDATE または INSERT によってインデックスが更新されますよね? インデクサーなどを呼び出す必要はありませんか?
2. タグ (ユーザーがドキュメントに入力したキーワード) とコンテンツの両方を検索して、タグの一致に関連性を高めることはできますか? 可能であれば、タグ検索を実装するにはどうすればよいですか (今では、逆インデックスのように別のテーブルに配置しています)
3. フィラー属性については、SphinxSE テーブルにそれらの複製を貼り付けるか、mysql を使用して私が持っている通常のドキュメント テーブルからフィッターする方が良いですか?

前もって感謝します！

ドキュメントのコレクションに検索エンジンの転置インデックスを書いています。現在、辞書の辞書としてインデックスを保存しています。つまり、各キーワードはdocID->出現位置の辞書にマップされます。

データモデルは次のようになります。{word：{doc_name：[location_list]}}

メモリにインデックスを作成することは問題なく機能しますが、ディスクにシリアル化しようとすると、MemoryErrorが発生します。これが私のコードです：

シリアル化の直前、私のプログラムは約50％のメモリ（1.6 Gb）を使用しています。cPickleを呼び出すとすぐに、クラッシュする前にメモリ使用量が80％に急上昇します。

cPickleがシリアル化に大量のメモリを使用するのはなぜですか？この問題に取り組むためのより良い方法はありますか？

質問：冗長性の高い強力なハッシュでインデックス付けされた非常に大規模な（数テラバイト）データベースを処理するために、どのような解決策またはヒントが必要ですか？

ある種の逆ストレージ？

Postgresでできることはありますか？

必要に応じて、自分のストレージをロールバックする準備ができています。

（ヒント：オープンソースである必要があり、Javaでなく、Linuxで実行されている必要があり、ディスクベースである必要があります。C/ C ++ / Pythonを推奨します）

詳細：

各レコードに次のような非常に大きなデータベースを作成する必要があります。

• いくつかの主キーを含むいくつかの任意のメタデータ（いくつかのテキストフィールド）
• 1つのハッシュ（128ビットハッシュ、強力なMD5のような）

レコードの量は、私が非常に大きいと見なすものです：数百から数千億）。行間でハッシュの大幅な冗長性があります（レコードの40％以上でハッシュが少なくとも別のレコードと共有されており、一部のハッシュは100Kレコードに存在します）

主な使用法は、ハッシュで検索してからメタデータを取得することです。二次的な使用法は、主キーで検索してからメタデータを取得することです。

これは分析タイプのデータベースであるため、全体的な負荷は中程度で、ほとんどが読み取り、少数の書き込み、ほとんどがバッチ書き込みです。

現在のアプローチは、主キーにインデックスを付け、ハッシュ列にインデックスを付けて、Postgresを使用することです。テーブルは、ハッシュのインデックスをオフにしてバッチでロードされます。

すべてのインデックスはbtreeです。ハッシュ列のインデックスは、テーブル自体と同じかそれ以上に大きくなっています。120 GBのテーブルでは、インデックスを再作成するのに約1日かかります。ただし、クエリのパフォーマンスは非常に優れています。

問題は、ターゲットデータベースの予測サイズが4TBを超えることです。これは、ターゲット全体の約10％に相当する400GBの小さなデータセットを使用したテストに基づいています。Postgresに読み込まれると、残念ながら、ストレージの50％以上がハッシュ列のSQLインデックスによって使用されています。

これは大きすぎます。そして、ハッシュの冗長性は、より少ないストレージの機会であると感じています。

これは問題を説明していますが、作成する必要のあるこれらのテーブルがいくつかあることにも注意してください。

逆索引がある場合 (たとえば、ブルータスのページのソート済みリスト、シーザーのページのソート済みリスト、およびカルプルニアのページのソート済みリストがある場合)、シーザー AND ブルータス AND カルプルニアを実行すると、どこかで読みました。 calpurnia と brutus のページ数が caesar のページ数よりも少ない場合は、caesar AND (brutus と calpurnia) を実行する必要があります。つまり、後者の AND を最初に評価する必要があります。一般に、一連の AND がある場合は常に、ページ数が最も少ないペアを最初に評価します。この背後にある理由は何ですか？なぜこれが効率的なのですか？

Luceneのどのクラスが転置インデックスを生成するのか知りたいですか？

ありがとう

全文検索の基本的な側面が逆索引の使用であることを理解しています。そのため、転置インデックスを使用すると、1 語のクエリに答えるのが簡単になります。インデックスが次のように構成されていると仮定します。

some-word -> [doc385, doc211, doc39977, ...] (ランク順、降順)

その単語のクエリに答えるには、インデックスで正しいエントリを見つけ (O(log n) 時間かかります)、インデックスで指定されたリストから特定の数のドキュメント (たとえば、最初の 10) を提示するだけです。

しかし、たとえば 2 つの単語に一致するドキュメントを返すクエリについてはどうでしょうか。最も簡単な実装は次のとおりです。

1. A を単語 1 を持つドキュメントのセットに設定します (インデックスを検索することにより)。
2. B を単語 2 (同上) を持つドキュメントのセットに設定します。
3. A と B の交点を計算します。

さて、ステップ 3 の実行にはおそらく O(n log n) の時間がかかります。非常に大きな A と B の場合、クエリの応答が遅くなる可能性があります。しかし、Google のような検索エンジンは、常に数ミリ秒で回答を返します。したがって、それは完全な答えではありません。

明らかな最適化の 1 つは、Google のような検索エンジンは一致するすべてのドキュメントを返すわけではないため、交差全体を計算する必要がないことです。最小のセット (例: B) から始めて、他のセット (例: A) にも属する十分なエントリを見つけることができます。

しかし、次の最悪のケースはまだあり得ませんか? A を一般的な単語に一致するドキュメントのセットに設定し、B を別の一般的な単語に一致するドキュメントのセットに設定した場合でも、A ∩ B が非常に小さい (つまり、組み合わせがまれである) 場合があります。つまり、検索エンジンは B のすべての要素 x メンバーを直線的に調べ、それらが A の要素でもあるかどうかをチェックして、両方の条件に一致する少数を見つける必要があります。

線形は速くありません。また、検索する単語が 3 つ以上ある場合もあるため、並列処理を採用するだけでは完全な解決策にはなりません。では、これらのケースはどのように最適化されるのでしょうか? 大規模な全文検索エンジンはある種の複合インデックスを使用しますか? ブルームフィルター？何か案は？

検索エンジン (または同様の Web サービス) は、フラット ファイルおよび nosql データベースを使用します。Inverted Index の構造は多対多の関係より単純ですが、後者の関係で処理する方が効率的です。数十億の Web ページと数百万のキーワードに対して 2 つのテーブルが必要です。5,000 万行のテーブルをテストしました。mysql の速度は BerkeleyDB の速度に匹敵します。

大規模な mysql データベースを操作する際の問題は、ALTER TABLE などを扱うときに発生すると思います (ここでは当てはまりません)。このパフォーマンスは、mysql が非常に優れている読み取り集中型です。SELECT で行を読み取るとき、数行のテーブルと数百万行のテーブルの間に大きな違いは見つかりませんでした。数十億の行がある場合は異なりますか?

注: Google や Bing (または全文検索などの高度な機能) を意味するのではなく、概念について説明しています。

私は現在、テキスト検索におけるベクトル空間モデルに似た視覚的単語ベースの画像検索システムのバッグを書いています。このフレームワークでは、各画像はベクトル (または文献ではヒストグラムとも呼ばれます) で表されます。基本的に、ベクトル内の各数値は、その画像内で各「ビジュアル ワード」が出現する回数をカウントします。2 つの画像が互いに「近い」ベクトルを持っている場合、これは、多くの画像特徴が共通しており、したがって類似していることを意味します。

私は基本的に、そのようなベクトルのセットの逆ファイル インデックスを作成しようとしています。自家製のデータ構造のハックが機能しないように、数千 (試用段階) から数十万または数百万以上の画像にスケーリングできるものが必要です。

私はLuceneを見てきましたが、どうやらそれはテキストのみにインデックスを付けているようです（間違っている場合は修正してください）が、私の場合は数字（つまりベクトル自体）にインデックスを付けたいと思っています。次の方法でベクターをテキスト ドキュメントに変換するケースを見てきました。

<3, 6, ..., 5> --> "w1 w2... wn". 基本的に、ゼロ以外のコンポーネントは、テキストの単語 "w[n]" に置き換えられます。ここで、n はその数値のインデックスです。次に、この「ドキュメント」が Lucene に渡されてインデックスが作成されます。

この方法を使用する際の問題は、ベクトルのテキスト表現が特定の「単語」の出現頻度をエンコードしないため、取得した画像のランキングが良くないことです。

Lucene を引き続き使用できるように、ベクターを処理できる成熟したインデックス API を知っている人はいますか? また、Lucene for Image Retrieval (LIRE) プロジェクトを調べ、付属のデモを試してみましたが、そのデモを実行したときに生成された例外の数により、それを使用するかどうかわかりません。

API の言語に関しては、C++ または Java を使用できます。

返信ありがとうございます。