Python字典的内存节省替代方案
在我现在的一个副项目中，我正在扫描一些文本，查看单词三元组的出现频率。第一次尝试时，我使用了默认的字典，深度为三层。换句话说，topDict[word1][word2][word3] 会返回这些单词在文本中出现的次数，而topDict[word1][word2] 则返回一个字典，里面包含所有在单词1和单词2后面出现的单词，等等。
这个方法是有效的，但它非常占内存。在我最初的测试中，它使用的内存大约是仅仅把三元组存储在文本文件中所需的20倍，这似乎占用了过多的内存。
我怀疑这些字典中有很多位置是多余的，实际上并没有被使用，所以我想用其他更节省内存的东西来替代字典。我希望能找到一种解决方案，能够像字典那样方便地查找键。
根据我对数据结构的了解，使用像红黑树或AVL树这样的平衡二叉搜索树可能是理想的选择，但我真的不想自己去实现它们。如果可能的话，我希望能使用标准的Python库，但如果有其他更好的选择，我也很乐意尝试。
那么，有人能给我一些建议吗？
补充说明：
感谢大家的回复。目前为止，有一些回答建议使用元组，但当我把前两个单词压缩成一个元组时，这对我帮助不大。我不太想把三个单词都作为一个键，因为我希望能方便地查找给定前两个单词时的所有第三个单词。（也就是说，我想要类似于topDict[word1, word2].keys()的结果）。
我现在正在处理的数据集是最新版本的Wikipedia For Schools。例如，解析前一千页的结果是一个大约11MB的文本文件，每行是三个单词和它们的计数，都是用制表符分开的。而我现在使用的字典格式存储这些文本大约需要185MB。我知道指针等会有一些额外的开销，但这个差距似乎太大了。
12 个回答
在这种情况下，ZODB¹ 的BTrees可能会很有帮助，因为它们占用的内存要少得多。你可以使用BTrees.OOBtree（对象键对应对象值）或者BTrees.OIBTree（对象键对应整数值），并且可以用三个单词的元组作为你的键。
像这样：
from BTrees.OOBTree import OOBTree as BTree
这个接口大致上像字典一样，额外的好处是，.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上有哦 ☺
使用元组。
元组可以作为字典的键，这样你就不需要把字典嵌套在一起了。
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"，那么可以在字典的键中用列表推导式来搜索。
如果你有一个元组 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) 开头的。
这里有一些测量数据。我用10MB的免费电子书文本计算了三元组的频率，生成了一个24MB的文件。把它存储在不同的简单Python数据结构中，所占用的空间（以kB为单位）如下，这些数据是通过运行ps命令得到的，d是字典，keys和freqs是列表，a、b、c和freq是三元组记录的字段：
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)；它们之所以被列出只是因为其他人建议过它们（或它们的变种）。（我有点不高兴，因为投票最高的答案并没有帮助，正如表格所示。）
‘对数组’是我原始答案中的方案（“我会从第一个两个单词作为键的数组开始...”），每对的值表用一个字符串表示。‘压缩对数组’和这个一样，只是省略了频率值为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'))
我还没有写出从这个结构中查找值的代码（可以使用下面提到的bisect模块），也没有实现下面描述的更复杂的压缩结构。
原始答案：一个简单的字符串排序数组，每个字符串是用空格分开的单词的连接，使用bisect模块进行搜索，应该是一个不错的开始。这可以节省指针等的空间。由于单词的重复，它仍然会浪费空间；有一个标准的技巧可以去掉公共前缀，并用另一个索引来找回它们，但这会复杂得多且速度较慢。（这个想法是将数组的连续块以压缩形式存储，必须顺序扫描，同时有一个随机访问的索引指向每个块。块的大小要足够大以便压缩，但又要小到合理的访问时间。这里适用的特定压缩方案是：如果连续的条目是‘hello george’和‘hello world’，那么第二个条目可以改为‘6world’（6是公共前缀的长度）。或者你也可以试试使用zlib？无论如何，你可以通过查找用于全文搜索的字典结构来了解更多这方面的内容。）所以具体来说，我会从一个以前两个单词为键的数组开始，配一个平行数组，列出可能的第三个单词及其频率。不过，这可能还是不太好——我觉得在内存高效的选项上你可能运气不好。
另外，二叉树结构在这里不推荐用于内存效率。例如，这篇论文测试了多种数据结构在类似问题上的表现（虽然是单元组而不是三元组），发现哈希表在这个指标上优于所有树结构。
我应该提到的，正如其他人所说的，排序数组可以仅用于单词列表，而不是用于二元组或三元组；然后对于你的“真实”数据结构，无论是什么，使用整数键而不是字符串——即单词列表的索引。（但这会让你无法利用公共前缀，除非在单词列表本身中。也许我不应该建议这个。）