c# - 将尝试保存到磁盘

Question

这听起来像一个简单的问题，但我不知道如何搜索它的答案。

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

谢谢。

Answer 1

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

需要考虑的问题：

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

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

• 优点：用户将看到更快的启动时间。
• 缺点：可能需要跨线程同步，在加载完全完成之前，用户会看到不完整的尝试。这可能是也可能不是一个展示停止器，具体取决于 trie 的用途。

Answer 2

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

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

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

• 结构的顶层是 a Dictionary<int, var>其中键是 n - 搜索词中的字母数。
• 字典中的每个值都是 a Lookup<string, string>，其中键是具有 n 个字母的字符串，值是所有以该字符串开头的字符串。例如，键“st”值可能是“start”、“stop”和“string”。

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

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

Answer 3

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

也就是说，要序列化 ​​trie 的节点，请执行以下操作：

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

编辑：只需重新阅读您的问题，您想从单词列表中从头开始构建 trie 吗？正如其他人所说，配置文件，但不仅仅是任何旧的分析器。他们并不都发现你的问题。这就是我所做的。它所花费的时间不应超过读取文件所花费的时间加上创建结构所花费的时间。