データ構造を保存/取得します

StackOverflow https://stackoverflow.com/questions/8300364

質問

私はaを実装しました 接尾辞ツリー Pythonでフルテキストサーチを作成し、非常にうまく機能しています。しかし、問題があります。インデックス付きテキストは非常に大きくなる可能性があるため、RAMに構造全体を持つことはできません。

enter image description here

画像： 単語用の接尾辞ツリー BANANAS （私のシナリオでは、100000倍大きい木を想像してください）。

だから、それについて少し研究している私は pickle モジュール、ファイルからの「ロード」および「ダンプ」オブジェクトのための優れたPythonモジュール、そして何を推測しますか？それは私のデータ構造で素晴らしく機能します。

それで、長いストーリーをより短くする：ディスクにこの構造を保存して取得するための最良の戦略は何でしょうか？つまり、各ノードをファイルに保存し、必要なときはいつでもディスクからロードすることができますが、これは最適ではありません（ディスクアクセスが多すぎます）。

脚注： この質問にタグを付けましたが , 、プログラミング言語は質問の重要な部分ではありません。ディスクの保存/取得戦略は本当に主要なポイントです。

役に立ちましたか？

解決

もしも pickle すでにあなたのために働いています、あなたは見たいかもしれません ZODB 上にいくつかの機能が追加されます pickle. 。ドキュメントを見ると、私はあなたが持っているサイズの懸念に対処しようとしているこの段落を見ました。

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

他のヒント

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

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

ファイルの冒頭に最初のノードを保存し、次のノードを指すオフセットがある場合があります。次のノードを読み取ることは、ファイルの正しいオフセットから読み取るだけです。

メモリマップされたファイルの利点は、それらがそれらです そうではありません 一度にメモリにロードされますが、必要に応じてディスクからのみ読み取ります。私はこれを（64ビットOSで）マシンに30 GBのファイルを使用して、4 GBのRAMのみがインストールされていますが、正常に機能しました。

どうですか それを保存します sqlite?

sqlite：

  • 最大2テラバイトのデータをサポートしています。
  • SQLクエリをサポートし、
  • アプリ内データを保存するのに最適な代替品です。
  • 1日あたり〜100kの訪問をサポートできます（平均Webアプリケーションに使用する場合）、

そのため、アプリケーション内にデータを保存する効率的な方法であることが証明されているため、このソリューションを詳しく調べることは良いかもしれません。

たぶん、あなたはcpickleとaを組み合わせることができます 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])

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

主なアイデアは、1文字のノードをたくさん持っている代わりに、それらを複数の文字の1つのノードにコンパクトして追加ノードを保存できることです。

ここのこのリンク（http://www.cs.sunysb.edu/~algorith/implement/suds/implement.shtml）160MBの接尾辞ツリーを33MBの圧縮接尾辞ツリーに変換できると言います。かなりの利益。

これらの圧縮ツリーは、巨大な弦での遺伝的サブストリングマッチングに使用されます。以前は、接尾辞ツリーでメモリが枯渇していましたが、圧縮した後、メモリのエラーが消えました。

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top