将trie保存到磁盘

Question

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

我在C#中有一个trie实现,它将存储来自字典文件的大约80K字.加载所有这些单词(超过5分钟)需要很长时间.我想知道,"持久化"这些数据的最佳方法是什么,所以每次启动应用程序时我都不必重新加载所有单词？

谢谢.

Answer 1

与所有其他性能问题一样,理想的解决方案将来自分析您当前的解决方案以及您提出的其他候选解决方案.瓶颈在哪里？I/O？翻译文字？在trie中形成链接？如果不了解您的性能目标,当前使用的特性和瓶颈的性质,将难以提出具体建议.

需要考虑的问题:

1. 存储格式:文字？二进制？
2. 持久数据:trie的整个结构(例如XML)或仅仅是一个单词列表,依靠运行时代码将它们推送到数据结构中的正确位置？什么是数据比率加成？解析有多重？
3. 存储位置:DB/flat-file/...？
4. 增量加载:可能吗？

一种可能的策略:使用最常用单词的1,000(左右)创建并保留"最常用单词"字典.在启动时将这些单词加载到trie中,并在另一个线程上生成完整字典的加载; 在读取新单词时逐步添加到创建的trie.

• 优点:用户将看到更快的启动时间.
• 缺点:可能需要跨线程同步,用户将看到一个不完整的trie,直到加载完全完成.根据trie的用途,这可能是也可能不是showstopper.