将 trie 持久保存到文件中 - C

Question

我有一个 trie，我用它来进行一些字符串处理。我有一个简单的编译器，它可以从一些数据生成 trie 。一旦生成，我的 trie 在运行时就不会改变。

我正在寻找一种方法，可以将特里结构保存在文件中并有效地加载它。我查看了sqllite来了解它们如何持久化b-tree，但它们的文件格式看起来有点高级，我可能不需要所有这些。

如果有人可以提供一些坚持并阅读 trie 的想法，那将会很有帮助。我正在使用 C 进行编程。

Answer 1

我做了一些研究并在网上发现了以下小宝石：

1. trie.h
2. trie.c

具有序列化和反序列化功能的工作 trie。它最初是为在 Python 中使用而编写的（有一个相应的 triemodule.c 用于将其绑定到 Python），但它是纯 C 语言；你可以挖掘它的想法或按照你的意愿使用它。

更新：

链接似乎不再有效。我会保留原件，但这里是回程机中的链接：

1. trie .h
2. trie.c

Answer 2

假设整个数据结构都适合内存，递归序列化方法是最简单的。 Sqllite 使用不适合内存的数据结构，因此尝试复制它们的方法可能有点过分了。

这是用于读/写节点的示例伪代码。它通过递归地读取/写入子节点来工作。它没有任何特定于 trie 的内容，并且也应该适用于其他树数据结构。

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)

Answer 3

如果所有节点的大小相同，那么您只需枚举节点 (root = 0) 并将每个节点写入其索引处的文件中即可。不过，在编写它们时，您必须将对其他节点的引用更改为这些节点的索引。您可能还需要一个 NULL 值。您可以使用 -1 或使用 (root = 1) 和 (NULL = 0)。

您可能还可以压缩这些节点通过将它们的指针字段更改为更小的类型来稍微改变。

如果您的节点大小不同，那么情况会更复杂。

Answer 4

一旦在内存中生成了trie，将其写入文件并不复杂，使用mmap，就像我们在连续的内存块中重新生成trie，或者可以用递归函数将每个节点写入文件中。