<p>一些测量。我获取了10MB的免费电子书文本,并计算了三元组的频率,生成了一个24MB的文件。将它存储在不同的简单Python数据结构中占用了大量的空间(以kB为单位),从运行ps的RSS中可以看出,其中d是dict,keys和freq是list,a、b、c、freq是trigram记录的字段:</p>
<pre><code>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
</code></pre>
<p>标记为[*]的条目没有有效的方法查找一对(a,b);它们被列出只是因为其他人建议它们(或它们的变体)。(如表所示,我有点恼火,因为排名靠前的答案没有帮助。)</p>
<p>“Pair array”是我最初的答案中的如下方案(“我将从带键的数组开始
作为前两个单词…),其中每对的值表是
表示为单个字符串压缩对阵列是一样的,
去掉等于1的频率值(最常见的
案例)“压缩单数组”类似于压缩对数组,但将键和值合并为一个字符串(带有分隔符)。压缩的单数组代码:</p>
<pre><code>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'))
</code></pre>
<p>我还没有编写代码来查找这个结构中的值(使用下面提到的等分),也没有实现下面描述的更高级的压缩结构。</p>
<p><strong>原始答案:</strong>一个简单的字符串排序数组,每个字符串是一个用空格分隔的单词串接,使用对分模块进行搜索,应该值得一试。这样可以节省指针等的空间。由于单词的重复,它仍然会浪费空间;有一个标准的技巧可以去掉常见的前缀,并使用另一个级别的索引将其还原,但这会更加复杂和缓慢。(其思想是以压缩的形式存储数组的连续块,这些块必须按顺序扫描,并随机访问每个块的索引。块足够大,可以压缩,但足够小,可以提供合理的访问时间。这里适用的特殊压缩方案是:如果连续的条目是“hello george”和“hello world”,则将第二个条目改为“6world”。(6是前缀的共同长度)或者也许你可以使用<a href="http://www.python.org/doc/2.5.2/lib/module-zlib.html" rel="noreferrer">zlib</a>?无论如何,您可以通过查找全文搜索中使用的字典结构来了解更多信息。)因此,具体地说,我将从键是前两个词的数组开始,使用一个并行数组,其条目列出可能的第三个词及其频率。不过,它可能仍然很烂——我想你可能会走运,因为电池包括内存效率高的选项。</p>
<p>此外,为了提高内存效率,建议使用二叉树结构<em>而不是</em>。E、 g.,<a href="http://www.cdf.toronto.edu/~csc148h/fall/assignment3/bursttries.pdf" rel="noreferrer">this paper</a>在一个类似的问题上测试各种数据结构(但是是unigrams而不是trigrams),并找到一个哈希表,通过这个度量击败所有的树结构。</p>
<p>我应该像其他人一样提到,排序数组可以只用于wordlist,而不是bigrams或trigrams;然后对于“真实”的数据结构,不管它是什么,都可以使用整数键而不是字符串——索引到wordlist中。(但这使您无法利用除wordlist本身之外的常见前缀。也许我不应该建议你这么做。)</p>