python - 为自动更正程序快速保存和检索 python 数据结构？

Question

因此，我用 Python 2 编写了一个自动完成和自动更正程序。我使用提到的方法编写了自动更正程序是 Peter Norvig 的关于如何编写拼写检查器的博客，link .

现在，我正在使用使用嵌套列表实现的 trie 数据结构。我正在使用一个特里树，因为它可以给我所有以特定前缀开头的单词。在叶子上将是一个包含单词的元组和一个表示单词频率的值。例如-单词 bad、bat、cat 将是另存为-

['b'['a'['d',('bad',4),'t',('bat',3)]],'c'['a'['t',('cat',4)]]]

其中 4、3、4 是单词被使用的次数或频率值。同样，我对英语词典中的大约 130,000 个单词进行了 trie，并使用 cPickle 将其存储。

现在，每次读取整个 trie 大约需要 3-4 秒。问题是每次遇到一个单词时，频率值必须递增，然后需要再次保存更新的 trie。正如您可以想象的那样，每次等待 3-4 秒来读取然后再次等待那么多时间来保存更新的 trie 将是一个大问题。每次运行程序时，我都需要执行大量更新操作并保存它们。

有没有更快或更有效的方法来存储将重复更新的大型数据结构？ IDE 和移动设备中自动更正程序的数据结构如何如此快速地保存和检索？我也对不同的方法持开放态度。

Answer 1

我想到了一些事情。

1) 拆分数据。假设使用 26 个文件，每个文件存储以特定字符开头的尝试。您可以改进它以便使用前缀。这样您需要写入的数据量就更少了。

2) 不要将所有内容都反射(reflect)到磁盘。如果您需要执行大量操作，请在 ram(内存)中执行它们，然后在最后写下来。如果你害怕数据丢失，你可以在 X 时间或一些操作之后检查你的计算。

3) 多线程。除非您的程序只进行拼写检查，否则很可能还需要做其他事情。有一个单独的线程来执行加载写入，这样它就不会在执行磁盘 IO 时阻塞所有内容。 python 中的多线程有点棘手，但可以做到。

4) 自定义结构。花在序列化上的部分时间是调用序列化函数。因为你有一个包含很多函数调用的所有东西的字典。在完美的情况下，您应该有一个与磁盘表示完全匹配的内存表示。然后您只需读取一个大字符串并将其放入您的自定义类(并在需要时将该字符串写入磁盘)。这有点高级，可能好处不会那么大，特别是因为 python 在处理位方面效率不高，但如果你需要从中挤出最后一点速度，这就是要走的路。