python - 如何从python中的gzip压缩文件中获取随机行而不将其读入内存

Question

假设我有一个 531 gz 的 gzip 文本文件，其中正好有 512 548 457 601 475 行被 '\n' 分割，并且想从中随机获取一行而不进行文件分割。 (别担心，它并没有那么大；只是想说明它是一个巨大的文件，我知道它有多少行。)

我通常如何处理较小的压缩文件:

import fileinput
import gzip
import random

list = []

for line in fileinput.input(file, openhook=gzip.open):
    list.append(line)

listLength = len(list)
randomListLineOne = line[random.randint(0, listLength)]
randomListLineTwo = line[random.randint(0, listLength)]
...

我在该主题上的发现:

How do I read a random line from one file in python?

import random

def random_line(afile):
    line = next(afile)
    for num, aline in enumerate(afile):
      if random.randrange(num + 2): continue
      line = aline
    return line

Waterman的《Reservoir Algorithm》由Alex Martelli翻​​译自Knuth的《The Art of Computer Programming》

你能为压缩文件改编这个吗？我尝试将我的压缩文件设置为一个文件，但这没有用。还是有另一种(更简单的)方法来实现这一目标？

Answer 1

蒙特卡洛

作为 reading the file line by line* 的替代品

(*使用David Robinson的方法将gzip文件作为标准文件读取):

如果所有行的大小大致相同，您可以跳转到文件中的随机位置，逐个字符回溯，直到到达换行符并从该点读取整行。如果线条的大小完全相同，则此方法是准确的。

但是，如果线条的大小不同，但您知道长度为 x 的线条的分布 - 您可以执行上述方法，但拒绝过多的 x 的概率为 P(x)，这样在文件中抓取随机行的概率是恒定的。

示例:

为简单起见，假设您有一个 5 行文件，长度为 X={2,3,5,5,5}。在文件中选择一个随机点，您有 10% (2/(2+3+5+5+5)) 的机会获得 x1，15% 的机会获得 x2，x3 的几率为 50%。你想要的分别是 20%/20%/60% 概率。我们各自的权重是 W=(3/2, 1, 6/5)，这些是满足 x1*w1 = 20% 的数字， x2*w2 = 20%，x3*w3=60%。归一化因子是这些权重的总和 Z = w1+w2+w3 = 37/10。从这里我们知道每条线的概率:

 P(w1) = w1/Z = 30/68
 P(w2) = w2/Z = 20/68
 P(w3) = w3/Z = 18/68

请注意 P(w1)+P(w2)+3*P(w3)=1，这是应该的。

为您的算法在文件中选择一个随机点。如果相关行的长度为 2，则在 q=[0,1] 之间选择一个随机数。如果 q>(30/68) 拒绝该点并重试。如果它小于停止并返回该行。

你什么时候知道X(w)？

我承认知道行长度的确切分布可能看起来有限制，但是有许多程序生成的文件(日志文件、硬件数据读出等)，其中的分布是确切已知的。此外，如果分布仅是近似已知的，我们可以使用上述方法确定样本拒绝标准作为最佳猜测，然后从那里开始。

蒙特卡洛？

这可能不是最好的方法(谁能与 Knuth 竞争？)，但它可能会提供一些以完全不同的方式解决问题的见解。对于那些不熟悉的人，上面的方法是一种重要性采样的形式，Monte Carlo方法。

如何在gzip文件中寻找？

根据 OP 的要求，这里是关于 seek Python 文件对象的入门读物。

import gzip, random

# Helper function to create some test data
def line(char,n): 
    return ''.join([("%s"%char)*n,"\n"])

# Create the test data as in the example
filename = "test.zip"
FOUT = gzip.open(filename,'wb')
FOUT.write(line('a',2))
FOUT.write(line('b',3))
FOUT.write(line('c',5))
FOUT.write(line('d',5))
FOUT.write(line('e',5))
FOUT.close()

# Since we know the distribution, we know the length
length = 2+3+3*5+5 # 5 newlines

# Print 7 random points in the file
FIN = gzip.open(filename,'rb')
for n in xrange(7):
    FIN.seek(random.randrange(length),0)
    print "Position %3i, char: %s" %(FIN.tell(), [FIN.read(1)])

样本运行的输出为:

Position   8, char: ['c']
Position  23, char: ['e']
Position  15, char: ['d']
Position  10, char: ['c']
Position   4, char: ['b']
Position  16, char: ['d']
Position   2, char: ['\n']