1

SSDでトライを作成する必要があります。トライが非常に大きいため、あまり RAM を使用できませんが、4 GB の RAM は問題ありません。

現在、私は次の方法でそれを行うことを考えています：

  • 1 つのメモリ マップト ファイルの使用
  • オブジェクトを protobuf でシリアライズし、ファイルの位置と長さで他のオブジェクトへのポインターを変更する

今、私は役立つツールを探しています。オブジェクト (ノード) が大きくなると問題が発生します。ファイル内でこのオブジェクトの新しい場所を見つけて、このオブジェクトへのすべてのリンクを変更する必要があります。そして、ファイルにギャップが残っています。次に、ツリーを圧縮し、すべてのオブジェクトのすべての位置を変更してギャップを埋める必要があります。各オブジェクトの後にいくらかのスペースを残すと、非常に多くのスペースが必要になります。

ライブラリを知っていますか、この問題を解決するためのヒント、またはこれらすべてをプログラミングするのに役立つヒントはありますか?

4

2 に答える 2

1

編集：これはメモリマップファイルアプローチのためのものです。私はあなたの直感が本当に好きでした。

Edit2 : 「ポイント」または「ポインター」と言うたびに、実際にはファイルの先頭からのゼロベースのオフセットを意味します。書き込まれたデータが移動することはないため、ノードの位置はノードのグローバル識別子として機能します。

ただし、ノードが実際に大きくなることはありません。私がそれを行う方法は、ノードを次のようにすることです。

  • ノードが保持する文字 (必要に応じて UTF-8 でエンコード)
  • その子へのポインターを保持する、たとえば 8 つの項目の配列。NULLこれは、これ以上子を指定しない (または 0)で静的にディメンション化されます。このリストが短くなることはなく、大きくなるだけです。
  • 子ポインタの別の配列を保持するメモリの一部へのポインタで、これも静的に次元付けされます。実際には余分なスペースが必要ない場合でも、常にこれを持っているので、そこに書き込むことができますNULL。
    • 実際の有効なメモリを指している場合、リストの直後に、必要に応じて追加のリストへの別のポインターがあるため、必要に応じてどこまででも移動できます。または、2 番目のリストは、すべての文字を保持するのに十分な大きさにすることができます。

別の方法として、最初からすべての文字に十分なメモリを静的に割り当てます。ただし、ツリーのまばらさによっては、これが大きくなりすぎる可能性があります。

いずれにせよ、この方法では実際のノード サイズは決して増加せず、静的な長さになることに注意してください。必要に応じて、ファイルの最後に追加のノードまたは追加のリスト チャンクを追加し、最初にすべての子を指すルートを保持することができるので、頭をいじる必要はありません。

于 2012-07-10T17:15:40.397 に答える
0

ここで、この問題に新しい角度を提供しようとしています: トライノードを SQLite のようなデータベースに保存してみませんか? SQLite は高速で、十分にテストされ、機能が豊富です。あなたよりもずっと良い仕事をする可能性が高いです。

リレーショナル データベースは実際にはツリーを格納するようには作られていませんが、ツリーを格納することはできます。カスタム トライ オンディスク データ構造を作成することで大幅に解決できる特定のクエリの問題は思い浮かびません。

于 2012-07-10T19:15:42.507 に答える