8

trie文字列処理を行うために使用しているものがあります。私はいくつかのデータから生成する単純なコンパイラを持っていtrieます。一度生成されると、trie実行時に変更されません。

トライをファイルに保存して効果的にロードできるアプローチを探しています。私はsqlliteそれらがどのように持続しているかを理解するために調べましたb-treeが、それらのファイル形式は少し高度に見え、それらすべてを必要としないかもしれません。

誰かが永続化して読むためのアイデアを提供できれば便利ですtrie。私はCを使ってプログラミングしています。

4

4 に答える 4

12

私はいくつかの調査を行い、次の小さな宝石をオンラインで見つけました。

  1. trie.h
  2. trie.c

シリアライゼーションとデシリアライゼーションを伴う作業トライ。もともとは Python で使用するために作成されました (Python にtriemodule.c関連付けるための対応するものがあります) が、純粋な C です。アイデアを掘り下げたり、必要に応じて使用したりできます。

更新：

リンクが機能していないようです。私はオリジナルを維持しますが、ウェイバックマシンのリンクは次のとおりです。

  1. trie.h
  2. trie.c
于 2010-04-03T17:53:20.390 に答える
5

データ構造全体がメモリに収まると仮定すると、再帰的なシリアル化アプローチが最も簡単です。Sqllite はメモリに収まらないデータ構造で動作するため、それらのメソッドをコピーしようとするのはおそらくやり過ぎです。

ノードの読み取り/書き込みの疑似コードの例を次に示します。子ノードを再帰的に読み書きすることで機能します。トライ固有のものはなく、他のツリー データ構造でも機能するはずです。

void writeNode(Node *node)
    write node data to file
    write node.numOfChildren to file
    for each child:
        writeNode(child)

Node *readNode()
    Node *node = allocateNewNode()
    read node data from file
    read node.numOfChildren from file
    for (i=0; i<node.numOfChildren; i++)
        Node *child = readNode()
        node.addChild(child)
于 2010-04-03T17:54:47.647 に答える
1

すべてのノードが同じサイズの場合は、ノードを列挙し、(root = 0)それぞれのノードをファイルのインデックスに書き込むことができます。ただし、それらを作成する際に、他のノードへの参照をそれらのノードのインデックスに変更する必要があります。NULLおそらく、値も必要になるでしょう。を使用することも、 and (-1を使用することもできます。(root = 1)NULL = 0).

これらのノードのポインター フィールドをより小さな型に変更することで、これらのノードをある程度圧縮することもできます。

ノードのサイズが異なる場合は、より複雑になります。

于 2010-04-05T07:46:10.230 に答える