Python字典的内存有效替代品

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

这功能正常,但内存非常密集.在我的初始测试中,它使用了将三元组存储在文本文件中的内存的20倍,这看起来像是一个过大的内存开销.

我怀疑这些词典中的许多都是使用比实际使用的更多的插槽创建的,所以我想用这种方式使用更高效的内存来替换字典.我强烈希望有一种解决方案,允许按字典的方式进行键查找.

根据我所知的数据结构,使用红黑或AVL之类的平衡二叉搜索树可能是理想的,但我真的不想自己实现它们.如果可能的话,我宁愿坚持使用标准的python库,但如果它们最好的话,我肯定会接受其他选择.

那么,有没有人对我有任何建议？

编辑添加:

感谢到目前为止的回复.到目前为止,一些答案建议使用元组,当我将前两个单词浓缩为元组时,这对我来说并没有什么作用.我很犹豫要把所有这三个用作关键因为我希望它能够很容易地查找前两个字的所有第三个字.(即我想要的结果topDict[word1, word2].keys()).

我正在玩的当前数据集是维基百科学校的最新版本.例如,对于文本文件,解析前几千页的结果类似于11MB,其中每行是三个单词并且计数所有选项卡分开.以我现在使用的字典格式存储文本大约需要185MB.我知道指针和诸如此类的东西会有一些额外的开销,但差异似乎过大.

一些测量.我拿了10MB的免费电子书文本并计算了三元组频率,产生了24MB的文件.将它存储在不同的简单Python数据结构中需要在kB中占用这么多空间,测量为运行ps的RSS,其中d是dict,keys和freqs是列表,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'))

我没有编写代码来从这个结构中查找值(使用bisect,如下所述),或者实现了下面描述的更高级的压缩结构.

原始答案:一个简单的排序字符串数组,每个字符串是一个空格分隔的单词串联,使用bisect模块搜索,应该值得一试.这节省了指针等空间.由于重复单词,它仍然浪费空间; 有一个标准的技巧来删除常见的前缀,使用另一个级别的索引来恢复它们,但这更复杂,更慢.(这个想法是以压缩的形式存储阵列的连续块,必须按顺序扫描,以及每个块的随机访问索引.块大到足以压缩,但足够小以获得合理的访问时间.特定压缩这里适用的方案:如果连续输入的是'hello george'和'hello world',请将第二个输入改为'6world'.zlib？无论如何,你可以通过查找全文搜索中使用的字典结构来了解更多内容.)具体来说,我从数组开始,键是前两个单词,有一个并行数组,其条目列出了可能的第三个词及其频率.尽管如此,它可能仍然很糟糕 - 我认为就电池包含的内存效率选项而言,你可能会失去运气.

此外,此处不建议使用二叉树结构来提高内存效率.例如,本文测试了类似问题的各种数据结构(虽然是unigrams而不是trigrams),并且找到了一个哈希表来通过该度量来击败所有树结构.

我应该像其他人一样提到,排序的数组只能用于wordlist,而不是bigrams或trigrams; 那么对于你的"真实"数据结构,无论它是什么,你都使用整数键而不是字符串 - 索引到单词列表中.(但这会阻止你利用常用的前缀,除了词汇表本身.也许我不应该建议这一点.)

使用元组.
元组可以是字典的关键,因此您不需要嵌套字典.

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",那么使用list comprehension在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)开头的元组中的第三个项目