快速序列化字典树

Question

我的应用程序的一部分使用了一个叫做字典树的结构来把单词组合在一起。比如说，["Summer", "in", "Los", "Angeles"]可以变成["Summer", "in", "Los Angeles"]。

这个字典树的数据是从一个大型数据库中获取的，这个数据库是以SQL格式存储在本地的，每次应用启动时都会加载。这个过程需要很长时间，大约15秒。我想缩短应用的启动时间，所以我考虑过将字典树进行序列化。但是，使用pickle序列化的速度太慢了——比从数据库加载所有数据还要慢。

有没有更快的方法来序列化我的字典树呢？

这是字典树类的样子：

class Trie:
    def __init__(self):
        self.values = set()
        self.children = dict()

    def insert(self, key, value):
        """Insert a (key,value) pair into the trie.  
        The key should be a list of strings.
        The value can be of arbitrary type."""
        current_node = self
        for key_part in key:
            if key_part not in current_node.children:
                current_node.children[key_part] = Trie()
            current_node = current_node.children[key_part]
        current_node.values.add(value)

    def retrieve(self, key):
        """Returns either the value stored at the key, or raises KeyError."""
        current_node = self
        for key_part in key:
            current_node = current_node.children[key_part]
        return current_node.values

有没有什么方法可以改变它，使它更容易被序列化呢？

Answer 1

我知道我不是在给出一个Python的答案，但这可能还是有用的：

创建、压缩和存储一个前缀树（trie）其实是个很难的任务。我花了不少时间思考自动建议的数据结构，按照我所知道的，最优雅的解决方案是由Giuseppe Ottaviano提出的，在我的博客文章中部分描述过。

虽然在Python中实现Ottaviano在他的论文中描述的完整解决方案可能没有太大意义，但你可以考虑他的基本思路：把整个前缀树存储为一个大的内存块，只保存跳转到下一个位置的引用。

这样，你就可以很方便地将这个数组或内存块序列化到硬盘上。我对Python的具体实现不是很确定，但我觉得这个操作应该可以工作，而且比序列化一个数据结构要快得多。

我知道Ottaviano的工作有C语言的实现，你甚至可以使用Python的C语言绑定。

Answer 2

我最后把这个字典树存储在了MongoDB里。

虽然这样会有一些网络延迟，但如果数据库是在本地的话，影响并不是很大。