11

全文検索を行うために Python でサフィックス ツリーを実装しましたが、非常にうまく機能しています。しかし、問題があります。索引付けされたテキストは非常に大きくなる可能性があるため、構造全体を RAM に格納することはできません。

ここに画像の説明を入力

IMAGE:単語のサフィックス ツリーBANANAS(私のシナリオでは、100000 倍大きいツリーを想像してください)。

それで、それについて少し調べてpickleみると、ファイルから/へオブジェクトを「ロード」および「ダンプ」するための優れたPythonモジュールであるモジュールが見つかりました。それは私のデータ構造で素晴らしく機能します。

長い話を短くすると、この構造をディスクに保存したり、ディスクから取得したりするための最良の戦略は何でしょうか? つまり、解決策は各ノードをファイルに保存し、必要なときにディスクからロードすることですが、これは最善の方法ではありません (ディスク アクセスが多すぎるため)。

脚注:この質問にというタグを付けましたが、プログラミング言語は質問の重要な部分ではなく、ディスクの保存/取得戦略が実際の要点です。

4

5 に答える 5

4

このような構造を管理する効果的な方法は、メモリ マップト ファイルを使用することです。ファイルには、ノード ポインターの参照を格納する代わりに、オフセットをファイルに格納します。pickleノード データをディスクに保存するのに適したストリームにシリアル化するために引き続き使用できますが、pickleモジュールはツリー全体を一度に埋め込もうとするため、参照の保存は避けた方がよいでしょう (これまで見てきたように)。

このmmapモジュールを使用すると、ファイルをアドレス空間にマップして、巨大なバイト シーケンスのように読み取ることができます。OS は、ファイルから実際に読み取り、ファイル バッファーとすべての詳細を管理します。

ファイルの先頭に最初のノードを格納し、次のノードを指すオフセットを設定する場合があります。次のノードの読み取りは、ファイル内の正しいオフセットから読み取るだけです。

メモリ マップト ファイルの利点は、ファイルが一度にすべてメモリに読み込まれるのではなく、必要なときにのみディスクから読み込まれることです。4 GB の RAM しかインストールされていないマシンで 30 GB のファイルを使用して (64 ビット OS で) これを実行しましたが、問題なく動作しました。

于 2011-11-28T18:49:13.527 に答える
3

pickleがすでに機能している場合は、にいくつかの機能を追加するZODBpickleを調べてみてください。ドキュメントを見ると、あなたが抱えているサイズの問題に対処するように見えるこの段落を見ました:

データベースは、メモリとストレージの間でオブジェクトを自由に移動します。オブジェクトがしばらく使用されていない場合、オブジェクトは解放され、次回の使用時にその内容がストレージからロードされます。

于 2011-11-28T18:59:07.037 に答える
1

それをsqliteに保存するのはどうですか？

SQLite:

  • 最大 2 テラバイトのデータをサポートし、
  • SQLクエリをサポートし、
  • アプリ内データを保存するための優れた代替品です。
  • 1 日あたり最大 10 万回の訪問をサポートできます (平均的な Web アプリケーションで使用する場合)。

このソリューションは、アプリケーション内にデータを保存する効率的な方法であることが証明されているため、詳しく見てみるとよいでしょう。

于 2011-11-28T18:42:32.823 に答える
1

おそらく、cPickle とbsddbデータベースを組み合わせて、ピクルされたノードをファイルシステムに保存される辞書のようなオブジェクトに保存できるようにすることができます。したがって、後でデータベースをロードして、必要なノードから非常に優れたパフォーマンスで取得できます。

非常に簡単な方法で：

import bsddb
import cPickle

db = bsddb.btopen('/tmp/nodes.db', 'c')
def store_node(node, key, db):
    db[key] = cPickle.dumps(node)

def get_node(key, db):
    return cPickle.loads(db[key])
于 2011-11-28T18:48:22.790 に答える
1

代わりに、圧縮されたサフィックス ツリーを試してください。

主なアイデアは、1 つのキャラクターのノードを多数持つ代わりに、それらを複数のキャラクターの 1 つのノードに圧縮して、余分なノードを節約できるということです。

このリンク ( http://www.cs.sunysb.edu/~algorith/implement/suds/implement.shtml ) には、160MB のサフィックス ツリーを 33MB の圧縮されたサフィックス ツリーに変換できると書かれています。かなりの利益。

これらの圧縮されたツリーは、巨大な文字列での遺伝的部分文字列の照合に使用されます。以前はサフィックス ツリーでメモリ不足が発生していましたが、圧縮したらメモリ不足エラーがなくなりました。

実装をよりよく説明する無料の記事を見つけられたらいいのにと思います。( http://dl.acm.org/citation.cfm?id=1768593 )

于 2011-12-16T03:10:58.617 に答える