4

逆インデックス/転記リストに関連して、最近学んでいる概念のいくつかを実装するために、いくつかの Python コードを書いています。私は Python を初めて使用し、場合によってはその効率を理解するのに苦労しています。

理論的には、それぞれが一意の ID を持つ一連のドキュメント D の逆インデックスを作成するには、次の手順を実行するdoc_id必要があります。

  1. Dでの各ドキュメントの構文解析/字句解析の実行
  2. ストップワードの削除、ステミングの実行など。
  3. (word,doc_id)すべてのペアのリストを作成する
  4. リストの並べ替え
  5. 重複を{word:[set_of_all_doc_ids]} (逆インデックス)に圧縮する

ステップ 5 は、多くの場合、メタデータ (単語の頻度、バイト オフセット) を含む単語と、投稿リスト (単語が出現するドキュメントのリスト) へのポインターを含む辞書を作成することによって実行されます。投稿リストは、効率的なランダム挿入を可能にするデータ構造、つまりリンクされたリストとして実装されることがよくあります。

私の問題は、Python が高水準言語であり、メモリ ポインター (したがって、リンクされたリスト) などを直接使用することは範囲外のように思われることです。非常に大きなデータセットの場合、適切な時間内にインデックスを計算するあらゆる種類の機能を保持するには、効率を最大化する必要があることが既にわかっているため、プロファイリングの前に最適化しています。

SO には、Python の逆インデックスに関する他のいくつかの投稿があり、MY の現在の実装と同様に、キーをリスト (またはセット) にマッピングする辞書を使用しています。このメソッドは、リンクされたリストへのポインターを直接コーディングできる言語と同様のパフォーマンスを期待できますか?

4

2 に答える 2

3

言いたいことがたくさんあります：

  1. 特定のリストの実装でランダム アクセスが必要な場合、 (使用するプログラミング言語に関係なく)リンク リストは最適ではありません。リストの i 番目の要素にアクセスするには、リンクされたリストで 0 番目の要素から i 番目の要素まで反復する必要があります。代わりに、リストは 1 つの連続したブロック (または非常に長い場合は複数の大きなブロック) として保存する必要があります。Python リスト[...]はこの方法で保存されるため、最初は Python リストで十分です。

  2. Python では、基本データ型 (または など) ではないオブジェクトの割り当ては 、ポインターを渡し、参照カウントを にインクリメントすることによって内部的に実行されます。したがって、がリストまたは辞書 (またはユーザー定義クラス) である場合、これは原則として、C または C++ でポインターを渡すことと大差ありません。a = bbintfloatbb

  3. ただし、明らかに、a) 参照カウントと b) ガベージ コレクションによってオーバーヘッドが発生します。実装が研究目的、つまり逆索引付けの概念をよりよく理解するためのものである場合、私はそれについて心配しません。しかし、本格的で高度に最適化された実装の場合、純粋な Python (Python に埋め込まれた C/C++ などではなく) を使用することはお勧めできません。

  4. 投稿リストの実装をさらに最適化すると、おそらく、a) ランダムな挿入を行い、b) 並べ替えを維持し、c) 圧縮を維持する必要があることがわかるでしょう。これらすべてを同時に行う必要があります。その時点で、標準の Python リストはもはや十分ではなくなり、より最適化されたリスト表現をC/C++で実装し、それを Pythonに埋め込むことを検討したくなるかもしれません。ただし、その場合でも、純粋な Python に固執することはおそらく可能です。たとえば、大きな文字列を使用してリストを実装し、ポインタ演算にある程度似た方法で特定の部分を使用itertoolsおよびアクセスすることができます。buffer

  5. Python で文字列を扱うときに常に心に留めておくべきことの 1 つは、代入操作について上で述べたことにもかかわらず、部分文字列操作には、単に参照カウントをインクリメントするのではなく、部分文字列text[i:j]の実際の (深い)コピーの作成が含まれることです。bufferこれは、上記のデータ型を使用することで回避できます。

于 2012-03-04T04:14:26.637 に答える
-1

Python の逆インデックスのコードとドキュメントは、http ://www.ssiddique.info/creation-of-inverted-index-and-use-of-ranking-algorithm-python-code.html で確認できます。

すぐに私はそれをC++でコーディングします..

于 2012-03-23T01:20:44.007 に答える