有效存储的字典.这个数据结构是否存在以及它的名称是什么？

Question

我想要一个存储大量低熵数据的数据结构,这些数据通常彼此相似.我希望有效地存储它们(以某种方式压缩)并通过索引或匹配来检索它们.快速检索比压缩更重要,但不能将它们存储为未压缩的选项.

我能想到的最好的例子是存储从文本卷中获取的十亿个书面句子(在磁盘上以压缩形式).

dict:
1: 'The quick brown fox jumps over the lazy dog.'
2: 'The quick green frog jumps over the lazy fox.'
3: 'The quick brown fox jumps over the lazy frog.'

如果两个句子相同,则它们应具有相同的索引.

我想通过索引或通配符匹配来检索它们(正则表达式也很好,但不是必需的).即:

dict.get(1) => 'The quick brown fox jumps over the lazy dog.'
dict.match('The quick brown *') => [1, 3]

我可以压缩每个句子,但忽略了许多条目相似的事实.

我可以对它们进行排序并存储差异.但是添加和删除元素非常困难.

它应该支持unicode.

我确信那里有一些树形结构可以做到这一点.

如果它有一个python包装器,奖励积分.

这个https://hkn.eecs.berkeley.edu/~dyoo/python/suffix_trees/看起来非常接近但是从2002/py2.2开始就没有看到动作,我无法运行它.如果有更新/更好的选择退房,我很想听听他们.

我包含了bioinformatics标签,因为我知道在那里使用了suffix_trees和类似的数据结构.

Answer 1

正如您已经指出的那样,后缀树或基数树可能是要走的路.我建议:

1. 创建基数树,将id存储在叶子中.检查一下这个答案中的链接,但我相信你必须根据你的需要微调你发现的任何内容;

2. 创建一个dict映射id到树中的路径.这将允许您通过id快速检索句子(找到路径,按照它来安装句子).请注意,这将使插入和删除成本有点高:每次更改非叶子节点时,每个后代都需要在dict中更新其路径;

   2.1.另一种方法(如果路径结束太长)是让每个节点存储对其父节点的引用,因此dict只需要引用叶节点.我相信大多数实现都没有这样做,因为尝试的主要目标是加速查找,而不是压缩文本本身.

3. 通配符搜索有点棘手,具体取决于您的需求的复杂程度.提供的示例很简单:按照前缀的节点,直到找到通配符,然后返回所有后代.在这种情况下,通用trie可能比更专业的基数树更容易处理,但空间要求更高一些.

顺便说一句,您还可以优化基数trie以减少空间,通过在节点中实现字符串的内部使用一些间接,以及为长的公共子字符串添加额外的节点.例:

unique_strings = [ # Not a real array, just an hypothetical "intern table"
    "The quick ",
    "brown fox ",
    "green frog ",
    "jumps over the lazy ",
    "dog.",
    "fox.",
    "frog.",
]
radix_trie = (0, {        # The quick *
    "b":(1, {             # The quick brown fox *
        "j":(3, {         # The quick brown fox jumps over the lazy *
            "d":(4,{},1), # The quick brown fox jumps over the lazy dog.
            "f":(6,{},3), # The quick brown fox jumps over the lazy frog.
        }),
    }),
    "g":(2, {             # The quick green frog *
        "j":(3, {         # The quick green frog jumps over the lazy *
            "f":(5,{},2), # The quick green frog jumps over the lazy fox.
        }),
    }),
})
# The nodes ("b", "j") and ("g", "j") wouldn't occur in a regular radix tree,
# since they have no siblings. Adding them, however, gives a net gain of space.
#
# "jumps over the lazy " is a common substring of
#     "brown fox jumps over the lazy " and
#     "green frog jumps over the lazy fox."
# which would occur naturally in a radix tree with only the 3 sentences given.
paths = {
    1:("b", "j", "d"),
    2:("g", "j", "f"),
    3:("b", "j", "f"),
}

当然,对于你的例子来说这很容易设置,但是"在野外"找到重复的子串将会有点棘手.(在任何一对字符串中找到长公共子串:非常昂贵的操作可行,请参阅更新)但是,假设插入/删除是不常见的操作,这应该不是一个大问题.

注意:我建议使用基数树而不是trie,因为前者的空间要求要小得多.

更新:以防万一你计划自己解决问题,这里还有一个使用基数树压缩数据的提示:根据维基百科关于最长公共子串的文章,你可以构建一个通用后缀树并用它来查找两个或多个字符串的常见子串(它还提到它主要用于生物信息学).为基数树的节点(或者至少是超过特定大小的节点)创建一个节点,您可以找到要在较小节点中拆分它们的情况.

使用您的示例,"常规"(没有单独的孩子)基数树将是:

radix_tree = ("The quick ", {
    "b":("brown fox jumps over the lazy ", {
        "d":("dog.",{},1),
        "f":("frog.",{},3),
    }),
    "g":("green frog jumps over the lazy fox.", {}, 2),
})

这显然不能很好地压缩你的文字.但是,在为每个节点中的单词集创建后缀树之后,很明显,这" jumps over the lazy "是一个很好的候选者,可以在两个或多个节点中进行实习和重用(导致我之前展示的示例).保存的空间将始终为(string_length - (1..2)*sizeof_node) * num_nodes(前缀/后缀为1,休息时为2),因此在进行此优化时根本不需要考虑短字符串.

复杂,是的,正如Adam Mihalcin指出的那样,纯Python解决方案可能成本太高,无法存储非常大的数据集.但是如果那里没有现成的解决方案,这就是我首先尝试的......

Answer 2

您的问题听起来与trie的用例完全相同，这是一种基于树的数据结构，用于按前缀存储字符串。我自己没有使用过这些实现，但是对 Google 代码的快速搜索显示了开源 trie 项目这里和这里和这里。前两个是 Java 语言，第三个是 C++ 语言。我预计为 Python 编写 C++ 包装器会比为 Java 编写包装器更容易，因为 Python 具有与 C 互操作的内置功能。

编辑

我查看了 GitHub，并且在 Python 实现方面取得了一些成功。我在这里、这里和这里找到了 Python trie 实现。

但是，如果您确实要处理十亿个句子，即使是编写得非常好的纯 Python 实现（这三个都是如此）也可能会耗尽内存。