Python字典的内存高效替代品

Question

在我当前的一个侧面项目中，我正在扫描一些文本，查看单词三元组的频率。在我的第一次尝试中，我使用了默认字典三个层次。换句话说，topDict[word1][word2][word3]返回这些单词出现在文本中的次数，topDict[word1][word2]返回一个字典，其中包含出现在单词1和2之后的所有单词，等等

这一功能正常，但内存非常密集。在我最初的测试中，它使用的内存大约是将三元组存储在文本文件中的20倍，这似乎是一个过大的内存开销。

我的怀疑是，这些词典中的许多都是用比实际使用的更多的槽来创建的，所以我想用其他一些以这种方式使用时更节省内存的东西来替换词典。我强烈希望有一个解决方案，允许沿着字典的行进行键查找。

根据我对数据结构的了解，使用诸如红黑或AVL之类的平衡二叉搜索树可能是理想的，但我真的不希望自己实现它们。如果可能的话，我更喜欢使用标准的python库，但是如果其他的库能发挥最好的作用，我肯定会接受它们。

那么，有人对我有什么建议吗？

编辑以添加：

谢谢你到目前为止的回复。到目前为止，有几个答案建议使用元组，当我将前两个单词压缩成元组时，这对我来说并没有多大帮助。我不太愿意把这三个单词都当作一个键，因为我希望在前两个单词中查找所有第三个单词都很容易。（也就是说，我想要类似于topDict[word1, word2].keys()的结果）。

我正在使用的当前数据集是Wikipedia For Schools的最新版本。例如，对前1000页的解析结果类似于文本文件的11MB，其中每一行是三个单词，count all选项卡是分隔的。以我现在使用的字典格式存储文本大约需要185MB。我知道指针和其他东西会有一些额外的开销，但是差别似乎太大了。

Answer 1

一些测量。我获取了10MB的免费电子书文本，并计算了三元组的频率，生成了一个24MB的文件。将它存储在不同的简单Python数据结构中占用了大量的空间（以kB为单位），从运行ps的RSS中可以看出，其中d是dict，keys和freq是list，a、b、c、freq是trigram记录的字段：

295760     S. Lott's answer
237984     S. Lott's with keys interned before passing in
203172 [*] d[(a,b,c)] = int(freq)
203156     d[a][b][c] = int(freq)
189132     keys.append((a,b,c)); freqs.append(int(freq))
146132     d[intern(a),intern(b)][intern(c)] = int(freq)
145408     d[intern(a)][intern(b)][intern(c)] = int(freq)
 83888 [*] d[a+' '+b+' '+c] = int(freq)
 82776 [*] d[(intern(a),intern(b),intern(c))] = int(freq)
 68756     keys.append((intern(a),intern(b),intern(c))); freqs.append(int(freq))
 60320     keys.append(a+' '+b+' '+c); freqs.append(int(freq))
 50556     pair array
 48320     squeezed pair array
 33024     squeezed single array

标记为[*]的条目没有有效的方法查找一对（a，b）；它们被列出只是因为其他人建议它们（或它们的变体）。（如表所示，我有点恼火，因为排名靠前的答案没有帮助。）

“Pair array”是我最初的答案中的如下方案（“我将从带键的数组开始 作为前两个单词…），其中每对的值表是 表示为单个字符串压缩对阵列是一样的， 去掉等于1的频率值（最常见的 案例）“压缩单数组”类似于压缩对数组，但将键和值合并为一个字符串（带有分隔符）。压缩的单数组代码：

import collections

def build(file):
    pairs = collections.defaultdict(list)
    for line in file:  # N.B. file assumed to be already sorted
        a, b, c, freq = line.split()
        key = ' '.join((a, b))
        pairs[key].append(c + ':' + freq if freq != '1' else c)
    out = open('squeezedsinglearrayfile', 'w')
    for key in sorted(pairs.keys()):
        out.write('%s|%s\n' % (key, ' '.join(pairs[key])))

def load():
    return open('squeezedsinglearrayfile').readlines()

if __name__ == '__main__':
    build(open('freqs'))

我还没有编写代码来查找这个结构中的值（使用下面提到的等分），也没有实现下面描述的更高级的压缩结构。

原始答案：一个简单的字符串排序数组，每个字符串是一个用空格分隔的单词串接，使用对分模块进行搜索，应该值得一试。这样可以节省指针等的空间。由于单词的重复，它仍然会浪费空间；有一个标准的技巧可以去掉常见的前缀，并使用另一个级别的索引将其还原，但这会更加复杂和缓慢。（其思想是以压缩的形式存储数组的连续块，这些块必须按顺序扫描，并随机访问每个块的索引。块足够大，可以压缩，但足够小，可以提供合理的访问时间。这里适用的特殊压缩方案是：如果连续的条目是“hello george”和“hello world”，则将第二个条目改为“6world”。（6是前缀的共同长度）或者也许你可以使用zlib？无论如何，您可以通过查找全文搜索中使用的字典结构来了解更多信息。）因此，具体地说，我将从键是前两个词的数组开始，使用一个并行数组，其条目列出可能的第三个词及其频率。不过，它可能仍然很烂——我想你可能会走运，因为电池包括内存效率高的选项。

此外，为了提高内存效率，建议使用二叉树结构而不是。E、 g.，this paper在一个类似的问题上测试各种数据结构（但是是unigrams而不是trigrams），并找到一个哈希表，通过这个度量击败所有的树结构。

我应该像其他人一样提到，排序数组可以只用于wordlist，而不是bigrams或trigrams；然后对于“真实”的数据结构，不管它是什么，都可以使用整数键而不是字符串——索引到wordlist中。（但这使您无法利用除wordlist本身之外的常见前缀。也许我不应该建议你这么做。）

Answer 2

使用元组。
元组可以是字典的键，所以不需要嵌套字典。

d = {}
d[ word1, word2, word3 ] = 1

另外，还可以使用defaultdict

• 所以没有条目的元素总是返回0
• 这样你就可以说d[w1,w2,w3] += 1而不必检查密钥是否已经存在

示例：

from collections import defaultdict
d = defaultdict(int)
d["first","word","tuple"] += 1

如果需要找到所有用（word1，word2）组成元组的单词“word3”，那么使用列表理解在dictionary.keys（）中搜索它

如果有一个元组t，则可以使用切片获取前两个项：

>>> a = (1,2,3)
>>> a[:2]
(1, 2)

使用列表理解搜索元组的一个小示例：

>>> b = [(1,2,3),(1,2,5),(3,4,6)]
>>> search = (1,2)
>>> [a[2] for a in b if a[:2] == search]
[3, 5]

在这里，我们得到了一个列表，其中列出了以（1，2）开头的元组中显示为第三个项的所有项

Answer 3

在这种情况下，ZODBüBTrees可能是有帮助的，因为它们不需要太多内存。使用BTrees.OOBtree（对象键到对象值）或BTrees.OIBTree（对象键到整数值），并使用3字元组作为键。

类似于：

from BTrees.OOBTree import OOBTree as BTree

这个接口，或多或少，像dict一样，附加的好处是.keys、.items、.iterkeys和.iteritems有两个min, max可选参数：

>>> t=BTree()
>>> t['a', 'b', 'c']= 10
>>> t['a', 'b', 'z']= 11
>>> t['a', 'a', 'z']= 12
>>> t['a', 'd', 'z']= 13
>>> print list(t.keys(('a', 'b'), ('a', 'c')))
[('a', 'b', 'c'), ('a', 'b', 'z')]

请注意，如果您使用的是Windows，并且使用的是Python>；2.4，我知道有一些最新的Python版本的软件包，但我记不起在哪里。

PS它们存在于CheeseShop☺