問題タブ [inverted-index]

私はバックグラウンドで何が起こっているのかを正確に理解しようとしています。

転置インデックスの単純化されたモデルを考えると（位置とスコアを忘れてください）：単語ごとに、ドキュメントIDのソートされたリストがあります。複数の単語のクエリは、それらのソートされたリストと交差して、別のそのようなリストを生成します。（最終的にはランキングがあります）

例えば

次のフィールドの理解は正しいですか？

異なるフィールドは、異なるインデックススペースまたは少なくとも異なるリストを意味します。たとえば、フィールドがabstractであり、bodyを持つと、次のようなシナリオになる可能性があります。

この理解は正しいですか？そうでない場合、基礎となる転置インデックスの観点から、これらのフィールドは何ですか？内部でどのように行われるかを明示的に示しているドキュメントは見つかりませんでした。

それとは別に、すべて/任意のフィールドで検索するような機能のサポートがあるかどうか疑問に思います。私が想定しているように実装した場合、これは面倒であるか、上記のようなリストを保持することによって冗長性が必要になるはずです。完全なワードリストのサブレンジを使用してフィールドを実装すると、確かにパフォーマンスが向上する可能性があります。

Luceneが実際に何をしているのかを知るのは素晴らしいことです。

これはSOに関する私の最初の投稿であり、私の質問が少し些細なものであることが判明した場合は、事前に謝罪します。プログラミングの世界は比較的新しいので、最初の「深刻な」OOP言語としてPythonを選択しました。SOアーカイブを検索しましたが、自分に完全に関連する質問は見つかりませんでした。さて、簡単に言えば、ここに問題があります：

私は転置インデックスに取り組んでいます。ネット上で従うべきチュートリアルとヒントをいくつか見つけ、次のことを行いました。

• 単語をステミングし、finditer関数のおかげで開始位置と終了位置でそれらを返すためのクラスドキュメント。

• ドキュメントのコレクション（リスト内のリスト）を取得し、それらをトークン化して、次の形式で転置インデックスに配置するクラスInverted_Index

{'word':{document_id:(start_pos, end_pos)}}

のように {'cloud': {0: [(5, 10)]}, 'document': {1: [(11, 19)], 2: [(22, 30)]} ...}。（私はSOトピックの助けを借りてdocument_idを実行し、ドキュメントの列挙されたコレクションを繰り返しました。ネストされた辞書については、次のように素人っぽく作成しました。

スタックowerflowを読んでいるときに、「defaultdict」データ型がそれを行うための非常に優れた方法であることに気付きましたが、「collections」モジュールをまだ理解していません。）

軌道に戻る：Inverted_Indexの内部で文字列をクエリとして受け取るQueryメソッド（OR演算子のバージョンのみ）を実行し、その文字列が転置インデックスのキー/用語と一致する場合、開始点と終了点が次のような用語：

そしてその後、私は...立ち往生しました。ドキュメント内で見つかった単語をその環境とともに出力するクエリ出力を作成したいのですが、クエリメソッド（開始位置と終了位置を持つdocument_id）と転置インデックスの結果を接続する方法がわかりません。彼女の環境内で一致したクエリを強調表示する方法の手がかりがあります。そのため、開始点と終了点を作成しましたが、Pythonでそれを強調する方法がわかりませんか？大胆に？

私は次のような結果を考えました：

###################
クエリ：「チョコレートプディング」
結果：
########
IDが1のドキュメントの場合：1
yaddi yaddi yadda Chocolate bla bla blaプリン
ホコレートブラブラブラプディングヤッディヤッディヤッダブラ

つまり、 http：//docs.python.org/2/library/string.html#string.centerを読んでいて、見つかった単語やクエリを同じ列に並べるとうまくいくと思っていました。しかし、そこにたどり着く方法がわからないので、Pythonの背後にあるロジックを理解することに固執しているので、プログラムに固執していないので、どんな種類のヒントも素晴らしいでしょう。その場合、チュートリアルはしません。正義。（はい、私はいくつかのPythonの本を手に入れましたが、おそらく初心者向けではないことを考慮して、この種の問題へのアプローチを拡張しましたが、どこから始めればよいのか、どのプログラムを使用できるのかわかりません。問題は、私たちは大学で言語理論とIR理論を学びますが、実際にはいくつかのことを行います。）

ありがとう！

そして、この私の人生の物語の終わりについて申し訳ありません：D

このトピックを曖昧にしないためのコードを忘れました：

ファイルから単語を読み取り、ダブルリンクリストに入れます.equals（）メソッドを使用して、単語がダブルリンクリストにあるかどうかを確認し、メソッドは正常に機能しましたが、compareto（）メソッドを使用して単語を並べ替えますこれらの例外が表示されます:-

メソッド:-

ダブルリンクリストの挿入方法:-

二重リンクリストの私の実装:

いくつかのブログや lucene の Web サイトでは、lucene が転置インデックスでデータ構造「スキップ リスト」を使用していることを知っています。しかし、私はそれについていくつかのパズルを持っています。

1:一般的に、スキップリストはメモリ上で使用される可能性がありますが、転置インデックスはディスク上に格納されます。では、インデックスを検索するときに lucene はどのように使用するのでしょうか? ディスク上でスキャンするか、メモリにロードするだけですか？

2:skip リストの挿入演算子は、次のレベルに挿入するかどうかを決定するためにランダム (0,1) を使用することがよくありますが、lucenne の導入では、すべての用語で一定の間隔のように見えます。

間違っている場合は修正してください。

ドキュメントを含む大規模なpostgresqlデータベースがあります。テーブル内の行として表されるすべてのドキュメント。新しいドキュメントがデータベースに追加されたら、重複をチェックする必要があります。selectしかし、完全に一致するものを見つけるためだけに使用することはできません。2つのドキュメントはわずかに異なる場合がありますが、それでも重複と見なすことができます。たとえば、一部のマイナーフィールドが異なり、他のすべてのフィールドが等しい場合などです。

私はこの問題を研究し、この問題を解決する方法を見つけます。すべてのドキュメントの署名を計算MinHashし、転置インデックスを作成して、データベースから同様のドキュメントをクエリすることができます。MinHashしかし、リレーショナルデータベースにマッピングする方法がわかりません。

私が理解しているように、MinHash署名はN個のハッシュのリストです。ここでNはいくつかの属性です。類似性は次のように計算されます。

すでに2つの署名がある場合、これは簡単です。問題は、データベース内で類似性がある程度の値以下のすべてのドキュメント（対応する署名を含む）を見つけることです。

たとえば、次のように複数の列を持つテーブルを作成できます。

各minhashX列は、ドキュメントの属性の1つのminhashに対応しdocid、ドキュメントの識別子です。次の方法で同様のレコードをクエリできます。

ここで、minhash2searchXは新しいドキュメントのミンハッシュであり、THRESHOLDは最小限の類似性です。ただし、このアプローチではフルスキャンが必要です。このアルゴリズムを高速化する方法はありますか？

私には仕事があります:逆インデックスの現在の実装をスピードアップします。私の意見では、クラウドで実行するのが最善の方法です。

1. 入力テキストをいくつかの部分に分割します (または、いくつかの異なるテキスト ファイルを取得します)。
2. テキストをノードに送信する
3. 異なる入力データに対して各ノードでアルゴリズムを実行する
4. 結果を収集してマージする

私の質問は、それを実装する最も簡単な方法は何ですか?

私の現在のアイデアは次のとおりです。

• Worker ロールを使用する Windows Azure - 異なるデータをノードに送信し、後でそれらをマージすることは可能ですか?
• Windows Azure と HPC スケジューラ - このようなタスクには強力すぎませんか? 構成とコストが心配です (新しいノード = 新しいワーカー ロール?)
• Amazon や Google などの他のクラウドを使用します。C# でコーディングしたいのですが、Microsoft テクノロジに精通しているため、少し恐れています。

この目標をどのように達成するかアドバイスをお願いします。

Invert Index のマップに巨大なデータを格納する必要がありますが、私のデータは非常に巨大であり、Map が大きくなるほど遅くなることがわかります。1 から数十億をカバーする、非常にまばらなインデックスを持つ Map コンテナについて話しています。

私のプログラムの 1 回の繰り返しで、いくつかの数値が計算され、多くのキー値 (数千になる可能性があります) が格納されます。これは、Map のサイズが繰り返しごとに約数千増加することを意味します。最初の数回の反復では 20 秒ほどかかりますが、70 回目の反復では 100 秒ほどかかります。約 5000 セットのデータがあります。つまり、これらすべてのデータに対して 5000 回の反復が必要です。各反復の時間が指数関数的に増加するため、計算に数日かかるため、これは受け入れられません。

この場合、私にできることはありますか？

テキストを検索し、検索されたテキストを逆索引で見て、対応する Web ページのセットを作成し、対応する Web ページをスローする検索エンジンがあります。

ここで、もう 1 つ機能を追加します。つまり、色に応じて検索します。

たとえば、「RED SHOES」を検索すると、逆インデックス データ構造にあるすべての赤い靴が表示されます。

同じアルゴリズムについて私が考えたことは、

1. 別の場所で画像のデータ構造を作成します。
2. ジャケットの画像と同じように、画像を見つけるたびに、何らかの色検出アルゴリズムを使用してすべての色を計算します。
3. そのイメージをすべてのカラー インデックスに入れます。

「赤い靴」のような検索が来たら、これがクローリングに対する私のアプローチです。赤色のインデックスで見て、対応する赤色のアイテムを見つけます。

これは私のアルゴリズム構築フェーズです。そのため、上記のアルゴリズムのコードを記述していません。正しいアプローチを取得したら、コーディング フェーズを開始します。

では、お勧めを教えてください、

それは良いアルゴリズムですか？また

必要な最適化や変更はありますか? もしそうなら、親切にその変更を私と共有/議論してください.

前もって感謝します。あなたの親切な対応を求めています。

前の質問: Data structure for storage huge number of indexs, each pointing to a setから、逆インデックスの実装に適したデータ構造に関する回答を得ました。ただし、問題は、Linux サーバーで 128 GB の RAM 制限にすぐに達する可能性があるため、再度メモリが不足した場合に備えて準備したいと考えています。

現在、インバート インデックスのインデックスの総数は 39 億に達しており、これには約 50 GB の RAM が必要です。データベースシステムなどを提案する人もいるかもしれませんが、これは実験的研究のためのものであり、独自のデータを管理したいと考えており、いかなる種類のデータベースシステムも使用しません.

ファイルアクセスにmmapを使用する必要があるのはいつですか？これは有望に見えますが、ググってみたら、最初に mmap に固定スペースを割り当ててから、データの挿入を開始する必要があることがわかりました。反転インデックスは大きくなりますが、ビルドするまで正確な数はわかりません。(一部のデータは、そのようなデータを反転インデックスにプッシュする前に最初に処理する必要があります) そのために大量のメモリを割り当てることができますが、現在の反転インデックスだけで既に 50 GB の RAM を取得しています。そして、これが 2 番目の問題 (2) につながります。私たちのサーバーには多くの人が使用しており、50 GB 以上のスペースがあると、データがハードディスク内で断片化されます。

あるいは、ファイル I/O を使用してこれを管理し、階層型ディレクトリのような B-Tree を作成するとどうなりますか? 具合が悪くなるかも…

今回は、上記の前の質問と同じように、いくつかの提案をお願いしたいと思いますが、今回は、RAM とハード ディスクの間でデータを交換する必要があります。128 GB の RAM はこれを保持できない可能性があります。