1

我需要在 ssd 上创建一个trie 。我不能使用太多 RAM，因为 trie 很大，但 4 GB RAM 没问题。

目前我考虑通过以下方式进行操作：

  • 使用一个内存映射文件
  • 使用 protobuf 序列化对象，使用文件位置和长度更改指向其他对象的指针

现在我正在寻找可以提供帮助的工具。当对象（节点）变大时我会遇到问题。我需要在文件中为该对象找到一个新位置，更改指向该对象的所有链接。然后我的文件中留下了一个空白。然后我需要压缩我的树并更改所有对象的所有位置以缩小一些差距。在每个对象之后留出一些空间会导致非常大的空间需求。

你知道图书馆或者有一些提示来解决这个问题或者可以帮助编程这一切吗？

4

2 回答 2

1

编辑：这是用于内存映射文件的方法，我真的很喜欢你的直觉。

Edit2：每次我说“点”或“指针”时，我实际上是指从文件开头开始的从零开始的偏移量。由于写入的数据永远不会移动，因此节点的位置充当它们的全局标识符。

一个节点不应该真的变大。我这样做的方式是让节点像：

  • 节点持有的字符（如果需要，UTF-8 编码）
  • 一个包含 8 个项的数组，其中包含指向其子项的指针。这是静态尺寸的NULL（或 0），指定不再有子级。这个列表永远不会变短，只会变大。
  • 指向一块内存的指针，该内存包含另一个子指针数组，也是静态尺寸的。即使您实际上并不需要额外的空间，您也总是拥有这个，您可以在NULL其中写入。
    • 如果指向实际有效内存，则在列表之后，如果需要，您将有另一个指向额外列表的指针，因此您可以走多远。或者，第二个列表可以大到足以容纳所有字符。

作为替代方案，从一开始就为所有字符静态分配足够的内存。但是，这可能会变得太大太快，具体取决于树的稀疏程度。

无论哪种方式，请注意，通过这种方式，您的实际节点大小永远不会增加，它具有静态长度。您可以根据需要在文件末尾添加额外的节点或额外的列表块，并在开头保留一个根以指向其所有子节点，这样您就不必弄乱头部了。

于 2012-07-10T17:15:40.397 回答
0

我试图在这里为这个问题提供一个新的角度：你为什么不将 trie 节点存储在 SQLite 之类的数据库中？SQLite 速度快、测试良好且功能丰富。它可能比你做得更好。

关系数据库并不是真正用来存储树的，但它们可以。我想不出任何特定的查询问题可以通过编写自定义的磁盘数据结构来更好地解决。

于 2012-07-10T19:15:42.507 回答