将 trie 保存到磁盘

Question

这听起来是一个简单的问题，但我不知道如何寻找它的答案。

我在 C# 中有一个 trie 实现，它将存储字典文件中大约 80K 的单词。加载所有这些单词需要相当长的时间（超过 5 分钟）。我想知道“保留”这些数据的最佳方法是什么，这样我就不必每次启动应用程序时都重新加载所有单词？

谢谢。

Answer 1

我只是以旧的 MFC 二进制方式序列化它。基本上，读/写应该尽可能快，你唯一要做的就是分配和初始化输入结构，无论如何你都需要这样做。

也就是说，要序列化特里树的节点，您可以执行以下操作：

Read/Write number N of subnodes
For each subnode
  If reading, allocate a subnode in this node
  Read/Write the character for the subnode
  Serialize the subnode
End

编辑：只需重新阅读您的问题，并且您想从单词列表从头开始构建特里树？正如其他人所说，分析，但不仅仅是使用任何旧的分析器。他们并不都发现你的问题。 这就是我所做的。 所花费的时间不应比读取文件所花费的时间加上创建结构所花费的时间多得多。

Answer 2

由于性能缓慢且序列化/反序列化时间缓慢，我最近重构了类似的数据结构。

我的解决方案是完全废弃 trie 并使用本机 .NET 集合 - 字典和查找。

我正在处理大约 40 万字。从内存中构建数据结构大约需要 5 秒，该数据结构是由多个字典和查找索引的对象列表。

• 该结构的顶层是
  Dictionary 其中键
  n - 中的字母数
  搜索词。
• 中的每个值
  字典是一个 Lookup 其中键是字符串
  有n个字母，值为全部
  以该字符串开头的字符串。
  例如对于关键的“st”值可能是
  “开始”、“停止”和“字符串”。

为了创建数据结构，我只需迭代 i = 1 到 maxlength 的整个单词列表，即可为每个 i 创建所有不同“开头为”字符串的查找。将它们插入顶级词典中即可完成。

这消除了对定制特里树的需要。我发现性能差异（搜索时间）可以忽略不计，但加载速度非常有利于我的设计（更不用说使用简单 .NET 类型的简单性和可维护性）。

Answer 3

与所有其他性能问题一样，理想的解决方案将通过分析您当前的解决方案和您提出的其他候选解决方案得出。瓶颈在哪里？输入/输出？对文本进行词法分析？在特里树中形成链接？如果不了解您的性能目标、特里结构使用的性质以及当前存在的瓶颈，将很难提出具体建议。

需要考虑的问题：

1. 存储格式：文本？二进制？
2. 持久数据：trie 的整个结构（例如 XML）或只是单词列表，依靠运行时代码将它们推送到数据结构中的正确位置？标记与数据的比率是多少？解析起来有多重？
3. 存储位置：数据库/平面文件/...？
4. 增量加载：可能吗？

一种可能的策略：创建并保留一本包含 1,000 个（左右）最常用单词的“最常用单词”字典。在启动时将这些单词加载到 trie 中，并在另一个线程上生成完整词典的加载；当读取新单词时逐渐添加到创建的特里树中。

• 优点：用户将看到更快的启动时间。
• 缺点：可能需要跨线程
  同步后，用户将看到
  不完整的 trie 直到加载
  完全完成。这可能是也可能不是一个阻碍因素，具体取决于特里树的用途。